TY - GEN
T1 - Robot map verification of a graph world
AU - Deng, Xiaotie
AU - Milios, Evangelos
AU - Mirzaian, Andy
N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].
PY - 1999
Y1 - 1999
N2 - In the map verification problem, a robot is given a (possibly incorrect) map M of the world G with its position and orientation indicated on the map. The task is to find out whether this map, for the given robot position and orientation in the map, is correct for the world G. We consider the world model with a graph G = (V G,E G) in which, for each vertex, edges incident to the vertex are ordered cyclically around that vertex. This holds similarly for the map M = (V M,E M). The robot can traverse edges and enumerate edges incident on the current vertex, but it cannot distinguish vertices and edges from each other. To solve the verification problem, the robot uses a portable edge marker, that it can put down and pick up as needed. The robot can recognize the edge marker when it encounters it in G. By reducing the verification problem to an exploration problem, verification can be completed in O(|V G| × |E G|) edge traversals (the mechanical cost) with the help of a single vertex marker which can be dropped and picked up at vertices of the graph world [DJMW1],[DSMW2]. In this paper, we show a strategy that verifies a map in O(|V M|) edge traversals only, using a single edge marker, when M is a plane embedded graph, even though G may not be (e.g., G may contain overpasses, tunnels, etc.). © Springer-Verlag Berlin Heidelberg 1999.
AB - In the map verification problem, a robot is given a (possibly incorrect) map M of the world G with its position and orientation indicated on the map. The task is to find out whether this map, for the given robot position and orientation in the map, is correct for the world G. We consider the world model with a graph G = (V G,E G) in which, for each vertex, edges incident to the vertex are ordered cyclically around that vertex. This holds similarly for the map M = (V M,E M). The robot can traverse edges and enumerate edges incident on the current vertex, but it cannot distinguish vertices and edges from each other. To solve the verification problem, the robot uses a portable edge marker, that it can put down and pick up as needed. The robot can recognize the edge marker when it encounters it in G. By reducing the verification problem to an exploration problem, verification can be completed in O(|V G| × |E G|) edge traversals (the mechanical cost) with the help of a single vertex marker which can be dropped and picked up at vertices of the graph world [DJMW1],[DSMW2]. In this paper, we show a strategy that verifies a map in O(|V M|) edge traversals only, using a single edge marker, when M is a plane embedded graph, even though G may not be (e.g., G may contain overpasses, tunnels, etc.). © Springer-Verlag Berlin Heidelberg 1999.
UR - http://www.scopus.com/inward/record.url?scp=84948995229&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84948995229&origin=recordpage
U2 - 10.1007/3-540-48447-7_11
DO - 10.1007/3-540-48447-7_11
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 3540662790
SN - 9783540662792
VL - 1663
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 86
EP - 97
BT - Algorithms and Data Structures - 6th International Workshop, WADS 1999, Proceedings
PB - Springer Verlag
T2 - 6th International Workshop on Algorithms and Data Structures, WADS 1999
Y2 - 11 August 1999 through 14 August 1999
ER -