TY - CONF
ID - rekleitis_dujmovic_dudek_99_efficient
T1 - Efficient Topological Exploration
A1 - Rekleitis, I. M.
A1 - Dujmovic, V.
A1 - Dudek, G.
TI - Proceedings 1999 {IEEE} International Conference on Robotics and Automation ({ICRA}-99)
Y1 - 1999
SP - 676
EP - 681
SN - 0-7803-5180-0
KW - graph theory
KW - LEARNING (ARTIFICIAL INTELLIGENCE)
KW - learning algorithm
KW - mobile robot
KW - mobile robots
KW - PATH PLANNING
KW - robot vision
KW - ROBOT VISION topological exploration
KW - undirected planar graph
N2 - 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.
M1 - date-added={2012-09-03 15:47:30 +0200}
M1 -
date-modified={2012-09-03 15:47:30 +0200}
M1 -
notes={Interesting literature links: Chatila / Laumond (1985): Position referencing and consistent world modelling for mobile robots (topological map representations form metrical data) Kuipers / Levitt (1988): Navigation and mapping in large-scale space (metric maps from topological representations) Arkin (1990): Integrating behavioural
M1 - perceptual
M1 - and world knowledge in reactive navigation (combining metric and topological aspects) Engelson / McDermott (1992): Error correction in mobile robot map learning (comb metric and top. aspects) Deng / Papdimitriou (1990): Exploring an unknown graph (theoretical issues covering an unknown graph using topological exploration) Dudek (1988): Segmentation using information from multiple features (one marker mapping) Dudek / Jenkin / Milios / Wilkes (1991): Robotic exploration as graph construction (one marker mapping) Deng / Mirzaian (1996): Competitive robot mapping with homogeneous markers (one marker mapping) Dudek / Freedman / Hadjres (1992): Algorithms for active exploration of unknown environments (alternative models of the environments using topological exploration) Dudek / Jenkin / Milios / Wilkes (1997): On building and navigating with a globally topological but locally metric map (same with limited amount of metric data) Dudek / Jenkin / Milios / Wilkes (1997): Map validation and robot self-loca(li?)zation in a graph-like world (map verification
M1 - robot localization) Dudek / Freedman / Hadjres (1993): Using local information in a non-local way for mapping graph-like worlds (map verification
M1 - robot localization)}
M1 -
project={fremdliteratur}
M1 -
registry={A83}
M1 -
state={printed}
ER -