PLANET node:

Artform at the University of Huddersfield


Background:

Research into Planning and Scheduling in Artform of the University of Huddersfield has steadily increased over the last five years, with projects supported by the UK's research council and the National Air Traffic Services. The projects involve both fundamental and applied research, and encompass symbolic and subsymbolic AI, statistical and OR techniques.


Projects:

Planform: An Open Environment for Building Planners

The Planform project is a major EPSRC-funded project which started in December 1999 and which involves researchers from the Universities of Huddersfield, Durham and Salford. The project is also supported by the UK National Air Traffic Services Ltd and CogSys Ltd.

The Planform project aims to research, develop and evaluate a method and supporting high level research platform for the systematic construction of planner domain models and abstract specifications of planning algorithms, and their automated synthesis into sound, efficient programs that generate and execute plans.

Object-Centred Language: Specification of planning domain models

The Object-Centred Language (OCL) and more recently the hierarchical version OCLh development method forms a rigorous approach to capture the functional requirements of classical planning domains. Using OCL, one builds a model of the planning world, including valid world states and operator schema modelling possible actions. The operators' preconditions and postconditions are specified in terms of the substate transitions of objects. This approach utilises the notion of ``lifting'' a world's representations from the level of the literal to the level of a more abstract object-centred representation.

Object-centred Planning with TO and PO Planners

An investigation has been carried out into the use of domain models written in OCL with three different object-centred planners. The algorithm for an object-centred planner is consistent with the OCL domain model in that it functions at the object level rather than the predicate level. The first planner is an object-centred total-order planner, based on McCluskey's FM. The planner calculates for each object the difference, if any, between its current state and its goal state. It then seeks to reduce this difference by finding steps that achieve the object's goal state. If these steps are applicable in the current planning state, then they are immediately applied, and planning continues from this advanced state. The other 2 planners are both object-centred partial-order planners. One is based on UCPOP and it plans by finding actions that achieve a required transformation from one object substate to another. These actions are partially ordered with respect to each other. Planning stops once a state satisfying the goal is reached. The second partial order planner focuses on one object at a time, building a path of partially ordered actions from its initial state to its goal state. Once a path has been constructed it is the merged into the global plan. Both the total_order planner and the partial-order path planner can make use of top-level goal orderings to help improve their performance.

Object-Centred HTN Planning

The objective of the research is to extend the structures in OCL so that it is expressive enough to be used in realistic applications with for example HTN planner technology. An HTN planner called "EMS" has been created that processes hierarchically defined domains in OCLh. "EMS" can input problems posed as combinations of goals, action schema and constraints, and it outputs valid plans that solves these problems.

Planning Using an Object-Plan Graph

This ongoing work integrates two strands of planning research - that of using plan graphs to speed up planning, and that of using object representations to better represent planning domain models. To this end we have designed and implemented "OCL-graph", a plan generator which builds and searches an object-centred plan graph, extended to deal with conditional effects. Our initial design and experimental results appear to confirm our conjectures that the extra information and structure of OCL benefits plan generation efficiency and algorithmic clarity.

Knowledge-intensive conflict resolution planning

The research was sponsored by the UK NATS, and focused on the domain problem of conflict resolution for the 4D multi-segment flight-plan clearances which figure in current methods of air traffic control over the Atlantic. Development of a prototype problem solver for conflict resolution of flight plans involved integration of AI and OR techniques.

An investigation into ways of achieving more flexible and adaptable, artificial intelligence based, nurse rostering systems

This research is centred round the use of multi-modal reasoning to improve workforce scheduling, particularly in the nursing domain. The two key paradigms being investigated are Case-Based Reasoning (CBR) and Constraint Logic Programming (CLP). The aim is to find ways of storing previous schedule solutions as cases held as partially instantiated and generalised CLP descriptions. Similarity measures will be used to extract all or parts of these descriptions for use in the generation of new schedules. The reason for this choice of multi-modal reasoning is to increase the possibilities for adaptation and learning within the system. Of particular interest is that ability of case-based reasoning to reflect expertise or preferences that are not explicitly expressed.

Publications:

Here are some recent publications.

Contacts:

Lee McCluskey - t.l.mccluskey@hud.ac.uk

Ron Simpson - r.m.simpson@hud.ac.uk