Answer Set Planning was one of the first challenging applications of Answer Set Programming (ASP). However, when putting plans into practice, their execution and monitoring lead to an increased complexity. Foremost, this is due to the inherent incompleteness of information faced in real-world scenarios. This fundamental problem has already been addressed in various ways, as in conformant, assertional, and assumption-based planning, and often combined with additional sensing actions. Our objective is to conceive a framework for planning and execution under incomplete information by combining the key concepts of the aforementioned approaches in a uniform ASP-based framework. This paper reports on our first step in this direction. More precisely, we define a series of increasingly complex ASP problems reflecting the successive integration of the key concepts. Our prime concern lies in obtaining a uniform characterization that matches the expressive realm of ASP. This is reflected by developing appropriate approximations that are implemented by means of metaencoding techniques.
Being able to operate in a dynamic environment has been one of the critical traits of intelligent agents. This includes the ability to create plans that transform the state of the world from an initial state to a desirable state. Planning is computationally expensive and it is harder when the initial state is incomplete and sensing actions are needed. Assuming that actions are deterministic and the plan’s length is polynomially bounded by the size of the problem, the complexity of the planning problem in this situation is PSPACEcomplete. By not considering sensing actions, the complexity of the planning problem, often referred to as conformant planning problem, is 2P -complete; using an incomplete approximation semantics lowers the complexity of the problem to NP-complete (e.g., using the 0-approximation) [6].
Planning using logic programs under the answer set semantics, or answer set planning (ASP, [15]), was one of the earlier applications of answer set programming. It has been extended to deal with incomplete information about the initial state and/or sensing actions. More specifically, ASP has been extended to solve conformant planning [10, 18, 20] and conditional planning problems [19]. It is worth noticing that, except [10], previous approaches to planning with incomplete information and sensing actions using logic programming have to rely on the approximation semantics. The main reason lies in its low complexity. The experimental results in these works show that ASP is competitive with other approaches to planning with incompleteness and sensing actions.
ASP has been an integral part of the intelligent agent architecture AAA proposed in [5] and further developed in [3, 4] whose key component is the Observe-Think-Act loop. However, the planning problem considered in applications employing this architecture— solved during the Think phase of the loop—does not consider incomplete information and sensing actions.
Alternative approaches for intelligent agents to dealing with incomplete information and sensing actions include assumption-based planning (ABP) [9] and continual planning [7]. In ABP, an agent acts as though it knows the truth values of unknown fluents when it needs to create a plan; during the execution of the plan, the agent adjusts and replans when some assumptions turn out to be incorrect. Continual planning addresses the problem by providing an agent with a skeleton of a plan (or an incompletely specified plan, that can only be completed when additional information is available) that allows the agent to interleave planning and execution while guaranteeing that the intended goal is achieved. This approach is similar to that of using GOLOG [14] (or its extensions) in robotics [8]. Although there has been an attempt to extend ASP to employ GOLOG in plan generation [17], it does not deal with incomplete information and/or sensing actions; it has not been integrated into an implementation of the AAA architecture as well.
Our goal in this paper is to further investigate the use of logic programming in dealing with incomplete information in dynamic domains. Instead of focusing on the encoding of a specific planning problem (e.g., conformant, conditional, assumption-based, or continual planning), we develop an abstract framework that can eventually combine the features present in all types of planning problems. Our long term goal is to employ this framework in robotic environments and integrate it with appropriate ASP reasoning engines such as ROSoClingo [1]. 2
A logic program P over a set A of atoms is a set of rules of form
a1; : : : ; am
am+1; : : : ; an; an+1; : : : ; ao
(
To ease the use of ASP in practice, several extensions have been developed. First of all, rules with variables are viewed as shorthands for the set of their ground instances. For a 2 A, a choice rule r is of the form fag B (r) and stands for the pair of rules a B (r); a0 and a0 B (r); a where a0 is a new symbol associated with a. We define H (r) = fag for a choice rule as r. Further language constructs include conditional literals and cardinality constraints [16]. The former are of the form a : b1; : : : ; bm; the latter can be written as s fd1; : : : ; dng t; where a and bi are possibly negated (regular) literals and each dj is a conditional literal; s and t provide optional lower and upper bounds on the number of satisfied literals in the cardinality constraint. We refer to b1; : : : ; bm as a condition. The practical value of both constructs becomes apparent when used with variables. For instance, a conditional literal like a(X) : b(X) in a rule’s antecedent expands to the conjunction of all instances of a(X) for which the corresponding instance of b(X) holds. Similarly, 2 fa(X) : b(X)g 4 is true whenever at least two and at most four instances of a(X) (subject to b(X)) are true. Finally, assignments are of form t = fd1; : : : ; dng. E.g., Y = fa(X) : b(X)g is true if Y equals the number of satisfied instances of a(X) : b(X).
We identify the choice rules, normal rules, and integrity constraint in a logic program P by means of c(P ), n(P ), and i(P ), respectively. We define a program P as normalized, if it can be partitioned into c(P ), n(P ), and i(P ), such that B (r) = ; for each r 2 c(P ) and n(P ) is stratified [2]. For simplicity, in this paper, we restrict ourselves to normalized programs, although the implementation handles arbitrary programs.
In what follows, we rely on reification for translating a logic program P into a set of facts
R(P ) = fchoice(a)
j r 2 c(P ); a 2 H (r)g
[ frule(r )
[ fhead (r ; a)
[ fbody (r ; +; a)
[ fbody (r ; ; a)
[ fscc(c; a)
j r 2 n(P ) [ i(P )g
j r 2 n(P ); a 2 H (r)g
j r 2 n(P ) [ i(P ); a 2 B (r)+g
j r 2 n(P ) [ i(P ); a 2 B (r) g
j a 2 Cc; Cc 2 SCC (P )g
where SCC (P ) contains all strongly connected components of the positive atom
dependency graph of P .1 As an example, consider the program P1 consisting of the rules
(
scc(C ; X ); head (R; X ); scc(C ; X 0); body(R; +; X 0)
wait (C ; X ; 0 )
wait (C ; R; I )
wait (C ; X ; I )
scc(C ; X ); ab(X ); fbody(R) : head (R; X ); internal (C ; R) (
1 ) : head (R; X ); internal (C ; R) normal (R)
head (R; X )
atom(X )
atom(X )
head (R; X )
body(R; V ; X )
Note that the rules in lines (
For instance, the unique stable model of P1 is fa; qg; it corresponds to the only stable
model of R(P1) [ M containing t (a), f (b), and t (q ). Accordingly, neither P1 [ fb g
nor R(P1) [ frule(
Our goal in this paper is to develop an abstract framework for planning with incomplete information that builds on a basic ASP encoding. As such, we present this encoding through an example.
Example 1. Consider a cleaning robot in a house with two rooms 1 and 2 connected through a door. Initially, the robot is at 1, the door is open, and both rooms are not clean. The robot can move between rooms if the door is open. It can also sweep the room it is in. The goal is to clean both rooms. Obviously, the robot can start with sweeping room 1, then go to room 2, and sweep room 2.
A logic program encoding this problem would use atoms of the form holds(f; t),
holds(neg(f ); t), and occ(a; t) where f is a fluent in fclean(
occ(sweep(R); T ) – expressing the indirect effects of actions, e.g., to state that the robot is not at one room if it is at another room: holds(neg(at(R)); T ) holds(at(R0); T ); R 6= R0 The program also contains rules for expressing inertia, rules for generating action occurrences, rules for goal verification, and rules encoding the initial states. For this problem, the initial state is encoded by
holds(at(
98ASP
In this section, we introduce the notion of a 98ASP problem, similar to that of a quantified
Boolean formula in propositional logic, to capture conformant planning problems. More
specifically, a conformant planning problem is viewed as a program with two sets of
atoms, one characterizes the set of possible plans, and the other the incomplete initial
state. This notion allows us to deal with incompleteness keeping intact the ASP encoding
of the planning problem except for the rules representing the initial state. For example,
assume that the robot in Example 1 does not know whether any room is clean, we
only need to declare that the problem is concerned with the situation where clean(
Definition 1 (98ASP Problem). An 98ASP problem is a tuple (P; A; X; Y; Z) where P is a a logic program over A, and (X; Y; Z) is a partition of A.
For simplicity, we sometimes use 9X8Y P to refer to the 98ASP problem (P; A; X; Y; Z),
leaving implicit the sets A of atoms appearing in P and Z = A (X [ Y ). Let Pr
be the program in Example 1 without the rules in (26), A be its set of atoms, X =
focc(a; t) j a is an action; t is a stepg, Y = fholds(clean(
We sometimes abuse notation and identify a set X of atoms with the set of facts j a 2 Xg. Next we define the solutions to 98ASP problems. fa Definition 2 (98ASP Solution). A set of atoms X0 X is a solution to the 98ASP problem (P; A; X; Y; Z) if for all sets Y 0 Y , the program X0 [ Y 0 [ P has some stable model.
There is a unique solution to the problem 9X8Y Pr of Example 1. It contains the atoms
occ(sweep(
q a; b Example 2. Let P2 be the logic program f g h u a; f a; f h
b The solutions to the 9fa; ug8fgP2 problem are fag and fa,ug, and the unique solution to the 9fag8fugP2 problem is fag.
Example 3. Let P3 be the result of extending P2 with the set of rules The solutions to 9fa; bg8fugP3 are both fag and fbg.
We compute the solutions to 9X8Y P with an encoding extending R(P ) [ M . For
simplicity, we assume that atoms in X and Y do not appear in any rule heads in P , i.e.,
(X [ Y ) \ fa 2 H(r) j r 2 c(P ) [ n(P )g = ;, although this restriction may easily be
lifted. Let F (X; Y ) be the set of facts
fexists (a)
j a 2 Xg [ fforall (a)
j a 2 Y g
reifying the atoms in X and Y , and let EF be the set of rules
The rule in (27) allows for choosing the truth values of the existentially quantified atoms.
Without the one in (28) we would derive f (a) for all atoms a in Y , since we are assuming
that atoms in Y are excluded from rule heads. Observe that now in the meta encoding
M no rule can infer t (a) nor f (a) for any a in Y . Hence, every atom derived using the
meta encoding is independent of the truth value of the atoms a 2 Y . Then, the rules in
lines (
In the following, we write E(9X8Y P ) to denote the encoding R(P ) [ M [ F (X; Y ) [ EF . The next theorem establishes that it can be used to compute solutions of 9X8Y P .
Theorem 1. Let (P; A; X; Y; Z) be an 98ASP problem, then for every stable model S of the logic program E(9X8Y P ), fa j t(a) 2 Sg \ X is a solution to the problem. Example 4. (Cont. Example 2). The encoding E(9fa; ug8fgP2) has two stable models, one contains atoms t(a), f (u), f (f ), f (g), t(h), t(q), and the other t(a), t(u), t(f ), t(g), f (h), t(q). They correspond to the solutions fag and fa,ug.
The next examples show that in general the encoding E(9X8Y P ) is not complete, i.e., there might be solutions it cannot compute. Example 5. (Cont. Example 2). The problem 9fag8fugP2 has one solution fag, but E(9fag8fugP2) has no stable model. This example shows that our encoding cannot reason by cases, which is needed to find the solution: if u is true, using a we obtain q after deriving f and g, and if u is false, we obtain q after deriving h, so in every case we could obtain q.
Example 6. (Cont. Example 3). The encoding E(9fa; bg8fugP3) has one stable model with f (a), t(b), f (g), t(h), t(q), corresponding to the solution fbg of 9fa; bg8fugP3, but there is no stable model for the solution fag.
All our encodings extend E(9X8Y P ) and are therefore incomplete. For this reason we say that they are approximations to the problems they aim to solve. 3.1
The stable models of the encoding E(9X8Y P ) may contain atoms t (a) or f (a) for some a 2 Z. To capture their meaning we define the extended solutions to a 98ASP problem, which may assign atoms a 2 Z to true or false. To this end, we need some extra notation. Let X; Y A be sets of atoms. By XY we denote the set X \ Y . A partial interpretation over X is a pair hT; F i where T; F X and T \ F = ;. We say that hT; F i is total on X if TX [ FX = X. We define a preorder over partial interpretations, where hT; F i is more specific than hT 0; F 0i, written hT; F i hT 0; F 0i, if T T 0, and F F 0.
being total on X is an extended solution to the 98ASP problem (P; A; X; Y; Z) if for all sets Y 0 Y , the program TX [ Y 0 [ P [ f a j a 2 TZ g [ f a j a 2 FZ g has some stable model.
It turns out that, considering the atoms t (a) and f (a) for a 2 X [ Z, every stable model of E(9X8Y P ) corresponds to an extended solution to the problem. Note that in Theorem 1 we considered only the t (a) for a 2 X.
Theorem 2. Let (P; A; X; Y; Z) be an 98ASP problem, then for every stable model S of the logic program E(9X8Y P ), hfa j t(a) 2 SgX[Z ; fa j f (a) 2 SgX[Z i is an extended solution to the problem.
The following propositions establish the relation between solutions and extended solutions to an 98ASP problem.
Proposition 2. Let X0 be a solution to the 98ASP problem (P; A; X; Y; Z), then hX0; X X0i is an extended solution to the problem.
Proposition 3. Let hT; F i be an extended solution to the 98ASP problem (P; A; X; Y; Z), then TX is a solution to the problem.
We say that an extended solution hT; F i is maximal, if it is maximal among all extended solutions wrt the ordering . It is easy to see that if hT; F i is a maximal extended solution, then all partial interpretations hT 0; F 0i with hT X0 ; F X0 i = hTX ; FX i and hT Z0 ; F Z0 i hTZ ; FZ i are also extended solutions. In particular, hTX ; FX i is an extended solution. Example 7. (Cont. Example 4). The 98ASP 9fa; ug8fgP2 problem has two maximal extended solutions, hfa; h; qg; fu; f; ggi, and hfa; u; f; g; qg; fhgi, which correspond to the two stable models of E(9fa; ug8fgP2) described in Example 4. Some non maximal extended solutions are, for example, hfag; fugi and hfa; u; qg; fgi.
Example 8. (Cont. Example 5). The extended solutions to 9fag8fugP2 are hfa; qg; fgi and hfag; fgi; only the first one is maximal. None of them is computed by E(9fag8fugP2), that has no stable models.
Example 9. (Cont. Example 6). The maximal extended solutions to 9fa; bg8fugP3 are hfa; qg; fbgi and hfb; h; qg; fa; ggi. The last one corresponds to the unique stable model of the encoding E(9fa; bg8fugP3), described in Example 6.
In general, not all stable models of E(9X8Y P ) correspond to maximal extended solutions. For example, deleting the constraint q from P2, the unique stable model of E(9fag8fugP2) would contain t(a) and correspond to the extended solution hfag; fgi, which is less specific than the maximal extended solution hfa; qg; fgi. 4
98ASP is sufficiently expressive for representing conformant planning problems, but it cannot be used to represent problems that require sensing actions, i.e., reasoning about beliefs/knowledge. For instance, consider a variation of the problem in Example 1. Assume that initially the door is closed. The door may either have a key lock or a card lock. The robot has a key and a card, but the type of the lock is initially unknown. If the robot tries to open the door with the wrong object, the lock gets stucked so that afterwards there is no way to open the door. The robot can sense the type of the lock with a sensing action check. It is easy to see that this problem has no conformant plan, while there is a conditional plan with two branches after the execution of the sensing action check. Another approach for solving this problem is to introduce an assertion action assert(open) [7] establishing that the door is open if the type of the lock is known. Then there is a plan that contains actions check and assert(open), and achieves the goal. Assertions are abstract actions that by definition cannot be executed in the real world. So after sensing the type of the lock, assert(open) cannot be executed, and the robot must replan. Observe that now the type of the lock is already known, so there is again a plan achieving the goal, using the appropriate object to open the door. This example shows the method for continual planning using assertions: first, a plan is found containing a sensing and an assertion action, then, after executing the sensing action in the real world, the system replans, and using the sensed information it finds a plan without assertions that can be normally executed.
To represent such an approach, we introduce the notion of a logic program with knowledge and extend the notion of 98ASP to this new class of programs. If X is a set of atoms, by Xkw we denote the set fakw j a 2 Xg of know-whether atoms of X. Definition 4 (Logic program with knowledge). A logic program with knowledge P over A is a logic program over A [ Akw where Akw \ fa j r 2 P; a 2 H (r)g = ;. The last condition expresses that the know-whether atoms Akw are not allowed to appear in the head of the rules. Given a partial interpretation hT; F i over A, we say that an atom a 2 A is (known to be) true if a 2 T , it is (known to be) false if a 2 F , it is known(-whether) if a 2 T [ F , and otherwise it is unknown(-whether). The knowwhether atoms of logic programs with knowledge allow expressing that an atom a is known or unknown in a partial interpretation, via akw or akw, respectively. They are restricted to the bodies of rules to guarantee that their truth value is determined by the partial interpretation they are referring to. We next define the notions of a problem with knowledge and the corresponding solution.
is a tuple (P; A; X; Y; Z) where P is a logic program with knowledge over A, and (X; Y; Z) is a partition of A.
X[Z being total on X is a solution to the 98ASP problem with knowledge (P; A; X; Y; Z) if for all sets Y 0 Y , the program TX [ Y 0 [ P [ f a j a 2 TZ g [ f a j a 2 FZ g [ fakw a j a 2 T g [ fakw a j a 2 F g has some stable model. As before, we say that a solution to a 98ASP problem with knowledge is maximal if it is a maximal element of the set of solutions to the problem ordered by . Example 10. The problem with knowledge 9fg8fugP4 where P4 is the following logic program f i f kw; gkw j g gkw h k u hkw has a unique maximal solution hff; i; kg; fg; jgi. From the rules in the first line we obtain that f is known to be true, g is known to be false, and h is unknown. From the second line, given that f and g are known, we derive i but not j, and we obtain k since h is unknown.
Given a partial interpretation hT; F i, the rules fakw a j a 2 T g [ fakw a j a 2 F g of Definition 6 infer the atoms akw for every a 2 T [ F . In the Example 10, they derive atoms f kw and gkw, which are used to obtain i and block the derivation of j. Note that simply adding the set of rules fakw a j a 2 Ag [ fakw a j a 2 Ag to Definition 6 would not work, because then akw would always be true for all a 2 A.
The know-whether atoms akw express that either a is known to be true or a is known to be false in a partial interpretation. We can introduce new atoms akt and akf for expressing that a is known true in a partial interpretation, and that a is known false in a partial interpretation, respectively. They can be defined with the rules fakt a; akw j a 2 Ag [ fakf a; akw j a 2 Ag (29) Example 11. (Cont. Example 10) The problem 9fg8fugP4 [ f hg has no solution, since we cannot prove that h is false for all values of u. However, adding (29) and replacing h by hkt, the problem 9fg8fugP4 [ (29) [ f hktg has some solution again, since now the constraint only requires h not known to be true.
The next theorem states the relation between the solutions of a problem with knowledge and the solutions defined in the previous section.
Theorem 3. A partial interpretation hT; F i over X [ Z being total on X is a solution to the 98ASP problem with knowledge (P; A; X; Y; Z) if hT; F i is an extended solution to the 98ASP problem (without knowledge) (P 0; A [ Akw; X; Y; Z [ Akw) where P 0 = P [ fakw a j a 2 T g [ fakw a j a 2 F g.
The theorem reduces a problem with knowledge to a problem without it, where the know-whether atoms are treated as regular atoms, and the original program is extended with the rules to derive them appropriately.
Example 12. The problem with knowledge 9fg8fugP5 where P5 is the following logic program f f u u sense f kw has two maximal solutions: hff g; fsensegi and hfsenseg; fgi. In the first solution the atom f is true and sense cannot be derived, while in the second solution f is unknown and sense can be obtained.
Usually, approaches to knowledge consider that an atom is known if it holds for all possible values of the unknown atoms. Under this interpretation, in the previous example, only hff g; fsensegi would be a valid solution, since no matter the value of u, atom f is always true, so we can conclude that it is known and therefore sense is false. However, for an agent using an approximation, the solution hfsenseg; fgi is also reasonable. The agent using our encoding actually does not know the value of f , given that it cannot reason by cases. Then it is reasonable for the agent to derive sense, so that afterwards it senses the value of f . In this respect, our approach to knowledge does not capture the notion of what may be known by an agent using a logic program, but rather it represents what is actually known by that agent using an approximation.
Now let’s consider an example with an assertion action.
Example 13. Let P6 be the program that results after replacing in P2 (from Example 2) the rule h
a; f by these two h b; f a; b The problem 9fa; bg8fugP6 has no solution. Intuitively, there is a conditional solution where if u is true, then a is made true to achieve q, while if u is false, then b is made true instead. This simple type of conditional solution can be modeled with an assertion. Let P7 extend P6 with the following rules where f 0 is a new atom representing that f is known either because we know-whether it or because we have sensed it, sense senses fluent f , and c stands for an assertion that derives q when f 0 is true. The problem 9fc; senseg8fugP7 has one maximal solution hfc; sense; f 0; qg; fa; b; g; hgi. Atoms f and f 0 are unknown and true, respectively, representing the case where although f is not known-whether, it is known because it has been sensed. In the real-world, the agent would first sense f , and afterwards, given that the assertion c is an abstract action that cannot be executed, the agent would have to search for a new solution using the knowlege gathered by sensing.
For computing the solutions to a 98ASP problem with knowledge (P; A; X; Y; Z), we extend the encoding E(9X8Y P ) with the set of rules K
ft (akw ) fab(akw ) t (a) j a 2 Ag [ ft (akw ) t (a) j a 2 Ag [ fab(akw ) f (a) j a 2 Ag [ f (a) j a 2 Ag adding appropriately the rules fakw a j a 2 T g [ fakw a j a 2 F g of Definition 6. When an atom a is known true or false in a partial interpretation hT; F i, the encoding E(9X8Y P ) derives t (a) or f (a), respectively. Then the rules in the first line infer t (akw ), and the rules in the second line block the establishment of f (akw ) by the meta encoding. On the other hand, if a is unknown in hT; F i, then the rules in K are not applied, while the rules in the meta encoding infer f (akw ), given that know-whether atoms do not appear in the head of rules.
Theorem 4. Let (P; A; X; Y; Z) be an 98ASP problem with knowledge, then for each stable model S of the logic program E(9X8Y P ) [ K, hfa j t(a) 2 SgX[Z ; fa j f (a) 2 SgX[Z i is a solution to the problem.
Example 14. (Cont. Example 10). The encoding E(9fg8fugP4) [ K has one stable model, corresponding to the unique maximal solution to the problem.
Example 15. (Cont. Example 11). The encoding E(9fg8fugP4 [ f hg) [ K has no stable model, while E(9fg8fugP4 [ (29) [ f hktg) [ K has one, corresponding to the unique maximal solution to the problem.
Example 16. (Cont. Example 12). The encoding E(9fg8fugP5)[K has only one stable model, corresponding to the maximal solution hfsenseg; fgi to the problem. There is no stable model for the solution hff g; fsensegi, given that it would require reasoning by cases.
Example 17. (Cont. Example 13). The encoding E(9fa; bg8fugP6) [ K has no stable model, while E(9fc; senseg8fugP7) [ K has one stable model corresponding to the unique maximal solution to the problem. 5
In general, for dealing with incomplete information and sensing actions, agents may have to devise conditional plans, or plans with assertions. However, as argued in [9], this might be not necessary in many practical situations, where agents can still achieve their goals by making reasonable assumptions, planning, and executing the generated plan with the understanding that replanning might be needed sometimes. Let us reconsider the variation of the problem in Example 1 discussed in Section 4 with a slight change: when the robot tries to open the door with the wrong object, the door does not open, and there is a signal indicating the error. In this domain, the robot could proceed by assuming that the key can be used to open the door, and generating a plan involving this assumption (e.g., a reasonable plan is the sequence: sweep room 1, open the door with the key, move to b, and sweep room 2). The assumption is justified because the robot is familiar with this type of arrangements, and it has encountered far more doors with the key lock than with the card lock. When the robot executes the plan, if it realizes that the assumption was incorrect, it can address the issue by replanning. To represent this approach, we introduce the notion of a solution with assumptions, extending the notion of solution of a 98ASP problem.
over A being total on X is a solution with assumptions hTY ; FY i to the 98ASP problem (P; A; X; Y; Z) if hT; F i is a solution to the 98ASP problem (P [ TY [ f a j a 2 FY g; A; X; Y (TY [ FY ); Z [ TY [ FY ).
A solution with assumptions assumes truth values for a subset of the universally quantified atoms, and reduces the problem to one without assumptions. This is achieved extending the original program with facts for the atoms that are assumed to be true, and constraints for the atoms that are assumed to be false. Furthermore, the selected atoms are no longer quantified.
The implementation only requires allowing choices over the universally quantified atoms. This can be done with the following program A: fchoice(X )g Theorem 5. Let (P; A; X; Y; Z) be an 98ASP problem, then for each stable model S of the logic program E(9X8Y P ) [ A, hfa j t(a) 2 SgA; fa j f (a) 2 SgAi is a solution with assumptions hfa j t(a) 2 SgY ; fa j f (a) 2 SgY i to the problem. Example 18. (Cont. Example 2). Consider the problem 9fag8fugP2 of Example 2. As shown in Example 5, the solution hfa; qg; fgi cannot be computed by the program E(9fag8fugP2), but using E(9fag8fugP2)[A two solutions with assumptions can be computed. The first is hfa; f; g; q; ug; fhgi with assumptions hfug; fgi, and the second is hfa; h; qg; ff; g; ugi with assumptions hfg; fugi.
Example 19. (Cont. Example 13). Consider the problem 9fa; bg8fugP6 of Example 13 with no solutions. There are two solutions with assumptions that can be computed with E(9fa; bg8fugP6) [ A. The first is hfa; f; g; q; ug; fb; hgi with assumptions hfug; fgi, and the second is hfb; h; qg; fa; f; g; ugi with assumptions hfg; fugi.
Among the solutions with assumptions computed by E(9X8Y P ) [ A, we can select those with a minimal number of assumptions simply adding a minimize statement: #minimizef1; X : choice(X ); forall (X )g
Finally, the previous notions are seamlessly applied to logic programs with knowledge.
terpretation hT; F i over A being total on X is a solution with assumptions hTY ; FY i to the 98ASP problem with knowledge (P; A; X; Y; Z) if hT; F i is a solution to the 98ASP problem with knowledge (P [TY [f a j a 2 FY g; A; X; Y (TY [FY ); Z [TY [FY ). Theorem 6. Let (P; A; X; Y; Z) be an 98ASP problem with knowledge, then for each stable model S of the logic program E(9X8Y P ) [ K [ A, hfa j t(a) 2 SgA; fa j f (a) 2 SgAi is a solution with assumptions hfa j t(a) 2 SgY ; fa j f (a) 2 SgY i to the problem. 6
Starting from the basic problem of 98ASP, we provided a series of characterizations of increasing complexity in order to capture concepts for planning with incomplete information. We addressed the various problems by means of a metaencoding that allows us to approximate the actual solutions. This is driven by the desire to stay within the realm of ASP’s computational complexity.
The current implementation deals with logic programs, whose decision problem is NP-complete and whose heads are free of quantified atoms. The latter are captured via predicates exists =1 and forall =1 . Predicate kw =1 is used to represent know-whether atoms. The actual metaencoding generalizes the one described previously, and works for full clingo programs (and not just normalized ones). Alternatively, a metaencoding based in [22] can be used. The input program is reified by clingo, and passed along with the metaencodings once more to clingo for solving. The current implementation is available at https://github.com/javier-romero/oclingo/tree/master/ approximation (but will move to https://github.com/potassco).
The approximation can be seen as an attempt to generalize [20] from action theories to ASP; it is closely related to the work on FO(ID) of [22]. The knowledge part generalizes the approach of [7] from action language SAS to ASP. The idea of planning with assumptions comes from [9]. They use an action language with conditional effects, and propose a translation to classical planning.
Acknowledgement. This work was partially funded by DFG grant SCHA 550/9.