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
- 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
- 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.
PLANET RELATED ACTIVITIES
USEFUL PLANNING LINKS
Page maintained by Peter
Last updated: 1 Oct 1998