Robot Map Verification of a Graph World

Xiaotie Deng (), Evangelos Milios () and Andranik Mirzaian ()
Additional contact information
Xiaotie Deng: York University
Evangelos Milios: York University
Andranik Mirzaian: York University

Journal of Combinatorial Optimization, 2001, vol. 5, issue 4, No 1, 383-395

Abstract: Abstract 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 its orientation in the map, is correct for the world G. We consider the world model of a graph G = (V G, E G) in which, for each vertex, edges incident to the vertex are ordered cyclically around that vertex. (This also holds 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 at an edge of the graph world G and pick up later as needed. The robot can recognize the edge marker when it encounters it in the world 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 (G. Dudek, M. Jenkin, E. Milios, and D. Wilkes, IEEE Trans. on Robotics and Automation, vol. 7, pp. 859–865, 1991; Robotics and Autonomous Systems, vol. 22(2), pp. 159–178, 1997). 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 planar (e.g., G may contain overpasses, tunnels, etc.).

Keywords: robot exploration and map verification; on-line algorithm; topological graph; face tracing (search for similar items in EconPapers)
Date: 2001
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1011688823715 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:5:y:2001:i:4:d:10.1023_a:1011688823715

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1011688823715

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().