Timelines and Tokens

Consider a spacecraft traveling through deep space, tasked with taking pictures of specific targets. The spacecraft has an engine which can be fired to alter its pose. It also has a camera which is turned off when not in use. If the camera was previously off, it can require some warm up period before being ready. The spacecraft attitude is either pointing at a specific target, thus having a steady pose, or transitioning from one pose to another. There are 3 state variables of interest in this spacecraft scenario: Engine, Camera, and Attitude. A timeline captures the values of a state variable over time. The figure below illustrates timelines for each of the above state variables. Both the Camera and the Engine are Off and the spacecraft is PointingAt a target given by D12. The value of a state variable, specified with a Token, has temporal extent, which means it persists for some period of time. The temporal scope for a value is bounded by a start and end time. In the figure below, the start time of each token is fixed, but the end time is not. This indicates uncertainty and/or ambivalence about when the current value will end. A token includes a predicate with a possibly empty set of parameters, in keeping with conventional first-order-logic representations. The Engine can be Off or it can be Thrusting to a target pose. The Camera can be Off , WarmingUp, Ready , or TakingPicture at some target pose. The spacecraft Attitude is either PointingAt a target pose, or TurningTo a target pose.

Constraints and Causal Links

Suppose the spacecraft should take a picture of a specific asteroid. While it is taking a picture of the asteroid, it should be pointing at it. This can be said for any target pose. Also, in order to prevent jitter in the image, it is critical that the engine is Off while the shot is being taken. The figure below illustrates how the spacecraft timelines are filled out to accommodate this goal. It illustrates the values of timelines as they are expected to change, as well as the constraints between start times, end times and parameters. Causal Links form a chain connecting goals to initial conditions. A causal link is a directed edge from a master token to a slave token.

Note that the requirement that while taking a picture, the engine must be off is expressed as a constraint from the Camera timeline to the Engine timeline, with precedence constraints between timepoints capturing the while semantics. Also note the transition of the Camera timeline from Off to TakingPicture must go through intermediate states to first warm up and then be ready. The goal also requires a change in vehicle attitude. The adjustment in attitude is co-temporal with thrusting the engine. This is expressed by equality constraints between the start and end times of the respective tokens.

Modeling

So far we have used informal language to describe the spacecraft domain. NDDL is a formal modeling language used to specify a planning domain such that algorithms for search and inference can be applied to automatically fill out timelines as just described.

Class Declarations

A Target is a structure defining a point in cartesian space:

class Target{
 float x;
 float y;
 float z;

 Target(float _x, _y, _z){
  x = _x;
  y = _y;
  z = _z;
 }
}

The Engine timeline is declared thus:

class Engine extends Timeline{
 predicate Off{}
 predicate Thrusting{
  Target target;
 }

 Engine(){super();}
}

Similarly, we can declare Attitude and Camera timelines.

class Camera extends Timeline {
 predicate Off{}
 predicate WarmingUp{}
 predicate Ready{}
 predicate TakingPicture{
  Target target;
 }
 Camera(){super();}
}

class Attitude extends Timeline {
 predicate PointingAt{
  Target target;
 }
 predicate TurningTo{
  Target target;
 }

 Attitude(){super();}
}

Transition Constraints

There are a number of constraints governing transitions within a given timeline. For example, the engine will transition between Off and Thrusting . We can express this with rules constraining successor and predecessor values of each value:

Engine::Off{
 meets(Thrusting);
 met_by(Thrusting);
}
Engine::Thrusting{
 meets(Off);
 met_by(Off);
}

Meets and met_by are examples of qualitative constraints between temporal intervals known as Allen Relations. If the Camera is Off its next state will always be WarmingUp :

Camera::Off{
 meets(WarmingUp);
}

Similarly, if it is WarmingUp , it will transition into Ready , and its prior value must be Off .

Camera::WarmingUp{
 meets(Ready);
 met_by(Off);
}

The Attitude state variable is also constrained to transition between PointingAt and TurningTo . In this case, we have to introduce a constraint between parameters of tokens:

Attitude::PointingAt{
 meets(TurningTo);
 // There is a parameter constraint equating parameters of the current and previous values.
 met_by(TurningTo pred);
 pred.target == target;
}
Attitude::TurningTo{
 meets(PointingAt succ);
 target == succ.target;
 met_by(PointingAt);
}

Interaction Constraints

In addition to constraints on transitions within a timeline, we described a number of constraints between values across timelines. For example, the constraints holding on TakingPicture additionally include:

Camera::TakingPicture{
 contained_by(Engine.Off);
 contained_by(Attitude.PointingAt p);
 p.target == target;
}

Also, the interaction between Attitude.TurningTo and Engine.Thrusting can be stated simply:

Attitude::TurningTo{
 equals(Engine.Thrusting t);
 t.target == target;
}

Automated Planning

There is a very general notion that a plan might be flawed, and thus require fixing. The primary reasons why a plan is flawed are because it is incomplete or inconsistent. If a plan is incomplete, it must be further refined. If it is inconsistent it must be repaired. This section will illustrate the process of plan refinement using the spacecraft example, whereby an initial state and goal represent an incomplete partial plan that which can be incrementally refined until there is a valid trajectory of all state variables to get from the initial state to the goal. Plan repair will not be discussed at this time. Suffice to say, it requires a relaxation of the plan in some fashion. The series of diagrams below illustrate how an initial partial plan is refined repeatedly until all flaws are resolved.

Next, see do timelines map to execution?