The Concurrent, Continuous FLUX

1 Introduction

One of the most challenging and promising goals of Artificial Intelligence research is the design of autonomous agents, in­ cluding robots, that solve complex tasks in a dynamic world. To reach autonomy in partially known, constantly changing environments requires the high-level cognitive capabilities of reasoning and planning. Using a mental model of the state of their environment allows for the agents to calculate the outcome of different action sequences in advance and then choose the best plan to execute for a specific goal in mind.

Formal theories of reasoning about actions and change have the expressive power to provide such high-level capa­ bilities. The Fluent Calculus [Thielscher, 1999], as one of the established action representation formalisms, uses the con­ cept of state update axioms to solve the representational and inferential aspect of the classical Frame Problem. Based on this formal theory, the high-level programming method FLUX has been developed in recent years [Thielscher, 2002]. Using the paradigm of constraint logic programming, the powerful FLUX kernel provides general reasoning facilities, so that the agent programmer can focus on the high-level de­ sign of intelligent agents.

Autonomous agents in real-world environments have to take into account that the execution of actions takes differ­ ent amounts of time. Some actions can be modeled as dis­ crete changes, others involve continuous change and should rather be seen as the initiation or termination of complex pro­ cesses. Such processes may contain parameters whose values change continuously and which are formalized as functions over time. A car moving on a road with a constant veloc­ ity v, for instance, can be represented by a 'process fluent' Movement( x0 , t0 , v), where the parameter x0 denotes the location of the car at the time t0 when the motion was initi­ ated. The fluent Movement itself, although it describes the particular continuous change x = x0 + v * (t- t0 ) for the location x of the car at the time t, will stay unchanged until some other action will affect it. Continuous change is then modeled by fluents describing arbitrarily complex, continu­ ous processes. These fluents remain stable in between the oc­ currence of two consecutive actions, and yet they internally represent continuous change.

In a world full of ongoing processes, however, an agent ex­ ecuting a plan is not the only source of change. Also the laws of physics frequently imply an evolution of the environment, like for example, the action of a falling ball bouncing when it reaches the floor. The fundamental property of such so-called natural actions [Reiter, 1996] is that they must occur at their predicted times, provided no earlier actions (natural or delib­ erative) prevent them from occurring. Because such actions may occur simultaneously, concurrency must be accommo­ dated.

In this paper, we present a FLUX system which allows for the design of intelligent agents that reason and plan in do­ mains involving continuous change and where actions occur concurrently. Using the paradigm of constraint logic pro­ gramming, our extension to FLUX integrates both kinds of actions, deliberative and natural, into one method for the planning and execution of actions. Reasoning in terms of time intervals, our method allows for the efficient genera­ tion of plans in concurrent, continuous environments. Our work is based on the theoretical approach presented in [Herr­ mann and Thielscher, 1996; Thielscher, 2001a]. Other exist­ ing agent programming methods like the robot control lan­ guage developed in [Shanahan and Witkowski, 2000] or the GOLOG programming language [Levesque eta/., 1997], do not handle, in domains involving concurrency and continu­ ous change, the concept of a natural action at all or only have separate accounts for natural actions on the one hand [Reiter, 2001] and for deliberative actions on the other hand [Grosskreutz, 2002].

In the next section, we introduce our example scenario and shortly recapitulate the fundamentals of the FLUX system. We then give briefly the theoretic solution in the Fluent Calculus. Thereafter, we present our extension of FLUX to concurrent, continuous domains and discuss the employed con- 3 strained handling techniques. In the last section we conclude and show some possible future work. All programs are available on our web site: http: I /www. fluxagent. org/

2 FLUX

The example agent program in this paper is set in a waterway scenario. The agent has to steer a barge through a system of canals. The water levels in the canals are dependent on tides. At some places of the canals there are locks which a ship can only pass on a high tide. Due to the geographical facts the tide levels differ for different locks. The canals themselves are too small to turn around but sometimes there are intersections where the agent steering the barge can choose one direction (see also Fig. 1).

