Efficient topological exploration
- 20 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1 (10504729) , 676-681
- https://doi.org/10.1109/robot.1999.770053
Abstract
We consider the robot exploration of a planar graph-like world. The robot's goal is to build a complete map of its environment. The environment is modeled as an arbitrary undirected planar graph which is initially unknown to the robot. The robot cannot distinguish vertices and edges that it has explored from the unexplored ones. The robot is assumed to be able to autonomously traverse graph edges, recognize when it has reached a vertex, and enumerate edges incident upon the current vertex. The robot cannot measure distances nor does it have a compass, but it is equipped with a single marker that it can leave at a vertex and sense if the marker is present at a newly visited vertex. The total number of edges traversed while constructing a map of a graph is used as a measure of performance. We present an efficient algorithm for learning an unknown, undirected planar graph by a robot equipped with one marker. Experimental results obtained by running a large collection of example worlds are presented.Keywords
This publication has 11 references indexed in Scilit:
- Position referencing and consistent world modeling for mobile robotsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Error correction in mobile robot map learningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Exploring an unknown graphPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Vision-based motion planning and exploration algorithms for mobile robotsIEEE Transactions on Robotics and Automation, 1998
- Map validation and robot self-location in a graph-like worldRobotics and Autonomous Systems, 1997
- Competitive robot mapping with homogeneous markersIEEE Transactions on Robotics and Automation, 1996
- Robotic exploration as graph constructionIEEE Transactions on Robotics and Automation, 1991
- Integrating behavioral, perceptual, and world knowledge in reactive navigationRobotics and Autonomous Systems, 1990
- A sweepline algorithm for Voronoi diagramsAlgorithmica, 1987
- Parallel ear decomposition search (EDS) and st-numbering in graphsPublished by Springer Nature ,1986