Skip to main content

Planning under uncertainty

Planning under uncertainty is inherently an optimisation problem: plans of good quality tend to be hard to find, and plans found easily tend to be poor specially under uncertainty. We aim to develop new fast, efficient and robust planning methods for different problems, offering greater flexibility to trade off planning time, plan quality, and robustness of the solution under uncertainty. Below are current projects that needs to make planning decisions under uncertainty.


1). Risk-Bounded Planning for Safe Autonomous Systems

The project is a collaboration between Data61, ANU and MIT funded by Air Force Office for Scientific Research grant FA2386-15-1-4015 (05/2015-05/2018).

Autonomous systems operating in uncertain environments face the problem of optimizing their performance whilst bounding the risk of failing to satisfy safety constraints. Handling risk is required for automated planning algorithms to be trusted by mission planners, and is a prerequisite to their wider deployment within autonomous systems such as aerial, underwater and planetary vehicles. The above problems can be modelled as constrained stochastic shortest-path problems (C-SSPs). Finding efficient algorithms to solve C-SSPs is an active research topic in the operations research, artificial intelligence, robotics, and software synthesis communities. Unfortunately all known optimal algorithms explore the entire state space of the problem, making them impractical. The project scientific goal is to find practical C-SSP algorithms for increasingly expressive classes of constraints. In achieving this goal, we have bridged the gap between research in AI and the above-mentioned communities, leading to algorithms that hybridise their best features.

The following are the number of positive outcomes of the project

  •  I-dual is the first polynomial heuristic search algorithms that optimally solves C-SSPs. Its advantage over existing operations research methods such as linear or dynamic programming, is that, thanks to heuristic guidance, it needs only expand a fraction of the state space. It achieves this by embedding OR-style linear programming in the “dual” space of occupation measures in an AI-style heuristic search. Our experiments show that it can solve, in a matter of seconds, problems that would require linear programs with billions of variables.
  • For I-dual to work at its best, informative heuristics (lower bounds on the expected cost of the optimal solution) must be provided. Unfortunately, all existing domain-independent planning heuristics assume that the problem is deterministic and ignore probabilities. Our new occupation measure heuristics are the first heuristics that take into account probabilities and costs. Such heuristics had eluded researchers in over two decades of research on planning under uncertainty. Occupation measure heuristics are computed by relaxing the dual linear program. This computation can be directly embedded into I-dual, leading to further efficiency gain and to a new type of heuristic search algorithm.
  • We have started to work on C-SSPs with expressive probabilistic temporal logic constraints. These are widely used in the verification community to synthesize controllers. We have provided the first synthesis algorithm which is correct and complete for constraints in the very expressive PCTL* logic. Again, this algorithm doesn’t require full state space exploration. Our ultimate goal is now to find the most expressive subset of PCTL* that can be handled by i-dual, whilst maintaining its attractive computational complexity. If we succeed, this will be a major improvement over current synthesis algorithms for probabilistic temporal logic.

Other outcomes and collaborations: RAO* is a heuristic search algorithm that handles a subset of partially observable C-SSPs. A first implementation has been applied by MIT to generate risk-bounded sequences of maneuvers for autonomous cars through a collaboration with Toyota, and to generate risk-bounded plans for Mars Rovers science missions through a collaboration with NASA.

MCMP is a new class of SSPs with dead-ends, whose solution is the minimum expected cost policy among those with maximum success probability, and which can be solved efficiently using a variant of I-dual (3-order of magnitude speedup over competing models and algorithms).  This work was done in collaboration with F. Teichteil-Koenigsbuch from Airbus.

Awards: Papers [4] and [5] both received the best paper award at ICAPS, two years in a row.

List of Project Publications with Data61 Authors:

1.       Peter Baumgartner,  Sylvie Thiébaux, Felipe Trevizan. Policy Synthesis for MDPs with PCTL* Constraints.  Proceedings of the 26th International Conference on Automated Reasoning with Analytic Tableaux and Related Methods (Tableaux-17), 2017. CORE A.

