2.1 Answer set programming

As usual, a logic program consists of rules of the form

\begin{equation*} a_1 \vee \ldots \vee a_m \leftarrow a_{m+},\dots,a_n,{ not \:} a_{n+1},\dots,{ not \:} a_o,\end{equation*}

where each $a_i$ is an atom of form $p(t_1,\dots,t_k)$ and all $t_i$ are terms, composed of function symbols and variables. Atoms $a_1$ to $a_m$ are often called head atom, while $a_{m+1}$ to $a_n$ and ${ not \:} a_{n+1}$ to ${ not \:} a_o$ are also referred to as positive and negative body literals, respectively. An expression is said to be ground, if it contains no variables. As usual, ${ not \:}$ denotes (default) negation. A rule is called a fact if $m=o=1$ , normal if $m=1$ , and an integrity constraint if $m=0$ . Semantically, a logic program produces a set of stable models, also called answers sets, which are distinguished models of the program determined by the stable model semantics; see the paper by (Gelfond and Lifschitz Reference Gelfond and Lifschitz1991) for details.

To ease the use of ASP in practice, several simplifying notations and extensions have been developed. First of all, rules with variables are viewed as shorthands for the set of their ground instances. Additional language constructs include conditional literals and cardinality constraints (Simons et al. Reference Simons, Niemelä and Soininen2002). The former are of the form $a:{b_1,\dots,b_m}$ , the latter can be written as $s\{d_1;\dots;d_n\}t$ , ^{Footnote 3} where a and $b_i$ are possibly default-negated (regular) literals and each $d_j$ 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 $b_1,\dots,b_m$ 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\;\{a(X):b(X)\}\;4$ is true whenever at least two and at most four instances of a(X) (subject to b(X)) are true. Finally, objective functions minimizing the sum of a set of weighted tuples $(w_i,\boldsymbol{t}_i)$ subject to condition $c_i$ are expressed as $\#minimize\{w_1@l_1,\boldsymbol{t}_1:c_1;\dots;w_n@l_n,\boldsymbol{t}_n:c_n\}$ . Analogously, objective functions can be optimized using the $\#{maximize}$ statement. Lexicographically ordered objective functions are (optionally) distinguished via levels indicated by $l_i$ . An omitted level defaults to 0. Furthermore, $w_i$ is a numeral constant and $\boldsymbol{t}_i$ a sequence of arbitrary terms. Alternatively, the above minimize statement can be expressed by weak constraints of the form $\hookleftarrow c_i [w_i@l_i,\boldsymbol{t}_i]$ for $1\leq i\leq n$ .

As an example, consider the following rule:

\begin{equation*}1 \{ \mathit{move}(D,P,T) : \mathit{disk}(D), \mathit{peg}(P) \} 1 \leftarrow \mathit{ngoal}(T-1), T\leq n.\end{equation*}

This rule has a single head atom consisting of a cardinality constraint; it comprises all instances of $\mathit{move}(D,P,T)$ where T is fixed by the two body literals and D and P vary over all instantiations of predicates $\mathit{disk}$ and $\mathit{peg}$ , respectively. Given 3 pegs and 4 disks, this results in 12 instances of $\mathit{move}(D,P,T)$ for each valid replacement of $\mathit{T}$ , among which exactly one must be chosen according to the above rule.

Full details of the input language of clingo, along with various examples and its semantics, can be found in the papers by (Gebser et al. Reference Gebser, Kaminski, Kaufmann, Lindauer, Ostrowski, Romero, Schaub and Thiele2015). The interested reader is also referred to the work by (Calimeri et al. Reference Calimeri, Faber, Gebser, Ianni, Kaminski, Krennwallner, Leone, Maratea, Ricca and Schaub2019) for the description of the ASP Core 2 Language.

A logic program can have zero, one, or multiple answer sets. This distinguishes answer set semantics from other semantics of logic programs such as the well-founded semantics of (Van Gelder et al. Reference Van Gelder, Ross and Schlipf1991) or perfect models semantics of (Przymusinski Reference Przymusinski1988). Answer set semantics, together with the introduction of choice rules and constraints, enables the development of ASP as proposed by (Lifschitz Reference Lifschitz1999). Following this approach, a problem can be solved by a logic program whose answer sets correspond one-to-one to the problem’s solutions. Choice rules are often used to generate potential solutions and constraints are used to eliminate potential but incorrect solutions.

2.2 Reasoning about actions: The action description language $\mathcal{B}$

We review the basics of the action description language $\mathcal{B}$ (Gelfond and Lifschitz Reference Gelfond and Lifschitz1998). An action theory in $\mathcal{B}$ is defined over a set of actions A and a set of fluents F. A fluent literal is a fluent $f \in \mathbf{F}$ or its negation $\neg f$ . A fluent formula is a Boolean formula constructed from fluent literals. An action theory is a set of laws of the form

(1) \begin{eqnarray} & \textbf{caused}(\varphi , f) \end{eqnarray}

(2) \begin{eqnarray} & \textbf{causes}(a,f, \varphi) \end{eqnarray}

(3) \begin{eqnarray} & \textbf{executable}(a, \varphi) \end{eqnarray}

(4) \begin{eqnarray} & \textbf{initially}(f), \end{eqnarray}

where f and $\varphi$ are a fluent literal and a set of fluent literals, respectively, and a is an action. A law of the form (1) represents a static causal law, that is, a relationship between fluents. It conveys that whenever the fluent literals in $\varphi$ hold then so is f. A dynamic causal law is of the form (2) and represents the (conditional) effect of a while a law of the form (3) encodes an executability condition of a. Intuitively, an executability condition of the form (3) states that a can only be executed if $\varphi$ holds. A dynamic law of the form (2) states that f is caused to be true after the execution of a in any state of the world where $\varphi$ holds. When $\varphi = \emptyset$ in (3), we often omit laws of this type from the theory. Statements of the form (4) describe the initial state. They state that f holds in the initial state. We also often refer to $\varphi$ as the “precondition” for each particular law.

An action theory is a pair $(D,\Gamma)$ where $\Gamma$ , called the initial state, consists of laws of the form (4) and D, called the domain, consists of laws of the form (1)–(3). For convenience, we sometimes denote the set of laws of the form (1) by $D_C$ .

Example 1 Let us consider a modified version of the suitcase s with two latches from the work by (Lin Reference Lin1995). We have a suitcase with two latches $l_1$ and $l_2$ . $l_1$ is up and $l_2$ is down. To open a latch ( $l_1$ or $l_2$ ), we need a corresponding key ( $k_1$ or $k_2$ , respectively). When the two latches are in the up position, the suitcase is unlocked. When one of the latches is down, the suitcase is locked. In this domain, we have that

\begin{equation*}\mathbf{A} = \{open(l_i), close(l_i), get\_key(k_i) \mid i \in \{1,2\}\}\end{equation*}

and

\begin{equation*}\mathbf{F} = \{locked\} \cup \{up(l_i), holding(k_i) \mid i \in \{1,2\}\}.\end{equation*}

The intuitive meaning of the actions and fluents is clear. The problem can be represented using the laws

\begin{equation*}D^s = \left \{\begin{array}{ll}\textbf{causes}(open(l_i), up(l_i), \emptyset) & \\[4pt]\textbf{causes}(close(l_i), \neg up(l_i), \emptyset) & \\[4pt]\textbf{causes}(get\_key(k_i), holding(k_i), \emptyset) & \\[4pt]\textbf{executable}(open(l_i), \{holding(k_i)\}) & \\[4pt]\textbf{caused}(\{\neg up(l_i)\}, locked) & \\[4pt]\textbf{caused}(\{up(l_1), up(l_2)\}, \neg locked), & \\[4pt]\end{array}\right.\end{equation*}

where, in all laws, $i = 1,2$ . The first three laws describe the effects of the action of opening a latch, closing a latch, or getting a key. The fourth law encodes that we can open the latch only when we have the right key. Observe that the omission of executability laws for $close(l_i)$ or $get\_key(k_i)$ indicates that these actions can always be executed. The last two laws are static causal laws encoding that the suitcase is locked when either of the two latches is in the down position and it is unlocked when the two latches are in the up position.

A possible initial state of this domain is given by

\begin{equation*}\Gamma^s = \left \{\begin{array}{lllll}\textbf{initially}(up(l_1)) \\[4pt]\textbf{initially}(\neg up(l_2)) \\[4pt]\textbf{initially}(locked) \\[4pt]\textbf{initially}(\neg holding(k_1)) \\[4pt]\textbf{initially}(holding(k_2)). \\[4pt]\end{array}\right .\end{equation*}

$\diamond$

A domain given in $\mathcal{B}$ defines a transition function from pairs of actions and states to sets of states whose precise definition is given below. Intuitively, given an action a and a state s, the transition function $\Phi$ defines the set of states $\Phi(a,s)$ that may be reached after executing the action a in state s. The mapping to a set of states captures the fact that an action can potentially be non-deterministic and produce different results (e.g., an action open might be successful in opening a lock or not if we account for the possibility of a broken lock). If $\Phi(a,s)$ is an empty set it means that the execution of a in s is undefined. We now formally define $\Phi$ .

Let D be a domain in $\mathcal{B}$ . A set of fluent literals is said to be consistent if it does not contain f and $\neg f$ for some fluent f. An interpretation I of the fluents in D is a maximal consistent set of fluent literals of D. A fluent f is said to be true (resp. false) in I if $f \in I$ (resp. $\neg f \in I$ ). The truth value of a fluent formula in I is defined recursively over the propositional connectives in the usual way. For example, $f \wedge g$ is true in I if f is true in I and g is true in I. We say that a formula $\varphi$ holds in I (or I satisfies $\varphi$ ), denoted by $I \models \varphi$ , if $\varphi$ is true in I.

Let u be a consistent set of fluent literals and K a set of static causal laws. We say that u is closed under K if for every static causal law

\begin{equation*}\textbf{caused}(\varphi,f)\end{equation*}

in K, if $u \models \bigwedge_{p \in \varphi} p$ then $u \models f$ . By $Cl_K(u)$ we denote the least consistent set of literals from D that contains u and is also closed under K. It is worth noting that $Cl_K(u)$ might be undefined when it is inconsistent. For instance, if u contains both f and $\neg f$ for some fluent f, then $Cl_K(u)$ cannot contain u and be consistent; another example is that if $u = \{f,g\}$ and K contains

\begin{equation*}\textbf{caused}(\{f\}, h) \quad \quad {and} \quad \quad \textbf{caused}(\{f, g\}, \neg h),\end{equation*}

then $Cl_K(u)$ does not exist because it has to contain both h and $\neg h$ , which means that it is inconsistent.

Formally, a state of D is an interpretation of the fluents in F that is closed under the set of static causal laws $D_C$ of D.

An action a is executable in a state s if there exists an executability proposition

\begin{equation*}\textbf{executable}(a, \varphi)\end{equation*}

in D such that $s \models \bigwedge_{p \in \varphi} p$ . Clearly, if $\varphi = \emptyset$ , then a is executable in every state of D.

The direct effect of an action a in a state s is the set

\begin{equation*}e(a,s) = \left \{f \mid\textbf{causes}(a, f, \varphi ) \in D, s \models \bigwedge_{\textstyle{p \in \varphi}}p \right \}.\end{equation*}

For a domain D, the set of states $\Phi(a,s)$ that may be reached by executing a in s, is defined as follows.

1. 1. If a is executable in s, then

   \begin{equation*}\Phi(a,s) = \{s' \mid s' \mbox{ is a state and }s' =Cl_{D_C}(e(a,s) \cup (s\cap s'))\}; \end{equation*}

2. 2. If a is not executable in s, then $\Phi(a,s) = \emptyset$ .

