The SHAKEN action description language (SADL)

Jim Blythe, Feb 14th 2001
With contributions from Pete, John, Paul, Gary, Pat, Bruce, Ken, Yolanda, Jihie and others.

The SHAKEN system needs to be able to reason about processes that contain loops, conditional steps, partially ordered steps and disjunctive steps to meet our goals for May. The language described here makes minimal necessary extensions to the process description language already existing in KM that will allow this. Because the extensions are small, implementing them in each of the components of SHAKEN should be straightforward, and further extensions can be made in the future as needed. Because a process description will be shared between several components, we need a very clear understanding of the meaning of each construct in the language and also of how each component can use the language.

This document summarizes the existing language, describes the extensions and then shows how they are represented in KM. After this we mention some constructs that may be added later, and link to an example based on the December model of RNA transcription.

A short comparison between SADL and the action languages PDDL, DAML+S and TAPIR can be found here.

Events, steps and event instances

Feel free to skip this section unless you are interested in how the representation of sub-steps in processes has been influenced by KM's policy of creating skolem instances.

An event like ``Move'' is represented in KM independently of any particular process description. When a process description refers to a Move, it refers to a step in the process that implements the Move event. A process description may have several, distinct Move steps. Likewise a step in a process description has a next-step, but the event description does not. Finally when a process is executed, the actual execution of the step is an event instance.

This is a change from the original representation, where the sub-steps of a process were described directly as event classes. The reason for this change is that, if some of the sub-steps of a process form a loop, a different event instance should be created each time a sub-step is executed within the loop. In the original scheme, skolem event instances for sub-steps are created when the parent event is created, but for a sub-step in a loop it is not clear which execution the skolem event instance refers to. In the new scheme, skolem step instances are created when the parent event is created, and child event instances are only created when the sub-step is executed.

In the rest of this document I only refer to steps.

The existing action language

The current language for describing processes in KM makes use of steps that can have several sub-steps. When a step in a process is to be executed, all of its sub-steps should be executed. A step in a process may also include a next-step slot that determines the next step to be executed. Here is an example:

(every RNA-Transcription-Process has
   (sub-steps
     (a Step called "collide" with
       (event-type-to-do (Collide))
       (next-step (((the sub-steps of Self) called "recognize"))))
     (a Step called "recognize" with
       (event-type-to-do (Recognize))
       (next-step (((the sub-steps of Self) called "copy"))))
     (a Step called "copy" with
       (event-type-to-do (Copy))
       (next-step (((the sub-steps of Self) called "release"))))
     (a Step called "release")))

The meaning of the sub-steps and next-step values on this example is that to execute an RNA-Transcription-Process, the steps called ``collide'', ``recognize'', ``copy'' and ``release'' are executed in that order.

No sub-step is explicitly designated the first step in this process. Any step that is not the next-step for some other step could potentially take place first.

Loops, disjunctive, conditional and partially ordered steps

Steps in a process are partially ordered if the order in which the steps take place is incompletely specified. A partial ordering over steps does not mean that the steps can be executed simultaneously, only that the full, linear ordering of the steps is not specified. For instance if two trucks need to go through a narrow tunnel, they cannot both go through at the same time although we may not care which goes first.

A process description has a loop if a sequence of steps can be repeated. For example in the description ``the polymerase moves forward until the promoter region is reached'', the move step is a single-step loop. Loops usually have a termination condition which is tested each time the loop is completed.

A conditional step is one that is executed only if some condition is met, for example ``if the gas tank is empty, fill it''. The condition is usually tested against the world state immediately before choosing to execute the step.

Two or more steps are disjunctive if only one of them will take place. For instance: ``to get to the zoo, either take the 10 freeway or take the 5 freeway''.

For ease of implementation, this language defines both loops and disjunctive steps in terms of conditional steps, as I describe below.

Extending the existing KM representation

Partially ordered steps

A concise way to represent partial orders is to allow more than one step in the next-step field, with the intended meaning that each step is executed eventually, but their order is undefined. However, steps do not take place simultaneously. If two or more steps designate the same step e as next-step, and the designating steps have a common ancestor, then e is considered a join step, meaning that it cannot be executed until all the designating steps have been executed.

For example, suppose a process to move two trucks through a gate requires first opening the gate, then moving both trucks (in any order), then closing the gate. This can be represented as follows:

