O-Plan Web demonstration outputs

A range of different outputs can be produced by the O-Plan Web demos. This document provides a brief explanation.

Contents:

  1. O-Plan, tasks, and plans
  2. A demonstration
  3. Output formats

O-Plan, tasks, and plans

First, something about what O-Plan does. The O-Plan home page may also be consulted.

Tasks and plans

O-Plan is given a task, and it produces a plan. The task specifies actions to be carried out or conditions to be achieved. Since conditions are achieved by actions that have the required effects, both aspects of the task result in actions being added to the plan.

The plans that O-Plan produces are hierarchical, partially-ordered networks of actions. They're hierarchical because some actions are broken down (expanded) into subactions. They're partially ordered because actions don't always have to occur in sequence. Sequencing is added only when it's needed. For instance, if I'm going to go to work, I have to eat breakfast and get dressed first; but I could eat breakfast and get dressed in either order, and I might eat breakfast and read the paper at the same time.

Note that it's only the latter case - actions that could be happening at the same time - that can remain unordered. For actions that could happen in either order, a valid plan will have them in one order or the other; but both plans will be possible.

Conditions and effects

An action has conditions and effects. Conditions and effects have the form 
   pattern = value
for instance 
   {on a b} = true
   {size a} = 10
   {distance_between a b} = 3
   {location jeff} = work
   {breakfast_eaten} = true

If we imagine the actions of a plan taking place in time, then at any given time the state of the world at that time can be described as a list of pattern = value pairs, or p-v-pairs. If p=v is such a pair, we might say p has value v or perhaps that p=v is true. (Don't confuse this with the case where v is true.) The pairs are sometimes called facts.

An action's conditions describe what values certain patterns must have before the action can occur. An action's effects describe changes in pattern values.

Every condition in the plan must have at least one matching effect that (a) occurs at an earlier point in time, and (b) cannot be canceled by any intervening effect. This ensures that the required condition is true. When a condition depends on an effect in this way, the dependency is recorded in a table known as the GOST (for GOal STructure).

O-Plan does not explicitly track the state of the world. Instead, it records effects and when they occur in another table called the TOME (Table Of Multiple Effects). From this, and from information about when actions take place, it's possible to determine at least part of the state of the world at a given time, t. It may not be possible to determine the entire state at t, because it may not be known whether certain effects must happen before t or not.

For instance, suppose I'm traveling to Edinburgh on a train that will arrive between 10 and 11 at night and that we're using effects to record my position. (Forget about whether we could actually know the arrival time that precisely, given all the things that can go wrong.) We can represent this in a plan. The travel-to-Edinburgh action would have an end-point that is listed as being between 10 and 11, and there'd be an effect at that point such as 

  {location jeff} = Edinburgh
Now supppse we ask for the state of the world at 10:30. Am I in Edinburgh or not? The answer is that we can't say, because there's nothing in the plan that tells us. In the plan, I could be in Edinburgh by 10:30, but I am not definitely in Edinburgh until 11.

Time points and node-ends

It's time to say more precisely how actions, points in time, and so forth, are represented in a plan. We've already said that a plan is a network of actions, and we've mentioned some data structures, the TOME and GOST. Now we're going to say more about the network, and about time. Our aim is to reach a point where we can present a worked-out example.

A demonstration

Definitions

getting to work

Output formats

Postscript graph

A PostScript graph of the nodes and links in the plan. In order to simplify the graph, dummy nodes that can be removed without increasing the number of links have been removed, as have redundant links. However, all of the necessary order-relationships are preserved.

When possible, both ends of a node are shown as a single block. This happens when links do not enter or leave "between the ends", i.e. when links go only to the begin-half of the node or from the end-half.

Narrative

One possible execution trace of the plan.

KP trace

The output produced by the KP-1 Knowledge Platform while the planner is constructing a plan. It shows each the planner followed when finding the plan. (This is not available in all demos.)

Requesting a KP trace will substantially slow the planner.

World-1

The state of the world, or world view, at the end of node-1 as seen by conditions. Remember that the conditions at a given point (node-end) are infinitesimally before the effects at the same point. So this world-view does not show the effects that happen at the end of node-1. All you'll normally see are the "always" facts. However, some tasks, such as those in blocks-1, place their initial facts as effects at the beginning of node-1, and those effects will be seen.

The format is: 

  world
    pattern_1 = value_1
    pattern_2 = value_2
    ...
  end_world

World-2

The world view at the end of node-2. By convention, this is the final state after the completion of the plan, and although difficulties analogous to those of World-1 are possible in theory, they never actually arise. The format is the same as that of World-1.
Jeff Dalton