Standard O-Plan Demonstrations


This document describes a set of demonstration applications which can be used as an introduction to the O-Plan system. They range in complexity from simple block stacking problems to such things as space station construction, satellite control, and island evacuations. The demonstrations show many aspects of planning problems, from simple action expansions to complex, goal-directed reasoning.

For each demonstration there are a number of hypertext links that, when selected, run O-Plan on a machine in Edinburgh using the World-Wide Web's Common Gateway Interface. This results in a document that describes a plan for whatever problem ("task") the link you selected represents.

Instead of saying "applications", we'll often talk of domains. Informally, a domain is just a planning application area such as house-building or block-stacking. However, we'll also use "domain" in a narrower, technical sense to refer to a set of definitions prepared for O-Plan. Such domains are also called "domain descriptions", or "domain definitions" and are written in the Task Formalism (TF) language. More than one set of definitions can be written for a given application area; the variations will depend on what application features are of interest and on how one choses to represent them in TF. So there can be several different house-building or block-stacking domains in the narrower sense of "domain". Each one typically corresponds to a single TF source file, and these files / domains have names such as "blocks-1" or "house-4".

The hypertext links in this document that are used to run O-Plan look something like this:

The links above will work; but you should read this before trying them. The first line gives the domain, get-to-work. Select that link to get the TF definition of the domain. The "task" lines represent tasks or problems within the domain. Select a task to cause O-Plan to run and produce a plan.

The get-to-work domain is a simple example designed to help explain how O-plan works. You may want to read that explanation, at some point. It also describes the outputs that O-Plan produces.

Now, here's a preliminary description of the example domains. More complete descriptions, plus links for seeing the TF definitions and for running O-Plan, will follow.

Block stacking
Some TF files deal with various block stacking problems such as the Sussman Anomaly.
House Building
Several TF files define house building problems. The different files deal with time constraints, alternative building methods and contractors, etc.
Missionaries and Cannibals
This is the standard missionaries and cannibals problem in which the task is to move three missionaries and three cannibals from the right bank of a river to the left bank using a single boat. The constraint is that the cannibals should never outnumber the missionaries on either bank (otherwise the cannibals will eat the missionaries!).
Pacifica is an island state in the Pacific and the tasks consist of moving a number of evacuees from remote parts of the island to a central evacuation point and then flying them out. This example can be used to demonstrate the AutoCAD user interface to O-Plan (but not, unfortunately, on the Web).
Satellite Control
A TF file for a satellite command and control problem. The satellite has various experiments whose data must be captured and transmitted to earth, taking into account time and resource constraints.
Space Platform Construction
A TF file for a very simple space platform construction problem. This example can be used to demonstrate the AutoCAD user interface to O-Plan (though not via the Web).

Block Stacking

Block stacking puzzles are often used as a basic test domain for AI planning systems. In this particular demonstration the planner will be asked to solve the following type of problem:
                                     |     |
                                     |  A  |
         _____                       |_____|
        |     |                      |     |
        |  C  |                      |  B  |
        |_____|   _____              |_____|
        |     |  |     |             |     |             
        |  A  |  |  B  |             |  C  |
        |_____|  |_____|             |_____|
         Initial State              Goal State
The planner is to construct a plan to change the initial state into the goal state. This is a simple problem because the planner has only a few simple plan operators which rely on the following assumptions: A full list of file names and task schema names are provided in the following two tables. The file blocks-1 contains a single puton schema with which the planner must construct a plan. The file blocks-2 uses three schemas: a less capable puton and two others: makeon and makeclear.
  C      --->   B        (The Sussman Anomaly problem)
  A  B          C
 ------       -----
  A      --->   B
  B  C          C
 ------       -----
  C      --->   B
  A  B          A
 ------       -----
  C      --->   A
  A  B          C
 ------       -----