2.       Felipe Trevizan, Sylvie Thiébaux, Pedro Santana, Brian Williams. I-dual: Solving Constrained SSPs by Heuristic Search in the Dual Space. Proceedings of the 26th Joint International Conference on Artificial Intelligence (IJCAI-17), Sisters Conference Best Paper Track, Melbourne (USA), August 2017. CORE A*. Invited submission of a short version of our ICAPS-16 best paper.

3.       Felipe Trevizan, Florent Teichteil-Konigsbuch, Sylvie Thiébaux. Efficient Solutions for Stochastic Shortest Path Problems with Dead-Ends. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence (UAI-17), 2017.  CORE A*.

4.       Felipe Trevizan, Sylvie Thiébaux, Patrik Haslum. Occupation Measure Heuristics for Probabilistic Planning. Proceedings of the 27th International Conference on Automated Planning and Scheduling (ICAPS-17), AAAI Press, Pittsburgh (USA), June 2017. CORE A*. Best Paper Award.

5.       Felipe Trevizan, Sylvie Thiébaux, Pedro Santana and Brian Williams. Heuristic Search in Dual Space for Constrained Stochastic Shortest Paths Problems. Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS-16), AAAI Press, London (UK), June 2016. CORE A*.  Best Paper Award.


2). Alarm processing, Planning and Optimisation in Power Networks

In the last 5-6 years, optimisation and operational problems in power networks have been a focus of research for parts of the team. Our team members has made a good progress on the project. Some of the key achievements include:

  • Relaxations of power flow: Almost every decision problem relating to power networks (expansion planning, generator dispatch, transmission switching, fault diagnosis and voltage control) requires some consideration of the power flow. The non-linear AC power flow equations, which link real and reactive power, voltage and phase, and express the physical principle of how AC power propagates in a network, make these optimisation problems hard to solve. Team members invented new quadratic power flow relaxation, which offers a significantly better accuracy-complexity trade-off than previous approximations.
  • Switching planning: Most interesting optimisation problems in power networks combine discrete actions, such as switching lines on/off or changing discrete transformer tap settings, with the non-linear power flow constraints over the continuous quantities of power and voltage. The team developed new approaches to such problems, by combining AI planning with mathematical programming models [2], and refining MIP and MINLP formulations. Those approaches can take advantage of the improved power flow relaxations.
  • Alarm processing and diagnosis: Alarm cascades, in which the root cause fault is hidden in a flood of secondary fault signals, are a problem in the operation of many technical systems, including power networks. The team applied a discrete-event diagnosis perspective to the problem of filtering and synthesising alarm cascades [3], and in the process generalised the theory of conflict-directed diagnosis – the leading approach to diagnosis of static systems for 20+ years – to discrete and hybrid event-driven systems [4], and articulated the symmetry between discrete-event diagnosis and planning [5]. This allows new approaches to switching planning to be turned to the problems of fault diagnosis and alarm processing in power networks as well.

List of Project Publications with Data61 Authors:

1. H. Hijazi, C. Coffrin and P. van Hentenryck. Convec Quadratic Relaxations for Mixed-Integer Nonlinear Programming in Power Systems. Mathematical Programming Computation. 2014.

2. F. Ivankovic, P. Haslum, S. Thiébaux, V. Shivashankar and D. Nau. Optimal Planning with Global Numerical State Constraints. Int. Conf. Automated Planning & Scheduling (ICAPS), 2014.Winner: Best student paper award.

3. A. Bauer, A. Botea, A. Grastien, P. Haslum and J. Rintanen. Alarm processing with model-based diagnosis of discrete event systems. Workshop on Principles of Diagnosis (DX), 2011.

4. A. Grastien, P. Haslum and S. Thiébaux. Conflict-Based Diagnosis of Discrete Event Systems: Theory and Practice. Proceedings, Knowledge Representation (KR’12), 2012.

5. P. Haslum and A. Grastien. Diagnosis as Planning: Two Case Studies. Proceedings, ICAPS 2011 Scheduling and Planning Applications Workshop.