To develop an agent for this scenario, we use the high­ level programming method FLUX which is grounded in the action theory of the Fluent Calculus. The Fluent Calculus is a many-sorted predicate logic language with four stan­ dard sorts: FLUENT, STATE, ACTION, and SIT(for situations) [Thielscher, 1999]. States are composed offluents (as atomic states) using the standard function o : STATE x STATE f--> STATE and constant 0 : STATE (denoting the empty state). The program for our agent, for example, uses these two flu­ ents: At(x, y, t) , representing that the barge is at cell (x, y) at time t 1 , and Tide(l, w, t), denoting that at timet the wa­ ter level w at lock l is at high/low tide. Similarly as in the Situation Calculus [Reiter, 2001], the constant S0 denotes the initial situation and Do( a, t, s) the situation after having per­ formed action a in situations at timet. The state of a situation sis denoted by the standard function State(s) . For example, the initial state in the waterway scenario of Fig. 1 may be axiomatized as 2

(:lz) (State( So) =At(1 , 2, 0.0) o 1ide(Lock1,High, 0.0) o Tide(Lock2, High , 0.0) o Tide(Lock3, High , 0.0) o z 1\ (\fu, v, w) ·Holds(At(u, v, w), z) 1\ (\fu, v, w) ·Holds(T!de(u, v, w), z ))

The reader may notice that an incomplete state with addi­ tional negative information has been specified, i.e., the sub­ STATE z may contain many more fluents, but no more At or Tide fluents. The foundational axioms of the Fluent Calculus ensure that the composition function "o" exhibits the proper­ ties of the union function for sets (with 0 as the empty set), so that a state is identified with all the fluents that hold. On this basis, the macros Holds(! , z ) and Holds(! , s) are defined as follows:

1 In anticipation of the integration of continuous change, the ar­ gument t denotes the time when a fluent becomes true or an action takes place.

2 Predicate and function symbols, including constants, start with a capital letter whereas variables are in lower case. Free variables in formulas are assumed universally quantified. Variables of sorts FLUENT, STATE, ACTION,and SIT shall be denoted by letters f , z, a, and s, respectively. The function o is written in infix notation.

In our waterway scenario there are two elementary actions: GoByShip(d), the deliberative action of the agent to steer the barge to the next cell which lies in the direction d, and Turn1ide(l , w), the natural action indicating the turn to the tide w at lock l. The fundamental Frame Problem is solved in the Fluent Calculus by a so-called state update axiom for each action, which describes the effects of the action in terms of the difference between the states before and after the ex­ ecution of it. For example, the action Turn1ide(l, w) can be specified as

where"-" and"+" are macros for fluent removal and addi-. d h ( ) def · tlon; an t e macro Poss a, t, s = Poss( a, t, State( s)) denoting in the Fluent Calculus that at timet action a is possible in state State( s ).

To reflect the incomplete knowledge of an agent about its environment, incomplete states are encoded in FLUX as open lists, that is, lists with a variable tail, of fluents [Thielscher, 2002]. These lists are accompanied by constraints for negated state knowledge as well as for variable range restrictions. The constraints are of the form NotHolds(f, z ), indicating that flu­ ent f does not hold in state z ; and NotHoldsAll(j , z) , indicat­ ing that no instance off holds in z. In order to process these constraints, so-called declarative Constraint Handling Rules [Friihwirth, 1998] have been defined and proved correct un­ der the foundational axioms of the Fluent Calculus (for details see [Thielscher, 2002]).

For example, the initial state depicted in Fig. 1 may be specified by this clause,

init (ZO) : - ZO=[at(l,2,0.0) ,tide(lockl,high,O.O) ,tide( lock2, high, 0. 0), tide (lock3, high, 0. 0) I Z], not_holds all(at( , , ) ,Z), not_holds=all(tide(=,=·-) ,Z).

which also reflects the negative information that no At fluent occurs in sub-state z (the location of our agent is unique), and that there are no more Tide fluents other than specified in state zo.

The predicate Foss( a, t, z) realizes the precondition ax­ ioms for actions, that is, it defines under which conditions an action is possible at timet in state z. There is one such pred­ icate clause for each action. Conditioning in FLUX is based on the foundational predicates Knows(!, z ), KnowsNot(f, z), and KnowsVal(x, J, z ), representing that the agent knows that fluent f holds (respectively, does not hold) in state z, and that there exist ground instances of the variables in x such that fluent f is known to be true in state z. Take, for exal!lpl~, the precondition axiom for the action TurnTide(l , w) whtch 1s implemented as follows,

poss(turntide(L,W),T,Z) (W=high, knows_val([L,TR] ,tide(L,low,TR) ,Z), duration(L,low,D); W=low, knows val( [L,TR] ,tide(L,high,TR) ,Z), duration(L,high,D)), {T =:= TR + D}.