The problems are the same as in blocks-1, but the operators used to solve them are different.
  C      --->   B        (The Sussman Anomaly problem)
  A  B          C
 ------       -----
  A      --->   B
  B  C          C
 ------       -----
  C      --->   B
  A  B          A
 ------       -----
  C      --->   A
  A  B          C
 ------       -----

House Building

This application shows the development of a plan for the construction of a typical family house. The plan is developed in a top-down manner with high level actions such as install_services and decorate being inserted first and then expanded. This avoids the planner having to consider the detailed levels of the plan before the more important high level actions have been sketched out. The different house building tasks show how time and resources can be modelled within the domain.

A full list of file names and task schema names are provided in the following table.

Builds a simple family house.
Contains TF which shows how interactions occur between schemas and how schemas which provide alternate ways of achieving a task can be specified. The interaction can be seen in the plan trace as a failure to expand the first install-services schema chosen and as a result taking the second install-services schema instead.
A larger house building example that in house-1 or house-2. The plan constructed requires more condition satisfaction and interaction removal than in the previous house building problems.
A house building example similar to house-1 except that it includes durations for actions and time windows in which specified actions must take place.
Build the house within a set time period on difficult ground, with the time limits so tight that no solutuion is possible.
Build the house within a set time period on ready ground, 1 alternative possible (with standard kitchen).
Build the house within a set time period on ready ground, 2 alternatives possible (one with standard kitchen, one with luxury kitchen).
House-building constrained by strictly-consumable resources. The resources available are money, sticks, straw and bricks. (Guess who lives in this house.)
A simple family house with no restrictions on time and resources.
Builds a family home for a cost between 0 and 2000 pounds which is also proof against wolves.
Builds a home for a cost between 0 and 500 pounds.
Builds a home for a cost between 0 and 500 pounds which is also proof against wolves. (This turns out to be impossible.)

Missionaries and Cannibals

This is the standard missionaries and cannibals problem. The definition shows some of the numerical reasoning capabilities of the O-Plan system. The problem consists of moving 3 missionaries and 3 cannibals from the right bank of a river to the left bank using a single canoe. The constraint on the problem is that the cannibals must never outnumber the missionaries, for otherwise the missionaries will be eaten.

The problem is defined in several different ways, as listed below. All of them keep track of a "state" that lists the bank the boat is on and the numbers of missionaries and cannibals on each side. All record when a state has already been visited as a way to avoid pointless journeys. However, they differ in how arithmetic is performed or in the way they generate the sequence of moves. Some of the techniques developed for this problem have later been used in other domains.

The starting state has three missionaries and three cannibals on the left back of the river along with the canoe.

The mathematics of calculating the number of missionaries and cannibals is carried out using successor arithmetic based on matching against patters that describe simple sums. Another set of patterns describes the safe states.
Gets everyone to the right bank.
The mathematics of calculating the number of missionaries and cannibals is carried out using compute conditions that call Common Lisp functions. Safety is checked in a similar way.
Gets everyone to the right bank.
This is the last written and most radical of the three.
Gets everyone to the right bank.


This example develops plans for evacuations from a hypothetical island named Pacifica.

Pacifica is an island state located in the Pacific Ocean within long distance flying time of Honolulu, Hawaii. It has a very interesting coastline, but remains shrouded in mystery due to its inaccessibility over the centuries. Only in the last century has it been inhabited, though some areas of the island remain largely unexplored and are unmapped.

The story

A number of people must be evacuated from the cities Abyss, Barnacle, and Calypso. They will first be driven to the capital, Delta, then flown to Honolulu. Initially, a C5, a B707, and some ground transports (GTs) are located in Honolulu. From this initial situation, a plan is developed that moves the required transportation resources from Honolulu to Delta, uses the GTs to move the evacuees to Delta, and finally flies everything to Honolulu.

A list of file names and task schema names are provided in the following table.

Two Ground Transports (GTs) are available.

Satellite Control

