DPOLP

Dynamic Planning, Optimisation and Learning Project

The DPOLP Project (2004-2008) was a four way collaboration between DSTO, NICTA/ANU, the University of Adelaide and the University of South Australia. The project focused on fundamental and applied research into operations/project level planning. It produced several state of the art planners dealing with uncertainty and time, and made a number of significant contributions to bridging the gap between planning/heuristic search in artificial intelligence, petri nets analysis, and statistical machine learning.

Project Members | Research | Software | Publications

Project Members

Douglas Aberdeen, NICTA/ANU
Jonathan Billington, UNISA
Olivier Buffet, NICTA/ANU
Alfredo Gabaldo, NICTA/UNSW
Guy Gallasch, DSTO/UNISA
Karyn I'Anson, DSTO

Owen Thomas, NICTA
Patrik Haslum, NICTA/ANU
Sarah Hickmott, UofA/NICTA
Melissa Liew, UofA/NICTA
Iain Little, ANU/NICTA
Brice Mitchell, DSTO

Sanjeev Naguleswaran, UofA
Jussi Rintanen, NICTA/ANU
Scott Sanner, NICTA/ANU
Sylvie Thiebaux, ANU/NICTA
Lewis Warren, DSTO
Lang White, UofA
Lin Zhang, DSTO

Research

Operations planning involves larges groups of people choosing and co-ordinating tasks to produce a smoothly orchestrated operation. Automatically developing robust plans with hundreds of tasks is hard. Planning becomes even harder when trying to take the uncertainty of the world into account. NICTA, the Defence Science Technology Organisation (DSTO), the University of Adelaide, and the University of South Australia are developing theoretical frameworks, algorithms and tools that formalise, abstract, and solve such planning problems.

Research in the project explores a wide cross section of methods previously used in planning, including Markov decision processes, ML methods which would now be called "deep learning", SAT and logic based planning, planning graphs and search, Petri-net unfolding, and optimisation methods.

Software that automatically plans and schedules a set of tasks has been developed. Contributions include four planning servers to support military planning tools developed by DSTO. A further two planners received prizes at the 2006 International Probabilistic Planning Competition.

Applications of methods emerging from the project are of interest to the broader planning community, operations researchers, control theorists, and the day-to-day project managers who would like to know how a 50% chance of an adverse event could affect their project budget. DPOLP work is also becoming concerned with the presentation of planning information, including theoretical work in how to measure the similarity of plans, and how to present qualitatively different plans to the user from a spectrum of valid plans. Beyond traditional operations and project planning, DPOLP tools for the analysis of uncertainty contribute to the decision support and business planning domains.

Software

MOP, a planner based on heuristic search algorithms for Markov Decision Processes (a la LRTDP) which generates contingency plans for military operations planning problems. (Aberdeen et. al, ICAPS-04).
Prottle, the first probabilistic temporal planner; it extends heuristic search algorithms for Markov Decision Processes (a la LAO*) and planning graph heuristics to generate contingent temporal plans. (Little et. al, AAAI-05).
FPG, another very innovative planner which uses machine learning to solve probabilistic (temporal) planning problems. The technique used is factored policy gradient, which can be seen as a sort of "deep learning" method for planning. This planner won the 2006 International Probabilistic Planning Competition. (Aberdeen and Buffet, NIPS-05, ICAPS-07, AIJ-09). Code available here.
Paragraph, an extension of graphplan to concurrent probabilistic planning. This planner won the 3rd place at the 2006 International Probabilistic Planning Competition. (Little and Thiebaux, ICAPS-06).

Publications

Publications by NICTA/ANU members of the project:

