An efficient motion strategy to compute expected-time locally optimal continuous search paths in known environments

Alejandro Sarmiento, Rafael Murrieta-Cid, Seth Hutchinson

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper we address the problem of finding time-optimal search paths in known environments. In particular, we address the problem of searching a known environment for an object whose unknown location is characterized by a known probability density function (PDF). With this formulation, the time required to find the object is a random variable induced by the choice of search path together with the PDF for the object's location. The optimization problem we consider is that of finding the path that minimizes the expected value of the time required to find the object. As the complexity of the problem precludes finding an exact optimal solution, we propose a two-level, heuristic approach to finding the optimal search path. At the top level, we use a decomposition of the workspace based on critical curves to impose a qualitative structure on the solution trajectory. At the lower level, individual segments of this trajectory are refined using local numerical optimization methods. We have implemented the algorithm and present simulation results for the particular case when the object's location is specified by the uniform PDF.

Original languageEnglish (US)
Pages (from-to)1533-1560
Number of pages28
JournalAdvanced Robotics
Volume23
Issue number12-13
DOIs
StatePublished - Sep 1 2009
Externally publishedYes

Keywords

  • Path Planning
  • Pursuit-evasion
  • Search

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Human-Computer Interaction
  • Hardware and Architecture
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'An efficient motion strategy to compute expected-time locally optimal continuous search paths in known environments'. Together they form a unique fingerprint.

Cite this