Piecemeal Graph Exploration by a Mobile Robot

Baruch Awerbuch, Margrit Betke, Ronald L. Rivest, Mona Singh

Research output: Contribution to journalArticlepeer-review

78 Scopus citations

Abstract

We study how a mobile robot can learn an unknown environment in a piecemeal manner. The robot's goal is to learn a complete map of its environment, while satisfying the constraint that it must return every so often to its starting position (for refueling, say). The environment is modeled as an arbitrary, undirected graph, which is initially unknown to the robot. We assume that the robot can distinguish vertices and edges that it has already explored. We present a surprisingly efficient algorithm for piecemeal learning an unknown undirected graph G = (V, E) in which the robot explores every vertex and edge in the graph by traversing at most O(E + \/1+o(1)) edges. This nearly linear algorithm improves on the best previous algorithm, in which the robot traverses at most O(E + V2) edges. We also give an application of piecemeal learning to the problem of searching a graph for a "treasure."

Original languageEnglish (US)
Pages (from-to)155-172
Number of pages18
JournalInformation and Computation
Volume152
Issue number2
DOIs
StatePublished - Aug 1 1999
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Piecemeal Graph Exploration by a Mobile Robot'. Together they form a unique fingerprint.

Cite this