Assumption-based planning (ABP) is a recently proposed alternative to conformant planning. Like conformant planning, it is designed for domains in which the initial state is uncertain, and in which actions are deterministic. Unlike conformant planning, an ABP plan may make commonsensical assumptions about the initial state, which may result in simpler, easier-to-communicate plans that achieve the goal provided such assumptions hold. In this paper we extend the ABP paradigm to domains with sensing. We propose a polynomial compilation of ABP into an extension of conditional planning supporting negation as failure in action preconditions. We show that extending DNF, a well known conditional planner, with negation as failure, is fairly easy. In our theoretical analysis, we prove that our compilation is polynomial, sound, and complete. In our experimental evaluation we use DNF's extension and compare with existing, non-polynomial compilations of ABP to conditional planning, showing that in many domains conditional planners are able to solve instances that could be not solved before.
Assumption-based planning (ABP) [Davis-Mendelow et al., 2013] is a recently proposed approach to planning with uncertainty in which a solution plan is composed both by a course of action and a number of assumptions about the states visited during execution. For example, an ABP plan could assume that the subway is operational and return a plan consisting of taking the subway home. Assumptions allow the planning system to explore a wider range of plans, with the potential of returning a simple plan subject to a number of assumptions that are compatible with common sense. ABP may be more applicable than contingent planning in some applications in which uncertainties of the world are not under the control of the planning agent. For example, imagine a situation in which an autonomous rover is unaware of the truth value of a certain fluent f but cannot observe or affect its truth value by performing any action. Imagine further that this prevents the rover from building any plan that achieves the goal. In these cases, ABP, unlike other frameworks, provides a way of building a plan which will depend on assuming f or :f at a certain state during execution. Whether or not such an assumption is reasonable can be assessed later by a human expert, or achieved by other agents, if feasible.
Davis-Mendelow et al.’s approach to ABP is limited to generating plans for unobservable environments. In this paper, we provide a new definition of ABP that incorporates sensing actions. We formalize assumption-based planning with sensing (APBS) as an extension of conformant planning with deterministic actions. We prove that ABPS is not harder than contingent planning: indeed it is 2-EXP-complete. Furthermore, we show how to compile ABPS into a variant of contingent planning in which action preconditions may contain atoms negated under the negation as failure semantics. We show that negation as failure in preconditions is a feature that does not make the task of deciding plan existence harder in terms of computational complexity. In addition, it allows us to propose a polynomial-time translation. This property is important and was not enjoyed by Davis-Mendelow et al.’s compilation of ABP to classical planning.
We show that implementing negation as failure into the state-of-the-art contingent planner DNF [To et al., 2011] involves the addition of only a handful of lines of code, suggesting that incorporating such a feature to other planners may be just as easy.
In our experimental evaluation, we compare to DavisMendelow et al.’s approach in unobservable domains. Results are mixed. While their compilation to classical planning allows exploiting highly optimized classical planners, in some domains their compilation excels possibly because DNF’s heuristic is very weak. In other domains, however, Davis-Mendelow et al.’s worst-case exponential-time translation either runs out of memory or generates an input that is not handled well by the back-end planner, allowing DNF to solve problems that cannot be solved by Davis-Mendelow et al.’s approach.
An approach to finding small plans related to ours is Meuleau and Smith’s [2003], which focuses on computing best possible plans with at most k contingencies. As presented, it does not consider the notion of assumptions. Our approach is related but very different from Brafman and Shani’s [2012], which implicitly makes assumptions in states based on probability criteria. Our approach does not need probabilities. As motivated above, assumptions do not have to be necessarily facts that are usually true, yet they may be facts that are sometimes necessary to find a plan or to find a compact plan, regardless of their likelihood. 2
The following sections describe the background necessary for the rest of the paper. 2.1
Given a set of propositions (or fluents) F , the set of literals of F , L(F ), is defined as L(F ) = F [ f:p j p 2 F g. A clause is a disjunction of literals.
Boolean formulae over F —denoted by B(F )— are defined inductively as usual, and may contain constants > and ?, which are used to denote “true”and “false”, and standard connectives ( , :). We assume the j= relation to be defined in ^ the standard way; that is, a formula ' is entailed by a set of clauses C, denoted by C j= ', iff all models of C satisfy '. If F is a set of propositions, we define the set of literals with negation as failure as Lnot (F ) = L(F ) [ fnot p j p 2 L(F )g. If p 2 F , and C is a set of clauses, we say that C j= not p iff C 6j= p. Finally, we say C j= L if C j= `, for every ` 2 L.
A set of literals over F is said to be logically complete if it contains either p or :p, for every p 2 F . If p 2 F , then :p is the complement of p and p is the complement of :p. If ` is a literal, we denote its complement by `. A set of literals over F is consistent if it does not contain a pair of complementary literals. If S is a set of sets of literals, then we say that S j= L, iff for every s 2 S, it holds that s j= L. 2.2
Below we follow closely the definitions of Davis-Mendelow et al. [2013] for conformant plan and assumption-based plan.
tuple P = (F; O; I; G) where F is a finite set of fluents, O is a finite set of actions, I is a set of clauses over F , defining the set of possible initial states, and G is a boolean formula over symbols in F , that defines a goal condition.
For every action a, function prec(a), the precondition of a, returns a subset of L(F ). Furthermore, e (a), the effect of a, is a set of contingent effects, each of the form C ! `, where C L(F ) and ` 2 L(F ).
Example Imagine a situation in which we want to obtain a plan to go from home to the office. There are three ways of getting there: walking, by bus, or by subway. The actions are bus(A; B), which takes a bus from A to B, subway(A; B), which takes the subway from A to B, and walk(A; B) which, by foot, gets you from A to B. Action bus(A; B) is executable when there is no driver strike (denoted by fluent strike). Action walk(A; B) can be performed if the agent is at A. Formally, we define these actions as follows. For every x 2 fhome; subwayH g: prec(bus(x; o ce)) = f:strike; at(x)g
e (bus(x; o ce)) = f:at(x); at(o ce)g For every x; y 2 fhome; o ce; subwayH; subwayOg such that x 6= y, we define prec(walk(x; y)) = fat(x)g
e (walk(x; y)) = f:at(x); at(y)g
For every x; y 2 fsubwayH; subwayOg, where x 6= y, we define prec(subway(x; y)) = foperational; at(x)g
e (subway(x; y)) = f:at(x); at(y)g
A planning state for P is a set of literals over F that is both logically complete and consistent. An action a is applicable in a planning state s iff s j= prec(a). We denote by (s; a) the state that results from applying a in s. Formally, (s; a) =(s n f` j C ! ` 2 e (a); s j= Cg)[
f` j C ! ` 2 e (a); s j= Cg if s 2 F and a is applicable in s; otherwise, (s; a) is undefined. It is convenient to extend the definition of for sequences of actions. If is a sequence of actions and a is an action, we define (s; a) as ( (s; ); a) if (s; ) is defined. Furthermore, if is the empty sequence, then (s; ) = s.
P = (F; O; I; G) and a sequence of actions = a0a1 : : : an, we say that induces an execution trace = s0s1 sk iff 1. I j= s0, and s0 is a planning state. 2. (si; ai) = si+1, for all i < k, and 3. either k = n+1 or k < n+1 and (sk; ak) is undefined.
trace for is successful iff j j = j j + 1.
leads to (goal formula) G, iff sk j= G. execution = s0 sk
a conformant plan for P = (F; O; I; G) iff every execution trace of is successful and leads to G.
= s1 sk conforms to a sequence of boolean formulae = h1 hn with k n iff si j= hi, for every i 2 f1; : : : ; kg.
Finally, each of the execution traces of that conform to must actually lead to the goal. A formal definition of an assumption-based plan follows.
where is a sequence of k actions, and is a sequence of k + 1 boolean formulae over T is an assumption-based plan for P = (F; O; I; G; T ) iff any execution trace of that conforms to is successful and leads to G, and furthermore at least one such execution trace exists.
Example (continued) Assume we define the initial state as I = fat(home)g, and the goal as G = at(o ce). Note this means that it is not known whether the subway is operational or whether their is a bus strike. Then the only conformant plan for the problem is given by walk(home; o ce).
However, if operational is an assumable fluent, then ( 1; 1) is an ABP plan, with: 1 1 = = operational; >; >; > walk(home; subwayH ); subway(subwayH; subwayO); walk(subwayO; o ce)
Finally, if strike is assumable, then ( 2; 2) is also an ABP plan, with: 2 2 = = :strike; > bus(home; o ce) 2.3
Contingent planning extends conformant planning by allowing the agent to observe the world via sensing actions. As such, we assume the set of action operators is partitioned into two (disjoint) sets Ow and Os, which contain, respectively, the actions that modify the world and sensing actions.
Formally a contingent planning problem is characterized by a tuple (F; Ow; Os; I; G), where F , I, and G are defined as above. Likewise, functions prec and e return the precondition and effect of each action a in Ow. For every sensing action o 2 Os, we associate a precondition prec(o) specifying the conditions under which o is executable, and we associate an observation obs(o), which is a Boolean formula over F specifying the condition that is sensed by o.
In general, contingent plans look like programs with ifthen-else conditions. In the formalization, we focus on treelike programs to simplify our definitions. Tree-like programs are as expressive as programs with if-then-else constructs. Definition 8 (Contingent Program) A contingent program for contingent planning task (F; Ow; Os; I; G) is the language for variable prog of the following BNF grammar. act ::= a obs ::= o prog ::= " prog ::= act prog prog ::= branch(obs; prog; prog) (for every a 2 Ow) (for every o 2 Os) (the empty program) (for a 2 Ow) (for o 2 Os)
Just like any action sequence induces an execution trace of states, so do contingent plans. Providing a formal definition for these traces will ultimately allow us to give a formal definition for a plan. First, however, we need an intermediate step: we need to define what does it mean to execute a program. We do this by first defining the notion of configuration.
Given a contingent planning problem, a configuration is a pair (S; p), where S is a set of planning states—also referred to below as belief state—and p is a program. Now we define the relation which can be intuitively related to atomic execution steps. More precisely, if (S; p) (S0; p0) then the execution of one atomic step of p in S leads to state S0, with p0 remaining to be executed. Formally, 1. (S; a p) (S0; p), for every a 2 Ow, if and only if
S j= prec(a) and S0 = f (s; a) j s 2 Sg. 2. (S; branch(o; p1; p2)) (S0; p), for every o 2 Os, if and only if S j= prec(o), and either S0 = T and p = p1 or S0 = S n T and p = p2, where T = fs 2 S j s j= obs(o)g.
Now we formally define a trace of execution for a program. Definition 9 (Trace of Configurations) Given a contingent planning problem (F; Ow; Os; I; G), and a program p, we say p induces an execution trace c0c1 : : : cn iff: 1. c0 = (S0; p), where S0 = fs j s is a state and I j= sg. 2. ci 1
ci, for every i 2 f1; : : : ; ng. 3. there is no c such that cn c.
As before successful traces are those that involved executing every single action of the program.
trace of configurations c1 : : : cn is successful if and only if cn = (S; "), for some s.
configurations c0c1 : : : cn leads to G if cn = (S; p) and S j= G.
a plan for P = (F; Ow; Os; I; G) if and only if every trace of configurations of p over P is successful and leads to G. Example (continued) Assume the initial state and goal state are defined as above, and that in addition we have the following sensing actions to sense whether or not the subway is operational. For each x 2 fstnO; stnH g: prec(senseOp(x)) = fat(x)g obs(senseOp(x)) = operational In addition to the plan walk(home; o ce), we have the contingent plan:
walk(home; stnH) branch(senseOp(stnH); p1; p2) and where p2 may describe various plans that involve waking. Important is the fact that p2 may not consider taking the bus, since fluent strike is unknown, unobservable, and its truth value cannot be changed by the agent. 3
Our translation uses a version of contingent planning that requires negation as failure (NAF) in action preconditions. This is not standard in contingent planning systems [Hoffmann and Brafman, 2005; Albore et al., 2009; To et al., 2011]. Nevertheless, as we show in this section, it is easy to extend a stateof-the-art contingent planner with NAF in preconditions. In the rest of the section, we first show that adding support for NAF in preconditions does not change the complexity class of contingent planning. Then, we show how to incorporate this feature to a state-of-the-art planner. 3.1
NAF in preconditions is related to modal logic modalities in
preconditions [Bonet, 2010]. Bonet proved that adding modal
operators like p (“always p”) and p (“possibly p”) to
preconditions does not change the complexity class of
contingent planning, for the more general case of finding an
unconstrained branching plan
In short, our proof follows from three facts. First, plan existence for a contingent planning problem is a 2-EXPcomplete decision problem [Rintanen, 2012]. Second, 2EXP is equivalent to AEXPSPACE; that is, the class of problems that can be decided with an alternating Turing machine (ATM) that uses exponential space. This means there exists an exponential-space ATM, say, M , that decides existence of a contingent plan. Third, we can modify M to now decide existence of a plan for a contingent problem with NAF preconditions, without requiring more memory. Indeed, such a machine is a slight modification of M . The only modification is the module in which preconditions are checked. For contingent planning, for every ` 2 prec(a) we need to check S j= `, where the size of S may be exponential in the size of the problem (jSj is worst-case the set of all possible states). Note that S j= ` does not require more than exponential space since it can be done in non-deterministic polynomial time in jSj + j`j. Adding support for NAF requires checking S 6j= `, which clearly can also be done in exponential space in the size of the problem. The rest of the M is left with no further modifications. Formally, Theorem 1 Contingent planning with NAF in preconditions is in 2-EXP.
Corollary 1 Contingent planning with NAF in preconditions is 2-EXP-complete.
Proof: Follows from the fact that contingent planning, a 2-EXP-complete problem is a particular case of contingent planning with negation as failure.
Now we turn into a more practical aspect of negation as failure: its implementation in a state-of-the-art system, namely, DNF [To et al., 2011].
As its name suggests, DNF represents belief states using disjunctive normal form; that is, as disjunctions of literal conjunctions. 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 action. Essentially, it checks that every literal in prec(a) is in every conjunction c of the belief state cs. Extending Algo
Input: An action a, a set of conjunctions of literals cs 1 for each conjunction c in cs do 2 for each ` 2 prec(a) do 3 if ` 62 c then 4 return false 5 return true rithm 1 to support negation as failure is extremely easy. Algorithm 2 shows how we did it in our implementation. The main difference is in Lines 2–8, which will declare that cs j= not ` if cs contains a conjunction in which ` does not appear.
Input: An action a, a set of conjunctions of literals cs 1 exec true 2 for each “not `” in prec(a) do 3 for each conjunction c in cs do 4 if ` 62 c then 5 exec true 6 break Now we extend the definition of ABP to the case of sensing. At the formal level an ABPS instance is simply a tuple (F; Ow; Os; I; G; T ), where all elements are defined as in conformant planning, and T F are the assumable fluents.
As with regular ABP, we want to allow an assumption prior to each action execution. Plans for an ABPS problem look like contingent programs where each world action or sense action is accompanied with an assumption. We call these programs assumption-based contingent programs.
An assumption-based contingent program is any element of the language defined by the prog variable of the BNF grammar of Definition 8, when replacing the rules for act and obs by the following: act ::= [h; a] obs ::= [h; o] (for every a 2 Ow; h 2 B(F )) (for every o 2 Os; h 2 B(F ))
Now we adapt the definitions for contingent planning to consider the effect of an assumption. The main difference between ABPS and contingent planning is that assumptions filter out some of the states in belief states; specifically, those states that are inconsistent with the assumption. We only require the goal to hold in the worlds that have not been filtered out. An additional requirement is that assumptions cannot filter out all states of the belief state. This is needed for two reasons. First, we do not want to allow assumptions that are inconsistent with all states in the belief state. Second, by definition, every action is executable in an empty belief state, and every formula is satisfiable in an empty belief state. As such, if we don’t prevent empty belief states to arise, we would obtain plans with an arbitrary number of spurious actions.
We formalize the notion of filter with the following definition Filter(S; h) = fs 2 S j s j= hg. Relation for ABPS is defined in the following way.
1. (S; [h; a] p) (S0; p), for every a 2 Ow, if and only if Sh = Filter(S; h) is nonempty, Sh j= prec(a) and S0 = f (s; a) j s 2 Shg. 2. (S; branch([h; o]; p1; p2)) (S0; p), for every o 2 Os, if and only if Sh = Filter(S; h) is nonempty, Sh j= prec(o), and either S0 = T and p = p1 or S0 = S n T and p = p2, where T = fs 2 Sh j s j= obs(o)g.
A assumption-based contingent program p is a plan for P = (F; Ow; Os; I; G; T ) if and only if every trace of configurations of p over P is successful and leads to G. Example (continued) Suppose, like above, that operational can be sensed by action senseOp, but that strike can be assumed but cannot be sensed by any action. Then the following is an ABPS plan for the resulting problem.
[>; walk(home; stnH)]
[>; branch(senseOp(stnH); p1; p2)] where p1 = [>; subway(stnH; stnO)] [>; walk(stnO; o ce)]; and where p2 can now consider an action that takes the bus, while assuming there is no strike. Indeed, p2 may be [:strike; bus(stnH; o ce)].
Note that our definition does not need to define a notion of conformity (cf. Definition 7), because we ensure a plan conforms to the assumptions by applying the Filter function. In the absence of sensing actions, Definitions 14 and 6 are equivalent, for those plans that do not assume anything about the final state.
Theorem 2 Let P = (F; O; I; G; T ) and P 0 = (F; O; ;; I; G; T ) be respectively ABP and ABPS problems. Then (h0 : : : hn >; a0 : : : an) is a plan for P if and only if [h0; a0] [hn; an] is a plan for P 0.
Finally, ABPS is in the same complexity class as contingent planning.
Theorem 3 Deciding existence of an ABPS plan is 2-EXPcomplete.
Proof: Follows from the correctness of the translation we propose in the following section. 5
Our translation takes an ABPS problem P = (F; Ow; Os; I; G; T ) as input and produces a contingent planning problem with NAF preconditions, P 0 = (F 0; Ow0; Os0; I0; G). The assumable fluents in T are translated into a set of world actions and sensing actions that, by being applied in a certain order, will have the same effect of making an assumption about the current state of the world. Notice that G is the only set that remains unmodified.
To understand the intuition underlying our translation, we first observe that assumptions can be related to sensing actions. Indeed, a sensing action o will, in one branch, filter out from the belief those states inconsistent with obs(o) whereas in the other branch those states consistent with the observation are filtered out. For sensing actions a plan is needed for both branches. For assumptions, on the other hand, we are only interested in the belief state that has filtered out those states inconsistent with the assumption.
One way of mapping an assumption into a sensing action would be to have a sensing action capable of performing both an observation and a change in the world. If t is an assumable fluent, one would create a sensing action whose observation is t. In addition, we would add a conditional effect :t ! g, for every g in the goal G.1 Such a sensing action would immediately “solve the problem” in the branch that is inconsistent with t. Unfortunately, the current model for contingent planning that planning system support does not handle conditional effects in sensing actions.
What our compilation does is to model assumptions with 4 distinguished actions for each assumable fluent. First, and foremost, there is a sensing action whose observation is the assumable fluent; its role is to filter out states that are consistent/inconsistent with the assumption. Second, there is a world action (assumme(t)) that intuitively starts “assumption mode”. An effect of this action is the fluent lock, which does not allow other world actions to be performed as soon as it becomes true. Then there are actions done and unlock. Both of them can only be performed after the sensing action. Action unlock, as the name implies, makes lock false, while action done, makes the goal true.
The details of the compilation are as follows.
1We assume here the goal is a set of literals to simplify the presentation, but the compilation can be adapted if G is a Boolean formula.
The set of fluents of the compiled problem is de
fined as:
F 0 = F [ flockg [ FA; where fluent lock resembles an “assumption mode” in which regular actions from the original problem (those in Ow or Os) are not executable. When lock is true, only assumptionrelated actions are applicable. Consequently, when it is false, only actions that belong exclusively to Ow or Os are applicable. Finally, FA = fassuming(t) j t 2 T g. Fluent assuming(t) intuitively indicates that “t is being assumed”. Its dynamic should be clear after reading how actions are defined.
Actions All actions in P are “copied into” P 0, but their precondition is modified to include lock. Formally, Ow0 = fa^ j a 2 Owg [ Aw
Os0 = fa^ j a 2 Osg [ As We modify the preconditions of actions in Ow [ Os to include the lock fluent. Formally, prec(a^) = prec(a) [ f:lockg, for each a 2 Ow [ Os Below we define Aw and As constructively, assuming they are initially empty. For each t 2 T that assumes a literal p to be true, we add: 1. An action assume(t) 2 Aw. This action initiates the process of making an assumption.
prec(assume(t)) = f:lock; not t; not :tg
e (assume(t)) = fassuming(t); lockg Since an assumption will be reduced to several world and sensing actions applied in an specific order, the fluent assuming(t) is needed to ensure the correct course of action execution. Note that this is the action that requires NAF in preconditions. Essentially the precondition is saying that we can only assume a fluent t if neither t nor :t is true; in other words, we can assume t if t is unknown. 2. A sensing action assume-s(t) 2 As. This is the next action to be applied. It will split the current belief state in two: one containing states where t is true and one containing the remaining states, where :t is true. When making an assumption only the branch where t is true is relevant, and so two more actions are needed in order to finish the process of making an assumption. This will be explained in the following two steps. Before that, we specify the preconditions for this action.
prec(assume-s(t)) = fassuming(t); lockg This action does not have any effects besides the branching due to its sensing nature. 3. An action done 2 Aw. The previously described sensing action will branch the plan into two paths. Since we are making an assumption, there is one branch which is not needed anymore and therefore has to be pruned so the plan does not continue expanding it. The action done is the one responsible for finishing off this branch. It does this by adding all goal fluents.
prec(done(t)) = flock; :t; assuming(t)g
e (done(t)) = fg j g 2 Gg 4. Finally, unlock(t) removes the lock fluent to allow the planner to continue using world and sensing actions (by removing lock) in the branch that is consistent with the assumption (i.e., in which t holds). Its definition follows. prec(unlock(t)) = flock; t; assuming(t)g
e (unlock(t)) = f:lock; :assuming(t)g
I0 = I [ f:lockg [ f:f j f 2 Fag: 6
A note on DNF’s performance In earlier stages of the experimental phase, we noticed that DNF was prone to choose actions that led to just one belief state as a result, over than those that generated a new one (like sensing and assumption actions). This was because the PrAO* algorithm [To et al., 2011] attempts to minimize the branching in the returned plans, which is not good if we want to generate plans with assumptions. To minimize this effect, we modified the heuristic modified the heuristic to increase likelihood of choosing nodes that come from a branching action. We called this variant DNF-ABPSA.
We designed two sets of experiments. In the first, we compared with our ABP predecessor, A0+Lama [DavisMendelow et al., 2013] in problems that do not have sensing actions. We evalueated over two of the four domains that were evaluated by Davis-Mendelow et al. [2013]: alogistics a modified version of logistics in which assumptions are needed to get to the goal, and the well-known coins domain, which included assumption actions that allow assuming the initial location of coins. Results are shown Table 1.
In our second set of experiments, the objective was to compare a contingent planner with an ABPS planner on the same problem, which the conformant planner does not, but the intent here was to evaluate difference on performance and on plan size. Of course, the ABP planner has access to a set of assumption actions. We ran DNF (without assumptions), and the two versions of DNF that used our translation (DNF-ABPS and DNF-ABPSA) over modified conformant domains dispose and push-to. In these domains we are can assume the position of the objects. Finally, we created medical-allergy inspired by IPC’s medical. In this domain there is a fixed number of illnesses and medicines that can cure each. Unfortunately, treatments may cause an allergic reaction, not deadly, but undesired. To determine whether or not a person is allergic, a number of actions that have to be performed. Furthermore, if the person turns out to be allergic to a medicine, there is an alternative medicine available, but it has to be imported (this was simulated by a number of actions). In this problem one can assume that a patient is not allergic. Results for all three domains are shown in Table 2. Experimental Conclusions A0, which uses LAMA [Richter et al., 2008] as a back-end planner, performs significantly better in the alogistics domain. This is possibly due to the fact that the DNF uses a very weak heuristic (goal counting), and does not exploit the advanced search techniques (like preferred operators) that are key to LAMA’s performance [Richter and Helmert, 2009].
In the push-to domain, on the other hand, A0 cannot translate almost any instance, and DNF and our approach can solve many of them in a couple of seconds or minutes, depending on the complexity of the problem. While observing the result for the different versions of DNF over the push-to and dispose domains, we can note, firstly that the translation time is not significantly different when assumption actions are added. Secondly, it is easy to see that the modification over DNFABPS improves its performance and balances the priority of world actions and branching actions. Hence, more assumptions are made in plans found by DNF-ABPSA. Thirdly, observing the characteristics of the plans themselves, DNF tends to take a shorter time to give a solution but these solutions are the longest. DNF-ABPS obviously takes more time to find a solution since its search space is wider and since it penalizes assumption actions, it doesn’t have a quick escape route to simplify it. In contrast, DNF-ABPSA, by doing more assumptions, provides considerably shorter solutions.
Finally, in medical-allergy, when the planner has more available assumptions, planning takes longer (probably due to the increasing branching factor), but solutions are shorter. Most likely, best results in both aspects, time and length, would come from a domain that allows assumptions and yet puts some kind of restrictions over what assumption can be performed. In future work, we would like effect on performance and plan quality when varying the set of assumable fluents in various ways. 7
We proposed an extension of ABP for domains in which sensing actions are available. We proposed a polynomial-time translation of ABP problems with sensing to contingent planning with negation as failure. Even though negation as failure is not a standard feature of contingent planners, we show that modifying one such a planner (DNF) is easy to do.
In our evaluation, we confirm that using assumptions may reduce plan size. In comparison to A0, the translator of the previous approach to ABP that does not support sensing and uses classical planners as a back end, we observe that in some cases the optimized classical planner outperforms the contingent planner we use. In other cases, however, our polynomialtime translation seems to pay off, allowing our planner to solve instances that cannot be translated by A0.
In future work we plan to extend our experimental
evaluation to more domains, and will evaluate the effect of
using different sets of assumable fluents. We also will
investigate different quality objectives (e.g., smaller plans, fewer
assumptions). Another line of future research is the
integration of these types of assumptions into logic-programming
planning frameworks