where the auxiliary predicate Duration(l, w, d) denotes the duration d of the corresponding tide w at lock l. The execu­ tion time t of the action will be constrained, using the syn­ tax of the constraint handling library CLP(R) of the Eclipse­ Prolog system, to be the sum of the starting time of the old tide plus the duration of the old tide.

As in the Fluent Calculus, the effects of actions are encoded as state update axioms. For this purpose, the FLUX kernel provides a definition of the auxiliary predi­ cate Update(z1,{)+,{)-,z2). Its intuitive meaning is that state z2 is the result of positive and negative effects {)+ and {)-, respectively, wrt. state z1 . In other words, the pred­ icate encodes the state equation z2 = ( z1 - {)-) + {)+. On this basis, the agent programmer can easily implement the update axioms by clauses which define the predicate StateUpdate(z1, a, t , z2 ), as for example in the following en­ coding for the action TurnTide(l , w):

state update(Zl,turntide(L,W) ,T,Z2) hold~(tide(L,WO,TO) ,Zl), W=high, update (Zl, [tide (L, high, T)] , [tide(L,WO,TO)] ,Z2); W=low, update(Zl, [tide(L,low,T)], [tide(L,WO,TO)] ,Z2).

3 The concurrent, continuous Fluent Calculus

The Fluent Calculus for concurrent actions is based on the additional pre-defined sort CONCURRENT, of which ACTION is a sub-sort [Thielscher, 200la]. Single actions which are performed simultaneously are composed to terms of sort CONCURRENT by a new binary function. The latter is de­ noted by "·" and written in infix notation. This function shares with the function combining fluents to states the prop­ erties of associativity, commutativity, idempotency and exis­ tence of a unit element. The constant "t:" (read: no-op) of sort CONCURRENT acts as the unit element wrt. function"·". Similar to the Holds macro the abbreviation In(c1 , c) is used to denote that concurrent action c1 is included in concurrent action 2:

State update axioms for concurrent actions are recursive. They specify the effect of an action relative to the effect of arbitrary other, concurrent actions:

I.e., {)- and -a+ are the additional negative and positive, re­ spectively, effects which occur if action a is performed be­ sides c. Here, a can be a single action or a compound action which produces synergic effects, that is, effects which no sin­ gle action would have if performed alone. Using recursive state update axioms, the effect of, say, two simultaneous but independent actions can be inferred by first inferring the ef­ fect of one of them and, then, inferring the effect of the other action on the result of the first inference. The recursions stops with the base case of the empty action, which is defined as:

Two or more actions may interfere when executed concur­ rently, which is why the condition ~ in the above state update axiom may restrict the applicability of the implication in view of concurrent action c.

Integrating continuous change in the Fluent Calculus re­ quires the introduction of process fluents which can repre­ sent arbitrarily complex, continuous processes. Because such processes may be modeled by equations of motions, contin­ uous time must be represented. To this end, the new sort REAL is added, which is to be interpreted as the real numbers [Thielscher, 200la] . The sort is accompanied by the usual arithmetic operations along with their standard interpretation. The continuous Fluent Calculus includes the pre-defined flu­ ent StartTime(t), where t is of sort REAL, determining the time Start( z ) at which a state arises, provided that StartTime is unique:

As already indicated throughout the paper, a parameter t of sort REAL is also used to denote the time at which a fluent arises as in Tide(l, w, t) or to represent the occurrence of an action as in Do( a, t, s). A standard requirement for the possi­ bility to perform a concurrent action c at time t in state z may then be expressed as follows : 4

The Fluent Calculus for continuous change includes the distinction between deliberative and natural actions [Thielscher, 200la]. The latter are not subject to the free will of a planning agent. Rather they happen automatically under specific circumstances. In our example domain, the action of the turn of the tide is a natural one. The standard predicate Natural(a) [adopted from [Reiter, 1996]] declares the action a to be natural. To facilitate the formalization of the automatic evolution of natural actions, the continu­ ous Fluent Calculus introduces two macros. The expression ExpectedNatActions( c, t, z) shall indicate that in state z ac­ tions c are all the natural actions that are expected to happen at timet:

3 Variables of the new sort CONCURRENT are denoted by the let­ ter c.

4 In our example domain we have no actions that are in mutual conflict. Therefore, we do not need to specify additional constraints in this precondition axiom.

