Computing Planning Centroids and Minimum Covering States using Symbolic Bidirectional Search

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 13:54:30

Abstract: In some scenarios, planning agents might be interested in reaching states that keep certain relationships with respect to a set of goals. Recently, two of these types of relationships were proposed: centroids, which minimize the average distance to the goals; and minimum covering states, which minimize the maximum distance to the goals. Existing approaches compute these states by searching forward either in the original or a reformulated task. In this paper, we propose several algorithms that use symbolic bidirectional search to efficiently compute centroids and minimum covering states. Experimental results in both existing and novel benchmarks show that our algorithms scale much better than previous approaches, establishing a new state of the art technique for this problem.

Main paper: 
 introduction: 
 Automated Planning typically deals with the task of finding a sequence of actions, namely a plan, which achieves a goal state from a given initial state (Ghallab, Nau, and Traverso 2004) . However, in some scenarios planning agents might be interested in reaching states that keep certain relationships with respect to a set of (potential) goals. Recently, two of these states were proposed (Pozanco et al. 2019; Karpas 2022) : centroids, which minimize the average distance to the goals; and minimum covering states, which minimize the maximum distance to the goals. These states have proven to be useful for tasks such as deceptive planning (Price et al. 2023) or anticipatory planning (Burns et al. 2012) .Figure 1 illustrates the centroid (blue) and minimum covering states (green) of the planning task introduced by Pozanco et al. (2019) , where a forest ranger has to put out fires that might arrive dynamically in the locations marked with a flame. Under these circumstances, the ranger should generate a plan to set the camp at a location that minimizes the cost (time) of a plan to put out any fire that might arrive.There exist two approaches in the literature to compute these states. The first one, introduced by Pozanco et al. (2019) , uses a best-first search algorithm that expands all the reachable states from the initial state, computing one optimal plan to each goal from each state. The second approach, introduced by Karpas (2022) , compiles the original planning task into a multi-agent planning task where each agent is trying to achieve one of the goals. They proposed two slightly different compilations for centroids and minimum covering states, both being inspired by seminal work on goal recognition design (Keren, Gal, and Karpas 2014, 2015) . In the reformulated task to compute centroids, agents can either perform actions together, with an associated cost of 0, or split and perform actions separately, with their original cost. The idea behind the compilation is that the agents will try to execute as many joint actions as possible, and the state where they start executing separate actions will be the centroid of the planning task. Empirically, Karpas (2022) showed that computing centroid and minimum covering states by solving the reformulated tasks was orders of magnitude faster than using the exhaustive search approach by Pozanco et al. (2019) in most planning tasks.In this paper we propose to use symbolic bidirectional search to compute centroid and minimum covering states. We believe this search paradigm offers two main benefits over previous approaches. First, symbolic search uses succint data structures to efficiently represent and manipulate sets of states. This allows us to compute all the centroid and minimum covering states without conducting exhaustive search. Second, these states are defined as those that (i) optimize a given statistical measure with respect to their distance to the goals; and (ii) are reachable from the initial state. We can speed-up their computation by using backward search to find the former, and forward search to find the latter.In the rest of the paper we introduce a set of symbolic bidirectional search algorithms to compute centroid and minimum covering states. Experimental results in both existing and novel benchmarks show that these algorithms are faster and scale better than state of the art approaches. 