(every move-trucks-process has
  (sub-steps
    (a Step with
      (event-type-to-do (open-gate))
      (next-step (((the sub-steps of Self) called "move1")
                  ((the sub-steps of Self) called "move2"))))
    (a Step called "move1" with
      (event-type-to-do (move))
      (next-step (((the sub-steps of Self) called "close-gate"))))
    (a Step called "move2" with
      (event-type-to-do (move))
      (next-step (((the sub-steps of Self) called "close-gate"))))
    (a Step called "close-gate" with
      (event-type-to-do (close-gate)))))

Since open-gate is the only step in the process that is not the value of next-step for some other step, it is the first step to be executed. After open-gate, either move1 or move2 are executable. Suppose move1 is executed. Although the next-step field is close-gate, this step cannot be executed because move2, which also has close-gate as its next-step field, has not yet been executed. So after executing move1, the order of the remaining steps is uniquely determined.

If there is more than one step in a process that is not designated as the next-step of some other step, they should be interpreted as a set of potential first steps that are unordered with respect to each other.

Conditional steps

The following syntax can be used to represent conditional steps:

(a Step called "move" with
  (event-type-to-do (Move))
  (test ('((the location of Self) = (the promotor region...))))
  (next-step ((:args t   ((the sub-steps of Self) called "recognize"))
              (:args NIL ((the sub-steps of Self) called "move")))))

Either branch can be empty, indicating that there is no next step in that case.

Loops

The above example implements a loop where the move step is repeated until the test in the next-step condition is met. The condition plays the role of the termination condition for the loop. A loop involving several steps can also be made simply by having the next-step of a step point to an ``earlier'' step.

For example, a simple RNA-Copy process could be defined like this:

(every RNA-Copy has
  (sub-steps (
    (a Step called "create" with
      (event-type-to-do (Create))
      (next-step (((the sub-steps of Self) called "attach"))))
    (a Step called "attach" with
      (event-type-to-do (Attach))
      (next-step (((the sub-steps of Self) called "move"))))
    (a Step called "move" with
      (event-type-to-do (Move))
      (test ('((the location of Self) = (the promotor region...))))
      (next-step ((:args NIL ((the sub-steps of Self) called "create"))))))))

This approach to defining loops is flexible since it allows multiple entry points and multiple exit points under different conditions. However a SME might find it hard to reason about the loop because it is represented implicitly. One possibility is for an explicit loop construct to be translated into this syntax for ease of implementation (an idea that Peter referred to as a ``macro''). For example the construct

repeat step1 step2 .. stepn until

could be translated into a loop in which stepn has a conditional next-step.

Disjunctive steps

Disjunctive steps can be represented in terms of a conditional step using an explicit non-deterministic test. Again an explicit macro construct may help an SME, for example the SME might use the construct

 either take the 10 freeway or take the 5 freeway

which could be translated to

(a Step with
  (test ('(equal (toss-a-coin) heads)))
  (next-step ((:args t   (take the 10 freeway))
              (:args NIL (take the 5 freeway)))))

Here, toss-a-coin is a non-deterministic operation that either yields heads or tails.

Other constructs that may be added later

There has also been some discussion about other constructs that may be needed for May. We intend to include some way to handle "errors" that can arise when processes are executed, using a small extension that follows the approach already taken by Paul and his group. There are some other potential extensions that have been discussed, but which will probably not be included before the summer unless we see that they are definitely needed. These include:

maintenance conditions (eg if an agent carries an object, then the agent must be holding the object for the entire period of the carry)
Interpreting a richer language for dependencies between events, including temporal dependencies (eg, two events must take place concurrently, or must start at the same time). Note that we can already represent these dependencies, since Allen's interval calculus is available in the component library, but the effect that these construct have on the simulators is currently undefined.
loop counters (eg, repeat this step 10 times). We currently plan to implement counters through event effects.
an explicit treatment of resources (eg, since the polymerase is a discrete, reusable resource it can only be used by one transcription event at a time, but is available for other transcription events after the current event is finished).
An ability for a process to "spawn" others, ie start a subprocess without suspending action until the subprocess finishes. Over time an unlimited number of subprocesses could be spawned.

Example: RNA transcription

A version of the December RNA transcription model in KM, following this language, can be found here. (As of Feb 14, this example is still under review.)

Please send comments and suggestions to Jim Blythe.