Douglas Aberdeen. Policy-gradient methods for planning. Proceedings of the Eighteenth Annual Conference on Neural Information Processing Systems (NIPS), The MIT Press, 2005.
Douglas Aberdeen and Olivier Buffet. Concurrent probabilistic temporal planning with policy-gradients. Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling (ICAPS) pages 10-17. AAAI Press, 2007.
Douglas Aberdeen, Olivier Buffet, and Owen Thomas. Policy-gradients for PSRs and POMDPs. Proceedings of the 11th International Conference on Artificial Intelligence and Statistics (AIstats). Society for Artificial Intelligence and Statistics, 2007.
Douglas Aberdeen, Sylvie Thiebaux, and Lin Zhang. Decision-theoretic military operations planning. Proceedings of the Fourteenth International Conference on Automated Planning and Scheduling (ICAPS), pages 402-412, 2004.
Blai Bonet, Patrik Haslum, Sarah Hickmott, and Sylvie Thiebaux. Directed unfolding of Petri nets. LNCS Transactions on Petri Nets and Other Models of Concurrency, volume 5100 of Lecture Notes in Computer Science, pages 172-198. Springer-Verlag, 2008.
Olivier Buffet. Reachability analysis for uncertain SSPs. Proceedings of the 17th International Conference on Tools with Artificial Intelligence (ICTAI), pages 515-522. IEEE, 2005.
Olivier Buffet. Reachability analysis for uncertain SSPs. International Journal on Artificial Intelligence Tools, 16(4):725-749, 2007.
Olivier Buffet and Douglas Aberdeen. Robust planning with (L)RTDP. Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI), pages 1214-1219.
Olivier Buffet and Douglas Aberdeen.FF+FPG: Guiding a policy-gradient planner. Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling (ICAPS), pages 42-48. AAAI Press, 2007.
Olivier Buffet and Douglas Aberdeen.The factored policy gradient planner (FPG). Artificial Intelligence, 2009.
Esra Erdem and Alfredo Gabaldon. Cumulative effects of concurrent actions on numeric-valued fluents. In Proceedings of the 20th AAAI Conference on Artificial Intelligence (AAAI), pages 627-632. AAAI Press, 2005.
Esra Erdem and Alfredo Gabaldon. Representing action domains with numeric-valued fluents. Proceedings of the 10th European Conference on Logics in Artificial Intelligence (JELIA), LNCS 4160, pages 151-163, 2006.
Alfredo Gabaldon.Formalizing complex task libraries in Golog. Proceedings of the 17th European Conference on Artificial Intelligence (ECAI), pages 755-756. IOS Press, 2006.
Alfredo Gabaldon and Gerhard Lakemeyer. ESP: A logic of only-knowing, noisy sensing and acting. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI), pages 974-979. AAAI Press, 2007.
Robby Goetschalckx, Scott Sanner, and Kurt Driessens. Reinforcement learning with the use of costly features. Proceedings of the 18th European Conference on Artificial Intelligence (ECAI), pages 779-780. IOS Press, 2008.
Charles Gretton and Sylvie Thiebaux. Exploiting first-order regression in inductive policy selection. Proceedings of the 20th Conference in Uncertainty in Artificial Intelligence (UAI), pages 217-225. AUAI Press, 2004.
Patrik Haslum. Reducing accidental complexity in planning problems. Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI), pages 1898-1903. AAAI Press, 2007.
Patrik Haslum. A new approach to tractable planning. Proceedings of the Eighteenth International Conference on Automated Planning and Scheduling (ICAPS), pages 132-139. AAAI Press, 2008.
Patrik Haslum, Malte Helmert, Blai Bonet, Adi Botea, and Sven Koenig. Domain-independent construction of pattern database heuristics for cost-optimal planning. Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI), pages 1007-1012. AAAI Press, 2007.
Malte Helmert, Patrik Haslum, and Joerg Hoffmann. Flexible abstraction heuristics for optimal sequential planning. Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling (ICAPS), pages 176-183. AAAI Press, 2007.
Malte Helmert, Patrik Haslum, and Joerg Hoffmann. Explicit-state abstraction: A new method for generating heuristic functions. Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI), pages 1547-1550, 2008.
Sarah Hickmott, Jussi Rintanen, Sylvie Thiebaux, and Lang White. Planning via Petri net unfolding. Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI) , pages 1904-1911. AAAI Press, 2007.
Iain Little, Douglas Aberdeen, and Sylvie Thiebaux. Prottle: A probabilistic temporal planner. Proceedings of the 20th National Conference on Artificial Intelligence (AAAI), pages 1181-1186. AAAI Press, 2005.
Iain Little and Sylvie Thiebaux. Concurrent probabilistic planning in the Graphplan framework. Proceedings of the Sixteenth International Conference on Automated Planning and Scheduling (ICAPS), pages 263-273. AAAI Press, 2006.
Silvia Richter, Douglas Aberdeen, and Jin Yu. Natural actor-critic for road traffic optimisation. Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems (NIPS), pages 1169-1176. The MIT Press, 2006.
Jussi Rintanen. Compact representation of sets of binary constraints. Proceedings of the 17th European Conference on Artificial Intelligence (ECAI), pages 143-147. IOS Press, August 2006.
Jussi Rintanen.Unified definition of heuristics for classical planning. Proceedings of the 17th European Conference on Artificial Intelligence (ECAI), pages 600-604. IOS Press, August 2006.
Jussi Rintanen. Asymptotically optimal encodings of conformant planning in QBF. Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI-07), pages 1045-1050. AAAI Press, 2007.
Jussi Rintanen. Complexity of concurrent temporal planning. Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling (ICAPS), pages 280-287. AAAI Press, 2007.
Jussi Rintanen. Planning graphs and propositional clause-learning. Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR), pages 535-543. AAAI Press, 2008.
Jussi Rintanen. Regression for classical and nondeterministic planning. Proceedings of the 18th European Conference on Artificial Intelligence (ECAI), pages 568-571. IOS Press, 2008.
Sylvie Thiebaux and Olivier Buffet. Planification d’opérations. In Processus décisionnels de Markov en intelligence artificielle, Vol 2, pages 219-247, Hermes, June 2008.
Sylvie Thiebaux, Charles Gretton, John K. Slaney, David Price, and Froduald Kabanza. Decision-theoretic planning with non-Markovian rewards. Journal of Artificial Intelligence Research, 25:17-74, 2006.
Xinhua Zhang, Douglas Aberdeen, and S. V. N. Vishwanathan. Conditional random fields for multi-agent reinforcement learning. Proceedings of the Twenty-Fourth International Conference (ICML), pages 1143-1150. ACM, 2007.

Conference tutorials and invited talks:

Mausam, David Smith, Sylvie Thiebaux Probabilistic Temporal Planning, tutorial at the International Conference on Automated Planning and Scheduling (ICAPS), 2007.
Jussi Rintanen. Planning: Techniques for Efficient State-Space Traversal, Tutorial at the AAAI Conference on Artificial Intelligence (AAAI), Boston, Massachusetts, July 16, 2006.
Jussi Rintanen. Reasoning about Dynamic Systems by Satisfiability Testing: Planning, Model-Checking and Diagnosis, Tutorial at the International Joint Conference on Artificial Intelligence (IJCAI), Hyderabad, India, January 8, 2007.
Sylvie Thiebaux. Probabilistic Temporal Planning, International Workshop on Planning and Scheduling for Space, invited talk, 2006.

This document is maintained by Sylvie Thiebaux
Last Modified April 2016