Using Meta-Level Search for Eficient Optimal Planning

  • Fox, Maria, (Principal Investigator)
  • Long, Derek, (Co-investigator)

Project: Research


Our current work, on which this proposal is based, suggests a way of guiding the search for a plan using meta-level information about the structure of the problem. Using an analysis of where the hard parts of the problem lie, we construct a meta-level CSP representation of the problem and use it to focus a SAT-solving search. In our published work we have shown that this approach is extremely successful for propositional planning, finding parallel optimal plans efficiently even for very large problem instances. We believe that it is possible to extend our approach beyond propositional planning and to show that optimality is realistically achievable, even for large problems, if appropriate meta-level information can be obtained. Our goal in this project is to extend our ability to analyse problem structure in order to identify powerful meta-variables in the non-propositional case, so that we can efficiently solve problems for which non-propositional expressive power is required. Our work has important potential application. Safety-critical decision-making in emergency egress planning, start-up and shut-down procedure planning in electrical power and chemical plants, docking procedures and surgical preparation planning and are all examples of problems that require non-propositional modelling and that need to be solved to optimality. In this project we will develop novel techniques to solve such mixed integer linear programming problems, efficiently and makespan-optimally. Currently, optimal planning is so far from application to real word problems that some fundamental developments need to be made before industrial scale problems can be addressed. By showing that optimal planning is feasible for large, non-propositional, planning problems we will make an exciting theoretical contribution to constraint reasoning research and also start to bridge the gap between optimal non-propositional planning theory and practice.

Key findings

This project explored the relationship between planning and constraint programming, leading to important cross-disciplinary work. The planner Constance was developed, which led to some of the initial foundations of the Planning Modulo Theories idea, within our group, which followed later. The project also investigated optimal planning more broadly, considering admissible heuristics for planning within forward state space search. We investigated a variety of constraint problems in planning, such as management of temporal constraints including concurrent activity within plans. Work on this project also led to ideas in QBF planning, which was done in association with EP/G023360.
Effective start/end date1/01/0831/12/11


  • EPSRC (Engineering and Physical Sciences Research Council): £328,644.44


Chemical plants
Linear programming
Power plants
Decision making