Path Planning for Minimizing the Expected Cost Until Success

Consider a general path planning problem of a robot on a graph with edge costs, where each node has a Boolean value of success or failure (with respect to some task) with a given probability. The objective is to plan a path for the robot on the graph that minimizes the expected cost until success. I...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on robotics 2019-04, Vol.35 (2), p.466-481
Main Authors: Muralidharan, Arjun, Mostofi, Yasamin
Format: Article
Language:English
Subjects:
AI reasoning methods
autonomous agents
Boolean algebra
Complexity
Complexity theory
Computer simulation
Cost engineering
Economic models
field robots
Game theory
Markov processes
Optimization
Path planning
Planning
planning under uncertainty
Probabilistic logic
Robots
Search problems
Success
Task analysis
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Consider a general path planning problem of a robot on a graph with edge costs, where each node has a Boolean value of success or failure (with respect to some task) with a given probability. The objective is to plan a path for the robot on the graph that minimizes the expected cost until success. In this paper, it is our goal to bring a foundational understanding to this problem. We start by showing how this problem can be optimally solved by formulating it as an infinite-horizon Markov decision process, but with an exponential space complexity. We then formally prove its NP-hardness. To address the space complexity, we then propose a path planner, using a game-theoretic framework, that asymptotically gets arbitrarily close to the optimal solution. Moreover, we also propose two fast and nonmyopic path planners. To show the performance of our framework, we do extensive simulations for two scenarios: a rover on Mars searching for an object for scientific studies, and a robot looking for a connected spot to a remote station (with real data from downtown San Francisco). Our numerical results show a considerable performance improvement over existing state-of-the-art approaches.
ISSN:1552-3098
1941-0468
DOI:10.1109/TRO.2018.2883829