Iterative Approaches to Adaptive Planning

The "traditional" approach to planning is to begin with a start state and search for a series of operations which transforms this into a goal state (or vice versa). This process is generally exponentially hard and therefore too expensive to use on large real-world problems. Yet humans do manage to plan in complex real-world domains. It seems likely that rather than plan from scratch, humans will use knowledge of plans which have been successful for similar problems in the past, and attempt to adapt them for the current problem. Similarly, a human will rarely start by generating an optimal plan for a problem, but instead will come up with a plan that works, and improve it incrementally as it is used. The aim of these projects is to investigate potential techniques for improving plans by iterative modification. For an example of previous work in this area (on which some of the proposals below build) see Graham Ison's 1996 Dissertation.

Benchmarks for Planning
Two of the biggest obstacles to progress in adaptive planning research are:
- the lack of benchmark planning problems, or more importantly, sets of representative problems, for comparing different approaches, and
- the difficulty of choosing well-justified fitness functions for evaluating plans and partial plans.
These problems make it difficult to say with any generality that one approach is superior to another (other than on a specific problem, in a specific domain, with a particular choice of fitness function) and form the focus of this project. For example, one difficulty with obtaining data-sets for evaluation is that manually collecting, formalising and expressing real-world domains is both a labour-intensive process and requires a large degree of industrial input. A more tenable solution is to generate data-sets of plans automatically, providing it can be justified that the plans generated are a suitable reflection of real world domains. This will require surveying domains used for evaluating and comparing planners in the literature, and using this information to parameterize and appropriately weight a plan generation system.
Using Domain Structure in Adaptive Planning
One of the problems encountered in using adaptive techniques, such as genetic algorithms, for plan modification is the large number of possible modifications (for example cross-overs) and the sparseness of promising candidates (for example, plans that "nearly" work) within the space of modified plans. If we were able to draw a directed graph of plans (states joined by operators), however, we would see "clustering" or "bottlenecks" around certain states, which might suggest prefered cross-over points. It is also possible that these points are appropriate places to "partition" plans for expression by higher-level operators in a hierarchical planning framework (such as ABSTRIPS [Sacerdoti74]). The aim of this project is to investigate whether these cluster points can be found, perhaps with the use of hierarchical planning information, and utilised to select promising modifications.
Parallel Adaptive Planning
In adaptive planning there is, at any stage, many rules or operators that can be applied. Using genetic algorithms, for example, there will be cut and splice operations as well as a range of mutations that can be applied to any member of the plan population. A choice, generally determined by weighted probabilities, must be made at each stage to determine which operators to apply. It is very difficult to find the best weightings - they will vary with planning domain, and also change as the population changes over the course of plan modification. The aim of this project is to investigate whether the operations can be treated as (largely) independent "agents" which learn to optimise their own behaviour. These agents would take plans from populations posted on a "blackboard" (data structure common to all agents) to which they would post their results. The ultimate aim is for agents to learn, based on their performance, to recognise and focus upon plans that they are likely to have most success with. More successful agents may also "multiply", and less successful ones "die out", in order to make optimal use of resources. This is a large problem and it is unlikely that it could be "solved" within the space of a one year honours project - the aim here is to to develop a "proof of concept" to determine the feasibility of this approach.

Learning Planning (or Search) Algorithms from Examples

The aim of speed-up learning is to improve the efficiency of algorithms, usually by making them more specific to a particular class of problems. For example, planning or searching over a domain may be NP-hard, but for specific subdomains, or for the majority of problems appearing in a domain (hopefully those which occur more frequently in practice!) polynomial algorithms may exist.

Planner Synthesis from Examples
One approach to speed-up learning in planning is to attempt to synthesise new planners from examples of successful plans [Dormer+MacNish95]. This can be achieved in a logical setting by looking at the conditions under which operators are applied in the successful plans, and generalising these to form operator preconditions in a new planner. There are statistical techniques which relate the number of examples needed and the coverage of the synthesised planner. While these numbers give theoretical guarantees, they are usually much higher than the number of examples used by more pragmatic learning techniques. The aim of this project is to implement an algorithm for synthesising planners based on the above approach and to carry out empirical studies of the utility of this approach compared with other learning techniques.

Some additional references for further reading.