This application shows the development of a plan for the control of a simple satellite we have called EUSAT (Edinburgh University Satellite). This satellite is based on the actual University of Surrey's successful UoSAT series of satellites. Earlier research into the application of task planning and scheduling at Edinburgh has included work on defining a task formalism description for O-Plan1 for a spacecraft similar to UoSAT-II but omitting confidential information (which we called BOGUSAT). This was further extended in the T-SCHED scheduling system, which took a scheduling perspective as opposed to the task planning view of O-Plan1, and generated actual on-board computer Diary commands. The O-Plan project EUSAT model uses the same spacecraft model as BOGUSAT.

The experiments of the spacecraft include:

  1. Navigational Magnetometer (NAVMAG)
  2. Sun Sensor
  3. Horizon Sensor
  4. Space Dust Analyser
  5. Digital Voice Recording (DigiTalker)
  6. Charge Coupled Device (CCD)
  7. Particle Wave Experiment
The experiments are connected via a series of switches to a tape recorder (DSR) and then to either a 70cm or 2m antenna for transmission to the ground. Alternatively some experiments can be connected directly to an antenna through line6 instead of passing through the DSR. One of the experiments, called the DigiTalker, allows for a message to be loaded into a tape recorder (the DCE) from the ground and subsequently re-transmitted at a later time back to the ground. As well as the series of experiments, the satellite must also send telemetry data to the ground. The movement of data from an experiment to an antenna is modelled as a set of switch settings. Each switch has a valid set of inputs and outputs, as follows:
Switch No   Inputs                           Outputs
---------   ------                           -------
1           line0 line1 line2 line3 line4    line5
2           line5                            line6 line7
3           line7 line8 line9                line10
4           line6 line12 line13 line15       line 16
5           line16                           antenna70cm antenna2m
6           antenna70cm antenna2m            ground buffer
A task given to O-Plan describes the requirements for work in a typical day in the life of the spacecraft.
  1. monitor_spacecraft_health: Send current telemetry data to ground.
  2. capture CCD: Collect data from the CCD and send it to the ground via the DSR.
  3. capture p_w: Collect data from the particle wave experiment and send it to the 2m antenna either directly or via the DSR.
  4. capture space_dust: Collect data from the space dust analyser and send it to the 2m antenna either directly or via the DSR.
  5. DCE_communicate: Receive and re-send a message from and back to ground.
The task specifies the objectives of the mission. This is a series of experiments whose data must be collected and transmitted to a ground buffer via one of two antennas. O-Plan is able to generate a plan for such a mission and give output in a form that could be accepted by the normal diary based dispatch execution system on board a simple spacecraft.

The following table describes the files and task schemas which are available in this domain.

Capture the data from a series of experiments and transmit it to a ground buffer. The order of the data capture is specified by the user and is sequential.
Similar to the task above except that the order of data capture is unspecified.
The O-Plan planning agent has been demonstrated generating a plan for such a task and passing it to an O-Plan architecture based execution system for simple dispatch and monitoring to take place.

Other related work at Edinburgh has led to the two planning systems for the European Space Agency. The first was the Plan-ERS system which could generate mission plans for the European Space Agency's ERS-1 spacecraft. This prototype was built in the KEE knowledge representation system and uses a simple plan representation. A second system, OPTIMUM-AIV, is able to generate and support the execution of plans for spacecraft assembly, integration and verification. This second planner uses a Goal Structure based plan representation working alongside links to a traditional project management support system (ARTEMIS).

Space Platform Construction

This application shows the development of a plan for the construction of one of a number of different Space Platforms. Platforms are constructed from a series of joints, trusses, pressurised modules, solar panels, radiators and antennas.

This domain is normally used to demonstrate the AutoCAD user interface that has been constructed for O-Plan. AutoCAD can draw a PostScript picture (like this one) of a platform at any point in its construction, based on information from a complete or developing plan. A screen dump of the AutoCAD interface is shown above. (Select the picture to see a larger version.)

The following list describes the files and task schemas which are available in this domain.

