The SRT method is a randomized strategy for exploring unknown environments using mobile robots equipped with range finders. The basic tool is the Sensor-based Random Tree (SRT), a compact data structure representing a roadmap of the explored area. The SRT can be considered as a sensor-based version of the Rapidly-exploring Random Tree (RRT) concept developed by LaValle. In particular, each node of an SRT records a robot configuration and the Local Safe Region (LSR) perceived from that location, while an arc between two nodes represents a collision-free path between the two associated configurations. The SRT is incrementally built by the robot by using a randomized local planner, which generates the next configuration towards the frontier of the current LSR boundary, thus privileging directions that lead from the current configuration to unexplored areas. This mechanism automatically realizes a trade-off between information gain and navigation cost when choosing the next robot configuration.
The SRT method is a general paradigm. The shape of the Local Safe Region may be easily adapted to the range finder characteristics and/or the adopted perception mode. In the figure below, we show from left to right the LSR for a sensor which provides only the distance to the closer obstacle (a somewhat abstract sensor realizing a conservative perception mode, suitable for very noisy/imprecise sensors), the LSR for a ring of ultrasonic sensors and the LSR for a laser range finder. In mathematical terms, the LSR is always a star-shaped region.
In its basic formulation, the SRT method assumes that the robot always knows its configuration through some localization module. To remove this limitation, we have developed an SRT-based integrated exploration strategy., i.e., a simultaneous localization/mapping/exploration scheme where exploration decisions are taken based on localization potential as well as information gain. In particular, the algorithm relies on an LSR feature-based continuous localization scheme.
The Multi-SRT Method, a multi-robot version of the SRT method aimed at cooperative exploration, has also been developed. It is presented in this page.
The SRT method is also amenable to an extension to high-dimensional configuration spaces (e.g., robotic manipulators). See this page for further details.
The SRT method has been designed and developed by: L. Freda, G. Oriolo, M. Vendittelli.
For a quick introduction to the SRT Method, see these slides. More details are given in these papers:
The SRT Method: Randomized strategies for exploration
G. Oriolo, M. Vendittelli, L. Freda and G. Troso
2004 IEEE International Conference on Robotics and Automation
Frontier-based probabilistic strategies for sensor-based exploration
L. Freda and G. Oriolo
2005 IEEE International Conference on Robotics and Automation.
A Randomized Method for Integrated Exploration
L. Freda, F. Loiudice, G. Oriolo
2006 IEEE/RSJ International Conference on Intelligent Robots and Systems.
A Randomized Strategy for Cooperative Robot Exploration
A. Franchi, L. Freda, G. Oriolo and M. Vendittelli
2007 IEEE International Conference on Robotics and Automation.
Realized either in Move3D (a software platform at the origin of the product KineoWorks currently marketed by the company Kineo CAM) or in Webots (to allow for more realistic sensor simulation) under the assumption of perfect localization, these simulation clips highlight the essential exploratory qualities of the SRT method.
Simulation 1: MagellanPro equipped with a ring of ultrasonic sensors.
Simulation 2: MagellanPro equipped with a laser range finder. Note how the robot either moves towards the local frontier (in yellow) or backtracks when the LSR has no frontier.
Simulation 3: MagellanPro equipped with a laser range finder: on the left, SRT using odometry for localization; on the right, SRT-based integrated exploration.
We have implemented the SRT Method on the mobile robots available in our laboratory.
Experiments 1 and 2: Khepera III equipped with a Hokuyo URG-04LX laser range finder.
Experiments 3 and 4: MagellanPro equipped with a ring of ultrasonic sensors.