[ Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. There won't be further updates to these pages. ]

(Related publication: [PUBLink])

The most prominent representative of sequence-oriented representations is the STRIPS model by Fikes and Nilsson [PUBLink], which is based on the Situation Calculus by McCarthy and Hayes [PUBLink] and is applied in many planning systems.

In STRIPS, a single fact is represented by an atomic proposition, such as IS_OPEN(DOOR). A set of these facts establishes a world state.

A plan is a sequence of actions, an action being defined by a precondition, a delete list and an add list. The precondition is a formula, which must be valid in the current world state. To obtain the subsequent world state, the facts of the delete list must be deleted from the current world state, and the facts of the add list must be added. Here is an example of an action MOVE(A,B,C) that moves block A from the top of block B onto block C:

Action:	MOVE(A,B,C)
Precondition:	CLEAR(A) & ON(A,B) & CLEAR(C)
Add List:	{ CLEAR(B), ON(A,C) }
Delete List:	{ ON(A,B), CLEAR(C) }

Sequence-oriented representations provide a rich framework for the treatment of decision alternatives. But in EXCALIBUR's multi-agent domain with its dynamic environment and temporally complex actions, this would result in an unmanageable complexity. Sequence-oriented representations have a branching point for each action decision of the agent. In a dynamic environment, the situation might change without the agent's activity. To capture these changes, each branching point would have to include all possible changes of the environment that might affect the agent's behavior. As computer game agents are commonly required to be highly interactive with their environment, this entails a vast combinatorial explosion. The incorporation of a richer temporal annotation (actions have a duration; simultaneity; synergies) is even more fatal. There must be branching points for each possible timestep providing for all possible changes in the environment that might affect the agent's behavior - a desperate approach.

The success of sequence-oriented representations like STRIPS is a result of assumptions negating external events and a richer temporal annotation. It must be said, though, that there are several extensions of STRIPS-like representations designed to remove specific backdraws, e.g., an extension to concurrent interacting actions by Boutilier and Brafman [PUBLink].

For questions, comments or suggestions, please contact us.

Last update:
May 19, 2001 by Alexander Nareyek