Piecemeal graph exploration by a mobile robot

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

36 Scopus citations

Abstract

We study how a mobile robot can piecemeal learn an unknown environment. 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 modelled 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 + V1+0(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)
Title of host publicationProceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995
PublisherAssociation for Computing Machinery, Inc
Pages321-328
Number of pages8
ISBN (Electronic)0897917235, 9780897917230
StatePublished - Jul 5 1995
Externally publishedYes
Event8th Annual Conference on Computational Learning Theory, COLT 1995 - Santa Cruz, United States
Duration: Jul 5 1995Jul 8 1995

Publication series

NameProceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995
Volume1995-January

Other

Other8th Annual Conference on Computational Learning Theory, COLT 1995
CountryUnited States
CitySanta Cruz
Period7/5/957/8/95

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Artificial Intelligence
  • Software

Fingerprint Dive into the research topics of 'Piecemeal graph exploration by a mobile robot'. Together they form a unique fingerprint.

Cite this