preliminaries classical planning: 
 A SAS + planning task (Bäckström and Nebel 1995) can be defined as a tuple Π = ⟨V, I, O, G⟩. V is a finite set of state variables, each associated with a finite domain D v . A partial state p is a function on a subset of variables V p ⊆ V that assigns each variable v ∈ V p a value in its domain, p[v]. A state s is a complete assignment to all the variables. With S we refer to the set of all possible states defined over V . We also use partial states to represent conditions on states. A state s satisfies a condition p (s |= p) if s(v) = p(v) for all v ∈ V p . We also identify any partial state p with the set of states that satisfy it: S p = {s | s |= p}. The state I ∈ S is the initial state of the planning task, and G is the goal condition, which defines the set of goal states S G ⊆ S.O is a set of operators, where an operator is a tuple o = ⟨pre o , eff o , c o ⟩ of partial variable assignments called preconditions and effects, respectively, andc o → N 0 is the non- negative cost of o. An operator o ∈ O is applicable in state s iff pre o is satisfied in s, i.e., s |= pre o . Applying operator o in state s results in a state s[o] where s[o](v) = eff o (v) for all variables v ∈ V eff o and s[o](v) = s(v) for all other variables.A sequence of operators π = ⟨o 0 , . . . , o n-1 ⟩ is applicable in a state s 0 if there are states s 1 , . . . , s n such that o i is applicable in s i-1 and s i = s i-1 [o i ] for all i = 0, . . . , n. The resulting state of this application is s 0 [π] = s n , and c(π) = oi∈π c oi denotes the cost of this sequence of operators. A state s is reachable iff there exist a sequence of operators π applicable in I such that I[π] = s. With S R ⊆ S we refer to the set of all reachable states of the planning task. The solution to a planning task Π is a plan, i.e., a sequence of operators π such that I[π] ∈ S G . A plan with minimal cost is optimal.We denote as h * (s, s ′ ) the optimal cost of reaching state s ′ from state s. If there is no path between the two states, h * (s, s ′ ) = ∞. We denote as g(s) = h * (I, s), and h * G (s) :S → N 0 ∪ {∞} for a goal G as min s G ∈S G h * (s, s G ).Binary Decision Diagrams (BDDs) (Bryant 1986 ) are a efficient data-structure to encode Boolean functions {0, 1} n → {⊤, ⊥}. We use BDDs to represent sets of states S ⊆ S. This requires to consider some arbirary encoding of the values of the state variables V in binary. To simplify the presentation, we assume without loss of generality that the set of variables V have a binary domain. Each set of states S is represented by a BDD encoding its characteristic function X S : S → {⊤, ⊥}, where X S (s) = ⊤ iff s ∈ S. We denote the set of states represented as a BDD as B.A BDD (Figure 2a ) is a directed acyclic graph with a single root node and up to two terminal nodes, ⊤ and ⊥. Each inner node corresponds to a binary variable v ∈ V , and has two successors depending on whether s(v) = 0 (dashed edge), or s(v) = 1 (solid edge). The size of a BDD |B| is simply the number of nodes in its directed acyclic graph. Given a state s ∈ S, and a BDD B, it can be checked whether s belongs to the set represented by B by a simple top-down traversal, which will always end in ⊤ if s ∈ B and ⊥ otherwise. For example, the BDD in Figure 2a has 5 nodes and represents a set with 3 states:{v 1 → 0, v 2 → 0, v 3 → 0}, {v 1 → 0, v 2 → 1, v 3 → 0}, and {v 1 → 1, v 2 → 1, v 3 → 0}.In general, the number of states represented by a BDD can be exponentially larger than its number of nodes. We denote as B p the BDD representing a (partial) state p, i.e., the set of states {s | s |= p}.We assume BDDs are reduced and ordered. BDDs are ordered whenever in any path from the root to the leaves variables are always checked in the same order (though some variables may be skipped). BDDs are reduced whenever (a) there are no irrelevant nodes whose both successor point to the same node; and (b) all nodes are unique (i.e., any equivalent nodes with the same variable and successors are merged). These properties are easy to maintain. Also, they allow to implement efficient operations on BDDs, whose runtime depends on the size of the BDDs and not on how many states they represent (which, again, could be exponentially larger). Specifically, the union (∪) and intersection (∩) of sets of states can be computed as the disjunction (B ∨ B ′ ) and conjunction (B ∧ B ′ ) of their characteristic functions, respectively. The runtime of these operations is O(|B||B ′ |). However, the conjunction/disjunction of n BDDs is worstcase exponential in n.Algebraic Decision Diagrams (ADDs) (Bahar et al. 1997 ) are similar to BDDs, but have an arbitrary numer of terminal nodes with different discrete values. That is, we can use them to represent the previously defined functions g, mapping each state to a numerical value. A schematic representation of an ADD is shown in Figure 2b . The APPLY operation takes an input two ADDs and a binary operation on the terminal values (e.g. +, -, ×, ÷, max, min), and returns a new ADD where the values of its terminal nodes are defined by the result of the binary operations. The runtime is O(ADD 1 , ADD 2 ).ADDs can be converted into BDDs and viceversa (Speck 2022 ). We will use the BDD(ADD, n ∈ N 0 ) function to convert ADD into a BDD representing the set of states {s | ADD(s) = n}. This can be done in linear time in the size of the ADD by replacing its terminal nodes by ⊤ and ⊥ and applying the reduction rules in a bottom-up fashion. In the example of Figure 2 , the BDD corresponds to BDD(ADD, 0).Symbolic search explores the state space by using the representation of sets of states as BDDs explained above. To do search directly in the symbolic representation, operators are represented as transition relations (TRs). A set of operators O ⊆ O can be represented as a TR containing the set of all state pairs (s, s ′ ) such that s ′ is reachable from s by applying an operator o ∈ O. For a given set of states B and TR T , the image/preimage operator computes all successors/predecessors of B with respect to the operators represented by T .In the forward direction, the search starts with a BDD representing the initial state B I , and iteratively constructs a set of BDDs with an associated cost B 0 , B 1 , B 2 , where B g = {s | h * (I, s) = g} represents the set of states that can be reached from I with a cost of g. Typically, the search terminates whenever the next set of states to be expanded has a non-empty intersection with the set of goal states, also represented as a BDD B G , meaning that an optimal plan has been found. However, one can also choose to continue the search beyond that point to exhaust the set of reachable states.On the other hand, symbolic backward search (regression) starts the search from the goal states, and applies the preimage operation until a non-empty intersection with the BDD that represents the initial state I is found. As a result, we obtain BDDs B 0 , B 1 , B 2 , where B h = {s | h * (s, G) = h} represents the set of states that can reach G with a cost of h. If the search is exhausted (ignoring I), this is equivalent to computing the perfect heuristic h * G . The combination of these two searches forms a bidirectional search used by most modern symbolic search planners (Torralba et al. 2017; Speck, Mattmüller, and Nebel 2020) . We will use STEP to denote a function that computes the image (preimage) of a forward (backward) search. Finally, we will use FINISHED to denote a boolean function that indicates if the given search has been exhausted, i.e., the image/preimage operation does not generate new nonexpanded states.Perimeter search (Dillenburg and Nelson 1994 ) consists of searching a perimeter around the goal. This idea has been used in the construction of heuristic functions for explicitstate search using a symbolic backward search, which is interrupted before termination (Kissmann and Edelkamp 2011; Torralba, Linares López, and Borrajo 2018) .Given an unfinished backward search initialized with G where the sets of states B 0 , . . . , B p have been generated up to h = p, the set of closed states is closed = i∈[0,p] B i , i.e., the set of states for which the real goal distance is known. Then, the perimeter heuristic is h P G (s) := i if s ∈ B i and h P G (s) = p + 1 otherwise. Note that h P G is a lower bound on the actual goal distance, i.e., h P G (s) ≤ h * G (s). As sets of states are generated with increasing values of h, we are certain that any remaining state will have a goal distance of at least p + 1. We will use CLOSED to denote a function that returns a BDD with the set of states closed by a given search. 
