Jim Blythe, Nov 1 2001
SADL, the Shaken Action Description Language, is used to described processes within Shaken system. A definition of the Shaken action description language (SADL) can be found here. This document compares SADL to the PDDL language as well as to TAPIR used by the UMass Sim SHAKEN team and to the process ontology within DAML-S. In this comparison I focus on each as a process representation language and ignore other aspects of the representations. In general, the three representations are compatible, allowing processes to be described in terms of a number of sub-processes, which may be loosely or tightly synchronised. They have all been designed with slightly different goals, and this affects the emphasis that each has placed on different aspects of the language. However the languages have typically made similar decisions about the aspects that they do cover; therefore this document takes the form of a mapping of language features rather than a comparison that highlights differences.
PDDL, which stands for Planning Domain Definition Language, was originally developed as part of the AIPS98 planning competition, and was intended to be a uniform domain representation for different AI planning systems involved in the competition. More details can be found from Drew McDermott's home page. PDDL allows a wide range of things to be said about actions and plans; probably no single system can make use of them all. In this comparison I focus on its language for describing actions in terms of sub-actions.
DAML-S is an ontology to support services on the semantic web as part of the DAML program. A process ontology is included to provide a detailed model of services for coordination and monitoring. The latest version of the ontology used for this comparison was 0.5, which can be found here. The DAML-S ontology shares with PDDL the aim of supporting a wide range of different systems but its focus is on web services rather than automatic planning.
TAPIR is the process language used by the Sim SHAKEN group at UMass, led by Paul Cohen. The group uses simulation to uncover information about processes, and so this language has gone further than the others in representing execution-time information such as handling interruptions.
SADL, the Shaken action description language, has been developed to support the Shaken system for knowledge acquisition, to allow human domain experts to specify information about processes. More information about SADL can be found here, and information about Shaken can be found here. SADL extends the action representation already found in the KM representation language which is used in Shaken. More details about KM can be found here.
In each of these languages, a process is represented as having preconditions and postconditions, and as having a collection of sub-processes. Here I concentrate on the representation of a process as a collection of sub-processes. The representation languages are compared across the following features of a process language:
In the following tables I indicate the forms that can be used within each language to produce the desired effect without explaining precisely how the form is used. The reader may follow the links above to the language descriptions for the details.
| Effect | PDDL | SADL | TAPIR | DAML+S |
|---|---|---|---|---|
| A linear sequence of processes | (series proc1 proc2 ...) | The next-step link between sub-steps in a process can be used to create a linear sequence. | (:do proc1 proc2 ...) | The Sequence construct holds a list of processes. |
| An unordered set of processes | (parallel proc1 proc2 ...) implies no ordering constraints. | The sub-step link points to each sub-process, no next-step link is used. With no temporal links, the processes are assumed to take place one at a time but in no specified order. Allen's interval calculus can be attached to processes to force parallel execution. | Either (:unordered proc1 proc2 ...) or (:parallel proc1 proc2 ...). :unordered implies that the subprocesses are executed one at a time but in no specified order. :parallel implies that the subprocesses may take place concurrently. | Either Unordered or Split. Unordered implies that the processes are executed one at a time but in no specified order. Split implies that the subprocesses take place concurrently. |
| Combinations, including arbitrary DAG orderings | series and parallel may be nested. The constraint form can also be used to assign tags to the beginning and end of a process which can then be ordered with respect to other processes, allowing arbitrary DAGs to be represented. | The next-step link can be used to form any DAG | :do, :parallel and :unordered can be nested to create arbitrary orderings. | Sequence, Unordered, Split and Split+Join can be nested to create arbitrary orderings. |
| Effect | PDDL | SADL | TAPIR | DAML+S |
|---|---|---|---|---|
| Conditional sub-processes in the decomposition of a process. | The in-context form specifies conditions on the subprocesses that appear in a decomposition. | The next-step link can be made conditional on the outcome of a test applied to the state at the time that the step is to be chosen | The :when construct. | The If-then-else construct. |
| Choice between alternative decompositions of a process | choice | The test in a conditional next-step link is defined as non-deterministic, representing that a system choice is to be made. | Choice expresses that a subset of the processes described is chosen and executed. The precise manner is to be determined in subclasses of Choice that are yet to be described as of DAML-S version 0.5 | |
| Interruption handling: actions to take in response to failure messages from subprocesses during execution | Currently not represented. There are plans to incorporate the technique used in TAPIR | The :handle construct specifies subprocesses to be instantiated when a specified message is received from a sibling or child subprocess during execution. The :generate construct specifies a message to send to the parent process. | Behaviour during execution is specified in the Process Control ontology in DAML-S, which is not described in version 0.5 |
| Effect | PDDL | SADL | TAPIR | DAML+S |
|---|---|---|---|---|
| A process with an iterative loop | The PDDL description does not discuss iteration in an action's expansion. In the spirit of the AI planning systems that inspired PDDL, this can probably be achieved by recursively referring to the parent process in the specification of sub-processes. Iterative expansion would terminate with a Choice or in-context form as described above. | The next-step links can form a loop, with loop unrolling at execution time managed by instantiating different step instances on each iteration around the loop. A conditional next-step link can be used to represent the loop's termination condition. | The :repeat-:until construct specifies a simple loop which can be combined with other language constructs. | The Iterate construct represents a process whose next process property has the same value as the current process. The Repeat-Until and Repeat-While subclasses use the If-Then-Else construct to manage termination. |
Please send comments and suggestions to Jim Blythe.