Accession Number:



Negotiating Mission Plans under Risk Bounds

Descriptive Note:

Technical Report,14 May 2015,13 May 2018

Corporate Author:

Australian National University Caberra United States

Report Date:


Pagination or Media Count:



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,

Subject Categories:

  • Statistics and Probability
  • Cybernetics

Distribution Statement: