An Efficient Strategy for Rapidly Finding an Object in a Polygonal World

Alejandro Sarmiento, Rafael Murrieta, Seth A. Hutchinson

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

Abstract

In this paper we propose an approach to solve the problem of finding an object in a polygon which may contain holes. We define an optimal solution as the route that minimizes the expected time it takes to find said object. The object search problem is shown to be NP-hard by reduction, therefore, we propose the heuristic of an utility function, defined as the ratio of a gain over a cost and an greedy algorithm in a reduced search space that is able to explore several steps ahead without incurring in too high a computational cost. This approach was implemented and simulation results are shown.

Original languageEnglish (US)
Title of host publicationIEEE International Conference on Intelligent Robots and Systems
Pages1153-1158
Number of pages6
Volume2
StatePublished - 2003
Event2003 IEEE/RSJ International Conference on Intelligent Robots and Systems - Las Vegas, NV, United States
Duration: Oct 27 2003Oct 31 2003

Other

Other2003 IEEE/RSJ International Conference on Intelligent Robots and Systems
CountryUnited States
CityLas Vegas, NV
Period10/27/0310/31/03

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Software
  • Computer Vision and Pattern Recognition
  • Computer Science Applications

Fingerprint Dive into the research topics of 'An Efficient Strategy for Rapidly Finding an Object in a Polygonal World'. Together they form a unique fingerprint.

Cite this