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.
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
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  and  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.
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:
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.