centroids, minimum covering states, and beyond: 
 In order to compute planning centroids and minimum covering states, we consider the same setting as in previous works (Pozanco et al. 2019; Karpas 2022 ) using the concept of Planning task with multiple possible goal conditions (PMG).Definition 1 (PMG) A planning task with multiple possible goal conditions is defined as P = ⟨V, I, O, G⟩, where V , I, and O are defined as in a SAS + planning task, and G is a set of possible goal conditions, where each possible goal condition G ∈ G is defined as in a standard planning task.Definition 2 (Planning centroid states) Given a PMG P, planning centroid states are those reachable states s ∈ S R that minimize the sum of costs to the possible goals, i.e., G∈G h * G (s). Definition 3 (Planning minimum covering states) Given a PMG P, planning minimum covering states are those reachable states s ∈ S R that minimize the maximum cost to any of the possible goals, i.e., max G∈G , h * G (s). We introduce a general definition that encompasses these and other states that optimize a given goal-related function.To do that, we first define goal-related functions. Definition 4 (Goal-related function) Let P be a PMG, andh * G (s) = (h * G1 (s), . . . , h * Gn (s)), a vector of optimal costs from s to each goal G i ∈ G. A goal-related function is a function ϕ(h * G (s)) → N 0 ∪ {∞}.Definition 5 (Goals-related states wrt ϕ) Given a PMG P, and a goal-related function ϕ, the set of goal-related states wrt ϕ, S ϕ , is the set of reachable states that minimize ϕ. This definition generalizes centroids (when ϕ is the sum), and minimum covering states (when ϕ is the maximum). In principle, one can be interested in any goal-related function. In this paper, we focus in functions that satisfy the following two properties, both of which are satisfied by centroids and minimum covering states. Definition 6 (Monotonic goal-related functions) A goalrelated function ϕ is monotonic iff increasing any of the costs in h * G (s) does not generate a lower ϕ value. Definition 7 (Aggregatable goal-related functions) A goal-related function ϕ is aggregatable iff its value can be computed by pairwise aggregation of the costs in h * G (s). Let us clarify these definitions by using a vector of costs h * G (s) = (1, 2, 3). In the case of centroids and minimum covering states, ϕ(h * G (s)) can be computed by pairwise aggregation, i.e., max(max(1, 2), 3) = max(1, 2, 3). This is not possible for other goal-related functions such as computing the median of the cost vector. It is also easy to see that when ϕ involves minimizing the sum or the maximum, any increase to any component of that vector would entail a worse solution. However, this is not the case for other goalrelated functions such as achieving a state with the same cost to all the goals, i.e., ϕ(h * G (s)) = max h * G (s) -min h * G (s) = 0. In the rest of the paper we will focus on centroids and minimum covering states, which are defined using monotonic and aggregatable goal-related functions, and use these general definitions to simplify notation.Finally, we are interested in the problem of, given a PMG P, and a function ϕ, find a state that is a goal-related state wrt ϕ. 
computing goals-related states with exhaustive symbolic search: 
 Using bi-directional search offers two main advantages over existing approaches: (i) we can perform independent backward searches for each goal; and (ii) we can decouple the search of candidate solutions from the reachability analysis. The first algorithm we propose is SBD e , an algorithm that exploits these observations by performing (a) exhaustive forward search to find the set of reachable states; and (b) exhaustive backward searches to find the perfect heuristic from each state to each goal. More precisely, SBD e starts by performing |G| independent symbolic backward searches, one from each possible goal G ∈ G, until all the searches are FINISHED. Each of these backward searches will give us an ADD having at the terminal nodes all the states that can achieve each goal G ∈ G with a given cost. We combine all the ADDs into a single backward ADD by using the APPLY operation either with the sum as function, if we are interested in finding centroids, or taking the maximum when computing minimum covering states. We will slightly abuse notation and use APPLY(ADDs, ϕ) to refer to an operation that perform these pairwise operations over a set of ADDs. Then, the algorithm performs a full forward search from the initial state, yielding the set of reachable states S R . We update the backward ADD by setting to ∞ the value of unreachable states, i.e., those states that do not appear in the CLOSED list of the forward search. Finally, we take the minimum of the backward ADD, and extract a BDD with the states that have that value in the backward ADD. The states in that BDD will be the centroids or minimum covering states, depending on the ϕ used in the APPLY operation that combines the backward ADDs. Finally, the algorithm returns any of the states in the BDD as the goal-related state. A plan from I to such state can be easily reconstructed by analyzing the forward search CLOSED list. This algorithm is symmetric, and we could exchange the forward and backward steps obtaining the same result. It could also be seamlessly adapted to compute goals-related states that optimize any aggregatable goal-related function by just modifying how the ADDs are combined. 