ExpectedNatActions( c, t, z) ~ c =/= c 1\ (\fa)(In(a, c) = Natural( a) 1\ Pass( a, t , z))

Given the above notion, the macro NextNatActions(c, t, z) stands for the concurrent action c being all natural actions that happen in state z at time t with t being the earliest possible time point at which natural actions are expected:

NextNatActions(c, t, z) ~ ExpectedNatActions(c, t, z ) 1\ -{:Jt', c')(ExpectedNatActions(c', t', z) 1\ t' < t)

The Fluent Calculus for continuous change uses the notion of a situation tree with trajectories [Thielscher, 200la] where a trajectory is associated with a situation and denotes the fur­ ther evolution of the state determined by the natural actions that are expected to happen. We do not follow this approach in this paper, as the original motivation for employing tra­ jectories has been domains with uncertainty about the occur­ rence of natural actions, and we do not consider such domains here. The incorporation of domains with uncertain natural ac­ tions is left for further work. Instead, we include the natural actions in the situation terms, as with deliberative actions.

4 Integrating Concurrency and Continuous Change into FLUX

Similar to the binary function "o", which denotes the compo­ sition of states from single fluents and is represented in FLUX by a list offluents, we represent the binary function"·" as a list of actions in FLUX. In this way, we introduce concur­ rency into FLUX, i.e., all the actions in the list are performed concurrently. On this basis, the unit element of the function "·",the constant "c", is encoded as the empty list [) .

Given the notion of a list of concurrent actions, the state up­ date axioms for the actions are defined recursively in FLUX. The predicate Res(z1 , s 1 , li, t, z2 , Do(li , t, s 1)) specifies the effect of performing at time t the list of concurrent actions l i in state z1 and situation s1 , and leading to the new state z2 and the new situation Do( li, t, s 1 ) after the execution of the concurrent actions. It represents one plan step and is encoded as follows

res(Zl,Sl, [) ,T,Z2,Sl) :­ holds(starttime(TO), Zl), update(Z1 , [starttime(T)), [starttime(TO)) ,Z2) . res(Z1,S1, [AILJ ,T,Z2,do( lAILl ,T,S1)) update ( [A I L J , [ J , [A) , L 1) , state_update(Z1, A, T, Z3), res(Z3, ,L1,T,Z2, ) .

where the clause for the base case of the recursion extends the effect of the constant "c", which by itself has none, to update the pre-defined fluent StartTime(t) needed for FLUX

with continuous change to the new value t . Similar to the encoding of the macros for fluent removal and addition, the predicate Update is used in the clause for the recursive case to implement the elimination of one single action from a term of arbitrary other, concurrent actions.

Consider, for example, the state update axiom of the single action GoByShip( d) which is implemented as:

state_update(Z1,gobyship(D) ,T,Z2) :- knows val([X,Y) ,at(X,Y,TO) ,Z1), holds(starttime(ST) ,Z1), {T >= ST + 1 .0} , adjacent(X,Y,D,X1,Y1), update(Z1, [at(X1,Y1,T)), [at(X,Y,TO)) ,Z2) .

That is, the location of the barge together with the agent will be updated from the old position (x, y) to the new cell (x1 , y1), where the auxiliary predicate Adjacent( x, y, d, x1 , yl) computes the adjacent cell ( x 1 , y1) lying in direction d of cell (x, y). The travel from one cell to another is assumed to take one hour in our example scenario. Therefore, although the execution time t of this action is not fixed by the clause in any way, the effects of the action man­ ifest at least one hour later as the formation of the old state. Now take, e.g., the FLUX query

?-init (ZO), res (ZO, sO, [gobyship (3), turntide(lock3,low)) ,2.0,Z1,S1) .

together with the above definition of the state update axiom and the definitions for the predicate Init(z) (with the addi­ tional inclusion of fluent start time ( o. o)) and the state up­ date axiom of action TurnTide given in Section 2. Together with an appropriate encoding of the fact that a high tide lasts two hours at the third lock, duration ( lock3, high, 2. o), and the knowledge that going south is represented by direc­ tion number 3, our extension of FLUX can infer the effects of this concurrent action by first inferring the effects of ac­ tion gobyship ( 3) and on the result of this inference infer the effects of action turn tide ( lock3, low). FLUX yields the correct substitution:

Z1=[at(1,1,2.0) ,tide(lock1,high,O.O), tide(lock2,high,O.O) ,tide(lock3,low,2.0), starttime(2.0) IZJ S1=do( [gobyship(3), turntide(lock3,low)) ,2.0,s0)

Continuous time is, as already shown above and in Sec­ tion 2, easily integrated into FLUX. The Eclipse-Prolog sys­ tem Version 5.4, which we use, includes the constraint han­ dling library CLP(R). This library allows for solving linear constraints with real numbers. Its syntax requires for con­ straints to be included in braces.

The precondition axioms and state update axioms for nat­ ural actions are encoded in our extension of FLUX in the same fashion as for deliberative actions (see Section 2). Ad­ ditionally, we include an implementation for the predicate Natural( a) which is as follows for the example domain:

natural(A) :- A=turntide(L,W), (L=lock1; L=lock2; L=lock3).

Given this predicate, we model the macro ExpectedNatActions(c, t, z) by the built-in second order predicate SetOf as follows:

setof(A, (natural(A) ,poss(A,T,Z)), C)

On this basis, the macro NextNatActions(c, t, z) is defined in FLUX as:

NextNatTime(T,Z) :­ natural(A), poss(A,T,Z), not (natural(Al), poss(Al,Tl,Z), Tl<T), ! . NextNatActions(C,T,Z) : - NextNatTime(T,Z), setof(A, (natural(A) ,poss(A,T,Z)), C).

Having defined natural actions in the same way as delib­ erative ones leads to the question: How to combine delibera­ tive and natural actions into one common approach for plan­ ning? Natural actions must occur at their predicted times. The times for the execution of deliberative actions are not fixed in advance. How to determine these execution times? The examination of every possible time would lead to a com­ binatorial explosion and is, in general, not possible for time of sort REAL. One general solution, which reduces the search space to a minimum and still yields answers for all possible domains, is to use qualitative instead of quantitative infor­ mation. We only consider periods of time in our approach. There we discriminate three time intervals for a deliberative action wrt. the next expected natural action(s): Firstly, the deliberative action can be postponed to the next plan step and the (possible set of) natural action(s) is executed. Secondly, the deliberative action is performed before all natural actions which are expected next. Finally, the deliberative action and the natural actions are joined together to a new concurrent action. The predicate Exec( z1 , s1 , z2 , s2 , depth) encodes the recursive planner for a plan with depth steps integrating de­ liberative and natural actions into one method. The computed plan leads from state z1 and situation s 1 to the new state z2 and the new situation s2 . The predicate is implemented as

exec(Zl,Sl,Zl,Sl,O).

exec(Zl,Sl,Z2,S2,Depth) Depth>O, NextNatActions(C,T,Z), ( {Tl=T}, Cl=C; action(A), poss(A,TA,Zl), holds(starttime(TO) ,Zl), {TA>=TO}, ({TA<T, Tl=TA}, Cl=[A]; {TA=T, Tl=T}, append([A] ,C,Cl))), res(Zl,Sl,Cl,Tl,Z3,S3), Depthl is Depth-1, exec(Z3,S3,Z2,S2,Depthl).

where the predicate Action( a) defines the action a to be de­ liberative and the auxiliary built-in predicate Append appends two list. For our example domain, the predicate Action is en­ coded by the fact action (gobyship (_)). To ensure that the time never goes backward, the execution time TA of the deliberative action is constrained in an appropriate way.

Reasoning with time constraints instead of real time ren­ ders planning efficient. Using this plan method we are left with only three choices regarding the execution time of a de­ liberative action. Furthermore, the order of these choices, which represents a kind of heuristic, can be adjusted to the concrete domain at hand. Only after a plan, where the con­ straint solution lies in the appropriate time intervals, has been computed, a concrete time for the execution of the actions is fixed and the actions are executed.

To complete our planning method, we include the follow­ ing definition of the predicate Goal( z ) denoting the goal state z,

goal(Z) : - knows(at(3,2, ),Z).

where the goal in our example scenario is that the barge is situated at the harbor in cell (3, 2) (see also Fig. 1).

Given the predicate Goal, we define a recursive predicate Ida(zo, so, z, s, n) representing the sequence of actions s which leads from the initial state z0 in the initial situation so to the goal state z in n steps. This predicate implements the iterative deepening algorithm, which is optimal and complete [Russell and Norvig, 1995]. It is encoded as follows:

ida(ZO,SO,Z,S,N) :- exec(ZO,SO,Z,S,N), goal(Z); Nl is N+l, findplan(ZO,SO,Z,S,Nl).

The precondition axiom for the action GoByShip is speci­ fied in the following way:

poss(gobyship(D) ,T,Z) :- knows_val([X,Y] ,at(X,Y, ) ,Z), directions(X,Y,DL), member(D,DL) adjacent(X,Y,D,Xl,Yl), (lockplace(L,Xl,Yl), knows_val([L,W,TO] ,tide(L,W,TO) ,Z), (W=high; W=low, duration(L,low,TD), {T>=TO+TD})); not (lockplace(L,Xl,Yl)).

That is, after having determined the current location, the aux­ iliary predicate Directions(x, y , dl) delivers a list of possi­ ble directions for the cell ( x, y) and the standard predicate Member selects one direction d. Afterwards, with the help of the auxiliary predicate LockP!ace(l, x, y) , denoting the oc­ currence of a lock l at cell (x, y), the adjacent cell (x1 , y1) is searched for a lock. If there is none, the action is possi­ ble without further constraints for the execution time t. In the other case, the water level at the lock must be high or the action has to be executed after the disappearance of the low tide. Specifying the preconditions for the actions GoByShip and TurnTide as given above and in Section 2, respectively, fulfills the general condition for the possibility to perform a concurrent action as given in Section 3.

Consider now, for example, all specified FLUX clauses to­ gether with suitably specified facts for the example domain and the following query:

?-init(ZO), ida(ZO,sO,Z,S,l).

Our extended FLUX system then generates a plan with four steps and yields the following substitutions and linear con­ straints:

Z = [start(TA_2) ,at(3,2,TA_2) ,tide(lock3, high,4.0) ,tide(lockl,low,4 . 0), tide(lock2,high,O . O) l_l S do([gobyship(2)], do([gobyship(l), turntide(lockl,low) ,turntide(lock3,high)], do([gobyship(2) ,turntide(lock3,low)], do([gobyship(3)] ,sO,TA_l) ,2 . 0) ,4 . 0) ,TA_2) Linear constraints: TA_l>=l.O, TA_l <2. 0 TA_2>=5.0, TA_2<6.0

The above sequence of actions s constitutes a solution to our planning problem given in Fig. 1. It is not yet completely specified. Rather, the execution times of some deliberative actions are given as time intervals. The reader may also notice that some deliberative actions are planned simultaneously to­ gether with natural actions. Finally, we can apply the built-in predicate Minimize(t), which tries to find a minimal solution for a constraint variable t, to the above linear constraints and get the following:

5 Discussion

We have presented an extension to FLUX for domains involv­ ing continuous change and where actions occur concurrently. Our method is based on the theoretic solution in the Fluent Calculus [Thielscher, 200la].

Our extension allows for the generation of plans includ­ ing both, deliberative and natural actions. If necessary, the system generates and executes concurrent actions, i.e., where two or more single actions are performed simultaneously. In order to plan efficiently, our FLUX program computes with time intervals instead of single time points using the paradigm of constraint logic programming. We have illustrated how this method can be successfully applied to example domains like the waterway scenario. Additionally, our approach can easily be applied, with only minor modifications, to more complex domains involving, for example, compound concur­ rent actions which produce synergic effects.

Other high-level programming languages for reasoning about action and change, like GOLOG or the robot control language, have not yet an approach to integrate both, delib­ erative and natural actions in a common system to generate plans. The robot control language [Shanahan and Witkowski, 2000] does not have the notion of a natural action. The systems based on GOLOG either accommodate only natu­ ral actions [Reiter, 2001] or handle only deliberative actions [Grosskreutz and Lakemeyer, 2000] in domains involving concurrency and continuous change.

The extension to domains involving uncertainty about the occurrence of a natural action has not been tackled in this paper. An approach to this problem could be the use of con­ ditional planning. Conditional plans based on a generalized concept of plan skeletons as search heuristics have been in­ corporated into FLUX [Thielscher, 200lb]. To use condi­ tional plans as a method to accommodate such domains is an important aspect of future work.

Acknowledgments

I want to thank my supervisor Michael Thielscher, Olaf Perner and all members of the FLUX Group at Technische Universitiit Dresden for many fruitful discussions about this work. Three anonymous reviewers provided helpful com­ ments on this article for which I am grateful.