--- title: "A Native Qualitative Numeric Planning Solver Based on AND/OR Graph Search" authors: - "Hemeng Zeng" - "Yikun Liang" - "Yongmei Liu" doi: "10.24963/ijcai.2022/651" url: "https://ijcai.org/proceedings/2022/651" pdf: "https://ijcai.org/proceedings/2022/0651.pdf" venue: "Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence" year: 2022 pages: "4693-4700" track: "Main Track" keywords: - "Planning and Scheduling: Planning under Uncertainty" - "Planning and Scheduling: Planning Algorithms" --- # A Native Qualitative Numeric Planning Solver Based on AND/OR Graph Search Hemeng Zeng, Yikun Liang, Yongmei Liu *Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence*, pages 4693-4700. DOI: [10.24963/ijcai.2022/651](https://doi.org/10.24963/ijcai.2022/651) ## Abstract Qualitative numeric planning (QNP) is classical planning extended with non-negative real variables that can be increased or decreased by some arbitrary amount. Existing approaches for solving QNP problems are exclusively based on compilation to fully observable nondeterministic planning (FOND) problems or FOND+ problems, i.e., FOND problems with explicit fairness assumptions. However, the FOND-compilation approaches suffer from some limitations, such as difficulties to generate all strong cyclic solutions for FOND problems or introducing a great many extra variables and actions. In this paper, we propose a simpler characterization of QNP solutions and a new approach to solve QNP problems based on directly searching for a solution, which is a closed and terminating subgraph that contains a goal node, in the AND/OR graphs induced by QNP problems. Moreover, we introduce a pruning strategy based on termination tests on subgraphs. We implemented a native solver DSET based on the proposed approach and compared the performance of it with that of the two compilation-based approaches. Experimental results show that DSET is faster than the FOND-compilation approach by one order of magnitude, and comparable with the FOND+-compilation approach. ## Full text ## 1 Introduction Qualitative numerical planning (QNP) is classical planning extended with non-negative real variables and nondeterministic actions that increase or decrease the values of these variables by some arbitrary amount. QNP was firstly introduced by Srivastava et al. [2011] to model the problems of planning with loops, where actions may have to be repeated unknown times to reach the goal. Recently, QNP has been widely used for generalized planning because it is decidable and provides a useful abstraction model for generalized planning. Generalized planning studies the computation of solutions that generalize over multiple planning instances [Levesque, 2005]. Some works [Bonet and Geffner, 2018; Bonet et al., 2019] learn potential features (numerical and boolean) and abstract actions from solutions of sample instances, and then abstract the generalized planning problems into QNP problems. Illanes and McIlraith [2019] consider a class of generalized planning problems called quantified planning problems, and abstract such problems into QNP problems based on the idea of quantifying over sets of similar objects. ∗Corresponding Author Existing works for solving QNP problems are exclusively based on compilation to fully observable non-deterministic planning (FOND) problems. First of all, Srivastava et al. [2011] propose a generate-and-test approach. They show that a QNP problem Q can be easily compiled into a FOND problem P whose strong cyclic solutions that terminate are solutions to Q. They introduce the SIEVE algorithm for testing whether a solution terminates. However, the generate-andtest method has two limitations: firstly, it is difficult to compute all solutions for P by using off-the-shelf FOND planners; secondly, the generate is done independently of the test, with the result that more solutions than necessary are generated. To save from the termination test, Bonet and Geffner [2020] propose a translator qnp2fond to compile a QNP problem Q into a FOND problem P ′ with extra variables and actions. They show that if Q is solvable, then a solution π′ solves P ′ . However, it remains open whether the flat solution for π′ , i.e., the solution obtained from π′ by ignoring the extra variables and actions, is a solution to the original problemQ. Moreover, introducing extra variables and actions increases the search space exponentially. Very recently, Rodriguez et al. [2021] propose the socalled FOND+ planning, that is, FOND planning with explicit fairness assumptions. They show that QNP is a special class of FOND+ planning, where the fairness assumption is that for any numerical variable x, if the value of x is increased infinitely often but decreased only finitely often, then eventually x becomes 0. They develop a FOND+ solver FONDASP by reducing FOND+ planning to answer set programming (ASP) [Brewka et al., 2011]. AND/OR graphs have been widely used in planning because the state spaces of many planning problems can be formalized as AND/OR graphs which can be traversed by offthe-shelf heuristic search algorithms, such as AO* [Nilsson, 1982] and LAO* [Hansen and Zilberstein, 2001]. To solve a FOND problem P, Bercher and Mattm¨uller [2009] introduce an approach that traverses the AND/OR graph induced by P using AO* to compute a strong solution. Mattm¨uller et al. [2010] find strong cyclic solutions for FOND problems by performing LAO* search. In this paper, we propose a new approach to solve a QNP problem Q based on directly searching for a solution in the AND/OR graph induced by Q. Our approach is based on a simpler characterization of QNP solutions and a key observation about termination of policies. Srivastava et al. [2011] characterize a solution to a QNP problem as a strong cyclic solution that terminates. We give a simpler characterization that a solution to a QNP problem is a closed and terminating policy with a reachable goal node. We make the key observation that any extension of a non-terminating policy is also non-terminating. Thus, we search over all policies by a backtracking algorithm and on identifying a non-terminating one, we prune all its extensions. Based on the proposed approach, we implemented a QNP solver DSET, and compared the performance of DSET with that of the compilation-based approach of Bonet and Geffner [2020], using two typical FOND solvers PRP [Muise et al., 2012] and FOND-SAT [Geffner and Geffner, 2018]. Experimental results show that on solvable domains, DSET is faster than the compilation-based solvers by one order of magnitude; and on unsolvable domains, DSET takes a few seconds, while the other solvers time out after 30 minutes. The main reason behind the performance gap is that the compilation to FOND problems introduces many extra variables and actions so that the search space for solutions is exponentially increased. We also compared the performance of DSET with that of FOND-ASP. It turns out that the two solvers have comparable performance on most domains since they consider the same search space for QNP solutions. ## 2 Preliminaries In this section, we introduce QNP problems, AND/OR graphs, and the existing characterization of QNP solutions. Given a set of propositional variables F and a set of nonnegative numerical variables V , we refer to p and ¬p for p ∈ F as the F -literals, and refer to v > 0 and v = 0 for v ∈ V as the V -literals. A pair of complementary literals has the form {p, ¬p} for p ∈ F, or {v > 0, v = 0} for v ∈ V . A set of literals is consistent if it does not contain complementary literals. Let LX (resp. LF ) denote the set of all consistent sets of literals from F ∪ V (resp. F). Definition 1. A QNP problem is a tuple Q = ⟨F, V, I, G, O⟩ where F and V are sets of propositional and non-negative numerical variables, I ∈ LX denotes the initial condition, G ∈ LX denotes the goal condition, O is a set of actions. Every a ∈ O has a set of preconditions pre(a) ∈ LX, propositional effects eff (a) ∈ LF and numerical effects N(a) which only contain special atoms of the form inc(v) or dec(v) (often abbreviated as v↑ or v↓) to increase or decrease v by some arbitrary amount for v ∈ V . Actions with the dec(v) effect must feature the precondition v > 0 for any variable v ∈ V . We distinguish between states and qualitative states (qstates): a state ¯ s is an assignment of values to all variables, a qstate s is an element of LX that contains a literal of each variable. ¯ s satisfies s if the assignment of values for variables in ¯ s satisfies all literals in s. Usually, given a QNP problem Q = ⟨F, V, I, G, O⟩, I is an initial qstate and G is a partially specified qstate corresponding to a set of goal qstates. Definition 2. Given a QNP problem Q = ⟨F, V, I,G,O⟩, an instance of Q is a quantitative planning problem whose initial state, which specifies a non-negative real number for each numerical variable, satisfies I, and the actions and goal condition are the same as Q. A simple QNP problem Qnest2 is shown as follows where ⟨C; E⟩ denotes an action with preconditions C and effects E. Example 1. Qnest2 = ⟨F, V, I,G,O⟩ with F = ∅, V = {x, y}, I = {x > 0, y > 0}, G = {x = 0, y = 0} and O = {a, b, c} where a = ⟨x > 0, y = 0; x ↓, y ↑⟩, b = ⟨y > 0; y ↓⟩, c = ⟨y > 0; y ↓, x ↑⟩. An instance of Qnest2 is one where x = 3 and y = 4 in the initial state. An action a is applicable in a qstate if it contains pre(a). An action a is applicable in a state ¯ s if it satisfies pre(a). If action a is applicable in state ¯ s, a state ¯ s′ is a successor state of ¯ s, if the following conditions hold: ¯ s′ contains eff(a), for each inc(v) ∈ N(a), ¯ s′ (v) > ¯ s(v), for each dec(v) ∈ N(a), ¯ s′ (v) < ¯ s(v), and for each variable v not appearing in eff(a) or N(a), ¯ s′ (v) = ¯ s(v). Definition 3. Given a QNP problem Q, a policy π for Q is a partial mapping from qstates to applicable actions. Given a policy π and a state ¯ s, let s be the qstate satisfied by ¯ s, we use π(s), if it is defined, to represent the action a assigned to ¯ s, and a(¯ s) to represent the set of all possible successor states after applying a in ¯ s. Given a policy π, a sequence of states ¯ s0, ¯ s1, . . . (finite or infinite) is called a πtrajectory if for i ≥ 0, ¯ si+1 ∈ ai(¯ si) where ai = π(si). Definition 4. For ϵ > 0, a π-trajectory is ϵ-bounded, if for any action performed, if it decreases a numerical variable v, then either the old value of v is < ϵ and the new value equals 0 or the amount of decrease is ≥ ϵ. Definition 5. Given a QNP problem Q, a policy π solves an instance of Q if for any ϵ > 0, every ϵ-bounded π-trajectory started at the initial state is goal reaching. A policy π solves Q if it solves every instance of Q. A policy π that solves Qnest2 in Example 1 is given by: π({x > 0, y > 0}) = b; π({x > 0, y = 0}) = a; π({x = 0, y > 0}) = b. Definition 6. Given a QNP problem Q, a policy π terminates if for any instance of Q, for any ϵ > 0, every ϵ-bounded πtrajectory started at the initial state is finite. The qstate space of a QNP problem can be formalized as an AND/OR graph. We now introduce basic terminologies of AND/OR graphs. An AND/OR graph G = ⟨N, C⟩ consists of a set of nodes N and a set of connectors C, where a connector is a pair ⟨n,M⟩, connecting the incoming node n ∈ N to a nonempty set of outgoing nodes M ⊆ N. A k-connector is a connector with exactly k outgoing nodes. Usually, G contains a distinguished initial node n0 ∈ N and a set of goal nodes Ng ⊆ N. A path in G is a sequence of nodes successively linked by connectors. A subgraph of G is an AND/OR graph G ′ = ⟨N ′ , C ′ ⟩ such that N ′ ⊆ N and C ′ only contains connectors from C whose involved nodes (incoming and outgoing nodes) are contained in N ′ . Usually, we require that the initial node n0 is contained in N ′ as the initial node n′0 and the set of goal nodes N ′g = N ′ ∩ Ng. In this paper, we restrict our attention to subgraphs where every non-goal node has at most one outgoing connector. We say a subgraph G ′ is closed if every non-goal node in G ′ has exactly one outgoing connector. We say a subgraph G ′ is proper if for every non-goal node n′ in G ′ , there is a finite path starting at n′ and ending in a goal node. The qstate space of a QNP problem Q can be formalized as an AND/OR graph G = ⟨N,C⟩. Specifically, nodes in N correspond to qstates of Q, the initial node corresponds to the initial qstate of Q and the goal nodes correspond to the goal qstates of Q. For an action a applicable in a qstate s, the application of a to s results in a set of qstates, denoted as a(s). The action with inc(v) results in a qstate with literal v > 0. The action with dec(v) results in two qstates, one with literal v > 0 and the other with v = 0. There is a connector ⟨s, a(s)⟩ ∈ C for each qstate s and action a applicable in s. The AND/OR graph induced by Qnest2 is shown in Figure 1 where the two nodes s0 and sg respectively correspond to the initial qstate and the goal qstate and the labels of connectors correspond to the names of actions in Qnest2 . Figure 1: The AND/OR graph induced by Qnest2 ![Image](https://ijcai.org/proceedings/2022/fulltext/651/image_000000_608477b9005907514c2d7fa713c61b6c8d666accc391f776ab1d9eea82ed9f92.png) Obviously, given a QNP problem Q and the AND/OR graph G induced by Q, there is a one-to-one correspondence between policies for Q and subgraphs of G. Thus, in the paper, we will use "policy" and "subgraph" interchangeably. A closed and proper subgraph is called a strong cyclic solution. The following result was proved by Srivastava et al. [2011]: Theorem 1. Given a QNP problem Q, a policy π solves Q iff it is a strong cyclic solution that terminates. Srivastava et al. [2011] introduce a sound and complete algorithm SIEVE, that verifies whether a policy π for Q terminates. Given G, the qstate transition graph induced by Q and π, SIEVE iteratively removes edges from G until G becomes acyclic or no additional edges can be removed as shown in Algorithm 1. SCC is the abbreviation for the strongly connected component of a graph. ## Algorithm 1: SIEVE ## Input: G 1 repeat - 2 Compute the SCCs of G; - 3 Choose an SCC g and a variable v that is decreased but not increased in g; - 4 if there is no such v to choose then - 5 return "Non-terminating"; - 6 Remove the edges (s, s′ ) such that s and s′ are in g and π(s) has a dec(v) effect; - 7 until G is acyclic; - 8 return "Terminating"; ## 3 Theoretic Foundation In this section, we introduce the theoretic foundation for our algorithm, i.e., a simpler characterization of QNP solutions and a key observation about termination of policies. The result of Srivastava et al. [2011] characterizes a solution to a QNP problem as a proper and closed subgraph that terminates. We now give a simpler characterization that a solution to a QNP problem is a closed subgraph that contains a goal node and terminates. Thus we replace the "properness" condition by the much relaxed condition of "presence of a goal node". Theorem 2. Given a QNP problem Q and the AND/OR graph G induced by Q, a subgraph G ′ of G is a solution to Q iff G ′ contains a goal node, is closed, and terminates. Proof. By Theorem 1, the only-if direction is easy since properness implies that there is a goal node. To prove the if direction, we only need to prove every non-goal node in G ′ is goal-reaching. We call nodes in G ′ that cannot reach a goal node deadends. Assume to the contrary that G ′ contains some deadends. Clearly, deadends can only reach deadends. Thus, there exists a SCC of deadends, otherwise, we get infinitely many deadends, contradicting that G is a finite graph. We call a SCC g a closed one if the outgoing nodes of all connectors in g are in g. Then there exists a closed SCC of deadends, otherwise, we get infinitely many SCCs, or we get a cycle of SCCs, which can be merged into a SCC, contradicting that each on the cycle is a SCC. Let g be a closed SCC of deadends. We now prove that this contradicts that G ′ passes the SIEVE test. For any variable v that is decreased in g, there is an edge (s, s′ ) in g where v > 0 in s and v = 0 in s′ ; since s′ is reachable from s in g, v must be increased in g. Thus no edge can be removed from g by SIEVE, so G ′ cannot pass the SIEVE test. Finally, we make the following observation: Proposition 1. Given a QNP problem Q, any policy that extends a non-terminating policy is also non-terminating. Proof. Let π be a non-terminating policy. Then there exists an infinite ϵ-bounded π-trajectory σ for some instance of Q and ϵ > 0. Let π′ extend π. Then σ is also a π′ -trajectory. Thus π′ is also non-terminating. ## 4 Find Solutions for QNP Problems With the above theoretic foundation, we propose a new approach that solves a QNP problem Q directly by searching subgraphs of the AND/OR graph G induced by Q. It will enumerate terminating subgraphs of G until a proper one that contains a goal node is found. When a non-terminating subgraph is identified, it will not be further expanded and thus pruning is done. ## 4.1 Avoid Non-terminating Solutions An important part of our approach is to generate terminating subgraphs, which improves the basic idea of the generateand-test approach by [Srivastava et al., 2011]. The basic generate-and-test approach solves a QNP problem Q by iteratively generating and verifying the termination of strong cyclic solutions (also called candidate solutions) of Q one by one until a terminating one is found or all candidate solutions are enumerated and verified to be non-terminating. However, it is inefficient due to the independence between the generation procedure and the termination test procedure because candidate solutions which have been tested and fail to terminate are not fully utilized to avoid generating nonterminating candidate solutions. As shown by Proposition 1, any subgraph that extends a non-terminating subgraph is non-terminating. Therefore, if the termination of subgraphs can be verified in advance, the generation of subgraphs containing non-terminating ones can be avoided. ## 4.2 Detailed Algorithm The pseudocode of our approach is shown in Algorithm 2. G is the AND/OR graph representing the qstate space of Q. The size of G is exponential with the number of variables in Q. s0 is the initial node. Sg is the set of goal nodes. G ′ is a subgraph corresponding to a policy for Q and initialized as containing only s0. A node in G ′ is said to be expanded if one of its outgoing connectors is chosen and added into G ′ . open is a stack storing the unexpanded nodes in G ′ and every node in open is reachable from s0. closed is an ordered list storing the expanded nodes in G ′ . The nodes in closed are arranged in the order they are expanded. In Algorithm 2, we will repeatedly pop the top node s from open and try to expand s until open is empty. If s is a nongoal node, it will try to expand s. When expanding, we ensure that G ′ is always terminating. A connector c is legal with respect to G ′ iff G ′ still terminates when adding c to it. Backtracking will be performed when failed to expand G ′ to satisfy conditions of terminating and containing a goal node. When trying to expand s in Algorithm 3, we examine each unvisited connector of s, test if it is legal and mark it as visited. If a legal connector c is found, it will be added to G ′ . Sc denotes the set of all outgoing nodes of c. We will add s to the end of closed meaning that s is the latest expanded node. In order to backtrack correctly, it is necessary to record the incoming connector when pushing a node into open. We record InConnector(s′ ) for s′ ∈ Sc if s′ has not been expanded and is not in open, and then push s′ into open. When failed to expand s, meaning that there is no legal connector for s with respect to G ′ , we undo the marking of all ## Algorithm 2: QNP Solver ``` Input: G, s0, Sg Output: a solution graph G ′ or "Unsolvable" 1 G ′ ← ⟨{s0}, ∅⟩; 2 open← {s0}; 3 closed ← {}; 4 repeat 5 if open ̸= ∅ then 6 s ← open.pop(); 7 if s /∈ Sg then 8 EXPAND(s); 9 if failed to expand then 10 if s = s0 then 11 return "Unsolvable"; 12 else BACKTRACK; 13 else 14 if G ′ contains at least one goal node then 15 return G ′ ; 16 else BACKTRACK; ``` connectors of s (to prepare for backtracking), then we backtrack or exit depending on whether s is the initial node as shown in Algorithm 2 Line 9-12. s = s0 means that we cannot backtrack thus we return "Unsolvable". s ̸= s0 means that we have to examine the next outgoing connector of the last expanded node, which is the last node in closed. So backtracking will be performed as shown in Algorithm 4. When open is empty, meaning that G ′ has no unexpanded nodes, G ′ is closed. As shown in Algorithm 2 Line 13-16, we will exit or backtrack depending on whether G ′ contains goal nodes. If G ′ contains at least one goal node, it means G ′ satisfies all the conditions in Theorem 2 and it is a solution of Q. If there is no goal node in G ′ , we will backtrack and try to re-expand the last expanded node as shown in Algorithm 4. As shown by Bonet and Geffner [2020], the complexity of solution existence for QNP problems is EXP-Complete. However, in the worst case, the time complexity of Algorithm 2 is doubly exponential with the number of variables of the given QNP problem since it will enumerate all subgraphs of the induced AND/OR graph. ## 4.3 Soundness and Completeness Theorem 3 (Soundness of Algorithm 2). Given a QNP problem Q, if Algorithm 2 returns a solution graph G ′ , then G ′ corresponds to a policy that solves Q. Proof. Proving soundness of Algorithm 2 is equivalent to proving that the solution graph G ′ returned by Algorithm 2 satisfies all three conditions in Theorem 2. Firstly, Algorithm 2 returns G ′ if the condition that G ′ contains at least one goal node and open = ∅ is satisfied. open is empty means that all non-goal nodes in G ′ are successfully expanded and have exactly one connector, so G ′ is closed. Secondly, Algorithm 3 guarantees that only the legal connectors can be added into G ′ and thus G ′ always terminates. ``` 1 Cs ← the set of unvisited connectors of s ; 2 foreach c ∈ Cs do 3 G←Graph(G ′ + c); 4 mark c as visited; 5 if SIEVE(G) = "Terminating" then 6 add c to G ′ ; 7 add s to the end of closed; 8 9 foreach s′ ∈ Sc do 11 InConnector(s′ ) ← c; 12 open.push(s′ ); return success; ``` ``` Sc ← the set of outgoing nodes of c; 10 if s′ /∈ open ∧ s′ /∈ closed then 13 14 open.push(s); 15 mark all connectors of s as unvisited; 16 return failure; ``` ``` Algorithm 3: EXPAND(s) Algorithm 4: BACKTRACK ``` ``` 1 s ← remove the last node of closed; 2 c ← the assigned connector of s; 3 Sc ← the set of outgoing nodes of c; 4 foreach s′ ∈ Sc do 5 if InConnector(s′ ) = c then 6 InConnector(s′ ) ← NULL; 7 remove s′ from open; 8 remove c from G ′ ; 9 open.push(s); ``` Theorem 4 (Completeness of Algorithm 2). Given a QNP problem Q, if Q is solvable, Algorithm 2 will return a solution graph corresponding to one of the policies that solve Q. Proof. When expanding G ′ in Algorithm 3, the pruning strategy is based on SIEVE. We ignore the pruning strategy since it performs pruning only when any expanding leads to a nonterminating G ′ , which can not be a part of the solution graph of Q according to Proposition 1. We prove that Algorithm 2 enumerates all closed subgraphs, in which there is exactly one outgoing connector for each non-goal node. Algorithm 3 assigns one of the outgoing connectors to s0 and add it to G ′ . All non-goal nodes s reachable from s0 in G ′ are pushed into open, and then will be assigned one outgoing connector and added to the end of closed, until G ′ is closed. In this process, all outgoing connectors of s are assigned to s one by one. When all outgoing connectors of s have been enumerated, it will backtrack to assign next outgoing connector of the last expanded node in closed. When all connectors of s0 are enumerated and open is empty, Algorithm 2 enumerates all closed subgraphs. If Q is solvable, it will return a solution graph of Q, one of all closed subgraphs that it enumerates. Table 1: The size of QNP problems and the corresponding FOND problems obtained by qnp2fond and the time for translation. Problems in the top half part are solvable while the rest are not. |fQ| and |AQ| are the number of variables and actions in QNP problems respectively. |fF | and |AF | are the number of variables and actions in the corresponding FOND problems respectively. | Domain | |fQ| | |AQ| | |fF | | |AF | | time(ms) | |---------------|------------------|------------------|-------------------|-------------------|------------| | BlocksClear | 2 | 4 | 20 | 16 | 7.2 | | BlocksOn | 5 | 7 | 47 | 36 | 6.2 | | ChoppingTree | 2 | 2 | 2 | 2 | 3.4 | | Cornera | 2 | 4 | 29 | 23 | 2.9 | | Delivery1 | 4 | 4 | 54 | 39 | 4.1 | | Delivery2 | 4 | 5 | 54 | 40 | 7.3 | | Delivery3 | 4 | 7 | 54 | 42 | 3.1 | | Gripper1 | 4 | 5 | 54 | 44 | 3.3 | | Nest2 | 2 | 2 | 29 | 19 | 10.2 | | Nest3 | 3 | 3 | 47 | 33 | 3.9 | | Nest10 | 10 | 10 | 285 | 243 | 11.0 | | Q1 | 4 | 4 | 4 | 4 | 2.6 | | Q3 | 4 | 4 | 41 | 29 | 5.7 | | Rewards | 2 | 2 | 29 | 19 | 2.9 | | ShovelingSnow | 3 | 3 | 47 | 30 | 7.7 | | TestOn | 3 | 3 | 35 | 24 | 24.0 | | Logistic1 | 20 | 12 | 517 | 439 | 13.4 | | Logistic2 | 20 | 13 | 517 | 440 | 14.0 | | Nest3u | 3 | 3 | 47 | 36 | 7.8 | | Nest10u | 10 | 10 | 285 | 253 | 13.3 | | Gripper1u | 4 | 5 | 54 | 44 | 2.8 | | Q2 | 4 | 4 | 41 | 29 | 5.5 | ## 5 Implementation and Experiments Based on the proposed approach, we implemented a QNP solver DSET 1 , meaning Direct Search and Early Terminationtesting. We compared the performance of DSET with the existing compilation-based approach that compiles a QNP problem Q into a FOND problem P via a translator qnp2fond [Bonet and Geffner, 2020], which provides a sound and complete translation from QNP problems to FOND problems without termination testing. We solve the resulting FOND problems by two off-the-shelf FOND solvers: PRP [Muise et al., 2012] and FOND-SAT [Geffner and Geffner, 2018]. We also compared with FOND-ASP solver proposed by Rodriguez et al. [2021] which solves QNP problems as FOND+ problems by providing sets of fairness assumptions. We do not compare with the generate-and-test approach proposed by Srivastava et al. [2011] because there are no off-the-shelf FOND solvers that can enumerate all strong cyclic solutions and it is not simple to amend one solver to do so. All the experiments were conducted on a Linux machine with a 2.9GHz Intel 10700 CPU and 4GB of memory. ## 5.1 Experimental Domains We adopt the following domains: - ChoppingTree, Nest2, Nest3 and ShovelingSnow are from Srivastava et al. [2011]. BlocksOn, Delivery2, [1 DSET is available at https://github.com/sysulic/DSET](https://github.com/sysulic/DSET) Table 2: Summary of the results for QNP problems by four solvers. The dashed line in the columns of time denotes out of time or memory while in the columns of size denotes "not applicable". | Domain | DSET - time(s) | DSET - Policy size | FOND-SAT - time(s) | FOND-SAT - Policy size | PRP - time(s) | PRP - Policy size | FOND-ASP - time(s) | FOND-ASP - Policy size | |---------------|------------------|----------------------|----------------------|--------------------------|-----------------|---------------------|----------------------|--------------------------| | BlocksClear | 0.0158 | 2 | 0.1007 | 4 | 0.1067 | 4 | 0.0440 | 2 | | BlocksOn | 0.0117 | 7 | 1.9778 | 11 | 0.2253 | 11 | 0.0471 | 7 | | ChoppingTree | 0.0127 | 2 | 0.0658 | 3 | 0.0617 | 3 | 0.0430 | 2 | | Cornera | 0.0165 | 2 | 0.2008 | 6 | 0.0875 | 5 | 0.5200 | 2 | | Delivery1 | 0.0139 | 6 | 2.3177 | 11 | 0.2658 | 16 | 0.0523 | 6 | | Delivery2 | 0.0217 | 6 | 2.1919 | 11 | 0.4689 | 16 | 0.1010 | 6 | | Delivery3 | 0.0287 | 6 | 2.3840 | 11 | 0.4873 | 16 | 0.0586 | 6 | | Gripper1 | 0.0174 | 10 | 114.9385 | 16 | 0.2463 | 28 | 0.1030 | 10 | | Nest2 | 0.0140 | 3 | 0.3720 | 9 | 0.1621 | 7 | 0.0450 | 3 | | Nest3 | 0.0179 | 7 | 3.5786 | 14 | 0.6258 | 15 | 0.0777 | 7 | | Nest10 | 5.1119 | 1023 | - | - | - | - | - | - | | Q1 | 0.0126 | 4 | 0.0735 | 4 | 0.0833 | 4 | 0.0465 | 3 | | Q3 | 0.0144 | 6 | 0.3989 | 6 | 0.1260 | 7 | 0.0437 | 4 | | Rewards | 0.0155 | 2 | 0.1886 | 6 | 0.1475 | 5 | 0.0408 | 2 | | ShovelingSnow | 0.0116 | 4 | 1.0984 | 11 | 0.2461 | 10 | 0.0436 | 4 | | TestOn | 0.0122 | 3 | 0.3167 | 7 | 0.1058 | 6 | 0.0433 | 3 | | Logistic1 | 15.6873 | 105 | - | - | - | - | 58.2216 | 127 | | Logistic2 | - | - | - | - | - | - | - | - | | Nest3u | 0.0147 | - | - | - | 22.0863 | - | 0.0460 | - | | Nest10u | 2.0198 | - | - | - | - | - | 21.2016 | - | | Gripper1u | 0.0187 | - | - | - | 743.6844 | - | 0.0586 | - | | Q2 | 0.0097 | - | - | - | 1200.2490 | - | 0.0430 | - | Gripper1 and Rewards are from Bonet et al. [2019]. BlocksClear, Delivery1, Delivery3, Q1, Q2 and Q3 are from Bonet and Geffner [2020] and Q2 is an unsolvable domain. - To test the performance of DSET on domains of larger size, we design three new solvable domains: Nest10 with a 10-fold nested loop, which is similar to Nest2 and Nest3, Logistics1, which is a QNP abstraction of the classical Logistics problem by grouping indistinguishable objects, and Logistics2, which adds to Logistics1 an extra action. - Considering that a QNP solver means that it not only returns a solution for solvable problems, but also informs about unsolvability for unsolvable problems, just like SAT solvers, we add three unsolvable domains Nest3u, Nest10u and Gripper1u by modifying the corresponding domains. More specifically, the preconditions and effects of some actions are rewritten so as to make the domains unsolvable. Table 1 shows the size of the benchmark QNP problems and the corresponding FOND problems generated by qnp2fond and the time for translation. In most cases, the corresponding FOND problems P have a much larger size than the original QNP problems Q because qnp2fond adds many extra variables and actions involving the stack operations for each numerical variable to guarantee that the solution of P corresponds to a solution of Q. Generally speaking, the number of stack-related variables and actions in P is cubic polynomial in the number of numerical variables in Q. ## 5.2 Main Results We compared the performance of the four solvers, each of which is evaluated in terms of solving time (the running time needed to solve a problem) and policy size (the number of qstate-action pairs in the solution) as shown in Table 2. The timeout is set to 1800 seconds to prevent a solver from running indefinitely. To eliminate the interference of background processes, for each problem, we run each solver 10 times, which is an empirical value, and take the average as the reported running time. The running time in the columns of FOND-SAT and PRP is the sum of the running time of the translator qnp2fond and the FOND solver. The solving time of DSET is less than that of FOND-SAT and PRP by more than an order of magnitude on most solvable QNP problems. The reason is that DSET searches for solutions in a much smaller qstate space and performs pruning when a non-terminating subgraph is found, while FONDSAT and PRP struggle with a much larger qstate space, especially for those hard problems like Nest10, Logistic1 and Logistic2. The running time of DSET increases with the size of QNP problems. Logistic1 can be solved within 16 seconds; however, with just one extra action, Logistic2 makes DSET run out of time. Since DEST is a naive enumeration method, these two domains are designed to test the border of scalability. When QNP problems are unsolvable, DSET returns "Unsolvable" within seconds while PRP and FOND-SAT usually take a much longer time and even timeout. For most QNP problems, solvable or unsolvable, the running time of DSET is comparable with that of FOND-ASP since they search or compute solutions in the same qstate space. When computing Nest10, FOND-ASP runs out of memory. The policies returned by DSET usually have a smaller size. A smaller policy is not necessarily more efficient, but it is more succinct. The reason why PRP and FOND-SAT return larger policies is that the FOND problems generated by qnp2fond require that a numerical variable v can be decreased only after v is pushed into the stack and v can be increased if v is not in the stack. If a numerical variable is in the stack, it must be popped before it can be increased. With this mechanism, PRP and FOND-SAT will return policies of larger size since some Push or Pop actions must be applied before a numerical variable is decreased or increased. In the following part, we focus on the analysis of one typical unsolvable QNP problem to illustrate why DSET returns "Unsolvable" much more quickly than PRP and FOND-SAT. Example 2. Q2 = {F, V, I,O,G} is an unsolvable QNP problem where F = {p, g}, V = {x, y}, I = {p, ¬g, x > 0, y > 0}, G = {g} and O = {a1, a2, a3, a4} where a1 = ⟨p, x > 0; ¬p, x ↓⟩, a2 = ⟨¬p; p, x ↑⟩, a3 = ⟨x = 0; g⟩ and a4 = ⟨y = 0; g⟩. Figure 2: The Qstate Transition Graph of Q2 ![Image](https://ijcai.org/proceedings/2022/fulltext/651/image_000001_6b03ce995cacf1577685ea0e12964a025f7b3397f6e09c31a8fc28eb47ff7d58.png) As shown in Figure 2, a4 is inapplicable in any qstates reachable from s0 since there is no action with the effect y ↓ and thus the precondition of a4 will never be satisfied. Moreover, it can be easily verified that Q2 has no solution because the action a2, which must be used to restore the precondition of a1 in the loop, increases x at the same time. Therefore, x will be decreased and increased in the loop forever and the policy will not terminate. It took DSET 0.0097 seconds to return "Unsolvable" for Q2, which is negligible compared with the running time of PRP and FOND-SAT. It took PRP 1200.2490 seconds to return "Unsolvable" because the corresponding FOND problem of Q2, has a much larger size and makes it timeconsuming for PRP. Specifically, PRP can prune the qstate space significantly by locating and propagating the deadends, which is based on the relevance between qstates. However, qnp2fond introduces a lot of stack-related variables and thus results in weaker relevance between qstates. ## 5.3 Evaluation of the Pruning Strategy Considering that the dataset shown in Table 1 is limited, to measure the impact of pruning non-terminating policies ahead of time, we set the number of numeric variables M and the number of actions N, randomly generate a set of 500 QNP problems Q = ⟨F, V, I,G,O⟩ where |F| = 3, |V | = M, |O| = N, as follows. I contains a literal of each variable in F ∪ V ; G and pre(a), a ∈ O, contain a literal of each variable in F ∪ V with probability 0.5; eff (a) contains a literal of each variable in F with probability 0.5, and contains the atom inc(v) or dec(v) of each variable in V with probability 0.5. Each literal in I, G and O is produced by randomly choosing from a pair of complementary literals of the corresponding variable. Each atom in eff (a) is produced by randomly choosing from a pair of inc(v) and dec(v) of the corresponding variable v. Table 3: Additional experiments. |VQ| and |AQ| are the number of numeric variables and actions in QNP problems respectively. | Domain | |VQ| | |AQ| | pruning(s) | no pruning(s) | |----------|------------------|------------------|--------------|-----------------| | Random1 | 8 | 12 | 0.3594 | 0.0753 | | Random2 | 10 | 20 | 1.3115 | 8.8865 | As shown in Table 3, we randomly generate 2 sets of 500 QNP problems using the method described above; compute the average running time of DSET on each set and compare the results with and without the pruning strategy. It turns out that there is a trade-off between pruning but doing termination-testing on non-closed subgraphs and nonpruning but only doing termination-testing on closed subgraphs. On Random1, the pruning strategy does not pay off; however, pruning shows its significant advantage on Random2. ## 6 Conclusions In this paper, we first propose a simpler characterization that a QNP solution is a closed and terminating policy with a reachable goal node, and make the observation that any extension of a non-terminating policy is also non-terminating. Based on the above characterization and observation, we propose a native QNP solver DSET, which works by formalizing the qstate space of a QNP problem Q into an AND/OR graph G and performing a subgraph search algorithm on G for solutions with a pruning strategy that involves termination tests of subgraphs. Experimental results show that on solvable QNP problems, the running time of DSET is less than that of the compilation-based approach proposed by Bonet and Geffner[2020] using FOND solvers PRP and FOND-SAT by more than an order of magnitude. For unsolvable QNP problems, DSET returns "Unsolvable" much more quickly than PRP and FOND-SAT. Meanwhile, DSET is comparable with the FOND+ solver FOND-ASP by Rodriguez et al. [2021]. However, DSET is a naive enumeration method and thus suffers from scalability as shown by the Logistic2 domain and classical planning instances since QNP extends classical planning. In the future, We will try to improve scalability of DSET with heuristic search. We are also interested in expanding the work presented in this paper to solve QNP problems where numeric variables are increased or decreased by restricted amounts rather than by some arbitrary amount. Such problems can function as better abstraction models for generalized planning. ## Acknowledgments We acknowledge support from the Natural Science Foundation of China under Grant No. 62076261. ## References 1. [Bercher and Mattmüller, 2009] Pascal Bercher and Robert Mattmüller. Solving non-deterministic planning problems with pattern database heuristics. In KI 2009: Advances in Artificial Intelligence, pages 57-64, 2009. 2. [Bonet and Geffner, 2018] Blai Bonet and Hector Geffner. Features, projections, and representation change for gener- alized planning. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pages 4667-4673, 2018. 3. [Bonet and Geffner, 2020] Blai Bonet and Hector Geffner. Qualitative numeric planning: Reductions and complexity. J. Artif. Intell. Res., 69:923-961, 2020. 4. [Bonet et al., 2019] Blai Bonet, Guillem Francès, and Hector Geffner. Learning features and abstract actions for com- puting generalized plans. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), pages 2703- 2710, 2019. 5. [Brewka et al., 2011] Gerhard Brewka, Thomas Eiter, and Miroslaw Truszczynski. Answer set programming at a glance. Commun. ACM, 54(12):92-103, 2011. 6. [Geffner and Geffner, 2018] Tomas Geffner and Hector Geffner. Compact policies for fully observable non- deterministic planning as SAT. In Proceedings of the 28th International Conference on Automated Planning and Scheduling (ICAPS), pages 88-96, 2018. 7. [Hansen and Zilberstein, 2001] Eric A. Hansen and Shlomo Zilberstein. LAO*: A heuristic search algorithm that finds solutions with loops. Artif. Intell., 129(1-2):35-62, 2001. 8. [Illanes and McIlraith, 2019] León Illanes and Sheila A. McIlraith. Generalized planning via abstraction: Arbi- trary numbers of objects. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), pages 7610- 7618, 2019. 9. [Levesque, 2005] Hector J. Levesque. Planning with loops. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI), pages 509-515, 2005. 10. [Mattmüller et al., 2010] Robert Mattmüller, Manuela Or- tlieb, Malte Helmert, and Pascal Bercher. Pattern database heuristics for fully observable nondeterministic planning. In Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS), pages 105- 112, 2010. 11. [Muise et al., 2012] Christian J. Muise, Sheila A. McIlraith, and J. Christopher Beck. Improved non-deterministic planning by exploiting state relevance. In Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS), 2012. 12. [Nilsson, 1982] Nils J. Nilsson. Principles of Artificial Intel- ligence. Springer, 1982. 13. [Rodriguez et al., 2021] Ivan D. Rodriguez, Blai Bonet, Se- bastian Sardiña, and Hector Geffner. Flexible FOND plan- ning with explicit fairness assumptions. In Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS), pages 290-298, 2021. 14. [Srivastava et al., 2011] Siddharth Srivastava, Shlomo Zil- berstein, Neil Immerman, and Hector Geffner. Qualita- tive numeric planning. In Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI), pages 1010- 1016, 2011.