Builds a medium sized space platform with 1 antenna, 4 solar panels, 2 radiators, 2 modules, 3 trusses and 3 joints.
Builds a small sized space platform with 1 antenna, 2 solar panels, 1 radiator, 1 module and 1 joint.
Builds a large sized space platform with 2 antenna, 6 solar panels, 2 radiators, 5 modules, 4 trusses, 3 tubes and 8 joints.

Creating and Running your own Applications

Unfortunately, you can't yet run your own applications over the Web, but we hope to change that soon.

The TF language allows users to develop their own applications. Some of the demonstration applications could be used as starting points. This section provides only a brief introduction and overview of what goes in a TF description file.

Task Schemas

The task schemas introduce the tasks the planner is asked to carry out. The first line of a task definition begins with task to indicate to the planner that it is a task schema. Other schema definitions begin with schema. Here's a sample task:
task build_stack_ABC;
  nodes 1 start,
        2 finish;
  orderings 1 ---> 2;
  conditions achieve {on a b} = true at 2,
             achieve {on b c} = true at 2;

This task schema provides an initial plan: start and finish nodes, which are always numbered 1 and 2 respectively. The orderings clause says that the start (1) must be before the finish (2). The conditions clause indicates to the planner any conditions it must achieve. In the example above there are two conditions to achieve by the finish of the plan (i.e., "at 2") which together represent a three-block tower: a b c.

A task schema can also be used to provide a high level action which the planning system must expand into progressively lower level actions until an executable plan is available. In the example below the action to be expanded is to build a house:

task build_house;
  nodes 1 start,
        2 finish,
        3 action {build house};
  orderings 1 ---> 3, 3 ---> 2;

Global Data and Object Types

These data items specify the objects in the domain and the classes to which they belong. They also declare specific statements which cannot be refuted by the effects of plan actions actions. These are referred to as "always statements" or "always facts". In the block stacking domain the following global data could be specified:
always {cleartop table} = true;      ;;; the table is always a clear object

types objects = (a b c table),       ;;; all objects in the domain
      movable_objects = (a b c);     ;;; stop the planner trying to
                                     ;;; move the table 

Application Schemas

The application schemas provide the "actions" of the plan together with information concerning variables, resources, time windows and domain information to help in search control. The schema below defines an action which puts one object on top of another, i.e. {puton ?x ?y}. Information concerning the variables ?x and ?y is given in two different places:
This statement introduces the variables of the schema together with their types (if known) and other relationships. The type is an enumerated set which allows the planner to determine all possible values the variable could take.
This statement introduces the equality and inequality relationships between variables in the schema. In the example below the /= (not-equal) relationship stops the planner binding the object being moved and the destination of the move to the same value.
schema puton;
  vars ?x = ?{type movable_objects},
       ?y = ?{type objects},
       ?z = ?{type objects};
  var_relations ?x /= ?y, ?x /= ?z, ?y /= ?z;
  expands {puton ?x ?y};
          {on ?x ?y}    = true,
          {cleartop ?y} = false,
          {on ?x ?z}    = false,
          {cleartop ?z} = true;
  conditions only_use_if {cleartop ?x},
             only_use_if {cleartop ?y},
             only_use_for_query {on ?x ?z};
The conditions statement specifies condition types that tell the planner how a particular condition should be satisfied. This also provides the planner with information as to the strength of commitment to maintaining the condition in a particular way. The names only_use_if, only_use_for_query, and (in one of the tasks above) achieve are all condition types. A complete list of condition types is described in the TF Manual.

The only_use_for_effects and effects statements inform the planner of the effects the schema asserts. The only_use_for_effects statement indicates the effects which the schema can be used to achieve, i.e. its primary effects. The effects statement indicates the side effects of the action. The schema should not be chosen specifically to achieve them.

The sections above give a brief overview. Facilities such as resources and time windows have not been described but are fully documented in the TF Manual.

Jeff Dalton
Brian Drabble