Negotiating Mission Plans under Risk Bounds
Abstract
The research group headed by Professor Sylvie Thiebaux, made significant advances in the development of practical solutions to constrained stochastic shortest path problems (C-SSPs). A specific problem of interest that can be modelled as a C-SSP is that of autonomous systems operating in uncertain environments, facing the problem of optimizing their performance whilst satisfying complex mission constraints with high probability and bounding the risk of plan execution failure. This is currently an active research topic in the operations research, artificial intelligence, robotics, and software verification communities. However, all existing algorithms for C-SSPs require generating and exploring the entire state space of the problem, making them impractical for autonomous systems which have huge state spaces. Over the course of this research project, the group has published ten top tier publications, two of which received best paper awards at the International Conference on Automated Planning and Scheduling (ICAPS) in 2016 and 2017. A summary of their results search group is highlighted by their development of 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, the research group devised the first domain-independent heuristics that take into account uncertainty, costs, and constraints. Their heuristics have since 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 28, 2018
- Accession Number
- AD1063227
Entities
People
- Sylvie Thiebaux