Node Overview | Links to Planning Work at Edinburgh | Node Members | PLANET Related Activities | Useful Planning Links

OVERVIEW

Edinburgh is one of the top centres worldwide for AI planning and scheduling research. Work over a 30 year period at Edinburgh has lead to innovations in planning techniques and to the creation of several practical planning systems used on a variety of specific applications. The Edinburgh team represents one of the largest and most active groups engaged in AI planning research worldwide and maintains active international links with governments, industry, academics, standards bodies, and professional institutions.

Early work included extension to OR techniques to perform heuristically guided search and the use of domain information to guide search. The Edinburgh Nonlin system in the mid 1970s put in place a number of techniques now commonplace in major planners characterised as "hierarchical partial-order planners" or "hierarchical task network planners". The techniques include Goal Structure Analysis and recording during search; domain model capture and use to guide and prune search; combining AI and incremental OR methods for planning and scheduling; etc. Applications of Nonlin included electricity turbine overhaul, spacecraft mission sequencing, and navel replenishment at sea.

Current work includes The O-Plan (the Open PLANning Architecture) Project which is exploring issues of coordinated command, planning and control. The objective of the O-Plan Project is to develop an architecture within which different agents have command (task assignment), planning and execution monitoring
roles. Each agent has a structure which separates the following components:

• the representation of the processing capabilities of an agent;
• the computational facilities available to perform these capabilities;
• the constraint managers and commonly used support routines which are useful in the construction of command, planning and control systems;
• the decision making about what the agent should do next;
• the handling of communications between one agent and others.

The main contribution of the O-Plan research is to provide a complete vision of a more modular and flexible planning and control system incorporating AI methods. We have demonstrated our approach on realistic problems related to military logistics. Our approach will have an impact in the following ways:

• it will allow for improved connectivity and consistency between command, planning and control;
• it will make plans open, inspectable, explainable and changeable;
• it will allow greater scope in Course of Action analysis and as such provide greater plan reliability.

Within the agent-based O-Plan architecture we have created specific agents to provide a domain-independent general planning and control framework with the
ability to embed detailed knowledge of the domain. The system combines a number of techniques:

• A hierarchical planning system which can produce plans as partial orders on actions similar to the Edinburgh Nonlin planner.
• An agenda-based control architecture in which each control cycle can post pending tasks during plan generation. These pending tasks are then picked up from the agenda and processed by appropriate handlers (Knowledge Sources).
• The notion of a ``plan state'' which is the data structure containing the constraints on emerging plan, the ``agenda'' of further requirements, and the information used in building the plan.
• Constraint posting and least commitment on object variables.
• Temporal and resource constraint handling using incremental algorithms which are sensitively applied only when constraints alter.
• O-Plan is derived from the earlier Nonlin planner from which it takes and extends the ideas of Goal Structure, Question Answering (Modal Truth Criterion) and typed conditions.
• We have extended Nonlin's style of task description language Task Formalism (TF).

LINKS TO PLANNING WORK AT EDINBURGH

• O-Plan - part of the DARPA/Air Force Research Laboratory (Rome) Planning Initiative (ARPI).
• <I-N-OVA> Constraint Model of Activity.
• I-X: Technology for Intelligent Agents and Tools.
• ISAT project - part of the DARPA/Air Force Research Laboratory (Rome) Planning Initiative (ARPI).
• Optimum-AIV - European Space Agency - spacecraft assembly, integration and test.
• TOSCA - Hitachi - job shop scheduling.
• SPAR - Shared Planning and Activity Representation.
• NIST PSL - National Institute of Standards and Technology - Process Specification.
• PIF - Process Interchange Format Standards.
• WfMC - Workflow Management Coalition.

NODE MEMBERS

• Dr. Peter Jarvis - PLANET Contact.
• Dr. John Levine.
• Prof.Dr.Ing. Austin Tate.

  Associate Members

• Dr. Brian Drabble, Computational Intelligence Research Laboratory, University of Oregon, USA.
• Dr. Carla Gomes, Air Force Research Laboratory and Cornell University, USA.

PLANET RELATED ACTIVITIES

• Knowledge Acquisition for Planning Technical Coordination Unit: The Edinburgh Node is facilitating this TCU.
• Workflow Technical Coordination Unit: The Edinburgh Node is a member of this TCU.

USEFUL PLANNING LINKS

• AIAI's Planning Information Service.
• UK Planning and Scheduling Special Interest Group.
• PLANET Home Page.