Negotiating Mission Plans under Risk Bounds
Abstract
Autonomous systems operating in uncertain environments face the problem of optimizing their performance whilst satisfying complex mission constraints with high probability and bounding the risk of plan execution failure. Such problems can be modelled as constrained stochastic shortest path problems (C-SSPs), which are an active research topic in the operations research, artificial intelligence, robotics, and software verification communities. However, all existing algorithms forC-SSPs require generating and exploring the entire state space of the problem, making them impractical for autonomous systems which have huge state spaces.This project has made significant advances towards more practical solutions to C-SSPs. We have devised the first heuristic search algorithms for C-SSPs. These algorithms typically explore a small fraction of the state space, and enable solving much larger problems than was previously possible. To be effective, they must be provided with an admissible heuristic function, that is a lower bound on the expected cost to reach the system goal under the constraints. To achieve this,we have devised the first domain-independent heuristics that take into account uncertainty, costs, and constraints. Our heuristics have become the state of the art also for regular (unconstrained) SSPs: even though heuristic search had been used to solve SSPs for over two decades, existing heuristics ignored uncertainty altogether. Moreover, we have extended these algorithms and heuristics in several directions, including to rich probabilistic temporal logic constraints, to partially observable environments, to hybrid discrete/ continuous environments, and to efficiently handle dead-ends. In doing so, we have bridged the gap between several areas of research, across several scientific communities, specifically, heuristic search, classical planning heuristics and planning under uncertainty in Artificial Intelligence, Markov decision processes in Operations Research,
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 28, 2018
- Accession Number
- AD1058770
Entities
People
- Brian Williams
- Felipe Trevizan
- Patrik Haslum
- Pedro Santana
- Peter Baumgartner
- Sylvie Thiebaux
- Tiago Vaquero
Organizations
- Australian National University