## 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 + V^{2}) edges. We also give an application of piecemeal learning to the problem of searching a graph for a "treasure."

Original language | English (US) |
---|---|

Pages (from-to) | 155-172 |

Number of pages | 18 |

Journal | Information and Computation |

Volume | 152 |

Issue number | 2 |

DOIs | |

State | Published - Aug 1 1999 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

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