A multi-robot strategy for rapidly searching a polygonal environment

Alejandro Sarmiento, Rafael Murrieta-Cid, Seth Andrew Hutchinson

Research output: Contribution to journalConference articlepeer-review


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 languageEnglish (US)
Pages (from-to)484-493
Number of pages10
JournalLecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)
StatePublished - 2004
Event9th Ibero-American Conference on AI: Advances in Artificial Intelligence- IBERAMIA 2004 - Puebla, Mexico
Duration: Nov 22 2004Nov 26 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'A multi-robot strategy for rapidly searching a polygonal environment'. Together they form a unique fingerprint.

Cite this