Finding objects through stochastic shortest path problems

Felipe W. Trevizan, Manuela M. Veloso

Research output: Contribution to conferencePaperpeer-review

2 Citations (Scopus)

Abstract

This paper presents a novel formulation for the problem of finding objects in a known environment while minimizing the search cost. Our approach consists in formalizing this class of problems as Stochastic Shortest Path (SSP) problems, a decision-theoretic framework for probabilistic environments. The obtained problems are solved by using off-the-shelf domain-independent probabilistic planners. The advantages of this approach includes: (i) a well defined optimization problem in which the probability of finding the object is maximized while minimizing the cost of searching for the object; and (ii) being able to take advantage, without any modifications to our model, of any (future) technique in the field of domain-independent probabilistic planners, such as better algorithms and better heuristics. We also contribute by empirically comparing three probabilistic planners algorithms, namely FF-Replan, UCT and SSiPP, using our proposed class of problems.

Original languageEnglish
Pages547-554
Number of pages8
Publication statusPublished - 2013
Externally publishedYes
Event12th International Conference on Autonomous Agents and Multiagent Systems 2013, AAMAS 2013 - Saint Paul, MN, United States
Duration: 6 May 201310 May 2013

Conference

Conference12th International Conference on Autonomous Agents and Multiagent Systems 2013, AAMAS 2013
Country/TerritoryUnited States
CitySaint Paul, MN
Period6/05/1310/05/13

Fingerprint

Dive into the research topics of 'Finding objects through stochastic shortest path problems'. Together they form a unique fingerprint.

Cite this