Intuitively, the states produced by $\Phi(a,s)$ are fixpoints of an equation, obtained by closing (with respect to all static causal laws) the set which includes the direct effects e(a,s) of action a and the fluents whose value does not change as we transition from s to s’ through action a (i.e., $s \cap s'$ ).

The presence of static causal laws introduces non-determinism to action theories, that is, $\Phi(a,s)$ can contain more than one element. For instance, consider the theory with the set of laws

\begin{equation*}\{\textbf{causes}(a,f), \quad \textbf{caused}(\{f, \neg g\}, \neg h), \quad \textbf{caused}(\{f, \neg h\}, \neg g)\}. \end{equation*}

It is easy to check that

\begin{equation*}\Phi(a, \{\neg f, \neg g, \neg h\}) = \{\{f, g, \neg h\}, \{f, \neg g, h\}\}.\end{equation*}

Every domain D in $\mathcal{B}$ has a unique transition function $\Phi$ , and we say $\Phi$ is the transition function of D. We illustrate the definition of the transition function in the next example.

Example 2 For the suitcase domain in Example 1, the initial state, given by the set of laws $\Gamma^s$ , is defined by

\begin{equation*}s_0 = \{up(l_1), \neg up(l_2), locked, \neg holding(k_1), holding(k_2)\}.\end{equation*}

In state $s_0$ , the three actions $open(l_2)$ , $close(l_1)$ , and $close(l_2)$ are executable. $open(l_2)$ is executable since $holding(k_2)$ is true in $s_0$ while $close(l_1)$ and $close(l_2)$ are executable since the theory (implicitly) contains the laws

\begin{equation*}\textbf{executable}(close(l_1),\{\}) {and} \textbf{executable}(close(l_2),\{\})\end{equation*}

which indicate that these two actions are always executable. The following transitions are possible from state $s_0$ :

\begin{eqnarray*} \{\: up(l_1), up(l_2), \neg locked,\neg holding(k_1), holding(k_2) \:\} & \in & \Phi(open(l_2), s_0).\nonumber\\ \{\: up(l_1), \neg up(l_2), locked,\neg holding(k_1), holding(k_2) \:\} & \in & \Phi(close(l_2), s_0).\nonumber\\ \{\: \neg up(l_1), \neg up(l_2), locked, holding(k_1),holding(k_2)\:\} & \in & \Phi(close(l_1), s_0).\nonumber\end{eqnarray*}

$\diamond$

The transition function $\Phi$ is extended to define $\widehat{\Phi}$ for reasoning about effects of action sequences in the usual way. For a sequence of actions $\alpha = \langle a_0,\ldots,a_{n-1} \rangle$ and a state s, $\widehat{\Phi}(\alpha, s)$ is a collection of states defined as follows:

• • $\widehat{\Phi}(\alpha, s) = \{s\}$ if $\alpha = \langle \ \rangle$ ;

• • $\widehat{\Phi}(\alpha, s) = \Phi(a_0, s)$ if $n=1$ ;

• • $\widehat{\Phi}(\alpha, s) = \bigcup_{s' \in \Phi(a_0, s)} \widehat{\Phi}(\alpha', s')$ if $n > 1$ , $ \Phi(a_0, s) \ne \emptyset$ , and $ \widehat{\Phi}(\alpha', s') \ne \emptyset$ for every $s' \in \Phi(a_0,s)$ where $\alpha' = \langle a_1,\ldots,a_{n-1} \rangle$ .

A domain D is consistent if for every action a and state s, if a is executable in s, then $\Phi(a,s) \neq \emptyset$ . An action theory $(D,\Gamma)$ is consistent if D is consistent and $s_0 = \{f \mid\textbf{initially}(f)\in \Gamma\}$ is a state of D. In what follows, we consider only consistent action theories and refer to $s_0$ as the initial state of D. We call a sequence of alternate states and actions $s_0a_0\ldots a_{k-1}s_k$ a trajectory if $s_{i+1} \in \Phi(a,s_i)$ for every $i=0,\ldots,k-1$ .

A planning problem with respect to $\mathcal{B}$ is specified by a triple $\langle D, \Gamma, \Delta \rangle$ where $(D,\Gamma)$ is an action theory in $\mathcal{B}$ and $\Delta$ is a set of fluent literals (or goal). A sequence of actions $\alpha = \langle a_0,\ldots,a_{n-1} \rangle$ is then called an optimistic plan for $\Delta$ if there exists some $s \in \widehat{\Phi}(\alpha, s_0)$ such that $s \models \Delta$ where $s_0$ is the initial state of D. Note that we use the term “optimistic plan” to refer to $\alpha$ , as used by (Eiter et al. Reference Eiter, Faber, Leone, Pfeifer and Polleres2003b), instead of “plan” because the non-determinicity of D does not guarantee that the goal is achieved in every state reachable after the execution of $\alpha$ . However, if D is deterministic, that is, $|\Phi(a,s)| \le 1$ for every pair (a,s) of actions and states, then the two notions of “optimistic plan” and “plan” coincide.

3.1 A direct encoding

The rules of $\Pi(\mathcal{P}, n)$ in this encoding are described by (Son et al. Reference Son, Baral, Nam and McIlraith2006). The main predicates in the program are:

1. 1. holds(F,T) – the fluent literal F is true at time step T;

2. 2. occ(A,T) – the action A occurs at time step T; and

3. 3. possible(A,T) – the action A is executable at time step T.

The program contains two sets of rules. The first set of rules is domain dependent. The rules in the second set are generic and common to all problems. For a set of literals $\varphi$ , we use $holds(\varphi, T)$ to denote the set $\{holds(L, T) \mid L \in \varphi\}$ .

3.1.1 Domain-dependent rules

For each planning problem $\mathcal{P} = \langle D,\Gamma, \Delta \rangle$ , program $\Pi(\mathcal{P}, n)$ contains the following rules:

1. 1. For each element $\textbf{initially}(f)$ of form (4) in $\Gamma$ , the fact

   (5) \begin{equation} holds(f, 0) \leftarrow\end{equation}
   stating that the fluent literal f holds at time step 0.

2. 2. For each executability condition $\textbf{executable}(a, \varphi)$ of form (3) in D, the rule

   (6) \begin{equation} possible(a, T) \leftarrow time(T), holds(\varphi,T)\end{equation}
   stating that it is possible to execute the action a at time step T if $\varphi$ holds at time step T.

3. 3. For each dynamic causal law $\textbf{causes}(a,f, \varphi)$ of form (2) in D, the rule

   (7) \begin{equation} \begin{array}{lll}holds(f, T+1) & \leftarrow & time(T), occ(a, T), holds(\varphi, T)\end{array}\end{equation}
   stating that if a occurs at time step T then the fluent literal f becomes true at $T+1$ if the conditions in $\varphi$ hold.

4. 4. For each static causal law $\textbf{caused}(\varphi, f)$ of form (1) in D, the rule ^{Footnote 5}

   (8) \begin{equation} holds(f, T) \leftarrow time(T), holds(\varphi,T)\end{equation}
   which represents a straightforward translation of the static causal law into a logic programming rule.

5. 5. To guarantee that an action is executed only when it is executable, the constraint

   (9) \begin{equation} \leftarrow time(T), occ(A, T), { not \:} possible(A,T).\end{equation}

We demonstrate the above translation by listing the set of domain dependent rules for the domain from Example 1.

Example 3 Besides the set of facts encoding actions and fluents and the initial state (for each $a \in \mathbf{A}$ , $f \in \mathbf{F}$ and $\textbf{initially}(l)\in \Gamma^s$ ),

\begin{equation*}action(a) \leftarrow fluent(f) \leftarrow holds(l,0) \leftarrow\end{equation*}

the encoding of the suitcase domain in Example 1 contains the following rules for $i=1,2$ :

\begin{equation*}\begin{array}{lll}holds(up(l_i), T+1) & \leftarrow & time(T), occ(open(l_i), T) \\[2pt]holds(\neg up(l_i), T+1) & \leftarrow & time(T), occ(close(l_i), T) \\[2pt]holds(holding(k_i), T+1) & \leftarrow & time(T), occ(get\_key(k_i), T) \\[2pt]possible(open(l_i), T) & \leftarrow & time(T), holds(holding(k_i), T) \\[2pt]holds(locked, T) & \leftarrow & time(T), holds(\neg up(l_i), T) \\[2pt]holds(\neg locked, T) & \leftarrow & time(T), holds(up(l_1), T), holds(up(l_2), T) \\[2pt]possible(close(l_i), T) & \leftarrow & time(T) \\[2pt]possible(get\_key(k_i), T) & \leftarrow & time(T). \\[2pt]\end{array}\end{equation*}

Each of the first six rules corresponds to a law in $D^s$ . The last two rules are added because there is no restriction on the executability condition of $close(l_i)$ or $get\_key(k_i)$ . $\Diamond$

3.1.3 Goal representation

The goal $\Delta$ is encoded by rules defining the predicate goal, which is true whenever $\Delta$ is true, and a rule that enforces that $\Delta$ must be true at time step n. For example, if $\Delta$ is a conjunction of literals $p_1 \wedge \ldots \wedge p_k$ , then the rules

(14) \begin{eqnarray}goal & \leftarrow & holds(p_1, n), \ldots, holds(p_k, n) \end{eqnarray}

(15) \begin{eqnarray} & \leftarrow & { not \:} goal \end{eqnarray}

encode $\Delta$ and enforce that $\Delta$ must be true at time step n.

3.1.4 Correctness of the encoding

Let $\mathcal{P} = (D,\Gamma,\Delta)$ and $\Pi(\mathcal{P},n)$ be the logic program consisting of

• • the set of facts encoding fluents and literals in D;

• • the set of domain-dependent rules encoding D and $\Gamma$ (rules (5)–(9)) in which the domain of T is $\{0,\ldots,n\}$ ;

• • the set of domain-independent rules (rules (10)–(12)) in which the domain of T is $\{0,\ldots,n\}$ ; and

• • the rules (13)–(15).

The following result shows the equivalence between optimistic plans achieving $\Delta$ and answer sets of $\Pi(\mathcal{P},n)$ . To formalize the theorem, we introduce some additional notation. For an answer set M of $\Pi(\mathcal{P},n)$ , we define

\begin{equation*}s_i(M) = \{f \ \mid f {is a fluent literal and} holds(f,i) \in M\}.\end{equation*}

Theorem 1 For a planning problem $\langle D,\Gamma,\Delta \rangle$ with a consistent action theory $(D,\Gamma)$ , $s_0a_0\ldots a_{n-1}s_n$ is a trajectory achieving $\Delta$ iff there exists an answer set M of $\Pi(\mathcal{P},n)$ such that

1. 1. $occ(a_i,i) \in M$ for $i \in \{0,\ldots,n-1\}$ and

2. 2. $s_i = s_i(M)$ for $i \in \{0,\ldots,n\}$ .

Remark 1

1. 1. The proof of Theorem 1 relies on the following observations: M is an answer set of $\Pi(\mathcal{P},n)$ iff

   • • for every i such that $0 \le i < n$ , there exists some $a_i \in \mathbf{A}$ such that $occ(a_i, i) \in M$ and $a_i$ is executable in $s_i(M)$ ;

   • • $s_0(M)$ is the initial state of the action theory $(D,\Gamma)$ and is consistent. Furthermore, for every i such that $0 \le i < n$ , $s_{i+1}(M) \in \Phi(a_i, s_i(M))$ ; and

   • • $\Delta$ is true in $s_n(M)$ .

The theorem is similar to the correspondence between histories and answer sets explored by (Lifschitz and Turner Reference Lifschitz and Turner1999) and by (Son et al. Reference Son, Baral, Nam and McIlraith2006).

1. 2. If $(D,\Gamma)$ is deterministic then Theorem 1 can be simplified to “ $a_0,a_1,\ldots,a_{n-1}$ is a plan achieving $\Delta$ iff there exists an answer set M of $\Pi(\mathcal{P},n)$ such that $occ(a_i,i) \in M$ for $i \in \{0,\ldots,n-1\}$ .”

2. 3. A different variant of this encoding, which uses $f(\vec{x}, t)$ and $\neg f(\vec{x}, t)$ instead of $holds(f(\vec{x}), t)$ and $holds(\neg f(\vec{x}), t)$ , respectively, can be found in several papers related to answer set planning, for example, in the papers by (Lifschitz Reference Lifschitz1999) and (2002).

3. 4. The action language $\mathcal{B}$ could be extended with various features such as default fluents, effects of action sequences, etc. as discussed by (Gelfond and Lifschitz Reference Gelfond and Lifschitz1998). These features can be easily included in the encoding of $\Pi(\mathcal{P},n)$ . On the other hand, such features are rarely considered in action domains used by the planning community. For this reason, we do not consider such features in this survey.

4. 5. Readers familiar with current answer set solvers such as clingo or dlv could be wondering why $holds(\neg f, t)$ is used instead of a perhaps more intuitive $\neg holds(f,t)$ . Indeed, the former can be replaced by the latter. The use of $holds(\neg f, t)$ is influenced by early Prolog programs written for reasoning about actions and changes by Michael Gelfond. A Prolog program that translates a planning problem to its ASP encoding can be found at https://www.cs.nmsu.edu/ tson/ASPlan/Knowledge/translate.pl.

5. 6. Different approaches to integrate various types of knowledge to answer set planning can be found in the work by (Dix et al. Reference Dix, Kuter and Nau2005) and (Son et al. Reference Son, Baral, Nam and McIlraith2006).

3.2 Meta encoding

The meta encoding presented in this section encodes a planning problem $\mathcal{P} = \langle D, \Gamma, \Delta \rangle$ as a set of facts, in addition to a set of domain-independent rules for reasoning about effects of actions. To distinguish this encoding from the previous one, we denote this encoding with $\Pi^m(\mathcal{P},n)$ . In this encoding, a set $\varphi$ is represented using the atom $set(s_\varphi)$ , where $s_\varphi$ is a new atom associated to $\varphi$ , and a set of atoms of the form $\{member(s_\varphi, p) \mid p \in \varphi \}$ . The laws in D are represented by the set of facts

(16) \begin{eqnarray}caused(f, s_{\mathit{sf}}). & set(s_{\mathit{sf}}). & s_{\mathit{sf}} {is the identifier for } \varphi {in } \textbf{caused}(f, \varphi) {in} D \end{eqnarray}

(17) \begin{eqnarray}causes(a, f, s_{\mathit{df}}).& set(s_{\mathit{df}}). & s_{\mathit{df}} {is the identifier for } \varphi {in } \textbf{causes}(a, f, \varphi) {in} D \end{eqnarray}

(18) \begin{eqnarray}executable(a, s_a). & set(s_a). & s_{a} {is the identifier for } \varphi {in} \textbf{executable}(a, \varphi) {in} D\;\;\;\;\end{eqnarray}

and the set of facts encoding $s_{\mathit{sf}}$ , $s_{\mathit{df}}$ , and $s_a$ .

In addition to the action generation rule (10), the inertial rules (11)–(12), the goal representation rules (14)–(15), and the constraint stating that actions can occur only when they are executable (9), the program $\Pi^m(\mathcal{P},n)$ contains the following rules for reasoning about effects of actions:

(19) \begin{eqnarray}holds(S, T) & \leftarrow & time(T), set(S), \end{eqnarray}

(20) \begin{eqnarray} & & holds(F,T): fluent(F), member(S,F); \nonumber \\[4pt] & & holds(\neg F, T): fluent(F), member(S, \neg F). \nonumber \\[4pt]holds(L, T+1) & \leftarrow & time(T), causes(A, F, S), occ(A, T), holds(S, T) \end{eqnarray}

(21) \begin{eqnarray}holds(L, T) & \leftarrow & time(T), caused(L, S), holds(S, T) \end{eqnarray}

(22) \begin{eqnarray}possible(A, T) & \leftarrow & time(T), executable(A, S), holds(S, T) \end{eqnarray}

Rule (19) defines the truth of a set of fluents S at time step T, by declaring that S holds at T if all of its members are true at T. The intuition behind the rules (20)–(22) is clear. Similarly to Theorem 1, answer sets of $\Pi^m(\mathcal{P},n)$ correspond one-to-one to possible solutions (optimistic plans) of $\mathcal{P}$ .

3.3 Adding heuristics: Going for performance

By using ASP systems for solving planning problems, we employ general purpose systems rather than genuine planning systems. In particular, the distinction between action and fluent variables or fluent variables of successive states completely eludes the ASP system. Pioneering work in this direction was done by (Rintanen Reference Rintanen2012), where the implementation of SAT solvers was modified in order to boost performance of SAT planning. Inspired by this research direction, (Gebser et al. Reference Gebser, Kaufmann, Otero, Romero, Schaub and Wanko2013) developed a language extension for ASP systems that allows users to declare heuristic modifiers that take effect in the underlying ASP system clingo.

More precisely, a heuristic directive is of form

\begin{equation*}\#\mathit{heuristic}\ a:b_1,\dots,b_m.\,[w,m],\end{equation*}

where a is an atom and $b_1,\dots,b_m$ is a conjunction of literals; w is a numeral term and m a heuristic modifier, indicating how the solver’s heuristic treatment of a should be changed whenever $b_1,\dots,b_m$ holds. Clingo distinguishes four primitive heuristic modifiers:

1. init for initializing the heuristic value of a with w,

2. factor for amplifying the heuristic value of a by factor w,

3. level for ranking all atoms; the rank of a is w,

4. sign for attributing the sign of w as truth value to a.

For instance, whenever a is chosen by the solver, the heuristic modifier sign enforces that it becomes either true or false depending on whether w is positive or negative, respectively. The other three modifiers act on the atoms’ heuristic values assigned by the ASP solver’s heuristic function. ^{Footnote 6} Moreover, for convenience, clingo offers the heuristic modifiers true and false that combine level and sign statement.

With them, we can directly describe the heuristic restriction used in the work by (Rintanen Reference Rintanen2011) to simulate planning by iterated deepening $A^*$ (Korf Reference Korf1985) through limiting choices to action variables, assigning those for time T before those for time T+1, and always assigning truth value true (where n is a constant indicating the planning horizon):

\begin{equation*}\#\mathit{heuristic}\ \mathit{occ}(A,T) : \mathit{action}(A), \mathit{time}(T).\, [n-T,\mathit{true}].\end{equation*}

Inspired by, and yet different from the work by (Rintanen Reference Rintanen2012), (Gebser et al. Reference Gebser, Kaufmann, Otero, Romero, Schaub and Wanko2013) devise a dynamic heuristic that aims at propagating fluents’ truth values backwards in time. Attributing levels via n-T+1 aims at proceeding depth-first from the goal fluents.

\begin{align*}\#\mathit{heuristic}\ \mathit{holds}(F,T-1) &: \mathit{holds}(F,T).\, [n-T+1,\mathit{true}]\\[4pt]\#\mathit{heuristic}\ \mathit{holds}(F,T-1) &: fluent(F), time(T), not \mathit{holds}(F,T).\, [n-T+1,\mathit{false}].\end{align*}

In an experimental evaluation conducted by (Gebser et al. Reference Gebser, Kaufmann, Otero, Romero, Schaub and Wanko2013), this heuristic led to a speed-up of up to two orders of magnitude on satisfiable planning problems.

3.4 Context: Classical planning

Classical planning has been an intensive research area for many years. The famous Shakey robot ^{Footnote 7} used a planner for path planning. This project also led to the introduction of the Stanford Research Institute Problem Solver (STRIPS) language (Fikes and Nilsson Reference Fikes and Nilsson1971), the first representation language for planning domain description. This language has since evolved into the Planning Domain Definition Language (PDDL) (Ghallab et al. Reference Ghallab, Howe, Knoblock, McDermott, Ram, Veloso, Weld and Wilkins1998), a major planning domain description language. We noted that PDDL with state constraints is as expressive as $\mathcal{B}$ . It is worth noticing that state constraints are often not considered by the planning community even though the benefit of dealing directly with state constraints is known (Thiebaux et al. Reference Thiebaux, Hoffmann and Nebel2003). Furthermore, it is often assumed that state constraints in PDDL are stratified, for example, the dependency graph among fluent literals ^{Footnote 8} should be cycle free.

Several planning algorithms have been developed and implemented such as forward or backward search over the state space (see, a survey by Hendler et al. Reference Hendler, Tate and Drummond1990) and search in the plans space (a.k.a. partial order planning, see, e.g. a survey by Weld Reference Weld1994). Such research also led to the development of domain-dependent planners which utilize domain knowledge to improve their scalability and efficiency (e.g., hierarchical planning systems Sacerdoti Reference Sacerdoti1974). Researchers realized early on that systematic state space search would not yield planning systems that are sufficiently scalable and efficient for practical applications. A significant milestone in the development of domain-independent planners is the invention of GraphPlan by (Blum and Furst Reference Blum and Furst1997). The basic data structure of GraphPlan, the planning graph, is an important resource for the development of planning heuristics (Kambhampati et al. Reference Kambhampati, Parker and Lambrecht1997). It plays a key role in the success of heuristic planners such as FF (Hoffmann and Nebel Reference Hoffmann and Nebel2001) and HSP (Bonet and Geffner Reference Bonet and Geffner2001) which dominate several International Planning Competitions (Long et al. Reference Long, Kautz, Selman, Bonet, Geffner, Köhler, Brenner, Hoffmann, Rittinger, Anderson, Weld, Smith and Fox2000; Bacchus Reference Bacchus2001; Gerevini et al. Reference Gerevini, Dimopoulos, Haslum and Saetti2004). This success is followed by several other systems (Helmert Reference Helmert2006; Richter and Helmert Reference Richter and Helmert2009; Helmert et al. Reference Helmert, Röger, Seipp, Karpas, Hoffmann, Keyder, Nissim, Richter and Westphal2011), whose impressive performance can be attributed to advances in the representation language for planning (e.g., the language SAS $^+$ that supports a compact representation of states Bäckström and Nebel Reference Bäckström and Nebel1995) and their underlying heuristics constructed via reachability analysis and techniques such as landmarks recognition, abstraction, operator ordering, and decomposition (Bonet and Helmert Reference Bonet and Helmert2010; Zhu and Givan Reference Zhu and Givan2004; Helmert and Domshlak Reference Helmert and Domshlak2009; Helmert and Geffner Reference Helmert and Geffner2008; Helmert and MattmÜller Reference Helmert and MattmÜller2008; Hoffmann et al. Reference Hoffmann, Porteous and Sebastia2004; Hoffmann Reference Hoffmann2005; Pommerening et al. Reference Pommerening, Röger, Helmert, Cambazard, Rousseau and Salvagnin2020; Richter and Helmert Reference Richter and Helmert2009; Röger and Helmert Reference Röger and Helmert2010; Vidal and Geffner Reference Vidal and Geffner2006). All of these planning systems implement a heuristic search algorithm. Therefore, their scalability and efficiency are heavily dependent on the implemented heuristic, that is, how discriminant is the heuristic and how efficient can it be computed. In most systems, completeness and efficiency have to be traded off. In some planner, an automatic mechanism for returning to systematic search is established whenever the heuristic deems not useful (e.g., the system FF).

The idea of using automated theorem solvers in planning can be traced back to the work by (Green Reference Green1969) who demonstrated that automated reasoning systems can be used for planning. A significant step in this direction is proposed by (Kautz and Selman Reference Kautz and Selman1992) who introduced satisfiability planning and showed that with an improved satisfiability solver, SAT-based planning can be competitive with search based planners (Kautz et al. Reference Kautz, McAllester, Selman, Aiello, Doyle and Shapiro1996). This approach was later advanced by several other researchers and results in many SAT-based or logic programming-based planning systems (Chen et al. Reference Chen, Huang, Xing and Zhang2009; Dimopoulos et al. Reference Dimopoulos, Nebel and Köhler1997; Rintanen et al. Reference Rintanen, Heljanko and Niemelä2006; Robinson et al. Reference Robinson, Gretton, Pham and Sattar2009; Rintanen Reference Rintanen2012) that are often competitive or more efficient comparing to search-based planners. Constraint satisfaction techniques have also been employed in planning (Kautz and Walser Reference Kautz and Walser1999; Do and Kambhampati Reference Do and Kambhampati2003; Sideris and Dimopoulos Reference Sideris and Dimopoulos2010; Dovier et al. Reference Dovier, Formisano and Pontelli2009). As we have mentioned in the introduction, the success of SAT-base planning is likely the source of inspiration for the use of logic programming with answer sets semantics for planning. Indeed, there are several similarities between a SAT-based encoding of a planning program proposed by (Kautz and Selman Reference Kautz and Selman1992) and its ASP-encoding presented in this section. They share the following features:

• • the use of time steps in representing the planning horizon: SAT-based encoding prefers to use $f(\vec{x},t)$ and $\neg f(\vec{x},t)$ instead of $holds(f(\vec{x}),t)$ and $holds(\neg f(\vec{x}),t)$ ;

• • the encoding of actions’ executability and the effects of actions;

• • the encoding of the frame axioms; and

• • the encoding for action generation.

In this sense, one can say that SAT-planning and answer set planning are cousins to each other. Both relish the use of knowledge representation techniques and the development of logical solvers in planning. The key difference between them lies in the underlying representation language and solver.

Green’s idea has also been investigated in event calculus planning. The main reasoning system behind this approach is the event calculus, which is introduced by (Kowalski and Sergot Reference Kowalski and Sergot1986) for reasoning about narratives and database updates. An action theory (or a planning problem) can be described by an event calculus program that is similar to the program described in Section 3.1. In particular, this program consists of rules encoding the initial state, effects of actions, and solution to the frame axiom. Earlier development of event calculus does not consider static causal laws. This issue is addressed by (Shanahan Reference Shanahan1999). (Eshghi Reference Eshghi1988) introduced a variant of the event calculus, called EVP (an event calculus for planning), and combined it with abductive reasoning to create ABPLAN. We believe that this is the first planning system that integrates event calculus and abduction. (Denecker et al. Reference Denecker, Missiaen and Bruynooghe1992) developed SLDNFA, a procedure for temporal reasoning with abductive event calculus, and showed how this procedure can be used for planning. The authors of SLDNFA continued this line of research and developed CHICA (Missiaen et al. Reference Missiaen, Bruynooghe and Denecker1995). The underlying algorithm of this system is a specialized version of the abductive reasoning procedure for event calculus. An interesting feature of this system is that it allows for the user to specify the search strategy and heuristics at the domain level, allowing for domain dependent information to be exploited in the search for a solution. Other proof procedures for event calculus planning can be founded in the work by (Endriss et al. Reference Endriss, Mancarella, Sadri, Terreni and Toni2004), (Mueller Reference Mueller2006), and (Shanahan Reference Shanahan2000) and 1997. It is worth noting that a major discussion in these work is the condition for the soundness and completeness of the proof procedures, that is, the planning systems. To the best of our knowledge, most of the event calculus based planning systems are implemented on a Prolog system and no experimental evaluation against other planning systems has been conducted.

4.1 Conformant planning with a security check using logic program

(Eiter et al. Reference Eiter, Faber, Leone, Pfeifer and Polleres2003b) introduced the system dlv $^\mathcal{K}$ for planning with incomplete information. The system employs a representation language that is richer than the language $\mathcal{B}$ , since it considers additional features such as defaults and effects after a sequence of actions. For simplicity of the presentation, we present the approach used in dlv $^\mathcal{K}$ for conformant planning problems specified in $\mathcal{B}$ . We note that the original dlv $^\mathcal{K}$ employs the direct encoding of planning problems as described in Remark 1, Item 3. We adapt it to the encoding used in the previous section.

dlv $^\mathcal{K}$ generates a conformant plan for a problem $\mathcal{P}$ in two steps. The first step consists of generating an optimistic plan; the second step is the verification that such plan is a secure plan, since an optimistic plan is not necessarily a secure plan. dlv $^\mathcal{K}$ implements Algorithm 1.

The two tasks in Lines 1 and 2 in Algorithm 1 are implemented using different ASP programs. The generation step (Line 1) can be done using the program $\Pi_{c_{dlv}}(\mathcal{P},n)$ which consists of the program $\Pi(\mathcal{P},n)$ together with the rules that specify the values of unknown fluents in the initial state:

(23) \begin{equation} holds(f, 0) \vee holds(\neg f, 0) \leftarrow \quad\quad (f {is a fluent and} \{f, \neg f\} \cap \delta^0 = \emptyset).\end{equation}

Algorithm 1: dlv $^\mathcal{K}$ Algorithm

It is easy to see that any answer set of $\Pi_{c_{dlv}}(\mathcal{P},n)$ contains an optimistic plan (Theorem 1). Assume that $\alpha = \langle a_0,\ldots,a_{n-1} \rangle$ is the sequence of actions generated by program $\Pi_{c_{dlv}}(\mathcal{P},n)$ , dlv $^\mathcal{K}$ takes $\alpha$ and the action theory $(D, \delta^0)$ and creates a program that checks whether or not $\alpha$ is a secure plan. If it is, then dlv $^\mathcal{K}$ returns $\alpha$ . Otherwise, it continues computing an optimistic plan and verifying that the plan is secure, until there are no additional optimistic plans available, which indicates that the problem has no solution. We next discuss the main idea in the second step of dlv $^\mathcal{K}$ (Line 2).

Intuitively, if $\alpha$ is a secure plan, then its execution in every possible initial state results in a final state in which the goal is satisfied. In other words, $\alpha$ is not a secure plan if there exists an initial state in which the execution of $\alpha$ is not possible. This can happen in the following situations:

• • the goal is not satisfied after the execution of $\alpha$ ;

• • some action $a_i$ in $\alpha$ is not executable, that is, $possible(a_i, i)$ is not true; or

• • some constraints are violated.

Let $Check(\mathcal{P}, \alpha, n)$ be the program obtained from $\Pi_{c_{dlv}}(\mathcal{P},n)$ by introducing a new atom, notex, which denotes that $\alpha$ is not secure and

• • replacing (9) with the rule

  \begin{equation*}notex \leftarrow time(T), occ(A, T), { not \:} possible(A,T)\end{equation*}

• • replacing (10) with the set of action occurrences

  \begin{equation*}\{occ(a_i,i) \mid i=0,\ldots,n-1\}\end{equation*}

• • replacing (13) with

  \begin{equation*}\begin{array}{rcl} notex & \leftarrow & fluent(F), T > 0, holds(F, T), holds(\neg F, T) \\[4pt] & \leftarrow & fluent(F), holds(F, 0), holds(\neg F, 0)\end{array}\end{equation*}

• • replacing (8), for each constraint $\textbf{caused}(\varphi, \mathit{false})$ , with the rule

  \begin{equation*}notex \leftarrow time(T), T > 0, holds(\varphi,T)\end{equation*}

• • replacing (15) with

  \begin{equation*}\leftarrow goal, { not \:} notex.\end{equation*}

If $Check(\mathcal{P}, \alpha, n)$ has an answer set M then either the goal is not satisfied or $notex \in M$ . Observe that the rules replacing (13) and (8) guarantee that $\{f \mid holds(f, 0) \in M\} \cup \{\neg f \mid holds(\neg f, 0) \in M\}$ is a state of the action domain in $\mathcal{P}$ . If the goal is not satisfied and $notex\not\in M$ , then we have found an initial state from which the execution of $\alpha$ does not achieve the goal. Otherwise, $notex\in M$ implies that

• • an action $a_i$ is not executable in the state at time step i or

• • there is some step $j > 0$ such that the state at time step j is inconsistent or violates some static causal laws.

In either case, this means that there exists some initial state in which the execution of $\alpha$ fails, that is, $\alpha$ is not a secure plan. On the other hand, if $Check(\mathcal{P}, \alpha, n)$ has no answer sets, then there are no possible initial states such that the execution of $\alpha$ fails, that is, $\alpha$ is a secure plan.

4.2 Approximation-based conformant planning

Approximation-based conformant planning deals with the complexity of conformant planning by proposing a deterministic approximation of the transition function $\Phi$ , denoted by $\Phi^a$ , which maps pairs of actions and partial states such that for every $\delta$ , $\delta'$ , and s such that $\Phi^a(a, \delta) = \delta'$ and $ s \in comp(\delta)$ , it holds that

• • a is executable in s; and

• • $\delta' \subseteq s'$ for every $s' \in \Phi(a, s)$ .

Intuitively, the above conditions require $\Phi^a$ to be sound with respect to $\Phi$ . We say that $\Phi^a$ is sound approximation of $\Phi$ if the above conditions are satisfied.

The function $\Phi^a$ is extended to define $\widehat{\Phi^a}$ in the similar fashion as $\widehat{\Phi}$ : for an action sequence $\alpha = \langle a_0, \ldots, a_{n-1} \rangle$ ,

• • $\widehat{\Phi^a}(\alpha, \delta) = \delta$ if $\alpha = \langle \ \rangle$ ;

• • $\widehat{\Phi^a}(\alpha, \delta) = \Phi^a(a_0, \delta)$ for $n=1$ ; and

• • $\widehat{\Phi^a}(\alpha, \delta) = \widehat{\Phi^a}(\alpha', \Phi^a(a_0, \delta))$ where $\alpha' = \langle a_1, \ldots, a_{n-1} \rangle$ , if $\widehat{\Phi^a}(\beta, \delta)$ is defined for every prefix $\beta$ of $\alpha$ .

Given a sound approximation $\Phi^a$ , we have that if $\widehat{\Phi^a}(\alpha, \delta) = \delta'$ then for every $ s \in comp(\delta)$ , $\widehat{\Phi}(\alpha,s) \ne \emptyset$ and for every $s' \in \widehat{\Phi}(\alpha,s) $ , $\delta' \subseteq s'$ . This means that a sound approximation can be used for computing conformant plans. In the rest of this section, we define a sound approximation of $\Phi$ and use if for conformant planning. Because the program $\Pi(\mathcal{P},n)$ implements $\Phi$ , we define the approximation by describing a program $\Pi^a(\mathcal{P},n)$ approximating $\Phi$ .

Let a be an action and $\delta$ be a partial state. We say that a is executable in $\delta$ if a occurs in an executability condition (3) and each literal in the precondition of the law holds in $\delta$ . A fluent literal l is a direct effect (resp. a possible direct effect) of a in $\delta$ if there exists a dynamic causal law (2) such that $\psi$ holds (resp. possibly holds) in $\delta$ . Observe that if a is executable in $\delta$ then it is executable in every state $s \in comp(\delta)$ . Furthermore, the direct effects of a in $\delta$ are also the direct effects of a in s, which in turn are the possible direct effects of a in $\delta$ .

We next present the program $\Pi^a(\mathcal{P},n)$ . Atoms of $\Pi^a(\mathcal{P},n)$ are atoms of $\Pi(\mathcal{P},n)$ and those formed by the following (sorted) predicate symbols:

• • de(l,T) is true if the fluent literal l is a direct effect of an action that occurs at the previous time step; and

• • ph(l,T) is true if the fluent literal l possibly holds at time step T.

Similar to $holds(\varphi, T)$ , we write $\rho(\varphi,T) = \{ \rho(l,T) \mid l \in \varphi \}$ and ${ not \:} \rho(\varphi,T) = \{{ not \:} \rho(l,T) \mid l \in \varphi \}$ for $\rho \in \{holds, de, ph\}$ . The rules in $\Pi^a(\mathcal{P},n)$ include most of the rules from $\Pi(\mathcal{P},n)$ , except for the inertial rules, which need to be changed. In addition, it includes rules for reasoning about the direct and possible effects of actions.

1. 1. For each dynamic causal law (2) in D, $\Pi^a(\mathcal{P},n)$ contains the rule (7) and the next rule

   (24) \begin{eqnarray}de(f, T+1) & \leftarrow & time(T), occ(a,T), holds(\varphi,T). \end{eqnarray}
   This rule indicates that f is a direct effect of the execution of a. The possible effects of a at T are encoded using the rule
   (25) \begin{equation} ph(f,T+1) \leftarrow time(T), occ(a,T), { not \:} holds(\overline{\varphi}, T) , { not \:} de(\overline{f},T+1)\end{equation}
   which says that f might hold at $T+1$ if a occurs at T and the precondition $\varphi$ possibly holds at T.

2. 2. For each static causal law (1) in D, $\Pi^a(\mathcal{P},n)$ contains the rule (8) and the next rule

   (26) \begin{eqnarray}ph(f,T)& {\leftarrow} & time(T), ph(\varphi,T). \end{eqnarray}
   This rule propagates the possible holds relation between fluent literals.

3. 3. The rule (6) stating that a can occur if its executability condition is satisfied.

4. 4. The inertial law is encoded as follows:

   (27) \begin{eqnarray}ph(L,T+1) & \leftarrow & time(T), fluent(L), { not \:} holds(\neg {L},T), { not \:} de(\neg {L},T+1) \quad \quad \end{eqnarray}
   (28) \begin{eqnarray}ph(\neg L,T+1) & \leftarrow & time(T), fluent(L), { not \:} holds( {L},T), { not \:} de( {L},T+1) \end{eqnarray}
   (29) \begin{eqnarray}holds(L,T) & \leftarrow & time(T), fluent(L), { not \:} ph(\neg {L},T), T \ne 0. \end{eqnarray}
   (30) \begin{eqnarray}holds(\neg L,T) & \leftarrow & time(T), fluent(L), { not \:} ph({L},T), T \ne 0. \end{eqnarray}
   These rules capture the fact that L holds at time moment $T > 0$ if its negation cannot possibly hold at T. Furthermore, L possibly holds at time moment $T+1$ if its negation does not hold at T and is not a direct effect of the action occurring at T. These rules, when used in conjunction with the rules (24)–(25), compute the effects of the occurrence of action at time moment T.

5. 5. $\Pi^a(\mathcal{P},n)$ also contains the rules of the form (9), (10), (13), and the rule encoding the initial state and the goal state as in $\Pi(\mathcal{P},n)$ .

It can be shown that if $\delta$ is a partial state and x is an action executable in $\delta$ then the program $\Pi^a(\mathcal{P},1) \cup \{occ(x, 0)\}$ , where $\mathcal{P} = \langle D, \delta, \emptyset \rangle$ , has a unique answer set M and $\{f \mid holds(f, 1) \in M\}$ is a partial state of D. For this reason, $\Pi^a(\mathcal{P},n)$ can be used to define a sound approximation $\Phi^a$ of $\Phi$ . The soundness of $\Phi^a$ is discussed in details by (Tu et al. Reference Tu, Son, Gelfond and Morales2011). This property indicates that $\Pi^a(\mathcal{P},n)$ can be used as an ASP implementation of a conformant planner. The planner CPasp, as described by (Tu et al. Reference Tu, Son, Gelfond and Morales2011), employs this implementation.

4.3 Context: Conformant planning

As with classical planning, several search-based conformant planners have been developed during the last three decades. Among them are GPT (Bonet and Geffner Reference Bonet and Geffner2000), CGP (Smith and Weld Reference Smith and Weld1998), CMBT (Cimatti and Roveri Reference Cimatti and Roveri2000), Conformant-FF (CFF) (Hoffmann and Brafman Reference Hoffmann and Brafman2006), KACMBP (Cimatti et al. Reference Cimatti, Roveri and Bertoli2004), POND (Bryce et al. Reference Bryce, Kambhampati and Smith2006), t0 (Palacios and Geffner Reference Palacios and Geffner2007; Palacios and Geffner Reference Palacios and Geffner2009), t1 (Albore et al. Reference Albore, Ramrez and Geffner2011), CpA ^{Footnote 9} (Son et al. Reference Son, Tu, Gelfond and Morales2005a; Tran et al. Reference Tran, Nguyen, Pontelli and Son2009), CpLs (Nguyen et al. Reference Nguyen, Tran, Son and Pontelli2011), DNF (To et al. Reference To, Pontelli and Son2009), CNF (To et al. Reference To, Pontelli and Son2010a), PIP (To et al. Reference To, Pontelli and Son2010b), GC[LAMA] (Nguyen et al. Reference Nguyen, Tran, Son and Pontelli2012), and CPCES (Grastien and Scala Reference Grastien and Scala2020). With the exception of CMBT, KACMBP, t0, and GC[LAMA], the others planners are forward search-based planners.

Differently from classical planning, a significant hurdle in the development of an efficient and scalable conformant planner is the size of the initial belief state and the size of the search space, which is double exponential in the size of the planning problem (see, e.g., the work by Tran et al. Reference Tran, Nguyen, Son and Pontelli2013 for a detailed discussion on this issue). Each of the aforementioned planners deals with this challenge in a different way. Different representations of belief states are used in CFF, DNF, CNF, and PIP. Specifically, CFF and t1 make use of an implicit representation of a belief state as a sequence of actions from the initial state to the belief state. KACMBP, CMBP, and POND use a BDD-based representation (Bryant Reference Bryant1992). CpA approximates a belief state using a set of subsets of states (partial states). t0 and GC[LAMA] translate a conformant planning problem to a classical planning problem and use classical planners to compute solutions, avoiding the need to deal with an explicit belief state representation. Additional improvements have been proposed in terms of heuristics (Bryce et al. Reference Bryce, Kambhampati and Smith2006) and techniques to reduce the size of the initial belief state, such as the $\textbf{oneof}$ -combination technique (Tran et al. Reference Tran, Nguyen, Son and Pontelli2013). Such a technique is useful for planners employing an explicit disjunctive representation of belief states, as in CpA (Tran et al. Reference Tran, Nguyen, Son and Pontelli2013) and DNF (To et al. Reference To, Pontelli and Son2009); a significant amount of work is required to apply this technique to other planners, due to the different representations they use. Likewise, the $\textbf{oneof}$ -relaxation technique proposed by (To et al. Reference To, Pontelli and Son2010a) is useful in CNF but is difficult to use in other planners. Additional techniques proposed to improve performance include extensions of the GraphPlan to deal with incomplete information, used in CGP, backward search algorithms, as in CMBT, landmarks, used in CpLs, and sampling technique, used in CPCES.

SAT-based conformant planning is studied by several researchers (Castellini et al. Reference Castellini, Giunchiglia and Tacchella2003; Palacios and Geffner Reference Palacios and Geffner2005; Rintanen Reference Rintanen1999). The system C-Plan (Castellini et al. Reference Castellini, Giunchiglia and Tacchella2003) has similarities to dlv $^\mathcal{K}$ , in that it starts with a translation of the planning problem into a SAT-problem, identifies a potential plan, and then validates the plan. (Palacios and Geffner Reference Palacios and Geffner2005) propose the system compile-project-sat, which uses a single call to the SAT-solver to compute a conformant plan. They show that the validity check can be done in linear time if the planning problem is encoded in a logically equivalent theory in deterministic decomposable negation normal form (d-DNNF). As compile-project-sat calls the SAT-solver only once, it is similar to CPasp. However, compile-project-sat is complete, while CPasp is not. The system QBFPlan by (Rintanen Reference Rintanen1999) differs from C-Plan and compile-project-sat in that it translates the problem into a QBF-formula and uses a QBF-solver to compute the solutions. A detailed comparison between these planning systems with CPasp, directly or indirectly, can be found in the paper by (Tu et al. Reference Tu, Son, Gelfond and Morales2011).

5.1 Action language $\mathcal{B}$ with sensing actions and conditional plans

In order to solve the planning problem in Example 5, sensing actions are necessary. Intuitively, the execution of a sensing action does not change the world; instead, it changes the knowledge of the action’s performer. We extend the language $\mathcal{B}$ with knowledge laws of the following form:

(31) \begin{eqnarray}& \textbf{determines}(a,\theta), \end{eqnarray}

where $\theta$ is a set of fluent literals. An action occurring in a knowledge law is referred to as a sensing action. The knowledge law states that the values of the literals in $\theta$ , sometimes referred to as sensed literals, will be known after a is executed. It is assumed that the literals in $\theta$ are mutually exclusive, that is,

1. 1. for every pair of literals g and g’ in $\theta$ , $g \ne g'$ , the theory contains the static causal law

   \begin{equation*}\textbf{caused}(\{g\}, \neg g')\end{equation*}
   and

2. 2. for every literal g in $\theta$ , the theory contains the static causal law

   \begin{equation*}\textbf{caused}(\{\neg g' \mid g' \in \theta \setminus \{ g \}\}, g).\end{equation*}

We refer to this collection of static causal laws as $\textbf{oneof}(\theta)$ . We sometimes write $\textbf{determines}(a,f)$ as a shorthand for $\textbf{determines}(a,\{f,\neg f\}).$

Example 6 The planning problem instance $\mathcal{P}_{window} = (D_{window},\Gamma_{window},\Delta_{window})$ in Example 5 can be represented as follows.

\begin{equation*}D_{window} = \left \{\begin{array}{lll}\textbf{executable}(push\_up, \{ closed\}) \\[2pt]\textbf{executable}(push\_down, \{ open\}) \\[2pt]\textbf{executable}(flip\_lock, \{ \neg open\}) \\\\\textbf{causes}(push\_down, closed, \{\}) \\[2pt]\textbf{causes}(push\_up, open, \{\}) \\[2pt]\textbf{causes}(flip\_lock, locked, \{closed\}) \\[2pt]\textbf{causes}(flip\_lock, closed, \{locked\}) \\\\\textbf{oneof}(\{open, locked, closed\})\\[2pt]\\\textbf{determines}(check, \{open,closed,locked\})\end{array}\right .\end{equation*}

\begin{equation*}\Gamma_{window} \;\; = \; \left \{\begin{array}{lll}\textbf{initially}(\neg open)\end{array}\right \}\end{equation*}

\begin{equation*}\Delta_{window} = \{ locked \}.\end{equation*}

It has been pointed out by several researchers (Warren Reference Warren1976; Peot and Smith Reference Peot and Smith1992; Pryor and Collins Reference Pryor and Collins1996; Levesque Reference Levesque1996; Lobo et al. Reference Lobo, Mendez and Taylor1997; Son and Baral Reference Son and Baral2001; Turner Reference Turner2002) that the notion of a plan needs to be extended beyond a sequence of actions, in order to allow conditional statements such as if-then-else, while-do, or case-endcase to deal with incomplete information and sensing actions. If we are interested in bounded-length plans, then the following notion of conditional plans is sufficient.

Clearly, the notion of a conditional plan is more general than the notion of a plan as a sequence of actions. We refer to the conditional plan in Item 3 of Definition 1 as a case-plan and the $g_j \rightarrow p_j$ ’s as its branches. Under the above definition, the following are two possible conditional plans in the domain $D_{window}$ :

\begin{equation*}p_1 = \langle push\_down;flip\_lock \rangle\end{equation*}

\begin{equation*}p_2 = \langle check; \; \textbf{cases} \left (\begin{array}{lll}open & \rightarrow & [] \\[2pt]closed & \rightarrow & [flip\_lock] \\[2pt]locked & \rightarrow & []\end{array}\right ) \rangle\end{equation*}

The semantics of the language $\mathcal{B}$ with knowledge laws also needs to be extended to account for sensing actions. Observe that, since it is possible that the initial state of the planning problem is incomplete, we will continue using the approximation $\Phi^a$ proposed in the previous section as well as other notions, such as partial states, a fluent literal holds or possibly holds in a partial state, etc. To reason about the effects of sensing actions in a domain D, we define

(32) \begin{equation} \Phi^a(a,\delta) = \{Cl_{D}(\delta \cup \{g \}) g \in \theta {and}Cl_{D}(\delta \cup \{g\}) {is consistent}\},\end{equation}

where a is a sensing action executable in $\delta$ and $\theta$ is the set of sensed literals of a. If a is not executable in $\delta$ then $\Phi^a(a,\delta) = \bot$ (undefined). The definition of $\Phi^a(a,\delta)$ for a non-sensing action is defined as in the previous section. Intuitively, the execution of a can result in several partial states, in each of which exactly one sensed-literal in $\theta$ holds.

As an example, consider ${D}_{window}$ in Example 5 and a partial state $\delta_1 = \{\neg open\}$ . We have

\begin{equation*}\begin{array}{rcl}Cl_{D_{window}}(\delta_1 \cup \{open\}) & = &\{ open, \neg open, closed, \neg closed, locked, \neg locked\} = \delta_{1,1} \\[2pt]Cl_{D_{window}}(\delta_1 \cup \{closed\}) & = &\{ \neg open, closed, \neg locked \} = \delta_{1,2} \\[2pt]Cl_{D_{window}}(\delta_1 \cup \{locked\}) & = &\{ \neg open, \neg closed, locked \} = \delta_{1,3}.\end{array}\end{equation*}

Among those, $\delta_{1,1}$ is inconsistent. Therefore, we have $\Phi^a(check,\delta_1)=\{\delta_{1,2},\delta_{1,3}\}$ .

The extended transition function $\widehat{\Phi^a}$ for computing the result of the execution of a conditional plan is defined as follows. Let $\alpha$ be a conditional plan and $\delta$ a partial state.

1. 1. If $\alpha = \langle \rangle $ then $\widehat{\Phi^a}(\alpha, \delta) = \delta$ .

2. 2. If $\alpha = \langle a; \beta \rangle$ and a is a non-sensing action and $\beta$ is a conditional plan then $\widehat{\Phi^a}(\alpha, \delta) = \widehat{\Phi^a}(\beta, \Phi^a(a, \delta))$ .

3. 3. if $\alpha = \langle a; \textbf{cases}(\{g_j \rightarrow \alpha_j\}_{j=1}^{n}) \rangle$ where a is a sensing action with the sensed-literals $\theta = \{ g_1, \dots, g_n \}$ and $\alpha_j$ ’s are conditional plans then

4. (a) $\widehat{\Phi^a}(\alpha, \delta) = \widehat{\Phi^a}(\alpha_k, \delta_k)$ if there exists $\delta_k \in \Phi^a(a, \delta)$ such that $\delta_k \models g_k$ .

5. (b) $\widehat{\Phi^a}(\alpha, \delta) = \bot$ (undefined), otherwise.

6. (4) $\widehat{\Phi^a}(\alpha, \bot) = \bot$ for every $\alpha$ .

Intuitively, the execution of a conditional plan progresses similarly to the execution of an action sequence until it encounters a case-plan. In this case, the sensing action is executed and the satisfaction of the formula in each branch is evaluated. If one of the formulae holds in the state resulting after the execution of the sensing action then the execution continues with the plan on that branch. Otherwise, the execution fails.

5.2 ASP-based conditional planning

Let us now describe an ASP-based conditional planner, called ASPcp, capable of generating conditional plans. The planner is a simple variation of the one described by (Tu et al. Reference Tu, Son and Baral2007). As in the previous sections, we translate a planning problem $\mathcal{P} = (D,\Gamma,\Delta)$ into a logic program $\Pi_{h,w}(\mathcal{P})$ whose answer sets represent solutions of $\mathcal{P}$ . Before we present the rules of $\Pi_{h,w}(\mathcal{P})$ , let us provide the intuition underlying the encoding.

First, let us observe that each plan $\alpha$ (Definition 1) corresponds to a labeled plan tree $T_\alpha$ defined as follows.

• • If $\alpha = \langle \: \rangle$ then $T_\alpha$ is a tree with a single node.

• • If $\alpha = \langle a \rangle$ , where a is a non-sensing action, then $T_\alpha$ is a tree with a single node and this node is labeled with a.

• • If $\alpha = \langle a; \beta \rangle$ , where a is a non-sensing action and $\beta$ is a non-empty plan, then $T_\alpha$ is a tree whose root is labeled with a and has only one subtree which is $T_\beta$ . Furthermore, the link between a and $T_\beta$ ’s root is labeled with an empty string.

• • If $\alpha = \langle a;\textbf{cases}(\{g_j \rightarrow \alpha_j\}_{j=1}^n) \rangle$ , where a is a sensing action, then $T_\alpha$ is a tree whose root is labeled with a and has n subtrees $\{T_{\alpha_j} \mid j \in \{1,\dots,n\}\}$ . For each j, the link from a to the root of $T_{\alpha_j}$ is labeled with $g_j$ .

For example, the plan tree for the plan

\begin{equation*}\alpha =\left\langle check;\textbf{cases} \left (\begin{array}{lll} locked & \rightarrow & \langle \rangle; \\[2pt] open & \rightarrow & \langle push\_down;flip\_lock\rangle; \\[2pt] closed & \rightarrow & \langle flip\_lock; flip\_lock; flip\_lock \rangle \end{array} \right )\right\rangle\end{equation*}

is given in Figure 1 (shaded nodes indicate that there exists an action occurring at those nodes, while white nodes indicate that there is no action occurring at those nodes).

Fig. 1. A plan tree.

For a plan p, let w(p) be the number of leaves of $T_p$ and h(p) be the number of nodes along the longest path from the root to the leaves of $T_p$ . w(p) and h(p) are called the width and height of $T_p$ respectively. Suppose w and h are two integers that such that $w(p) \le w$ and $h(p) \le h$ .

Let us denote the leaves of $T_p$ by $x_1,\ldots,x_{w(p)}$ . We map each node y of $T_p$ to a pair of integers $n_y$ = ( $t_y$ , $p_y$ ), where $t_y$ , called the t-value of y, is the number of nodes along the path from the root to y minus 1, and $p_y$ , called the p-value of y, is defined in the following way:

• • For each leaf $x_i$ of $T_p$ , $p_{x_i}$ is an arbitrary integer between 0 and w. Furthermore, there exists a leaf x such that $p_x = 0$ , and there exist no $i \ne j$ such that $p_{x_i} = p_{x_j}$ .

• • For each interior node y of $T_p$ with children $y_1,\ldots,y_r$ , $p_y = \min\{p_{y_1},\ldots,p_{y_r}\}$ .

For instance, Figure 2 shows some possible mappings with $h=3$ and $w=3$ for the tree in Figure 1. It is easy to see that if $w(p) \le w$ and $h(p) \le h$ then such a mapping always exists.

Fig. 2. Possible mappings for the tree in Figure 1.

Furthermore, from the construction of $T_\alpha$ , independently of how the leaves of $T_\alpha$ are numbered, we have the following properties.

1. 1. For every node y, $t_y \le h$ and $p_y \le w$ .

2. 2. For a node y, all of its children have the same t-value. That is, if y has r children $y_1,\ldots,y_r$ then $t_{y_i} = t_{y_j}$ for every $1 \le i,j \le r$ . Furthermore, the p-value of y is the smallest one among the p-values of its children.

3. 3. The root of $T_\alpha$ is always mapped to the pair (0,0).

The numbering schema of a plan tree provides a method for generating a conditional plan on a two-dimensional coordinated system (or grid) where the x- and y-axis correspond to the height and width of the plan tree, and where (0,0) is the initial state. Along a line of the same y-value is an action sequence and the execution of a sensing action creates branches on different lines, parallel to the x-axis. For example, the execution of the check action in the initial state of the plan tree in Figure 2 creates three branches, to lines 0, 1, and 2. In the following, we use path to indicate the branch number and refer to a coordinate (x,y) as a node.

Let us next describe the rules in program $\Pi_{h,w}(\mathcal{P})$ . Intuitively, the program is similar to the program $\Pi^a(\mathcal{P},n)$ in that it implements the approximation $\Phi^a$ and extends it to deal with sensing actions. Since a conditional plan is two-dimensional, all predicates holds, ph, possible, occ, de, etc. need to extend with a third parameter. That is, holds(L,T,P) – encoding that L holds at node (T,P) (the time step T and the line number P on the two-dimensional grid) – is used instead of holds(L,T). In addition, $\Pi_{h,w}(\mathcal{P})$ uses the following additional atoms and predicates.

• • $path(0..w)$ .

• • sense(a,g) if g is a sensed literal which belongs to $\theta$ in a knowledge law of the form (31).

• • $br(G,T,P,P_1)$ is true if there exists a branch from (T,P) to $(T+1,P_1)$ labeled with G. For example, in Figure 2 (left), we have br(open,0,0,1), br(closed,0,0,0), and br(locked,0,1,2).

• • used(T,P) is true if (T,P) belongs to some extended branch of the plan tree. This allows us to know which paths are used in the construction of the plan and allows us to check if the plan satisfies the goal. In Figure 2 (left), we have used(t,0) for $0 \le t \le h$ , and used(t,1) and used(t,2) for $1 \le t \le h$ .

The rules of $\Pi_{h,w}(\mathcal{P})$ are divided into two groups. The first group consists of rules from $\Pi^a(\mathcal{P},n)$ adapted to the two dimensional array for conditional planning. The second group consists of rules for dealing with sensing actions. We next describe the first group of rules ^{Footnote 12} in $\Pi_{h,w}(\mathcal{P})$ :

(33) \begin{eqnarray}holds(\Gamma,0,0)& \leftarrow & \end{eqnarray}

(34) \begin{eqnarray}possible(a,T,P)& \leftarrow & holds(\varphi,T,P) \end{eqnarray}

(35) \begin{eqnarray}holds(f, T+1, P) & \leftarrow & occ(a,T, P), holds(\varphi,T,P) \end{eqnarray}

(36) \begin{eqnarray}de(f, T+1, P) & \leftarrow & occ(a,T, P), holds(\varphi,T,P) \end{eqnarray}

(37) \begin{eqnarray}ph(f,T+1, P) & \leftarrow & occ(a,T, P), { not \:} h(\overline{\varphi}, T, P) , { not \:} de(\overline{f},T+1,P) \quad \end{eqnarray}

(38) \begin{eqnarray}ph(f,T,P)& {\leftarrow} & ph(\varphi,T, P) \end{eqnarray}

(39) \begin{eqnarray}holds(f,T,P)& \leftarrow & holds(\varphi,T,P) \end{eqnarray}

(40) \begin{eqnarray}ph(L,T+1,P)& \leftarrow & fluent(L), { not \:} holds(\neg L,T), { not \:} de(\neg L,T,P) \end{eqnarray}

(41) \begin{eqnarray}ph(\neg L,T+1,P)& \leftarrow & fluent(L), { not \:} holds(L,T), { not \:} de(L,T,P) \end{eqnarray}

(42) \begin{eqnarray}holds(L,T+1,P)& \leftarrow & fluent(L), { not \:} ph(\neg L,T,P) \end{eqnarray}

(43) \begin{eqnarray}holds(\neg L,T+1,P)& \leftarrow & fluent(L), { not \:} ph( L,T,P) \end{eqnarray}

(44) \begin{eqnarray}1\{occ(X,T,P) : action(X)\} 1 & \leftarrow & used(T,P), { not \:} goal(T,P) \end{eqnarray}

(45) \begin{eqnarray}& \leftarrow & occ(A,T,P), { not \:} possible(A,T,P). \end{eqnarray}

In the above rules, L is a fluent literal, T is a time moment in the range $[0,h-1]$ , and P is in the range [0,w]. Rule (33) encodes the initial state. The rules (34)–(43) are used for computing the effects of the occurrence of a non-sensing action at the node (T,P). The rules (44) and (45) are used for generating action occurrences, similarly to the rules for generating action occurrences in the previous sections. The difference is that the selection restricts the generation of action occurrences to nodes marked as ‘used’ (see below).

The key distinction between $\Pi_{h,w}(\mathcal{P})$ and $\Pi^a(\mathcal{P},n)$ lies in the rules for dealing with sensing actions. We next describe this set of rules.

• • Rules for reasoning about the effect of sensing actions: For each knowledge law (31) in D, $\Pi_{h,w}(\mathcal{P})$ contains the following rules:

  (46) \begin{eqnarray} 1\{br(g,T,P,X){:}new\_br(P,X)\}1 & \leftarrow & occ(a,T,P), sense(a,g). \end{eqnarray}
  (47) \begin{eqnarray}& \leftarrow & occ(a,T,P), sense(a, g), \nonumber \\[3pt] & & { not \:} br(g,T,P,P) \end{eqnarray}
  (48) \begin{eqnarray}& \leftarrow & occ(a,T,P), sense(a,g), \nonumber \\[3pt] & & holds(g, T,P) \end{eqnarray}
  (49) \begin{eqnarray}new\_br(P,P_1) & \leftarrow & P \le P_1. \end{eqnarray}
  When a sensing action occurs, it creates one branch for each of its sensed literals. This is encoded in the rule (46). The constraint (47) makes sure that the current branch P is continuing if a sensing action occurs at (T,P). The rule (48) is a constraint that prevents a sensing action to occur if one of its sensed literals is already known. To simplify the selection of branches, rule (49) forces a new branch at least at the same level as the current branch. The intuition behinds these rules can be seen in Figure 3.
  

  Fig. 3. Sensing action a that senses $\{g_1,g_2,g_3\}$ occurs at (t,p) - disallowed (Left) vs. allowed (Right).

• • Inertia rules for sensing actions: This group of rules encodes the fact that the execution of a sensing action does not change the world. However, there is a one-to-one correspondence between the set of sensed literals and the set of possible partial states.

  (50) \begin{eqnarray}& \leftarrow & P_1 < P_2, P_2 < P, br(G_1,T,P_1,P), \nonumber \\[3pt] & & br(G_2,T,P_2,P) \end{eqnarray}
  (51) \begin{eqnarray}& \leftarrow & P_1 \le P, G_1 \ne G_2, br(G_1,T,P_1,P), \nonumber \\[3pt] & & br(G_2,T,P_1,P) \end{eqnarray}
  (52) \begin{eqnarray}& \leftarrow & P_1 < P, br(G,T,P_1,P), used(T,P) \end{eqnarray}
  (53) \begin{eqnarray}used(T+1,P) & \leftarrow & P_1 < P, br(G,T,P_1,P) \end{eqnarray}
  (54) \begin{eqnarray}holds(G,T+1,P) & \leftarrow & P_1 \le P, br(G,T,P_1,P) \end{eqnarray}
  (55) \begin{eqnarray}holds(L,T+1,P)& \leftarrow & P_1 < P, br(G,T,P_1,P),holds(L,T,P_1) \end{eqnarray}
  (56) \begin{eqnarray}used(0,0) & \leftarrow & \end{eqnarray}
  (57) \begin{eqnarray}used(T+1,P)& \leftarrow & used(T,P). \end{eqnarray}
  The first three rules, together with rule (49), make sure that branches are separate from each other. The next rule is used to mark a node as used if there is a branch in the plan that reaches that node. This allows us to know which paths on the grid are used in the construction of the plan and allows us to check if the plan satisfies the goal (see rule (58)). The two rules (54)–(55), along with rule (53), encode the possible partial state corresponding to the branch denoted by literal G after a sensing action is performed at $(T,P_1)$ . They indicate that the partial state at $(T+1,P)$ should contain G (Rule (54)) and literals that hold in $(T,P_1)$ (Rule (55)). The last two rules mark nodes that have been used in the construction of the conditional plan.

• • Goal representation: Checking for goal satisfaction needs to be done on all branches. This is encoded as follows.

  (58) \begin{eqnarray}goal(T_1,P) & \leftarrow & holds(\Delta,T_1,P) \end{eqnarray}
  (59) \begin{eqnarray}goal(T_1,P) & \leftarrow & holds(L,T_1,P), holds(\neg L,T_1,P) \end{eqnarray}
  (60) \begin{eqnarray}& \leftarrow & used(h+1,P), { not \:} goal(h+1,P). \end{eqnarray}
  The first rule in this group says that the goal is satisfied at a node if all of its subgoals are satisfied at that node. The last rule guarantees that if a path P is used in the construction of a plan then the goal must be satisfied at the end of this path, that is, at node (h,P). The second rule provides an avenue to stop the generation of actions when an inconsistent state is encountered – by declaring the goal reached. As discussed by (Tu et al. Reference Tu, Son and Baral2007), the properties of the encoding of consistent action theories prevent this method from generating plans leading to inconsistent states.

5.3 Context: Conditional planning

As we mentioned earlier, the need for plans with conditionals and/or loops has been identified very earlier on by (Warren Reference Warren1976), who developed Warplan-C, a Prolog program that can generate conditional plans and programs given the problem specification. Warplan-C has only 66 clauses and is conjectured to be complete. The system was developed at the same time as other non-linear planning systems, such as Noah by (Sacerdoti Reference Sacerdoti1974). These earlier systems do not deal with sensing actions. Other systems that generate plans with if-then statements and can prepare for contingencies are Cassandra (Pryor and Collins Reference Pryor and Collins1996) and CNLP (Peot and Smith Reference Peot and Smith1992). These two systems extend partial order planning algorithms for computing conditional plans.

XII (Golden et al. Reference Golden, Etzioni and Weld1996) and PUCCINI (Golden Reference Golden1998) are two systems that employ partial order planning to generate conditional plans for problems with incomplete information and can deal with sensing actions. SGP (Weld et al. Reference Weld, Anderson and Smith1998) and POND (Bryce et al. Reference Bryce, Kambhampati and Smith2006) are conditional planners that work with sensing actions. These systems extend the planning graph algorithm (Blum and Furst Reference Blum and Furst1997) to deal with sensing actions. The main difference between SGP and POND is that the former searches solutions within the planning graph, whereas the latter uses it as a means of computing the heuristic function.

CoPlaS, developed by (Lobo Reference Lobo1998), is a regression Prolog-based planner that uses a high-level action description language, similar to the language $\mathcal{B}_K$ described in this section, to represent and reason about effects of actions, including sensing actions. (Van Nieuwenborgh et al. Reference Van Nieuwenborgh, Eiter and Vermeir2007) introduced $\mathcal{K}_c$ , an extension of language $\mathcal{K}$ , to deal with sensing actions and compute conditional plans as defined in this section using dlv $^\mathcal{K}$ . (Thielscher Reference Thielscher2000) presented FLUX, a constraint logic programming based planner, which is capable of generating and verifying conditional plans. QBFPlan is another conditional planner, based on a QBF theorem prover, is described in the paper by (Rintanen Reference Rintanen1999). This system, however, does not consider sensing actions.

Research in developing conditional planners, however, has not attracted as much attention compared to other types of planning domains in recent years. Rather, the focus has been on synthesizing controllers or reactive modules which exhibit specific behaviors in different environments (Aminof et al. Reference Aminof, De Giacomo, Lomuscio, Murano and Rubin2020; Camacho et al. Reference Camacho, Bienvenu and McIlraith2019; Camacho et al. Reference Camacho, Baier, Muise and McIlraith2018; Treszkai and Belle Reference Treszkai and Belle2020). This is similar to the effort of generating programs satisfying a specification as discussed earlier (e.g., the work by Warren Reference Warren1976) or attempts to compute policies (see, e.g., the book by Bellman Reference Bellman1957) for Markov Decision Processes (MDP) or Partially Observable Markov Decision Processes (POMDP). To the best of our knowledge, little attention has been paid to this research direction within the ASP community. We present this as a challenge to ASP in the last section of the paper.

6.1 A preference specification language

The proposed preference specification language addresses the description of three classes of preferences: basic desires, atomic preferences, and general preferences.

For a planning problem $\mathcal{P} = \langle D, \Gamma, \Delta \rangle$ , a basic desire can be in of the following possible forms:

1. (a) a state formula, which is a fluent formula $\varphi$ or a formula of the form occ(a) for some action a, or

2. (b) a goal preference, of the form $\textbf{goal}(\varphi)$ , where $\varphi$ is a fluent formula.

Basic desire formula.

A basic desire formula is a formula built over basic desires, the traditional propositional operators ( $\wedge$ , $\vee$ , and $\neg$ ), and the modalities $\textbf{next}$ , $\textbf{always}$ , $\textbf{eventually}$ , and $\textbf{until}$ . The BNF for the basic desire formulae is

\begin{equation*}\psi \stackrel{def}{=} \varphi \mid \psi_1 \wedge \psi_2 \mid \psi_1 \vee \psi_2 \mid \neg \psi_1 \mid \textbf{next}(\psi_1) \mid \textbf{until}(\psi_1,\psi_2) \mid \textbf{always}(\psi_1) \mid \textbf{eventually}(\psi),\end{equation*}

where $\varphi$ represents a state formula or a goal preference and $\psi$ , $\psi_1$ , or $\psi_2$ are basic desire formulae.

Intuitively, a basic desire formula specifies a property that a user would like to see satisfied by the provided plan. For example, to express the fact that a user would like to take the taxi or the bus to go to school, we can write:

\begin{equation*}\textbf{eventually}(occ(bus(home,school)) \vee occ(taxi(home,school))).\end{equation*}

If the user’s desire is not to call a taxi, we can write

\begin{equation*}\textbf{always}(\neg occ(call\_taxi(home))).\end{equation*}

If the user’s desire is not to see any taxi around his home, we can use the basic desire formula

\begin{equation*}\textbf{always}(\neg available\_taxi(home)).\end{equation*}

Note that these encodings have different consequences – the last formula prevents taxis to be present, independently from whether the taxi has been called.

The following are several basic desire formulae that are often of interest to users.

• • Strong Desire: For two formulae $\varphi_1$ and $\varphi_2$ , $\varphi_1 < \varphi_2$ denotes $\varphi_1 \wedge \neg \varphi_2$ .

• • Weak Desire: For two formulae $\varphi_1$ and $\varphi_2$ , $\varphi_1 <^w \varphi_2$ denotes $\varphi_1 \vee \neg \varphi_2$ .

• • Enabled Desire: For two actions $a_1$ and $a_2$ , $a_1 <^e a_2$ stands for $(executable(a_1) \wedge executable(a_2)) \Rightarrow (occ(a_1) < occ(a_2))$ where $executable(a) = \bigwedge_{l \in \varphi} l $ if $\textbf{executable}(a, \varphi) \in D$ .

• • Action Class Desire: For actions with the same set of parameters and effects such as drive or walk, we write $drive <^e walk$ to denote the desire $\bigvee_{l_1, l_2 \in S, \: l_1 \ne l_2} (drive(l_1, l_2) <^e walk(l_1, l_2))$ where S is a set of pre-defined locations. Intuitively, this preference states that we prefer to drive rather than to walk between locations belonging to the set S. For example, if $S = \{home, school\}$ then this preference says that we prefer to drive from home to school and vice versa.

Atomic preference.

Basic desire formulae are expressive enough to describe a significant portion of preferences that frequently occur in real-world domains. It is also often the case that the user may provide a variety of desires, and some desires are stronger than others; knowledge of such biases about desires becomes important when it is not possible to concurrently satisfy all the provided desires. In this situation, an ordering among the desires is introduced. An atomic preference formula is a formula of the form

\begin{equation*} \varphi_1 \lhd \varphi_2 \lhd \cdots \lhd \varphi_n, \end{equation*}

where $\varphi_1, \dots, \varphi_n$ are basic desire formulae. The atomic preference formula states that trajectories that satisfy $\varphi_1$ are preferable to those that satisfy $\varphi_2$ , etc.

Let us consider again the travel domain. Besides time and cost, users often have their preferences based on the level of comfort and/or safety of the available transportation methods. These preferences can be represented by the formulae ^{Footnote 13}

\begin{equation*}\mathit{cost} = \textbf{always}(\mathit{walk} <^e \mathit{bus} <^e \mathit{drive} <^e \mathit{flight})\end{equation*}

and

\begin{equation*}\mathit{time} = \textbf{always}(\mathit{flight} <^e \mathit{drive} <^e \mathit{bus} <^e \mathit{walk})\end{equation*}

and

\begin{equation*}\mathit{comfort} = \textbf{always}(\mathit{flight} <^e (drive \vee bus) <^e walk)\end{equation*}

and

\begin{equation*}\mathit{safety} = \textbf{always}(walk <^e \mathit{flight} <^e (drive \vee bus)).\end{equation*}

These four desires can be combined to produce the following two atomic preferences

\begin{equation*}\Psi^t_1 = \mathit{comfort} \lhd \mathit{safety} \:\:\: {and} \:\:\:\Psi^t_2 = cost \lhd time.\end{equation*}

Intuitively, $\Psi^t_1$ is a comparison between level of comfort and safety, while $\Psi^t_2$ is a comparison between affordability and duration.

General preference formulae.

Suppose that a user would like to travel as comfortably and as cheaply as possible. Such a preference can be viewed as a multi-dimensional preference, which cannot be easily captured using atomic preferences or basic desires. General preference formulae support the representation of such multi-dimensional preferences.

Formally, a general preference formula is a formula satisfying one of the following conditions:

• • An atomic preference $\Psi$ is a general preference;

• • If $\Psi_1, \Psi_2$ are general preferences, then $\Psi_1 \& \Psi_2$ , $\Psi_1 \mid \Psi_2$ , and $!\: \Psi_1$ are general preferences;

• • If $\Psi_1, \Psi_2, \dots, \Psi_k$ is a collection of general preferences, then $\Psi_1 \lhd \Psi_2 \lhd \cdots \lhd \Psi_k$ is a general preference.

In the above definition, the operators $\&, \mid, !$ are used to express different ways to combine preferences. For example, the preference $\Psi^t_1 \& \Psi^t_2$ indicates that the user prefers trajectories that are most preferred according to both $\Psi^t_1$ and $\Psi^t_2$ ; $\Psi^t_1 \mid \Psi^t_2$ states that, among trajectories with the same cost, the user prefers trajectories that are most comfortable or vice versa. A detailed discussion of general preferences can be found in the paper by (Son and Pontelli Reference Son and Pontelli2006).

Semantics.

In order to define the semantics of the preference language, we need to start from describing whether a trajectory $\alpha = s_0a_0\ldots a_{n-1} s_n$ satisfies a basic desire formula. We write $\alpha \models \varphi$ to denote that $\alpha$ satisfies a basic desire $\varphi$ . The definition of $\models$ is straightforward, and we report here only some of the cases (the complete definition can be found in the paper by Son and Pontelli Reference Son and Pontelli2006), where $\alpha[i] = s_i a_i \ldots a_{n-1}s_n$ .

• • $\alpha \models occ(a)$ if $a_0=a$ ;

• • $\alpha \models \ell$ if $s_0\models \ell$ and $\ell$ is a fluent;

• • $\alpha \models \textbf{always}(\varphi)$ if for all $0\leq i < n$ we have $\alpha[i]\models\varphi$ ;

• • $\alpha \models \textbf{next}(\varphi)$ if $\alpha[1] \models \varphi$ .

The satisfaction of desires is used to define two relations between trajectories, one expressing preference between trajectories and one capturing the fact that two trajectories are indistinguishable, denoted by $\prec_\Psi$ and $\approx_{\Psi}$ , respectively, where $\Psi$ is a preference formula. For two trajectories $\alpha$ and $\beta$ ,

1. 1. if $\Psi$ is a basic desire then $\alpha \prec_\Psi \beta$ ( $\alpha$ is more preferred than $\beta$ with respect to $\Psi$ ) if $\alpha \models \Psi$ and $\beta \not\models \Psi$ ; $\alpha \approx_{\Psi} \beta$ denotes that $\alpha \models \Psi$ iff $\beta \models \Psi$ .

2. 2. if $\Psi$ is an atomic preference $\varphi_1 \lhd \varphi_2 \lhd \cdots \lhd \varphi_n$ then $\alpha \prec_{\Psi} \beta$ if $\exists (1 \leq i \leq n)$ such that

   1. (a) $\forall (1 \leq j < i)$ we have that $\alpha \approx_{\varphi_j} \beta$ , and

   2. (b) $\alpha \prec_{\varphi_i} \beta$ . $\alpha \approx_{\Psi} \beta$ denotes that $\alpha \approx_{\varphi_j} \Psi$ for every $j=1,\ldots,n$ .

3. 3. if $\Psi$ is a general preference and has the form $\Psi = \Psi_1 \lhd \cdots \lhd \Psi_k$ then $\alpha \prec_\Psi \beta$ is defined similar to the second case. Otherwise, $\alpha \prec_\Psi \beta$

4. (a) if $\Psi = \Psi_1 \& \Psi_2$ and $\alpha \prec_{\Psi_1} \beta$ and $\alpha \prec_{\Psi_2} \beta$

5. (b) if $\Psi = \Psi_1 \mid \Psi_2$ and (i) $\alpha \prec_{\Psi_1} \beta$ and $\alpha \approx_{\Psi_2} \beta$ ; or (ii) $\alpha \prec_{\Psi_2} \beta$ and $\alpha \approx_{\Psi_1} \beta$ ; or (iii) $\alpha \prec_{\Psi_1} \beta$ and $\alpha \prec_{\Psi_2} \beta$ .

6. (c) if $\Psi = \:! \Psi_1$ and $\beta \prec_{\Psi_1} \alpha$ .

In all cases, $\alpha \approx_{\Psi} \beta$ iff $\alpha \approx_{\Psi'} \beta$ where $\Psi'$ is a component of $\Psi$ .

The following proposition holds (Son and Pontelli Reference Son and Pontelli2006).

The above proposition shows that maximal elements with respect to $\prec_\Psi$ exist, that is, most preferred trajectories exist.

6.2 Implementation: Computing preferred plans

Given a planning problem $\mathcal{P}$ and a preference formula $\Psi$ , a preferred trajectory can be computed using the following steps:

1. 1. Use one of the programs, denoted by $\mathit{Plan}(\mathcal{P},n)$ , introduced in Sections 3–4 to compute a potential solution $\alpha$ for $\mathcal{P}$ ;

2. 2. Associate to $\alpha$ a number, which represents the degree of satisfaction of $\alpha$ with respect to $\Psi$ ; and

3. 3. Use the $\#maximize$ statement of clingo to compute a most preferred trajectory.

This process requires an appropriate encoding of $\Psi$ . This is usually achieved by converting $\Psi$ to a canonical form, which provides a convenient way to translate $\Psi$ into a set of facts with predefined predicates. For example, a basic desire formula can be encoded using the predicates and, or, $\neg$ , occ, $\textbf{next}$ , $\textbf{until}$ , $\textbf{eventually}$ , $\textbf{always}$ , and final (stands for goal, to avoid confusion with the goal predicate defined in the previous sections). This translation can be done using a script (e.g., Son and Pontelli Reference Son and Pontelli2006 presented a Prolog program for such translation).

An atomic preference can be represented using an ordered set, consisting of a declaration atomic(id), indicating that id is an atomic preference, and a set of atoms of the form $member(id, \mathit{formula}, order)$ , where id, formula, and order represent the atomic preference identifier, the formula, and the order of the formula in id, respectively. Finally, a general preference can be encoded using the predicates $\&$ , $\mid$ , and $!$ , and the basic representations of basic desires and atomic preferences. In the following, we use $\Pi(\Psi)$ to denote the set of facts encoding $\Psi$ .

Since the first task in computing a most preferred trajectory is checking whether or not a trajectory satisfies a basic desire, we need to add to $\mathit{Plan}(\mathcal{P},n)$ rules for this purpose. This task can be achieved by a set of domain-independent rules $\Pi_{\mathit{pref}}$ defining the predicate $holds(sat(\varphi), t)$ , which states that the basic desire formula $\varphi$ is satisfied by the trajectory $s_t a_t \ldots a_{n-1} s_n$ . $\Pi_{\mathit{pref}}$ contains the following groups of rules:

• • Rules for checking the satisfaction of a propositional formula at a time step: such as

  \begin{equation*}\begin{array}{lcl}holds(sat(F), T) &\leftarrow & fluent(F), holds(F,T)\\[3pt]holds(sat(and(F,G)), T) &\leftarrow& holds(sat(F), T), holds(sat(G),T)\end{array}\end{equation*}

• • Rules for checking the satisfaction of a temporal formula at a time step: such as

  \begin{equation*}holds(sat(\textbf{next}(F)), T) \leftarrow holds(sat(F), T+1)\end{equation*}

• • Rules for checking the occurrence of an action:

  \begin{equation*}holds(sat(occ(A)), T) \leftarrow occ(A,T)\end{equation*}

• • Rules for checking the satisfaction of a goal formula:

  \begin{equation*}holds(sat(final(F)), 0) \leftarrow holds(sat(F), n).\end{equation*}

The following proposition holds.

The above proposition shows that $\mathit{Plan}(\mathcal{P},n) \cup \Pi(\varphi) \cup \Pi_{\mathit{pref}}$ can be used to compute a most preferred trajectory with respect to a basic desire formula. To do so, we only need to tell clingo that an answer set containing $holds(sat(\varphi), 0)$ is preferred.

To compute a most preferred plan with respect to a general preference or an atomic formula, (Son and Pontelli Reference Son and Pontelli2006) proposed a set of rules that assigns a number to a formula and then use the $\#maximize$ statement of clingo to select a most preferred trajectory. The proposed rules were developed at the time the answer set solvers did provide only limited capability to work with numbers. For this reason, we omit the detail about these rules here. Features provided in more recent versions of answer set solvers, such as multiple optimization statements and weighted tuples, are likely to enable a simpler and more efficient implementation. For example, we could translate an atomic preference

\begin{equation*}\varphi_1 \lhd \varphi_2 \ldots \lhd \varphi_n\end{equation*}

to a statement

\begin{equation*}\#maximize \{1@n : holds(sat(\varphi_1), 0); \ldots ; n@1 : holds(sat(\varphi_n), 0)\}\end{equation*}

as a part of $\Pi(\Psi)$ .

6.3 Context: Planning with preferences

Planning with preferences has attracted a lot of attention by the planning community. An excellent survey of several systems developed before 2008 and their strengths and weaknesses can be found in the paper by (Baier and McIlraith Reference Baier and McIlraith2008). Preferences have also been included in extensions of PDDL, such as PDDL3 (Gerevini and Long Reference Gerevini and Long2005). The majority of systems described in the survey employ PDDL3 where preferences are, ultimately, described by a numeric value. As such, most of the planning with preferences systems in the literature can be characterized as cost optimal, where the cost of actions plays a key role in deciding the preference of a solution. Hierarchical task planning is also frequently used in these systems. Representative systems in this direction are HPlan-P (Sohrabi et al. Reference Sohrabi, Baier and McIlraith2009), LPRPG-P (Coles and Coles Reference Coles and Coles2011), and PGPlanner (Das et al. Reference Das, Odom, Islam, Doppa, Roth and Natarajan2019). ChoPlan, developed by (Bidoux et al. Reference Bidoux, Pignon and BÉnaben2019), is a system which encodes a PDDL3 planning problem as a multi-attribute utility theory and a heuristic based on Choquet integrals to derive solutions.

satplan(P), developed by (Giunchiglia and Maratea Reference Giunchiglia and Maratea2007), shows that SAT-based planning is also competitive with other planning paradigms. (Giunchiglia and Maratea Reference Giunchiglia and Maratea2011) present a survey of SAT-based planning with preferences. In recent years, SMT-based planning has become more popular than SAT-based planning, thanks to the expressiveness of SMT compared to SAT and the availability of efficient SMT solvers. SMT-based planning, which can work with numeric variables, provides an excellent way to deal with preferences (Scala et al. Reference Scala, Ramrez, Haslum and ThiÉbaux2016). It is worth observing that ASP-based planning with action costs has been considered earlier by (Eiter et al. Reference Eiter, Faber, Leone, Pfeifer and Polleres2003a) and more recently by (Khandelwal et al. Reference Khandelwal, Yang, Leonetti, Lifschitz and Stone2014).

7.1 Diagnostic reasoning as answer set planning

As we said earlier, answer set planning can be used to determine whether a diagnosis is needed and for computing diagnostic explanations. Next, we introduce an ASP-based program for these purposes. Consider a domain D whose behavior up to step n is described by recorded history $H_n$ . Reasoning about D and $H_n$ can be accomplished by a translation to a logic program $\Pi(D, H_n)$ that follows the approach outlined in Section 3. Focusing for simplicity on the direct encoding, $\Pi(D, H_n)$ consists of:

• • the domain dependent rules from Section 3.1.1;

• • the rules related to inertia and consistency of states (11)–(13);

• • domain independent rule establishing the relationship between observations and the basic relations of $\Pi$ :

  (63) \begin{eqnarray}occ(A,T) \leftarrow hpd(A,T) \end{eqnarray}
  (64) \begin{eqnarray}holds(L,0) \leftarrow obs(L,0)\end{eqnarray}

• • the reality check axiom, that is a rule ensuring that in any answer set the agent’s expectations match the available observations (variable L ranges over fluent literals):

  (65) \begin{eqnarray}\leftarrow obs(L,T), { not \:} holds(L,T).\end{eqnarray}

The following theorem establishes an important relationship between models of a recorded history and answer sets of the corresponding logic program.

The proof of the theorem is in two steps. First, one shows that the theorem holds for $n=1$ , that is, that for a history $H_1$ there is a one-to-one correspondence between the transitions of the form $s_0a_0s_1$ and the answer sets of $\Pi(D,H_1)$ . Then, induction is leveraged to extend the correspondence to histories of arbitrary length. The complete proof can be found in the paper by (Balduccini and Gelfond Reference Balduccini and Gelfond2003).

Next, we focus on identifying the need for diagnosis. Given a domain D and ${\cal S} = \langle H_n,O^{m}_n\rangle$ , we introduce:

(66) \begin{equation}\mathit{TEST}({\cal S})= \Pi(D, H_n) \cup O^m_{n}.\end{equation}

The following corollary forms the basis of this approach to diagnosis.

Once a symptom has been identified, diagnostic explanations can be found by means of the answer sets of the diagnostic program

(67) \begin{equation}\Pi_d({\cal S})= \mathit{TEST}({\cal S}) \cup\{\ \ \ 1 \{ occ(A,T) : x\_act(A) \} 1 \leftarrow time(T), T < n.\ \ \ \}\end{equation}

Specifically, every answer set X of $\Pi_d({\cal S})$ encodes a diagnostic explanation

\begin{equation*}E=\{hpd(a,t) \,\,|\,\, occ(a,t) \in X \land a \in \mbox{\textbf{A}$_e$} \}.\end{equation*}

Note that the choice rule shown in (67) is simply a restriction of (10) to exogenous actions. As a result, $\Pi_d({\cal S})$ can be viewed as a variant of the translation $\Pi(\mathcal{P},n)$ of a planning problem, where planning occurs over the past $0..n\!-\!1$ time steps and over exogenous actions only, and the goal states are described by the observations from ${\cal S}$ .

Example 9 Consider the domain from Example 8. According to $H_1$ initially switches $sw_1$ and $sw_2$ are open, all circuit components are ok, $sw_1$ is closed by the agent, and b is protected. The expectation is that b will be on at 1. Suppose that, instead, the agent observes that at time 1 bulb b is off, that is $O_1 = \{obs(\neg on(b),1) \}$ . $\mathit{TEST}({\cal S}_0)$ , where ${\cal S}_0 = \langle H_1,O_1\rangle$ , has no answer sets and thus, by Corollary 1, ${\cal S}_0$ is indeed a symptom. The diagnostic explanations of ${\cal S}_0$ can be found by computing the answer sets of $\Pi_d(\mathcal{S})$ . Specifically, there are three diagnostic explanations:

\begin{equation*}\begin{array}{l}E_1 = \{occ(brk,0)\} \\[3pt] E_2 = \{occ(srg,0)\} \\[3pt] E_3 = \{occ(brk,0), occ(srg,0)\}.\end{array}\end{equation*}

7.2 Context: Planning and diagnosis

Classical diagnosis such as the foundational work by (Reiter Reference Reiter1987) aimed at providing a formal answer to the question of “what is wrong with a system given its (current failed) state.” Central to classical diagnosis is the use of the model of the system to reason about failures. Earlier formalizations considered a single state of the system and are often referred to as model based diagnosis, which is summarized by (De Kleer and Kurien Reference De Kleer and Kurien2003). Later formalization such as the proposal by (Feldman et al. Reference Feldman, Pill, Wotawa, Matei and de Kleer2020) considers a finite trace of states, taking into consideration the transitions at different time points in need of a diagnosis. This is closedly related to dynamic diagnosis, as described in this paper, which has been considered in the literature (Baral et al. Reference Baral, Kreinovich and Trejo2000; Baroni et al. Reference Baroni, Lamperti, Pogliano and Zanella1999; Cordier and ThiÉbaux Reference Cordier and ThiÉbaux1994; McIlraith Reference McIlraith1997; Thielscher Reference Thielscher1997; ThiÉbaux et al. Reference ThiÉbaux, Cordier, Jehl and Krivine1996; Williams and Nayak Reference Williams and Nayak1996).

The close relationship between model based diagnosis and satisfiability led to several methods for computing diagnosis using satisfiability such as the method proposed by (Grastien and Anbulagan 2013), (Metodi et al. Reference Metodi, Stern, Kalech and Codish2014), or described in several publications on diagnosing sequential circuits (e.g., by Feldman et al. Reference Feldman, Pill, Wotawa, Matei and de Kleer2020). In a recent work by (Wotawa Reference Wotawa2020), ASP has been used in the context of model-based diagnosis.

8.1 Centralized multiagent planning

We will start with the Multi-Agent Path Finding (MAPF) problem which appears in a variety of application domains, such as autonomous aircraft towing vehicles (Morris et al. Reference Morris, Pasareanu, Luckow, Malik, Ma, Kumar and Koenig2016), autonomous warehouse systems (Wurman et al. Reference Wurman, D’Andrea and Mountz2008), office robots (Veloso et al. Reference Veloso, Biswas, Coltin and Rosenthal2015), and video games (Silver Reference Silver2005).

A MAPF problem is defined by a tuple $\mathcal{M} = (R, (V,E), s, d)$ where

• • R is a set of robots,

• • (V,E) is an undirected graph, with the set of vertices V and the set of edges E,

• • s is an injective function from R to V, s(r) denotes the starting location of robot r, and

• • d is an injective function from R to V, d(r) denotes the destination of robot r.

Robots can move from one vertex to one of its neighbors in one step. A collision occurs when two robots move to the same location (vertex collision) or traveling on the same edge (edge collision). The goal is to find a collision-free plan for all robots to reach their destinations. Optimal plans, with the minimal number of steps, are often preferred.

A simple MAPF problem is depicted in Figure 5. In this problem, we have two robots $r_1$ and $r_2$ on a graph with five vertices $p_1, \ldots, p_5$ . Initially, $r_1$ is at $p_2$ and $r_2$ is at $p_4$ . The goal consists of moving robot $r_1$ to location $p_5$ and robot $r_2$ to location $p_3$ .

Fig. 5. A multi-agent path finding problem.

It is easy to see that a MAPF $\mathcal{M} = (R, (V,E), s, d)$ can be represented by

• • a set $\{\mathcal{P}_r \mid r \in R\}$ of path-planning problems for the robots in R, where for each $r \in R$ , $\mathcal{P}_r = \langle D_r, at(r, s(r)), at(r, d(r)) \rangle$ is a planning problem with

  \begin{equation*}D_r = \left \{\begin{array}{lll}\textbf{causes}(move(r,l,l'), at(r,l'), \{at(r,l)\}) && \mbox{ for } (l,l') \in E \\[3pt]\textbf{caused}(\{at(r,l)\}, \neg at(r,l')) \} && \mbox{ for } l \ne l', l,l' \in V \\[3pt]\end{array}\right.\end{equation*}

• • the set of constraints representing the collisions.

ASP-based solutions of MAPF problems have been proposed for both action-based as well as state-based encodings. In the context of this survey, we will focus on an action-based encoding. Consider a MAPF problem $\mathcal{M}= (R, (V,E), s, d)$ . The program developed in Section 3 for a single-agent planning problem can be used to develop a program solving $\mathcal{M}$ , denoted by $\Pi(\mathcal{M},n)$ , as follows. $\Pi(\mathcal{M},n)$ contains the following groups of rules:

1. 1. the set of atoms $\{agent(r) \mid r \in R\}$ encoding the robots;

2. 2. the collection of the rules from $\Pi(\mathcal{P}_r, n)$ ; and

3. 3. the constraints to avoid collisions:

   (68) \begin{eqnarray}& \leftarrow & agent(R), agent(R'), R \ne R' , \end{eqnarray}
   (69) \begin{eqnarray}&& holds(at(R, V), T), holds(at(R', V), T) \nonumber \\[3pt]& \leftarrow & agent(R), agent(R'), R \ne R' , \end{eqnarray}
   \begin{eqnarray}& & holds(at(R, V), T), holds(at(R', V'), T), \nonumber \\[3pt]& & holds(at(R, V'), T+1), holds(at(R', V), T+1). \nonumber\end{eqnarray}

Rule (68) prevents two robots to be at the same location at the same time, while rule (69) guarantees that edge-collisions will not occur. These two constraints and the correctness of $\Pi(\mathcal{P}_r,n)$ imply that $\Pi(\mathcal{M},n)$ computes solutions of length n for the MAPF problem $\mathcal{M}$ .

The proposed method for solving MAPF problems can be generalized to multi-agent planning as considered by the multi-agent community in the setting discussed by (Durfee Reference Durfee1999). We assume that a multi-agent planning problem $\mathcal{M}$ for a set of agents R is specified by a pair $(\mathcal{P}_{r \in R}, \mathcal{C})$ where $\mathcal{P}_r = \langle D_r, \Delta_r, \Gamma_r \rangle $ is the planning problem for agent r and $\mathcal{C}$ is a set of global constraints. For simplicity of the presentation, we will assume that

• • the agents in R share the same set of fluents and, wherever needed, parameterized with the names of the agents; for example, if an agent is carrying something then carrying(r, o) will be used instead of carrying(o) as in a single-agent domain;

• • the actions in the domain in $D_r$ are parameterized with the agent’s name r, for example, we will use the action move(r,l,l’) instead of the traditional encoding move(l,l’);

• • the constraints in $\mathcal{C}$ are of the form

  (70) \begin{equation}\textbf{executable}(sa, \varphi),\end{equation}
  where sa is a set of actions in $\bigcup_{r \in R} D_r$ and $\varphi$ is a set of literals. This can be used to represent parallel actions, non-concurrent actions, etc.

For a multi-agent planning problem $\mathcal{M} = (\mathcal{P}_{r \in R}, \mathcal{C})$ where $\mathcal{P}_r = \langle D_r, \Delta_r, \Gamma_r \rangle$ , the program $\Pi(\mathcal{M},n)$ that computes solution for $\mathcal{M}$ consists of

1. 1. the set of agent declarations, agent(r) for $r \in R$ ;

2. 2. the collection ^{Footnote 15} of the rules from $\Pi(\mathcal{P}_r, n)$ with the following modifications:

3. • the action specification of the form action(a) is replaced by action(r,a);

4. • the action generation rule is replaced by

   \begin{equation*}1 \{occ(A, T) : action(R, A)\} 1 \leftarrow time(T), agent(R),\end{equation*}
   where, without the loss of generality, we assume that every $D_r$ contains the action noop that is always executable and has no effect;