Humans, however, do manage to plan in complex real-world domains. It seems likely that rather than plan from scratch, humans will use knowledge of plans that have been successful for similar problems in the past, and attempt to combine and 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 synthesising and improving plans.
Reinforcement learning [Sutton92] is a technique, motivated by behavioural science, for training automated systems from examples. If a system behaves well on an example a positive feedback signal is used to reinforce that behaviour, whereas if it behaves badly a negative signal is used to discourage it. The idea of reinforcement learning can be used in automated planning. It is theoretically possible to associate values (called heuristics) with states that make the planning process extremely efficient. Unfortunately, finding these values in practice is in general computationally far more expensive (if possible at all) than the planning problem itself. Instead we can attempt to automatically learn, using an iterative reinforcement process, a function that approximates the ideal values.
There are many problems associated with the development of an effective reinforcement learning strategy - what information should be presented as inputs to the approximator, how should this information be represented, what sort of approximator is appropriate (linear approximator, neural network, etc), how should the error be measured and acted upon, and so on.
One or more projects are available investigating these issues. They will involve implementing planning domain representations (preferably with a graphical interface in Java) and reinforcement learning algorithms, running experiments in those domains and analysing the results in an attempt to improve planner performance.
Two of the biggest obstacles to progress in adaptive planning research are:
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. A first attempt at this can be found in [Ison96].
In order for a problem generation system to be adopted for benchmarking it must be justified that the problems generated are a suitable reflection of real world domains. This requires surveying the domains used for evaluating and comparing planners in the literature, and using this information to parameterize and appropriately weight a problem generation system.
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.
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", a data structure common to all agents [Erman80], 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.
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.
One approach to speed-up learning in planning is to attempt to synthesise new planners from examples of successful plans . 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 that relate the number of examples needed to 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, carry out empirical studies of the utility of this approach compared with other learning techniques, and examine approaches for reducing the number of examples required.
Default logic provides an important tool for reasoning from incomplete knowledge - something that humans do all the time. Unfortunately, like other approaches to this problem, it is computationally very expensive. Anytime reasoning is one approach for dealing with computationally expensive reasoning systems, in which answers are accepted that are as "good as possible" given the resources (particularly time) available. This relies on the property that the more time that is given, the closer the answer generated will be to an ideal answer. Unfortunately the algorithms available for default reasoning do not satisfy this property, and thus anytime reasoning strategies are not currently available (other than for very constrained subclasses).
The reason that default reasoning algorithms do not satisfy the above property is that they concentrate on individual sets of "beliefs" in isolation, and these sets may "live precariously". The aim of this project is to investigate the possibility of using observations from a population of candidate belief sets to avoid such pitfalls. This will be achieved using an approach based on genetic algorithms.
Object Constraint Language (OCL) is a specification language designed for use with (among other things) the Unified Modelling Language for object-oriented design. It is a formal language that is intended to be useable by practitioners who do not have a strong background in mathematics and formal methods.
The aim of this project is to investigate the use of OCL for specifying and checking the performance of methods in abstract data types, and in particular container classes (Queues, Stacks, Lists, etc), written in Java. It will involve assessing the strengths and weaknesses of OCL compared with other well-known specification languages, examining the tools available for automated validation of OCL statements and verification of code, and endeavouring to write software for testing code against the specifications. If successful this may be incorporated as part of the automated laboratory submission system (DATLAB) used in the Second Year Data Structures course.
Return to the 4th year project list