from exhaustive to perimeter search: 
 The main drawback of the exhaustive search is that it performs unnecessary computations by obtaining h * to each goal from each state in the problem. Some of these computations are not needed, since we are only interested in monotonic goal-related functions, meaning that we can stop the backward searches once a candidate solution is found.Let us assume a PMG P with 3 possible goals, where we are interested in computing the minimum covering state. The solution to such task is a single state that is at distance 10 of the further goal, and at distances 4 and 3 of the other two, respectively. In this case, any state with h * larger than 10 to any goal will not be part of the solution, so it is unnecessary to expand them as the previous exhaustive algorithm does. However, this raises the following question: up to when do we need to keep exploring?It is clear that we need to explore each search at least up to distances 10, 4, and 3 to each goal, since otherwise we wouldn't know the distance from the solution state to each of the goals. However, that is not sufficient to prove that this is indeed the optimal solution. At this point we know there is no minimum covering state at distance 3 or below, but there could be a solution at distance 5 from each goal. However, we do not need to expand all the backward searches up to distance 10 either. In this case, it would suffice to explore all states at distances 10, 9 and 3, assuming that there is no state at distance 9 or less in the first two searches. Alternatively, we could explore up to 10, 4 and 9, if there is no state at distance 9 or less in the first and third search.To formalize when we have performed enough search to guarantee that we have found the desired goal-related state, we define the set of candidate states with respect to the perimeter heuristics of all backward searches. Definition 8 Let BW be a set of perimeter searches, and h P G = (h P G1 , . . . , h P Gn ) a vector of the perimeter heuristics to each goal G ∈ G. The set of candidate states B C for some goal-related function ϕ(h * G ) is the set of states that minimizes arg min s∈S ϕ(h P G (s)). Proposition 1 Let ϕ(h * G ) be a monotone goal-related function. Let BW be a set of perimeter searches with a set of candidates B C . Then, if there exists s ∈ B C such that s ∈ closed (bw) for all bw ∈ BW and s ∈ S R , then s ∈ S ϕ .Proof: Since s is a candidate, then s has minimum ϕ(h P G ). Since s ∈ closed (bw) for all bw ∈ BW, thenh P G (s) = h * G (s) for all goals G ∈ G. Therefore ϕ(h P G ) = ϕ(h * G ). Finally, let s ′ ∈ S R be any other state. As h P G (s ′ ) ≤ h * G (s ′ ), by monotonicity of ϕ, we have that ϕ(h P G (s ′ )) ≤ ϕ(h * G (s ′ )). So, we conclude that ϕ(h * G ) = ϕ(h P G ) ≤ ϕ(h P G (s ′ )) ≤ ϕ(h * G (s ′ )).As this holds for all s ′ , s is a goalrelated state with respect to ϕ, i.e., s ∈ S ϕ .□ The second algorithm we propose is SBD bw , an algorithm that performs backward search until a solution candidate is found, then running forward search to verify that the candidate solution is reachable. Algorithm 1 shows this process in more detail. At each step (lines 4-18), the algorithm first checks whether there is a candidate solution. This is done by joining all the backward searches in a single ADD through the APPLY operator and the goal-related function ϕ (line 4). Then, the algorithm retrieves the lowest value in the terminal nodes of the resulting ADD, and use it to build a BDD with all the states satisfying that value (lines 5-6). After that, the algorithm checks whether those candidate states have been explored by the backward searches (lines 7-8). bw to advance.STEP()Step backward is the case, SBD bw starts progressing the forward search until a non-empty intersection with the candidate solutions is found. The states in that intersection are reachable and conform the set of minimum covering (centroid) states of the task, and SBD bw returns any of the states in that BDD. Otherwise, the algorithm selects which of the backward searches should be progressed (lines 15-18). First, it updates the set of backward searches BW by filtering out those backward searches that (i) have already finished (line 15); and (ii) have already explored the candidate states (line 16). These two filters leave as alternative to progress those backward searches that have not yet explored the states in B C . Then, the algorithm advances the easiest backward search in BW, which we defined as the one that is estimated to generate a lower number of nodes in the next step. This process is repeated until a minimum covering (centroid) is found.This algorithm can be slightly modified to first run forward search to detect all the reachable states, and then perform the backward searches only over these states. We refer to this variation of the algorithm as SBD f w .Proposition 2 Algorithm 1 always terminates and returns a goals-related states wrt ϕ, for any monotone function ϕ.Proof Sketch: Termination is guaranteed as at every iteration some unfinished backward search will take a step. The number of steps a backward search is bounded by the number of states in the planning task, so eventually all searches will finish. At that point, the goal distance to all states is known, so the algorithm will return a reachable state with minimum goal-related function value.Whenever the algorithm terminates, it always returns a goal-related state. Note that all states in B ϕ are candidates (due to line 6), closed in all unfinished backward searches (due to line 7), and reachable (due to line 11). Therefore, all conditions of Proposition 1 are met. □In the case of minimum covering states we can slightly modify Algorithm 1 to only use BDDs, which are typically faster to manipulate than ADDs. In this version of the algorithm, we do not select which backward search should be progressed, but perform one step in all of them. This is done by replacing lines 16 to 18 by ∀ bwi∈BW bw i .STEP(). Then, we remove lines 4 to 8, and define B C as the intersection of all the backward searches, i.e., G∈G bw G . If B C ̸ = ∅, those states represent candidate solutions, and the reachability check (lines 11-14) remains the same. We refer to these variations of the algorithm as SBDD bw and SBDD f w , depending on whether we start by finding solution candidates or computing reachable states. Note that we cannot use this variation of the algorithm to compute centroids. In that case we cannot stop the algorithm after finding an intersection at distance 2 of G 1 and G 2 (sum of 4), since it does not mean that we could not find an intersection at distance 3 from G 1 and 0 from G 2 (sum of 3). 
