### 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 + V^{1+0(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) |
---|---|

Title of host publication | Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995 |

Publisher | Association for Computing Machinery, Inc |

Pages | 321-328 |

Number of pages | 8 |

ISBN (Electronic) | 0897917235, 9780897917230 |

State | Published - Jul 5 1995 |

Externally published | Yes |

Event | 8th Annual Conference on Computational Learning Theory, COLT 1995 - Santa Cruz, United States Duration: Jul 5 1995 → Jul 8 1995 |

### Publication series

Name | Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995 |
---|---|

Volume | 1995-January |

### Other

Other | 8th Annual Conference on Computational Learning Theory, COLT 1995 |
---|---|

Country | United States |

City | Santa Cruz |

Period | 7/5/95 → 7/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

*Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995*(pp. 321-328). (Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995; Vol. 1995-January). Association for Computing Machinery, Inc.