Introduction
I am a Research Fellow in the Strathclyde Planning Group
and have been employed on two EPSRC projects within the group. The current project (EP/G023360/1) involves reasoning about modelling planning problems and automatically reformulating planning models in order to make solving more efficient. I also work on planning with continuous numeric resources, this work began as part of the first EPSRC project on which I was employed (EP/D062721/1).
Recent major contributions of my work include development of the planners: Colin, capable of reasoning with continuous numeric change; LPRPG, discrete numeric change using an LP to perform complex numerical reasoning; and CRIKEY 3 an expressive temporal planner capable of reasoning with concurrency. Temporal and numeric reasoning is vital in allowing planning to be applied to real world problems, which contain much of this type of structure: charge in Martian Rovers, Fuel in Logistics and Power Demand in Electricity supply.
My research interests include application of planning to real-world tasks, and through this I have been involved in developing VOLTS in conjunction with the Department for Electronic and Electrical Engineering at Strathclyde. VOLTS is a system for asset management based on the Grendon Substation, part of the UK's National Grid, near London. As part of my project in modelling I have also been involved in work on scheduling aeroplane landings and locomotive assignment on the Hungarian Railway Network.
If you are looking for Amanda Smith, that's me, I got married in June 2008.
Research Interests
Click one of the links for a summary of my research in the corresponing area.
Planning Theory
Temporal and Numeric Planning
In the real world resources are key to solving large scale planning problems. Current planning technology tends to focus on solving the propositional part of planning problems and encounters difficulty when expressive numeric effects are involved. We have created two planners: the first is LPRPG a numeric non-temporal planner able to reason with domains in which the transfer of numeric resources is critical in solving the problem. LPRPG uses a linear programming within heuristic computation to allow this more sophisticated reasoning. The second planner,
Colin, uses a linear programming scheduler to allow reasoning with continuous numeric effects, which necessitates reasoning about both time and numbers. Our approach uses a combination of the relaxed planning graph heuristic, and an LP (solved using CLP) to overcome many problems of the conventional approach. Colin is capable of handling domains with linear continuous effects, for sample problems and the binary for Colin see the
Colin Website.
SGPlan has exhibited excellent performance winning the two most recent International Planning Competitions. Its approach to problem solving is to decompose the planning problem into a number of smaller problems; solve these individually; and then use a cycling process, with penalty weights added to the heuristic, to find a consistent solution to the overall problem. The strong performance of SGPlan indicates that decomposition is indeed a promising way of solving the planning problem, yet very little is understood about precisely why SGPlan performs so well. To investigate why decomposition is such a successful approach to planning we have built the planner TSGP (Transparent Sub-Goal Planner). TSGP is an open-source implementation of SGPlan, as far as can be understood from the literature, with some novel solutions to issues in areas where is not clear how SGPlan works. Using TSGP we are able to investigate why decomposition planning is a good strategy and where the benifits of this approach arise.
Informed Probabilistic Replanning
With Andrew Coles (University of Strathclyde) and Sergio Jiménez (Universidad Carlos III de Madrid)
A topic of great recent debate in the planning community has been whether probabilistic reasoning in planning offers any benifits over re-planning. This question was particularly brought to light by the results of the First International Probabilistic Planning Competition, in which the planner FF-Replan outperformed all the planners using advanced probabilistic reasoning. The approach of FF-Replan is simple, to ignore the probabilistic effects of actions and plan as if the problem were deterministic, taking the most likely outcomes of actions. If execution does not occur as expected, then the planner simply generates a new plan to the goal from the current state. Re-planning can be done quickly as the problems posed to probabilistic planners are generally small due to the combinatorial search space that any 'true' probabilistic reasoning must explore. The weakness of the FF-Replan approach is that it completely ignores probabilistic information; this prompted researchers to highlight a class of problems that cannot be solved by FF-Replan. Our informed replanning approach models the probabilities of action failure as metric costs, and attempts to minimise the probability of failure. We also add dead-end detection techniques to allow the planner to predict certain failures and avoid taking these routes. Through this we can extend the capabilities of probabilistic replanners to deal with problems thought only to be solveable through a traditional approach.
Learning Macro-Actions in Planning
I am interested in the generation of macro-actions planning, in particular online techniques for learning and managing macro-actions. I co-authoured the planner Marvin which competed in the Fourth International Planning Competition; see the
the Marvin home-page.
The work in my PhD thesis was concerned with caching and managing macro-actions that are learnt during search. The macro-actions are sequences of actions that have been used to escape plateax in EHC search, as discovered by Marvin. Allowing macro-actions to be cached for use in solving future problems offers the potential for greater performance improvements. The work done includes investigating the properties of domains on which the techniques are useful; identifying the properties of the most useful macro-actions; and investigating the performance of the planner using a range of macro-action library management strategies. Further work investigates the extension of the techniques for use under the Causal Graph heuristic and the simulation of macro-actions through action re-ordering strategies. My thesis and a list of my publications are available from the publications section of this site.
This work involves applying more sophisticated local-search techniques to solve planning problems. Local search is popular for solving problems, it is used in FF and LPG. Our planner, Identidem (Latin meaning repeatedly), extends the local search in FF to allow local search on plataux. Search is stochastic allowing restarts and backtracking combining the strengths of LPG with the simplicity of FF.
Planning Applications
Application of Planning to Electricity Substation Control
For deatils of this project visit the VOLTS website
With Keith Bell (Department of Electronic and Electrical Engineering, University of Strathclyde); Andrew Coles, Maria Fox and Derek Long (Department of Computer and Information Sciences, University of Strathclyde)
We are working with power systems engineers in order to apply AI planning technologies to the problem of regulating voltage at electricity substations. We are considering the Grendon sub-station, this is an important part of the National Grid infrastructure as it is part of the system responsible for providing the electricty supply to London. Voltage regulation is an important problem faced by the National Grid, variations in customer demand throughout the day mean that voltages at the sub-station fluctuate throughout the day. The challenge to engineers is to maintain the voltage within a certain range: too low and the electircity supply to the city becomes inadequate, lights begin to dim and appliances don’t function properly; too high and safety issues arise, both in the substation and in overpowering customer appliances. Maintaining the voltage is an interesting planning problem, because not only must the voltage be maintained but the wear-and-tear on the transformers and capacitors used to control the voltage in the substations must be minimised. This has lead to us addressing a new challenge for AI planning: multi-objective optimisation with conflicting objectives. Our system provides engineers with automatically generated voltage targets instructing the automatic system what voltage to achieve at each time given the predicted demand and the wear-and-tear minimsation constraints.
Aeroplane Landing Scheduling
Over subscription is a big problem today in UK airports, with runway slots being at a premium and delays being rife. This work aims to build a planning model of major UK airports and apply state-of-the-art planning technology to solve the problems better optimising the use of landing slots at airports. We use our planner
Colin to solve these generated aeroplane landing problems taken from data on UK airport websites. The work has featured in
Scotland on Sunday. We currently have a student, Stuart Arthur, working on a user interface for the system that will allow airport staff to interact with the planner, inputting data about the current state of the airport, without the need to understand the PDDL modelling language used.
Professional Activities
Programme Committee Memberships
- 20th International Conference on Automated Planning and Scheduling (ICAPS 10)
- 19th European Conference on Artificial Intelligence (ECAI 2010)
- 19th International Conference on Automated Planning and Scheduling (ICAPS 09)
- 21st International Joint Conference on Artificial Intelligence (IJCAI 09)
- 27th Workshop of the UK Planning and Scheduling Special Interest Group (PlanSIG 08)
Workshop Organisation
I co-organised the ICAPS 2009 workshop on Planning and Learning.
Reviewer for
- Artificial Intelligence
- Journal of Artificial Intelligence Research (JAIR)
- Journal of Scheduling (JOSH)
- Knowledge Engineering Review (KER)
Education
I started my PhD studies, in October 2003, at the Department of Computer and
Information Sciences at the University of Strathclyde in Glasgow. I submitted my PhD thesis in 2006. My thesis, entitled "On The Inference and use of Macro-Actions in Forward Chaining Planning", can be found on my publications page
Before coming to Strathclyde, I gained a first-class batchelors degree in Artificial Intelligence at the University of Durham. For my final-year project I developed a simulation of
rovers
operating within a closed Martian environment. A domain, based on the Rover domain from the Third International Planning Competition was produced
which enabled the integration of a number of planners; notably
Metric-FF,
MIPS,
Sapa
and VHPOP.
The source code of the simulation is available on request; my project report can be found here.
Other Interests
Outside of work I enjoy playing the piano and trampolining.
