Dr Cara MacNish (cara@cs.uwa.edu.au)

1. 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. One approach to this problem 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 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.

2. 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 each time it is used. The aim of this project is to investigate potential techniques for iteratively modifying plans based on their success or otherwise. It will involve building a simple logical model for testing plans, and will explore the use of genetic algorithms and other techniques for plan modification.

3. Belief Revision and Requirements Specification
   Belief revision is a field of study which looks at the way theories (or information represented as sets of logical formulas) should change in order to incorporate new information without damaging the integrity of existing information. This is useful in many application areas. An example is requirements engineering, where we would like to be able to analyse the impact of changes to a specification in advance of making the changes. (It is estimated that about 80% of software costs in the aerospace industry result from changes rather than initial development!) Recent work in belief revision has focussed on finite "bases" for theories, thereby providing realistic possibilities for implementation. The aim of this project is to implement such a system, probably based around a Prolog theorem prover, and attempt to analyse its utility on a an example application of the student's choice.

4. "Intelligent" Keyboard Aids
   Entering textual information into computers now forms an integral part of many peoples daily lives. In a text entering device there is a trade-off between the "cost" in terms of physical effort (eg number or range of keystrokes required) and the complexity of generating appropriate strings. The traditional keyboard is at one end of this spectrum, requiring great dexterity from the user, with a simple algorithm for mapping keys to characters. While this is reasonably efficient for many users, for users with physical impairments (for whom computers should provide great potential) the cost of physical effort is often greater and computational aids have an important role to play. The most common computational aids for text entry are simple prediction algorithms, which attempt to complete words or sentences from a statistical record of previous sessions or existing texts. These algorithms require the user to select from a large number of alternative completions, many of which do not make grammatical sense. The resulting overheads often make the systems unviable. The aim of this project is to develop a more sophisticated text entry system which makes use of grammatical information and other techniques from computational linguistics.