experimental setting: 
 Approaches. We implemented our SBD algorithms on top of Symbolic Fast Downward (Torralba et al. 2017) 1 , and compare them against the two other approaches in the literature, GRS and COMP. GRS (Pozanco et al. 2019) 2 uses the Fast Downward planner (Helmert 2006) with the A * search algorithm (Hart, Nilsson, and Raphael 1968 ) and the LMcut heuristic (Helmert and Domshlak 2009) to perform exhaustive search in the original planning task with multiple possible goals P. COMP (Karpas 2022) 3 compiles P into a standard planning task Π. We use two planners to solve Π: the same Fast Downward configuration, as initially proposed by Karpas (2022) , COMP f d ; and the symbolic bi-directional configuration of Symbolic Fast Downward, COMP sbd , so we make sure any performance improvement of SBD does not come from using a different planner.Benchmarks and Reproducibility. We used two benchmarks. The first one consists of all domains and problems available at both software repositories 2,3 , except for HANOI, which contains tasks with only one possible goal. This gives us four planning domains (BLOCKS, FERRY, GRIPPER, and LOGISTICS), and one grid path-finding domain. The planning domains were adapted from standard IPC benchmarks, and the grid path-finding domains consists of 20 × 20 grids with a different percentage of obstacles (5%, 10%, 15%, and 20%). Each domain has 10 problem instances, for a total of 80 problems equally splitted between IPC and grid domains. This benchmark was used by Karpas (2022) , and we will refer to it as SMALL, as most of the tasks consists of small planning problems with few possible goals. For example, all BLOCKS instances contain only 5 blocks and 3 goals. The second benchmark, which we will refer to as LARGE, consists of novel P tasks in the same five domains, where we generated 80 tasks of increasing difficulty. In BLOCKS, we generated these instances by creating random configurations of 6, 8, 10 or 12 blocks, and having 2, 4, 8 or 16 possible goals (words) to be formed by stacking the blocks. In GRID, we generated 10×10, 20×20, 40×40 and 80×80 grids, with 2, 4, 8 or 16 possible goals (agent's locations). For FERRY, GRIPPER and LOGISTICS, we selected the 20 first problems available at the Planning Domains repository 4 , and created 4 different instances for each problem by generating between 2 and 5 possible goals. These goals are sets of cars/balls/packages being delivered at different locations/rooms/cities.Experiments were run on an Intel Xeon E5-2666 v3 CPU @ 2.90GHz x 8 processors with a 8GB memory bound and a time limit of 1800s. Code and benchmarks will be made available upon paper acceptance. 
results: 
 In this section we present the results of our evaluation, where we aim to investigate how our algorithms compare to existing approaches, in terms of coverage and execution time.Table 1 presents the results of our first analysis, where we focus on studying the coverage (C) of each approach, i.e., the number of problems they solve.Regarding centroids (left side of the table), COMP f d solves more than twice the tasks solved by GRS in the small instances, as previously reported by Karpas (2022) . This performance difference is emphasized in the larger tasks, where GRS solves only 22 tasks compared to the 257 for which COMP f d can compute a centroid state. Solving the compiled tasks using a symbolic planner (COMP sbd ) offers a worse performance across all domains, highlighting the fact that the reformulated task does not suit symbolic planners particularly well. Our baseline approach that performs exhaustive search (SBD e ) achieves results that are on par with COMP f d 4 https://github.com/AI-Planning/classical-domains in all small instances except for those from the GRID domain, where SBD e can only solve 1 out of 40 problems. This is because this arguably ill-defined domain uses a redundant (free ?c) predicate to denote that a given cell is free and the agent can move to it. Having this predicate turns GRID tasks into challenging for approaches using backward search, since the set of reachable states is orders of magnitude smaller than the set of states. For example, assuming a 20 × 20 grid without obstacles, the problem will have only 400 reachable states, but more than 2 400 total states that backward searches could potentially consider. This is also the reason why SBD bw obtains similar results, although it outperforms the exhaustive algorithm in larger tasks, being able to solve 44 tasks more. In fact, if we leave GRID aside, SBD bw would be the best performing algorithm, solving 1 task more than SBD f w , the winner across the benchmark with a coverage of 415. By first computing the reachable states and using that information to prune the backward searches, SBD f w is able to solve most of the GRID tasks, as well as showing a good performance in the rest of domains.Similar conclusions can be drawn from the minimum covering states results (right side of Table 1 ). In this case, SBD approaches outperform the compilation approach by even larger margins, with the best performing SBD variant solving 421 tasks compared to the 187 solved by COMP f d . This is because the compilation to compute minimum covering states is more involved than the centroids one, since it needs to discretize numerical variables. The performance of the SBDD algorithms is very similar to their SBD counterparts.Coverage results show that SBD approaches tend to outperform COMP approaches. Next, we conduct an analysis of execution time to test this further and study in more detail the differences between all the approaches. A summary of these results is shown in Figure 3 , where we represent the execution time in log scale of pairs of approaches. Each point in the plot corresponds to a problem of our joint benchmark (480 tasks), with its color indicating the domain it belongs to. Points above the diagonal indicate that the approach in the x axis is faster than the approach in the y axis. SBD vs COMP. First, we want to compare the execution time of the best variants of each approach. These results are shown in Figures 3a and 3b , where we compare the execution time of SBD f w (x axis) and COMP f d (y axis). In the case of centroids (Figure 3a ), 57% of the tasks were solved faster by SBD f w than by the compilation, i.e., 57% of the points fall above the diagonal line in the plot. We can observe some trends across domains. For example, SBD f w is consistently faster than COMP f d in BLOCKS and GRID instances, while the results in the other domains depend more on the task at hand. There is a cluster of simple problems that COMP f d can solve in less than a second, while SBD f w requires up to 1 second to solve them. Symbolic Fast Downward initializes some data structures before starting the search process, which slightly delays SBD algorithms in some simple tasks. Following the coverage trend, the execution time difference between both approaches increases in the case of minimum covering states (Figure 3b ), with 67% of the tasks being solved faster by SBD f w .Backward vs Forward. Forward SBD variants obtained higher coverage scores mainly due to Each graph shows a set of violinplots representing the execution time distribution (y axis) of each approach (different colors), as we fix the problem size (6, 8 and 12 blocks) and vary the number of possible goals (x axis).haustive algorithm SBD e , which needs to execute the same number of step operations for both states, we observe that the ADD operations require 16.1 ± 77.6 seconds in the case of centroids, versus the 12.4 ± 57.1 required in the case of minimum covering states.Finally, we study the scalability of the different approaches. Figure 4 shows the execution time of COMP f d and the three SBD variants when computing minimum covering states in BLOCKS, where we generated problems with increasing complexity by varying the number of blocks (size of the problem) and the number of words to build (number of possible goals). Each graph shows a set of violinplots representing the execution time distribution (y axis) of each approach (different colors), as we fix the problem size and vary the number of possible goals (x axis). We do not report results in problems with 12 blocks, since none of the approaches is able to solve any of the tasks.As we can see, our SBD approaches scale much better than the compilation ones, which cannot solve any task with 10 blocks (right plot) or with more than 4 goals in problems with 8 blocks. As expected, the exhaustive approach tends to be slower and scales worse than the backward and forward variants. This difference is not clear for small instances (left plot), mainly due to the low execution times and the limited sample of 5 problems per each combination of possible goals and number of blocks. The results indicate that problem size is the main execution time driver for our approaches, while the number of possible goals is the main factor in COMP f d execution time. Similar results were obtained in the case of GRID, the other domain with controlled problems, with the caveat that, as we already discussed, the backward searches cannot solve many of these tasks. 
conclusions and future work: 
 In this paper we have presented SBD, a family of symbolic bidirectional search algorithms to compute centroids and minimum covering states. Experimental results in existing and novel benchmarks show that our algorithms outperform current approaches both in coverage and execution time. These results establish our algorithms as a new state-of-theart technique for this task. The decision of which SBD algo-rithm should be used greatly depends on the task at hand. Forward alternatives are the best option when the number of reachable states is small compared to all states in the planning task, as it can prune many states and simplify the backward searches. Backward alternatives are the best choice in the rest of cases.This work paves the path for many interesting research avenues, that we group into two different areas: performance and generalization. We would like to further improve SBD performance in three directions. First, SBD advances the backward search that is estimated to generate a lower number of nodes in the next step. In future work, we would like to explore different heuristics to make this decision. Second, we would like to incorporate the h 2 preprocessor (Alcázar and Torralba 2015) to our planners, so we can increase the coverage in the variants that prioritize backward search, which tend to be faster. Third, we would like to estimate reachability with heuristics without conducting the forward search. This remains an open question, as it would require computing heuristics with respect to a set of goal states (our candidate set) represented as a BDD. Currently, this is only possible for admissible heuristics that are derived with symbolic search (Torralba et al. 2016; Torralba, Linares López, and Borrajo 2018) , but these are not competitive for satisficing planning. Finally, in this paper we have focused on two goal-related states that have already been defined and proved useful in the literature. In future work we would like to generalize SBD to consider other goal-related states, such as those that are at the same distance from all the goals, or those that are as far as possible from the goals. 
 
 Appendix: https://gitlab.com/atorralba/fast-downward-symbolichttps://github.com/apozanco/GRS 0.1https://github.com/karpase/grscompilation 


Decision: All reviewers liked the paper and agreed that its contribution is worth publishing. Some concerns, e.g., some clarity issues, were raised but the reviewers all agreed that they believe that these issues will be resolved in the revised version. With therefore recommend accepting this paper.

Reviews: review: strength_weakness: strength_weakness: My main issue with the paper is clarity. While the writing is generally very good, some technical aspects are unclear (concrete points listed in the section "Clarity" below). In these cases, the paper is understandable on an intuitive level but is missing details to understand the formal aspects. For the most part, I believe this to be easily fixable by extending the theoretical part of the paper (the intuitive explanations currently in the paper are useful, so theoretical details should be added to them not replace them).

In addition, the experimental design is not that informative. The main important questions are answered by the discussion of coverage but the remaining sections (in particular, "Runtime Analysis") do not add much additional insight. Configurations that have higher coverage than other configurations are show to run faster. This is not that surprising as the higher coverage could only be caused by lower run time or memory usage. I would suggest to cut most or all of this section and use the extra space for more details in the theoretical part of the paper.

There are two minor soundness issues in the correctness proof (Proposition 2) but these are mainly corner cases:
* Algorithm 1 doesn't specify what happens if BW is empty after filtering
* Proposition 2 (and maybe Algorithm 1) seems to assume that all goals are reachable and that a goal-related state wrt. phi exists.


Clarity
=======

In several places, the paper uses BDDs and ADDs in a manner that intuitively describes the operation without being clear on how that operation is performed. For example, Section 4 states: "Each of these backwards searches will give us an ADD having at the terminal nodes all the states ..." but formally, ADDs do not have states at their terminal nodes but numbers. Shortly after: "We update the backward ADD by setting to $\infty$ the value of unreachable states". It is still not clear to me how this is done. Would this iterate over unreachable states and do something for each one? How can you set the value of a state in an ADD? My guess is that this is some ADD "apply" operation with the ADD and some ADD representing the closed states but this is not explicit in the text.

The end of Section 4 mentions that the algorithm is symmetric but it isn't: The forward search is a single search that starts in one state, while there are several backward searches that start from multiple goals. Backward searches are represented with ADDs, the forward search is unspecified (it could be an explicit search). It is not clear at all that forward and backward step are exchangeable.

The discussion above Definition 8 is unclear as well. For one, the text doesn't justify statements like "we could explore up to 10, 4 and 9" but just states them as facts. Reading Proposition 1 afterwards does not help, because it doesn't mention g values, only closed states, so it doesn't directly apply to the text above.

In the pseudo code, lines 15 and 16 are unclear: they look like they would assign one element out of BW to BW, turning BW from a set of searches to a search. It would help to change $bw_i \in BW s.t. ...$ to $\{bw_i \in BW \mid ...\}$. Another issue is that BW is not a local variable, i.e., the global list of all searches is modified and some elements are removed from it forever. After some thought I convinced myself that this is fine but it makes the algorithm much harder to understand. If you would instead use a local variable here and filter the list of searches only for use in line 17, this would be easier.

Finally, the description of the special case using BDDs instead of ADDs is unclear. When doing just the modifications to the pseudo code described in the text, line 9 uses a variable B_expCand that was never set (because lines 7 and 8 were removed). Then, the conjunction of bw_G is not consistent with using bw_G.CLOSED() in other places (I assume this should also use the closed list of the search). Pseudo code for the modification and an argument for correctness of the algorithm would help here.

Minor comments
==============
* Introduction: "arrive" seems like the wrong verb for a fire. How about "break out"?
* Figures 1, 3, and 4 are hard to parse in a black-and-white printout. Maybe change "(blue)" to "(C, blue)" and use different colors in Figures 3 and 4.
* The symbol \mapsto is misused in different ways: it should only be used as part of a function definition ($s = {v_1 \mapsto 1}$) but not as defining the functions type (use $\chi: S \to {T, F}$ instead of $\chi: S \mapsto {T, F}$) or for individual elements (use $c_o \in \mathbb{N}_0$ instead of $c_o \mapsto \mathbb{N}_0$). In particular in Definition 4, $\phi(h(s))$ is an element of the image of the function, so $\phi(h(s)) \mapsto \mathbb{N}_0 \cup {\infty}$ doesn't make sense. This is also mixing concrete elements
  ($\phi(h(s))$) and the type of those elements ($\mathbb{N}_0 \cup {\infty}$).
  A fix would be to just specify the type as
  $\phi: (\mathbb{N}_0 \cup {\infty})^n \to (\mathbb{N}_0 \cup {\infty})$.
* "We denote the set of states ... as B": it is not clear if B should refer to the set or the BDD. Also, later you introduce B_p for the same concept.
* "nodes whose both successor point to the same node": nodes _in_which_ both successor_s_ point to the same node
* "the previously defined functions g": singular
* "takes an input two ADDs": as input?
* "The runtime is O(ADD_1, ADD_2)": O([|ADD_1|] * [|ADD_2|])
* "viceversa": two words
* Definition 7 defines one hand-wavy term (aggregatable) by another (pairwise aggregation). As this is a formal definition, the second one should be more precise.
* "the problem of, given": grammar. Maybe "The problem of finding ..., given ..."
* "The solution to such _a_ task"
* "assuming there is no _reachable_ state at distance 9"
* "turns GRID tasks into challenging" incomplete sentence
* Figure 4: "6, 8, and _10_ blocks"
questions: questions: 1. How does SBD_e update the backward ADD (see Section "Weaknesses" for the part that was unclear to me)?
2. Why is the lazy computation with BDDs correct for computing minimum covering states?

Response to Rebuttal
=================
Thank you for your response. I still believe the experimental section could be compressed a lot (specifically points (1) and (2) in your response) but I'm happy with all suggested changes.
strength_weakness: strength_weakness: The paper contains no siginficant weaknesses but I had a number of specific comments.  

SPECIFIC COMMENTS
p. 1: minimum covering state: does this state minimize the maximum shortest path between the state and any of the goals?  That seems to be the case (because another interpretation of this statement is the worst path one could take which introduces looping plans which could be infinite cost, which probably isn’t what is intended.)

p. 2: “This requires to consider some arbirary encoding of the values of the state variables V in binary.” should be written
“This requires some arbirary encoding of the values of the state variables V in binary.”

p. 2: “Also, they allow to implement efficient operations…” should be written “Also, they allow implementation of efficient operations…”

p. 2: “The runtime is O(ADD1, ADD2).”  What does this mean?  could this be missing a ‘max’ function?

p. 3: definition of monotone.  It may be worth emphasizing in the definition that increasing any of the single costs *alone* can’t decrease the h* value, but (as is the case with minimum covering states) that does not preclude a lower h* value arising from an increase in one cost and decreases in another cost.

p. 4: the narrative introduction to SBD_e and the more detailed description don’t quite match.  If you just reorder the narrative so that forward reachability is done first, then backward search from each goal G and combining the resulting ADD’s then you’re fine

p. 4 some sentences have some awkward repetition (Finally….Finally…)

p. 4: I am having some trouble with the discussion leading up to defn 8 / proposition 1.  Are we provided with *a* state that has distances 10,4,3 to the three goals?  Or is the argument that this state is the solution to this problem that search does not yet know is a solution?

p. 4: Definition 8 may not be written quite right from an editorial point of view.  Since you want states, mathematically speaking, arg_min returns those states minimizing your heuristic, so I think you can just drop ‘that minimizes’ from the textual definition and you’re fine 

p. 5:”The states in that intersection are reachable and con- form the set of minimum covering (centroid) states of the task…” should be written “The states in that intersection are reachable and contain the set of minimum covering (centroid) states of the task…”

p. 6: “Having this predicate turns G R I D tasks into challenging for approaches using backward search…” should be written “Having this predicate turns G R I D tasks into challenging ones for approaches using backward search…” 

p. 7: “ Forward S B D variants obtained higher coverage scores mainly due to GRID, but the forward variants were able to solve more problems in domains such as LOGISTICS and BLOCKS.”

 I think you meant to say “…the backward variants were able to solve more problems in domains such as LOGISTICS and BLOCKS.”  This is what the results table indicates.
questions: questions: One way of thinking about this line of work is that the centroid or covering goals essentially create a deterministic/classical problem in lieu of an expected value problem like an MDP or contingent planning problem.  In the forest fire example, we don’t know which fires will break out, so we want to position ourselves to handle them if and when they do.  How would one compare the problem formulations and solutions from these two disparate perspectives?

Are there ever problems in this setting that have no solution?  What would such a problem look like?  If any of the goals G is unreachable that’s enough for a problem to have no solution; if all the goals are reachable, then there has to be some state that solves the problems by definition (I think)

For future work, what if the goals are temporally scoped in some way, such as, take a picture of location A at time t1 or location B at time t2?  The problems are well defined because the definitions of ceontroid and minimum cover only involve cost, and the problems are all posed in terms of reachability, so temporal constraints limit state reachability. However, I could see the resulting minimum covering state being meaningless, i.e. it’s impossible to actually get to either location at the right time from any state other than the initial state.  Example: you can get to A by t1 from where you are, but you have to go the opposite direction to get to B by t2; the only time/place pair in common is the initial state.  So problems may have no solution, or the only solution may be 'trivial'.  What future work would be needed to extend the problems and algorithms?  Will BDDs work?  What do you do if they don’t?
strength_weakness: strength_weakness: The proposed technique is a fairly straightforward application of symbolic search to the problem, but given that this has not previously been tried I don't consider this a weakness of the paper. I don't think the paper has any significant weaknesses.
questions: questions: - Additional knowledge, such as probabilities associated with each goal, or different per goal utility values, might complicate this problem. Would your methods generalize to these cases? 

- The scalability results are reported mostly in terms of runtime in the results section. Do you have any estimates of how much exploration your approach saves in terms of the proportion of the state space is explored? This might be interesting to add.

- Consider a blocksworld problem in which on (A, B) is *not* part of the goal. Then for any state in which on (A, B) is true, there should be an equivalent state that is just as good in terms of the goals-related function phi in which on (A, B) is not true. This could be thought of as a form of inference or symmetry pruning. Have you investigated such approaches?

minor:

"The runtime is O(ADD1, ADD2)." is there a missing function here, e.g. max?


typos, etc:

there exist*s* a sequence

arbi*t*rary

to refer to an operation that perform*s*

splitted --> split

"These two filters leave as alternative to progress those backward searches that have not yet explored the states in BC." this sentence is a bit confusing, suggest rewriting.

"The states in that intersection are reachable and conform the set of minimum covering (centroid) states of the task" 'conform' seems like the wrong word here, 'contain' maybe?

"returns a goals-related states" remove 'a', or states --> state