Using Meta-Level Search for Efficient Optimal Planning

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.