EPSRC logo

Details of Grant 

EPSRC Reference: EP/F022883/1
Title: Using Meta-Level Search for Efficient Optimal Planning
Principal Investigator: Fox, Professor M
Other Investigators:
Long, Professor D
Researcher Co-Investigators:
Project Partners:
Department: Computer and Information Sciences
Organisation: University of Strathclyde
Scheme: Standard Research
Starts: 01 January 2008 Ends: 31 December 2011 Value (£): 324,412
EPSRC Research Topic Classifications:
Artificial Intelligence
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
18 Oct 2007 ICT Prioritisation Panel (Technology) Announced
Summary on Grant Application Form
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 information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Summary
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.strath.ac.uk