Assumption-Based Planning with Sensing via Contingent Planning Pamela Calvo and Jorge A. Baier Departamento de Ciencia de la Computación Pontificia Universidad Católica de Chile Santiago, Chile Abstract Assumption-based planning (ABP) [Davis-Mendelow et al., 2013] is a recently proposed approach to planning with Assumption-based planning (ABP) is a recently uncertainty in which a solution plan is composed both by a proposed alternative to conformant planning. Like course of action and a number of assumptions about the states conformant planning, it is designed for domains in visited during execution. For example, an ABP plan could which the initial state is uncertain, and in which assume that the subway is operational and return a plan con- actions are deterministic. Unlike conformant plan- sisting of taking the subway home. Assumptions allow the ning, an ABP plan may make commonsensical as- planning system to explore a wider range of plans, with the sumptions about the initial state, which may re- potential of returning a simple plan subject to a number of sult in simpler, easier-to-communicate plans that assumptions that are compatible with common sense. ABP achieve the goal provided such assumptions hold. may be more applicable than contingent planning in some In this paper we extend the ABP paradigm to do- applications in which uncertainties of the world are not un- mains with sensing. We propose a polynomial com- der the control of the planning agent. For example, imagine pilation of ABP into an extension of conditional a situation in which an autonomous rover is unaware of the planning supporting negation as failure in action truth value of a certain fluent f but cannot observe or affect preconditions. We show that extending DNF, a its truth value by performing any action. Imagine further that well known conditional planner, with negation as this prevents the rover from building any plan that achieves failure, is fairly easy. In our theoretical analy- the goal. In these cases, ABP, unlike other frameworks, pro- sis, we prove that our compilation is polynomial, vides a way of building a plan which will depend on assuming sound, and complete. In our experimental evalu- f or ¬f at a certain state during execution. Whether or not ation we use DNF’s extension and compare with such an assumption is reasonable can be assessed later by a existing, non-polynomial compilations of ABP to human expert, or achieved by other agents, if feasible. conditional planning, showing that in many do- Davis-Mendelow et al.’s approach to ABP is limited to mains conditional planners are able to solve in- generating plans for unobservable environments. In this pa- stances that could be not solved before. per, we provide a new definition of ABP that incorporates sensing actions. We formalize assumption-based planning 1 Introduction with sensing (APBS) as an extension of conformant planning Human beings can plan in the presence of high levels of un- with deterministic actions. We prove that ABPS is not harder certainty with remarkable ease. Arguably, the plans they con- than contingent planning: indeed it is 2-EXP-complete. Fur- struct do not always account for all possible contingencies; thermore, we show how to compile ABPS into a variant of much to the contrary, they make many assumptions about the contingent planning in which action preconditions may con- state of affairs of the world based on commonsensical criteria. tain atoms negated under the negation as failure semantics. These plans tend to be effective, regardless of how many as- We show that negation as failure in preconditions is a feature sumptions have been made. For example, when planning our that does not make the task of deciding plan existence harder way home or a trip, we hardly ever build contingency plans in terms of computational complexity. In addition, it allows for cases in which the city’s taxi drivers are on strike and both us to propose a polynomial-time translation. This property is your car and public transit fail to work altogether. important and was not enjoyed by Davis-Mendelow et al.’s In contrast, much of the standard AI machinery developed compilation of ABP to classical planning. to-date for the problem of planning in the presence of uncer- We show that implementing negation as failure into the tainty has focused on the construction of plans that achieve state-of-the-art contingent planner DNF [To et al., 2011] in- a goal no matter what is the initial state of the world. While volves the addition of only a handful of lines of code, suggest- this is desirable in some domains, in many applications one ing that incorporating such a feature to other planners may be desires a plan that is easy to understand and easy to commu- just as easy. nicate. In our experimental evaluation, we compare to Davis- Mendelow et al.’s approach in unobservable domains. Re- For every action a, function prec(a), the precondition of sults are mixed. While their compilation to classical plan- a, returns a subset of L(F ). Furthermore, eff (a), the effect ning allows exploiting highly optimized classical planners, of a, is a set of contingent effects, each of the form C → `, in some domains their compilation excels possibly because where C ⊆ L(F ) and ` ∈ L(F ). DNF’s heuristic is very weak. In other domains, however, Example Imagine a situation in which we want to obtain a Davis-Mendelow et al.’s worst-case exponential-time trans- plan to go from home to the office. There are three ways of lation either runs out of memory or generates an input that is getting there: walking, by bus, or by subway. The actions are not handled well by the back-end planner, allowing DNF to bus(A, B), which takes a bus from A to B, subway(A, B), solve problems that cannot be solved by Davis-Mendelow et which takes the subway from A to B, and walk(A, B) which, al.’s approach. by foot, gets you from A to B. Action bus(A, B) is ex- An approach to finding small plans related to ours is ecutable when there is no driver strike (denoted by fluent Meuleau and Smith’s [2003], which focuses on computing strike). Action walk(A, B) can be performed if the agent best possible plans with at most k contingencies. As pre- is at A. Formally, we define these actions as follows. For sented, it does not consider the notion of assumptions. Our every x ∈ {home, subwayH}: approach is related but very different from Brafman and Shani’s [2012], which implicitly makes assumptions in states prec(bus(x, office)) = {¬strike, at(x)} based on probability criteria. Our approach does not need eff (bus(x, office)) = {¬at(x), at(office)} probabilities. As motivated above, assumptions do not have to be necessarily facts that are usually true, yet they may be For every x, y ∈ {home, office, subwayH, subwayO} such facts that are sometimes necessary to find a plan or to find a that x 6= y, we define compact plan, regardless of their likelihood. prec(walk(x, y)) = {at(x)} eff (walk(x, y)) = {¬at(x), at(y)} 2 Preliminaries For every x, y ∈ {subwayH, subwayO}, where x 6= y, The following sections describe the background necessary for we define the rest of the paper. prec(subway(x, y)) = {operational, at(x)} 2.1 Propositional Logic Preliminaries eff (subway(x, y)) = {¬at(x), at(y)} Given a set of propositions (or fluents) F , the set of literals of  F , L(F ), is defined as L(F ) = F ∪ {¬p | p ∈ F }. A clause is a disjunction of literals. A planning state for P is a set of literals over F that is both Boolean formulae over F —denoted by B(F )— are defined logically complete and consistent. An action a is applicable inductively as usual, and may contain constants > and ⊥, in a planning state s iff s |= prec(a). We denote by δ(s, a) which are used to denote “true”and “false”, and standard con- the state that results from applying a in s. Formally, nectives (∧, ¬). We assume the |= relation to be defined in the standard way; that is, a formula ϕ is entailed by a set δ(s, a) =(s \ {` | C → ` ∈ eff (a), s |= C})∪ of clauses C, denoted by C |= ϕ, iff all models of C satisfy {` | C → ` ∈ eff (a), s |= C} ϕ. If F is a set of propositions, we define the set of liter- if s ∈ F and a is applicable in s; otherwise, δ(s, a) is un- als with negation as failure as Lnot (F ) = L(F ) ∪ {not p | defined. It is convenient to extend the definition of δ for p ∈ L(F )}. If p ∈ F , and C is a set of clauses, we say that sequences of actions. If α is a sequence of actions and a C |= not p iff C 6|= p. Finally, we say C |= L if C |= `, for is an action, we define δ(s, αa) as δ(δ(s, α), a) if δ(s, α) every ` ∈ L. is defined. Furthermore, if α is the empty sequence, then A set of literals over F is said to be logically complete if it δ(s, α) = s. contains either p or ¬p, for every p ∈ F . If p ∈ F , then ¬p is the complement of p and p is the complement of ¬p. If ` is a Definition 2 (Execution Trace) Given a planning problem literal, we denote its complement by `. A set of literals over P = (F, O, I, G) and a sequence of actions α = a0 a1 . . . an , F is consistent if it does not contain a pair of complementary we say that α induces an execution trace σ = s0 s1 · · · sk iff literals. If S is a set of sets of literals, then we say that S |= L, 1. I |= s0 , and s0 is a planning state. iff for every s ∈ S, it holds that s |= L. 2. δ(si , ai ) = si+1 , for all i < k, and 2.2 Contingent and Assumption-Based Plans 3. either k = n+1 or k < n+1 and δ(sk , ak ) is undefined. Below we follow closely the definitions of Davis-Mendelow Definition 3 (Successful Execution Trace) An execution et al. [2013] for conformant plan and assumption-based plan. trace σ for α is successful iff |σ| = |α| + 1. Definition 1 (Planning Problem) A planning problem is a Definition 4 (Leads to) An execution trace σ = s0 · · · sk tuple P = (F, O, I, G) where F is a finite set of fluents, O is leads to (goal formula) G, iff sk |= G. a finite set of actions, I is a set of clauses over F , defining the Definition 5 (Conformant Plan) A sequence of actions α is set of possible initial states, and G is a boolean formula over a conformant plan for P = (F, O, I, G) iff every execution symbols in F , that defines a goal condition. trace of α is successful and leads to G. Definition 6 (Conforms to) An execution trace guage for variable prog of the following BNF grammar. σ = s1 · · · sk conforms to a sequence of boolean for- mulae ρ = h1 · · · hn with k ≤ n iff si |= hi , for every act ::= a (for every a ∈ Ow ) i ∈ {1, . . . , k}. obs ::= o (for every o ∈ Os ) Finally, each of the execution traces of α that conform to prog ::= ε (the empty program) ρ must actually lead to the goal. A formal definition of an prog ::= act · prog (for a ∈ Ow ) assumption-based plan follows. prog ::= branch(obs, prog, prog) (for o ∈ Os ) Definition 7 (Assumption-Based Plan) The pair (ρ, α), Just like any action sequence induces an execution trace of where α is a sequence of k actions, and ρ is a sequence of states, so do contingent plans. Providing a formal definition k + 1 boolean formulae over T is an assumption-based plan for these traces will ultimately allow us to give a formal def- for P = (F, O, I, G, T ) iff any execution trace of α that inition for a plan. First, however, we need an intermediate conforms to ρ is successful and leads to G, and furthermore step: we need to define what does it mean to execute a pro- at least one such execution trace exists. gram. We do this by first defining the notion of configuration. Given a contingent planning problem, a configuration is a Example (continued) Assume we define the initial state pair (S, p), where S is a set of planning states—also referred as I = {at(home)}, and the goal as G = at(office). Note to below as belief state—and p is a program. Now we define this means that it is not known whether the subway is opera- the relation which can be intuitively related to atomic ex- tional or whether their is a bus strike. Then the only confor- ecution steps. More precisely, if (S, p) (S 0 , p0 ) then the mant plan for the problem is given by walk(home, office). execution of one atomic step of p in S leads to state S 0 , with However, if operational is an assumable fluent, then p0 remaining to be executed. Formally, (ρ1 , α1 ) is an ABP plan, with: 1. (S, a · p) (S 0 , p), for every a ∈ Ow , if and only if S |= prec(a) and S 0 = {δ(s, a) | s ∈ S}. ρ1 = operational, >, >, > α1 = walk(home, subwayH), 2. (S, branch(o, p1 , p2 )) (S 0 , p), for every o ∈ Os , if and only if S |= prec(o), and either S 0 = T and p = p1 subway(subwayH, subwayO), or S 0 = S \ T and p = p2 , where T = {s ∈ S | s |= walk(subwayO, office) obs(o)}. Now we formally define a trace of execution for a program. Finally, if strike is assumable, then (ρ2 , α2 ) is also an ABP plan, with: Definition 9 (Trace of Configurations) Given a contingent planning problem (F, Ow , Os , I, G), and a program p, we ρ2 = ¬strike, > say p induces an execution trace c0 c1 . . . cn iff: α2 = bus(home, office) 1. c0 = (S0 , p), where S0 = {s | s is a state and I |= s}.  2. ci−1 ci , for every i ∈ {1, . . . , n}. 3. there is no c such that cn c. 2.3 Contingent Planning As before successful traces are those that involved execut- ing every single action of the program. Contingent planning extends conformant planning by allow- Definition 10 (Successful Trace of Configurations) A ing the agent to observe the world via sensing actions. As trace of configurations c1 . . . cn is successful if and only if such, we assume the set of action operators is partitioned into cn = (S, ε), for some s. two (disjoint) sets Ow and Os , which contain, respectively, the actions that modify the world and sensing actions. Definition 11 (Leads to, for Configurations) A trace of Formally a contingent planning problem is characterized configurations c0 c1 . . . cn leads to G if cn = (S, p) and by a tuple (F, Ow , Os , I, G), where F , I, and G are defined S |= G. as above. Likewise, functions prec and eff return the precon- Now we are ready to define contingent plans. dition and effect of each action a in Ow . For every sensing Definition 12 (Contingent Plan) A contingent program p is action o ∈ Os , we associate a precondition prec(o) specify- a plan for P = (F, Ow , Os , I, G) if and only if every trace of ing the conditions under which o is executable, and we asso- configurations of p over P is successful and leads to G. ciate an observation obs(o), which is a Boolean formula over F specifying the condition that is sensed by o. Example (continued) Assume the initial state and goal In general, contingent plans look like programs with if- state are defined as above, and that in addition we have the then-else conditions. In the formalization, we focus on tree- following sensing actions to sense whether or not the subway like programs to simplify our definitions. Tree-like programs is operational. For each x ∈ {stnO, stnH}: are as expressive as programs with if-then-else constructs. prec(senseOp(x)) = {at(x)} Definition 8 (Contingent Program) A contingent program for contingent planning task (F, Ow , Os , I, G) is the lan- obs(senseOp(x)) = operational In addition to the plan walk(home, office), we have the con- Proof: Follows from the fact that contingent planning, a tingent plan: 2-EXP-complete problem is a particular case of contingent planning with negation as failure.  walk(home, stnH) · branch(senseOp(stnH), p1 , p2 ) where 3.2 Implementing Negation as Failure in DNF Now we turn into a more practical aspect of negation as fail- p1 = subway(stnH, stnO) · walk(stnO, office), ure: its implementation in a state-of-the-art system, namely, and where p2 may describe various plans that involve waking. DNF [To et al., 2011]. Important is the fact that p2 may not consider taking the bus, As its name suggests, DNF represents belief states using since fluent strike is unknown, unobservable, and its truth disjunctive normal form; that is, as disjunctions of literal con- value cannot be changed by the agent.  junctions. Internally, belief states are represented as sets of conjunctions. Algorithm 1 shows a pseudocode for the C++ routine actually used in DNF to check the applicability of an 3 Negation as Failure in Preconditions action. Essentially, it checks that every literal in prec(a) is Our translation uses a version of contingent planning that re- in every conjunction c of the belief state cs. Extending Algo- quires negation as failure (NAF) in action preconditions. This is not standard in contingent planning systems [Hoffmann and Algorithm 1: DNF’s precondition evaluation Brafman, 2005; Albore et al., 2009; To et al., 2011]. Never- Input: An action a, a set of conjunctions of literals cs theless, as we show in this section, it is easy to extend a state- 1 for each conjunction c in cs do of-the-art contingent planner with NAF in preconditions. In 2 for each ` ∈ prec(a) do the rest of the section, we first show that adding support for 3 if ` 6∈ c then NAF in preconditions does not change the complexity class 4 return false of contingent planning. Then, we show how to incorporate 5 return true this feature to a state-of-the-art planner. 3.1 A Note on Complexity rithm 1 to support negation as failure is extremely easy. Algo- NAF in preconditions is related to modal logic modalities in rithm 2 shows how we did it in our implementation. The main preconditions [Bonet, 2010]. Bonet proved that adding modal difference is in Lines 2–8, which will declare that cs |= not ` operators like p (“always p”) and ♦p (“possibly p”) to pre- if cs contains a conjunction in which ` does not appear. conditions does not change the complexity class of contin- gent planning, for the more general case of finding an uncon- Algorithm 2: Precondition evaluation with NAF strained branching plan (Theorem 2, Bonet 2010). We can do Input: An action a, a set of conjunctions of literals cs likewise for the case of NAF. 1 exec ← true In short, our proof follows from three facts. First, plan 2 for each “not `” in prec(a) do existence for a contingent planning problem is a 2-EXP- 3 for each conjunction c in cs do complete decision problem [Rintanen, 2012]. Second, 2- 4 if ` 6∈ c then EXP is equivalent to AEXPSPACE; that is, the class of prob- 5 exec ← true 6 break lems that can be decided with an alternating Turing machine (ATM) that uses exponential space. This means there exists 7 if not exec then an exponential-space ATM, say, M , that decides existence of 8 return false a contingent plan. Third, we can modify M to now decide 9 for each conjunction c in cs do existence of a plan for a contingent problem with NAF pre- 10 for each ` ∈ prec(a) ∩ L(F ) do conditions, without requiring more memory. Indeed, such a 11 if ` 6∈ c then machine is a slight modification of M . The only modifica- 12 return false tion is the module in which preconditions are checked. For contingent planning, for every ` ∈ prec(a) we need to check 13 return true S |= `, where the size of S may be exponential in the size of the problem (|S| is worst-case the set of all possible states). Note that S |= ` does not require more than exponential space 4 Assumption-based Planning with Sensing since it can be done in non-deterministic polynomial time in |S| + |`|. Adding support for NAF requires checking S 6|= `, Now we extend the definition of ABP to the case of sens- which clearly can also be done in exponential space in the ing. At the formal level an ABPS instance is simply a tu- size of the problem. The rest of the M is left with no further ple (F, Ow , Os , I, G, T ), where all elements are defined as in modifications. Formally, conformant planning, and T ⊆ F are the assumable fluents. As with regular ABP, we want to allow an assumption prior Theorem 1 Contingent planning with NAF in preconditions to each action execution. Plans for an ABPS problem look is in 2-EXP. like contingent programs where each world action or sense Corollary 1 Contingent planning with NAF in preconditions action is accompanied with an assumption. We call these pro- is 2-EXP-complete. grams assumption-based contingent programs. Definition 13 (Assumption-based Contingent Program) Theorem 2 Let P = (F, O, I, G, T ) and P 0 = An assumption-based contingent program is any element (F, O, ∅, I, G, T ) be respectively ABP and ABPS problems. of the language defined by the prog variable of the BNF Then (h0 . . . hn >, a0 . . . an ) is a plan for P if and only if grammar of Definition 8, when replacing the rules for act [h0 , a0 ] · · · [hn , an ] is a plan for P 0 . and obs by the following: Finally, ABPS is in the same complexity class as contin- act ::= [h, a] (for every a ∈ Ow , h ∈ B(F )) gent planning. obs ::= [h, o] (for every o ∈ Os , h ∈ B(F )) Theorem 3 Deciding existence of an ABPS plan is 2-EXP- Now we adapt the definitions for contingent planning to complete. consider the effect of an assumption. The main difference Proof: Follows from the correctness of the translation we between ABPS and contingent planning is that assumptions propose in the following section.  filter out some of the states in belief states; specifically, those states that are inconsistent with the assumption. We only re- quire the goal to hold in the worlds that have not been filtered 5 ABPS via Contingent Planning out. An additional requirement is that assumptions cannot fil- ter out all states of the belief state. This is needed for two Our translation takes an ABPS problem P = reasons. First, we do not want to allow assumptions that are (F, Ow , Os , I, G, T ) as input and produces a con- inconsistent with all states in the belief state. Second, by defi- tingent planning problem with NAF preconditions, nition, every action is executable in an empty belief state, and P 0 = (F 0 , Ow 0 , Os0 , I 0 , G). The assumable fluents in T every formula is satisfiable in an empty belief state. As such, are translated into a set of world actions and sensing actions if we don’t prevent empty belief states to arise, we would ob- that, by being applied in a certain order, will have the same tain plans with an arbitrary number of spurious actions. effect of making an assumption about the current state of the We formalize the notion of filter with the following defini- world. Notice that G is the only set that remains unmodified. tion Filter(S, h) = {s ∈ S | s |= h}. Relation for ABPS To understand the intuition underlying our translation, we is defined in the following way. first observe that assumptions can be related to sensing ac- 1. (S, [h, a] · p) (S 0 , p), for every a ∈ Ow , if and only tions. Indeed, a sensing action o will, in one branch, filter out if Sh = Filter(S, h) is nonempty, Sh |= prec(a) and from the belief those states inconsistent with obs(o) whereas S 0 = {δ(s, a) | s ∈ Sh }. in the other branch those states consistent with the observa- tion are filtered out. For sensing actions a plan is needed for 2. (S, branch([h, o], p1 , p2 )) (S 0 , p), for every o ∈ Os , both branches. For assumptions, on the other hand, we are if and only if Sh = Filter(S, h) is nonempty, Sh |= only interested in the belief state that has filtered out those prec(o), and either S 0 = T and p = p1 or S 0 = S \ T states inconsistent with the assumption. and p = p2 , where T = {s ∈ Sh | s |= obs(o)}. One way of mapping an assumption into a sensing action Definition 14 (Assumption-based Plan with Sensing) would be to have a sensing action capable of performing both A assumption-based contingent program p is a plan for an observation and a change in the world. If t is an assumable P = (F, Ow , Os , I, G, T ) if and only if every trace of fluent, one would create a sensing action whose observation is configurations of p over P is successful and leads to G. t. In addition, we would add a conditional effect ¬t → g, for every g in the goal G.1 Such a sensing action would imme- Example (continued) Suppose, like above, that diately “solve the problem” in the branch that is inconsistent operational can be sensed by action senseOp, but that with t. Unfortunately, the current model for contingent plan- strike can be assumed but cannot be sensed by any action. ning that planning system support does not handle conditional Then the following is an ABPS plan for the resulting prob- effects in sensing actions. lem. What our compilation does is to model assumptions with 4 distinguished actions for each assumable fluent. First, and [>, walk(home, stnH)]· foremost, there is a sensing action whose observation is the [>, branch(senseOp(stnH), p1 , p2 )] assumable fluent; its role is to filter out states that are con- where sistent/inconsistent with the assumption. Second, there is a world action (assumme(t)) that intuitively starts “assump- p1 = [>, subway(stnH, stnO)] · [>, walk(stnO, office)], tion mode”. An effect of this action is the fluent lock, which and where p2 can now consider an action that takes the does not allow other world actions to be performed as soon bus, while assuming there is no strike. Indeed, p2 may be as it becomes true. Then there are actions done and unlock. [¬strike, bus(stnH, office)].  Both of them can only be performed after the sensing action. Action unlock, as the name implies, makes lock false, while Note that our definition does not need to define a notion action done, makes the goal true. of conformity (cf. Definition 7), because we ensure a plan The details of the compilation are as follows. conforms to the assumptions by applying the Filter function. In the absence of sensing actions, Definitions 14 and 6 are 1 We assume here the goal is a set of literals to simplify the pre- equivalent, for those plans that do not assume anything about sentation, but the compilation can be adapted if G is a Boolean for- the final state. mula. Fluents The set of fluents of the compiled problem is de- done is the one responsible for finishing off this branch. fined as: It does this by adding all goal fluents. F 0 = F ∪ {lock} ∪ FA , prec(done(t)) = {lock, ¬t, assuming(t)} where fluent lock resembles an “assumption mode” in which eff (done(t)) = {g | g ∈ G} regular actions from the original problem (those in Ow or Os ) are not executable. When lock is true, only assumption- 4. Finally, unlock(t) removes the lock fluent to allow the related actions are applicable. Consequently, when it is false, planner to continue using world and sensing actions (by only actions that belong exclusively to Ow or Os are appli- removing lock) in the branch that is consistent with the cable. Finally, FA = {assuming(t) | t ∈ T }. Fluent assumption (i.e., in which t holds). Its definition follows. assuming(t) intuitively indicates that “t is being assumed”. Its dynamic should be clear after reading how actions are de- prec(unlock(t)) = {lock, t, assuming(t)} fined. eff (unlock(t)) = {¬lock, ¬assuming(t)} Actions All actions in P are “copied into” P 0 , but their precondition is modified to include lock. Formally, Initial State The new initial state of the problem is: 0 Ow = {â | a ∈ Ow } ∪ Aw I 0 = I ∪ {¬lock} ∪ {¬f | f ∈ Fa }. Os0 = {â | a ∈ Os } ∪ As 6 Empirical Evaluation We modify the preconditions of actions in Ow ∪Os to include the lock fluent. Formally, A note on DNF’s performance In earlier stages of the ex- perimental phase, we noticed that DNF was prone to choose prec(â) = prec(a) ∪ {¬lock}, for each a ∈ Ow ∪ Os actions that led to just one belief state as a result, over than those that generated a new one (like sensing and assump- Below we define Aw and As constructively, assuming they tion actions). This was because the PrAO* algorithm [To et are initially empty. For each t ∈ T that assumes a literal p to al., 2011] attempts to minimize the branching in the returned be true, we add: plans, which is not good if we want to generate plans with as- 1. An action assume(t) ∈ Aw . This action initiates the sumptions. To minimize this effect, we modified the heuris- process of making an assumption. tic modified the heuristic to increase likelihood of choosing nodes that come from a branching action. We called this vari- prec(assume(t)) = {¬lock, not t, not ¬t} ant DNF-ABPSA . eff (assume(t)) = {assuming(t), lock} We designed two sets of experiments. In the first, we compared with our ABP predecessor, A0+Lama [Davis- Since an assumption will be reduced to several world Mendelow et al., 2013] in problems that do not have sens- and sensing actions applied in an specific order, the flu- ing actions. We evalueated over two of the four domains that ent assuming(t) is needed to ensure the correct course were evaluated by Davis-Mendelow et al. [2013]: alogistics a of action execution. Note that this is the action that re- modified version of logistics in which assumptions are needed quires NAF in preconditions. Essentially the precondi- to get to the goal, and the well-known coins domain, which tion is saying that we can only assume a fluent t if neither included assumption actions that allow assuming the initial t nor ¬t is true; in other words, we can assume t if t is location of coins. Results are shown Table 1. unknown. In our second set of experiments, the objective was to com- 2. A sensing action assume-s(t) ∈ As . This is the next pare a contingent planner with an ABPS planner on the same action to be applied. It will split the current belief state problem, which the conformant planner does not, but the in two: one containing states where t is true and one intent here was to evaluate difference on performance and containing the remaining states, where ¬t is true. When on plan size. Of course, the ABP planner has access to a making an assumption only the branch where t is true is set of assumption actions. We ran DNF (without assump- relevant, and so two more actions are needed in order to tions), and the two versions of DNF that used our transla- finish the process of making an assumption. This will tion (DNF-ABPS and DNF-ABPSA ) over modified confor- be explained in the following two steps. Before that, we mant domains dispose and push-to. In these domains we are specify the preconditions for this action. can assume the position of the objects. Finally, we created medical-allergy inspired by IPC’s medical. In this domain prec(assume-s(t)) = {assuming(t), lock} there is a fixed number of illnesses and medicines that can cure each. Unfortunately, treatments may cause an allergic This action does not have any effects besides the branch- reaction, not deadly, but undesired. To determine whether or ing due to its sensing nature. not a person is allergic, a number of actions that have to be 3. An action done ∈ Aw . The previously described sens- performed. Furthermore, if the person turns out to be aller- ing action will branch the plan into two paths. Since we gic to a medicine, there is an alternative medicine available, are making an assumption, there is one branch which but it has to be imported (this was simulated by a number of is not needed anymore and therefore has to be pruned actions). In this problem one can assume that a patient is not so the plan does not continue expanding it. The action allergic. Results for all three domains are shown in Table 2. A0 + Lama DNF-ABPS DNF-ABPSA Problem Total T Sol Len #Ass Trans T Plan T Total T Sol Len #Ass Plan T Total T Sol Len #Ass alog-01 445,31 35 2 0,278 32,526 32,804 112 2 131,230 131.508 109 2 alog-02 0,02 36 3 1,145 TO - - - TO - - - alog-04 0,03 36 3 83,753s TO - - - TO - - - alog-06 1,45 41 4 0,374 TO - - - 1470,01 1470,384 568 5 alog-10 0,02 33 4 0,294 1739,744 1740,038 132 5 21,989 22,283 151 5 Coins 01 0,01 5 3 0,166 0,014 0,18 18 2 0,019 0,185 16 2 Coins 07 0,08 8 5 0,198 1,038 1,236 36 4 1,356 1,554 30 4 Coins 13 4,29 10 7 0,316 TO - - - TO - - - Coins 19 214,96 7 7 0,359 TO - - - TO - - - Coins 25 129,12 16 16 9,582 TO - - - TO - - - Coins 30 398,32 52 21 17,45 TO - - - TO - - - Table 1: T0 + Lama, DNF-ABPS y DNF-ABPSA , alogistics and coins. Times in seconds. DNF-ABPS DNF-ABPSA DNF-Cont Problem Trans T Plan T Total T Sol Len #Ass Plan T Total T Sol Len #Ass Trans T Plan T Total T Sol Len push-to-4-3 0,459 51,113 51,572 108 2 18,695 19,154 50 3 0,457 14,987 15,354 107 push-to-5-3 1,427 742,415 743,482 135 0 159,063 160,49 44 3 1,622 106,629 108.251 213 push-to-5-4 2,174 TO - - - TO - - - 2,386 TO - - push-to-5-5 3,127 TO - - - TO - - - 3,57 TO - - push-to-8-1 9,396 2,388 11,784 42 1 0,715 10,111 13 1 10,912 0,976 11.888 135 push-to-8-2 23,258 423,714 446,972 154 1 78,639 101,897 49 2 27,269 81,760 109,029 232 push-to-8-3 49,459 TO - - - TO - - - 52,007 TO - - push-to-8-10 516,833 TO - - - TO - - - 8m37.427 TO - - push-to-10-1 63,729 11,234 74,963 69 1 7,344 71,073 88 1 63,404 3.227 66,631 326 push-to-10-2 147,608 TO - - - 456,567 604,175 67 2 154,947 414.303 569,25 308 dispose-4-5 0,35 TO - - - TO - - - 0,282 TO - - dispose-7-3 2,41 TO - - - TO - - - 2,51 TO - - dispose-7-6 3,812 TO - - - TO - - - 3,331 TO - - dispose-10-1 28,765 1,427 30,192 16 1 2,22 30,985 34 1 28,903 1,853 30,756 400 dispose-10-4 32,47 TO - - - TO - - - 39,804 TO - - medical001 0,161 0,006 0,167 5 1 0,004 0,165 5 1 0,144 0,027 0,171 11 medical002 0,149 0,193 0,342 28 1 0,159 0,308 19 2 0,176 0,048 0,224 45 medical003 0,145 0,229 0,374 55 2 0,231 0,376 27 3 0,158 0,131 0,289 113 medical004 0,162 0,548 0,71 67 3 (5) 0,545 0,707 34 4 0,16 0,445 0,605 300 medical005 0,157 1,856 2,013 104 4(7) 0,365 0,522 53 5 0,155 1,191 1,346 620 Table 2: DNF-ABPS, DNF-ABPSA , and DNF-Contingent, push-to, dispose, and medical-allergy. Times in seconds. Experimental Conclusions A0, which uses LAMA would come from a domain that allows assumptions and yet [Richter et al., 2008] as a back-end planner, performs sig- puts some kind of restrictions over what assumption can be nificantly better in the alogistics domain. This is possibly performed. In future work, we would like effect on perfor- due to the fact that the DNF uses a very weak heuristic (goal mance and plan quality when varying the set of assumable counting), and does not exploit the advanced search tech- fluents in various ways. niques (like preferred operators) that are key to LAMA’s per- formance [Richter and Helmert, 2009]. 7 Summary and Future Work In the push-to domain, on the other hand, A0 cannot trans- late almost any instance, and DNF and our approach can solve We proposed an extension of ABP for domains in which sens- many of them in a couple of seconds or minutes, depending ing actions are available. We proposed a polynomial-time on the complexity of the problem. While observing the result translation of ABP problems with sensing to contingent plan- for the different versions of DNF over the push-to and dis- ning with negation as failure. Even though negation as failure pose domains, we can note, firstly that the translation time is is not a standard feature of contingent planners, we show that not significantly different when assumption actions are added. modifying one such a planner (DNF) is easy to do. Secondly, it is easy to see that the modification over DNF- In our evaluation, we confirm that using assumptions may ABPS improves its performance and balances the priority of reduce plan size. In comparison to A0, the translator of the world actions and branching actions. Hence, more assump- previous approach to ABP that does not support sensing and tions are made in plans found by DNF-ABPSA . Thirdly, ob- uses classical planners as a back end, we observe that in some serving the characteristics of the plans themselves, DNF tends cases the optimized classical planner outperforms the contin- to take a shorter time to give a solution but these solutions are gent planner we use. In other cases, however, our polynomial- the longest. DNF-ABPS obviously takes more time to find time translation seems to pay off, allowing our planner to a solution since its search space is wider and since it penal- solve instances that cannot be translated by A0. izes assumption actions, it doesn’t have a quick escape route In future work we plan to extend our experimental eval- to simplify it. In contrast, DNF-ABPSA , by doing more as- uation to more domains, and will evaluate the effect of us- sumptions, provides considerably shorter solutions. ing different sets of assumable fluents. We also will inves- Finally, in medical-allergy, when the planner has more tigate different quality objectives (e.g., smaller plans, fewer available assumptions, planning takes longer (probably due assumptions). Another line of future research is the integra- to the increasing branching factor), but solutions are shorter. tion of these types of assumptions into logic-programming Most likely, best results in both aspects, time and length, planning frameworks (e.g., Tu et al. 2007). References [Albore et al., 2009] Alexandre Albore, Héctor Palacios, and Hector Geffner. A translation-based approach to contin- gent planning. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI), pages 1623–1628, Pasadena, CA, 2009. [Bonet, 2010] Blai Bonet. Conformant plans and beyond: Principles and complexity. Artificial Intelligence, 174(3- 4):245–269, 2010. [Brafman and Shani, 2012] Ronen I. Brafman and Guy Shani. Replanning in domains with partial information and sensing actions. Journal of Artificial Intelligence Re- search, 45:565–600, 2012. [Davis-Mendelow et al., 2013] Sammy Davis-Mendelow, Jorge A. Baier, and Sheila A. McIlraith. Assumption- based planning: Generating plans and explanations under incomplete knowledge. In Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI), 2013. [Hoffmann and Brafman, 2005] Jörg Hoffmann and Ronen Brafman. Contingent planning via heuristic forward search with implicit belief states. In Proceedings of the 15th International Conference on Automated Planning and Scheduling (ICAPS), pages 71–80, Monterey, CA, USA, June 2005. Morgan Kaufmann. [Meuleau and Smith, 2003] Nicolas Meuleau and David E. Smith. Optimal limited contingency planning. In Pro- ceedings of the Proceedings of the 19th Conference on Un- certainty in Artificial Intelligence (UAI), pages 417–426, Acapulco, Mexico, August 2003. [Richter and Helmert, 2009] Silvia Richter and Malte Helmert. Preferred operators and deferred evaluation in satisficing planning. In Proceedings of the 19th Interna- tional Conference on Automated Planning and Scheduling (ICAPS), 2009. [Richter et al., 2008] Silvia Richter, Malte Helmert, and Matthias Westphal. Landmarks revisited. In Proceed- ings of the 23rd AAAI Conference on Artificial Intelligence (AAAI), pages 975–982, Chicago, IL, 2008. [Rintanen, 2012] Jussi Rintanen. Complexity of conditional planning under partial observability and infinite execu- tions. In Proceedings of the 20th European Conference on Artificial Intelligence (ECAI), pages 678–683, 2012. [To et al., 2011] Son Thanh To, Enrico Pontelli, and Tran Cao Son. On the effectiveness of CNF and DNF rep- resentations in contingent planning. In Proceedings of the 23rd International Joint Conference on Artificial Intelli- gence (IJCAI), pages 2033–2038, 2011. [Tu et al., 2007] Phan Huy Tu, Tran Cao Son, and Chitta Baral. Reasoning and planning with sensing actions, in- complete information, and static causal laws using answer set programming. Theory and Practice of Logic Program- ming, 7(4):377–450, 2007.