## Abstract

In this paper we address the problem of finding an object in a polygonal environment as quickly as possible on average, with a team of mobile robots that can sense the environment. We show that for this problem, a trajectory that minimizes the distance traveled may not minimize the expected value of the time to find the object. We prove the problem to be NP-hard by reduction, therefore, we propose the heuristic of a utility function. We use this utility function to drive a greedy algorithm in a reduced search space that is able to explore several steps ahead without incurring too high a computational cost. We have implemented this algorithm and present simulation results for a multi-robot scheme.

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

Pages (from-to) | 484-493 |

Number of pages | 10 |

Journal | Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science) |

Volume | 3315 |

State | Published - Jan 1 2004 |

Event | 9th Ibero-American Conference on AI: Advances in Artificial Intelligence- IBERAMIA 2004 - Puebla, Mexico Duration: Nov 22 2004 → Nov 26 2004 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)