Admissible Abstractions for Near-optimal Task and Motion Planning

1 Introduction

Consider a problem domain like the one shown in figure 1. A holonomic two-dimensional agent is tasked with navigating to a specified goal region as quickly as possible. The path is blocked by doors that can only opened by pressing the appropriate switch. Planning the sequence of switches to toggle requires combinatorial search; deciding if a path exists to each switch requires motion planning. As in many real-world planning domains, such as object manipulation and navigation among movable objects, the combinatorial search and motion planning problems are coupled and cannot be completely separated.

Practical approaches to solving such problems generally use abstraction to reason about the properties of groups of primitive plans simultaneously. For example, the aSyMov system developed by [Cambon et al., 2009] uses a symbolic task planner to compute a lower bound on the number of manipulation operations required to reach a goal state and keeps track of a set of configurations that could be reached following a given sequence of such operations. [Kaelbling and Lozano-P´erez, 2011] use a hierarchy to guide high-level decision making, resolving low-level decisions arbitrarily and trusting in the reversibility of the system to ensure hierarchical completeness. Though the many approaches present in the literature vary widely in how they deal with the interaction between geometric planning and combinatorial search, very few provide any guarantee about the quality of the solutions they return. Even optimizing approaches, such as the work of [Wolfe et al., 2010], are generally limited to guarantees of hierarchical optimality. In order to be useful, a planner must generate plans of reasonably low cost, and must do so reasonably quickly; this often requires substantial design effort and domain-specific tuning, and the trade-offs involved are poorly understood.

Figure 1: The door-switch problem, an example task and motion planning domain. A two-dimensional robot must navigate from the start location to a goal location, but the way is obstructed by doors that can only be opened by toggling a corresponding switch. The optimal solution to this problem instance is to toggle the switches in the order (1, 3, 2, 4, 5) and then go to the goal set. Because the size of the configuration space grows exponentially with the number of doors, planning is computationally challenging. Abstraction can render such planning problems tractable.

Angelic semantics [Marthi et al., 2008] provide a way to describe an abstraction that preserves optimality, ensuring that the plans returned have a cost within a user-defined factor of the optimal cost. However, it is unclear precisely what criteria must be met to define an angelic abstraction in a continuous domain. In this paper, we describe sufficient conditions under which an abstraction will preserve the ability to find the optimal motion plan while accelerating planning. We derive abstractions for two continuous planning domains, and we show that using these abstractions can dramatically reduce the complexity of search relative to a direct motion planner. We find near-optimal motion plans in planning problems involving 1013 states without using a separate task planner.

2 ProblemFormulation

We are interested in planning problems involving some underlying continuous configuration space X, such as the position of a robot or the configuration of its joints. Our task is to find a path through free space that starts in a specified state s0 and ends in a goal set Sgoal. This goal set may be specified implicitly, as the set of all states satisfying some constraint.

A path is a continuous map p : [0, 1] → X. We define a concatenation operator ◦ for paths.

Let PX(S, S′ ) be the set of all paths starting in S ⊂ X and ending in S′ ⊂ X. Let c : X × TX → R>0 be a cost function, where TX is the tangent space of X . We can define an associated cost functional C : PX →R≥0.

For example, the arc length of a path p corresponds to a cost function c(p, ˙p) = ‖ ˙p(t)‖. Because C is additive, C[p1 ◦p2] = C[p1] + C[p2]. We define the set-valued optimal cost function c∗ : 2X ×2X →R≥0 as

We define the ϵ-approximate planning problem as the search for a path ˆ p ∈ PX ({s0}, Sg) with cost less than (1+ϵ) the optimal cost for any ϵ ∈ R≥0 ∪ {∞}.

The case where ϵ = ∞, when we wish to find any feasible path to the goal set, is the problem of satisficing planning. The case where ϵ = 0 is optimal planning.

The set PX(X,X) of all possible paths from all possible start and goal locations is continuous and topologically complex. To simplify planning, we assume we have available a finite set A0 of primitive operators, low-level actions that can be executed in the real world. The problem of constructing such a set of operators in continuous motion planning domains is well studied; in this document, we will assume the set of operators are given by the edges in a probabilistic roadmap (PRM*) [Kavraki et al., 1996; Karaman and Frazzoli, 2011]. That is, we randomly sample a finite set of configurations Vn ⊂ X, and for each such configuration v, we define an operator pv. The operator pv ensures that the robot will end at the state v if executed from any state in the open ball of radius rn around v, where rn ∝ (logn/n)1/d is a radius that increases slowly with the size of the discretization. Any feasible plan can be well-approximated by a sequence of these randomly sampled operators as the number of sampled configurations tends to infinity. For example, we can show that if A∗0,n is the set of all paths through a PRM* with n sampled configurations, then

This was proven by [Karaman and Frazzoli, 2011] for the case where the system is subject to analytic differential constraints, and by [Vega-Brown and Roy, 2016] when the system has piecewise-analytic differential constraints (as in object manipulation problems).

Because the set of primitive operators can grow quite large, especially in problems with high-dimensional configuration spaces, a direct search for primitive plans is computationally intractable. Instead, we will use angelic semantics to encode bounds on the cost of large groups of plans. We can use these bounds to plan efficiently while preserving optimality.

3 Angelic Semantics

We define an abstract operator a ⊂ P(X,X) as a set of primitive plans. Because the space of plans is infinite, we define operators implicitly, in terms of constraints on the underlying primitive plans. For example, in a navigation problem, we might define an operator as any primitive plan that remains inside a given set of configuration space and ends in a different set of configuration space.

The concatenation of two operators a1 ◦ a2 is an abstract plan containing all possible concatenations of primitive plans in the operators.

Concatenations of a well-chosen small set of abstract operators can express very complicated plans in a compact way.

In order to use these abstract operators for planning, we need a way to compare abstract plans. We do this using the valuation of an operator or plan. A valuation V [a] for an operator or plan a is the unique map V [a] : X ×X → R≥0 that takes a pair of states and gives the lowest cost path between the pair.

Note that if there are no paths in a linking s1 and s2, then V [a](s1, s2) = inf ∅ = ∞.

Valuations allow us to compare abstract plans without reference to the primitive plans they contain. Given two abstract plans p and p′ , if we can prove that for any pair of states x, x′ , either V [p](x, x′ ) < V [p′ ](x, x′ ) or V [p′ ](x, x′ ) = ∞, then either there is a solution to our planning problem in p, or there is no solution in p or p′ . Either way, we do not need to consider any plan in p′ ; we can prune p′ from our search space. Under such a condition, we say that p dominates p′ and we write V [p] ≺ V [p′ ]. Similarly, if either V [p](x, x′ ) ≤ V [p′ ](x, x′ ) or V [p′ ](x, x′ ) = ∞, then we say that p weakly dominates p′ and we write V [p] ⪯ V [p′ ].

Unfortunately, determining the valuation of an operator is itself an optimization problem, and one that is not necessarily any easier than the planning problem we are trying to solve. The computational advantage comes from reasoning about bounds on the valuation of an abstract operator. By representing these bounds symbolically, we will be able to reason without reference to the underlying states or plans.

We first define bounds on the valuation of an operator over a set of states.

A symbolic valuation bound ˆ V [a] can be written as a set of tuples {(s, s′ , l, u)}, where s, s′ are symbolic states and l < u ∈ R≥0 ∪ {∞}. A bound ˆ V [a] is admissible if

In words, a bound (s, s′ , l, u) is admissible if for any state x in s there exists a plan p ending in some state x′ in s′ with cost c = C[p] bounded above by u and below by l. We can also interpret a symbolic valuation bound ˆ V as a bound over sets of states.

Note that if ˆ V [a] is admissible, then ˆ VL[a](s, s′ ) ≤ VL[a](s, s′ ) and VU[a](s, s′ ) ≤ ˆ VU[a](s, s′ ) for all abstract state pairs s, s′ .

As we will see in sections 4.1 and 4.2, for many domains we will not need to write down a valuation explicitly. Instead, we can use domain information to make metric computations and generate the necessary elements of a valuation procedurally.

By working with symbolic bounds, we can efficiently compute bounds on the cost of plans consisting of sequences of abstract operators, without reference to a dense discretization of the underlying space of plans. For example, if we have bounds on a plan ˆ V [a] and an operator ˆ V [a′ ], we can compute a bound ˆ V [a ◦ a′ ].

If ˆ V [a] and ˆ V [a′ ] are admissible, then ˆ V [a◦a′ ] is admissible as well.

4 Admissible Abstractions

We can use angelic semantics to specify an abstraction that will enable efficient planning. Suppose that p, p′ are abstract plans, with p ⊂ p′ . Then V [p′ ] ⪯ V [p], since any plan in p is also in p′-but because p is a smaller set than p′ , our bounds may tighten. If our bounds allow us to conclude that ˆ VU[p′ ] ≺ ˆ VL[p], then we can also conclude that V [p′ \ p] ≺ V [p′ ]. We can incrementally construct an increasingly accurate estimate of V [p] by iteratively considering smaller and smaller subsets of an operator p and pruning those subsets that cannot contain an optimal plan.

We can make precise the construction of these increasingly fine subsets by introducing a refinement relation R ⊂ A∗ × A∗ , where ∗ denotes the Kleene closure. The elements of R are ordered pairs (p, p′ ) such that p′ ⊂ p. We can construct a relation R by defining several simple operations. First, we define operations BASE : A∗ → A∗ , HEAD : A∗ → A, and EXT : A∗ → A∗ that split a plan into three segments so that p = BASE(p) ◦ HEAD(p) ◦ EXT(p). Second, we define a relation ¯R ⊂ A × A∗ . Then (p, p′ ) ∈ R if and only if p′ = BASE(p) ◦ p′′ ◦ EXT(p) and (HEAD(p), p′′ ) ∈ ¯R.

We can combine these elements into an abstraction over a problem domain (X, c, s0, Sg). Formally, an abstraction is a tuple (S,A, ¯R, ˆ V ), where

• S is a collection of propositional symbols,
• A is a collection of operators, including a distinguished top-level operator Act,
• ¯R⊂ A×A∗ is a refinement relation, and
• ˆ V is a symbolic valuation bound.

The valuation bound encodes both the cost and the dynamics of our problem domain. The refinement relation structures the space of abstract plans.

Angelic planning algorithms accept an abstraction as an argument in much the same way that the A* search algorithm [Hart et al., 1968] accepts a heuristic. This raises an important question: under what circumstances will an abstraction (S,A, ¯R, ˆ V ) allow us to find the optimal primitive plan for a domain (X, c, s0, Sg), and to prove we have done so? We will generalize the idea of an admissible heuristic to define an admissible abstraction.

In fact, two properties suffice.

1. For each abstract operator a ∈ A, for each primitive plan p in a, there is a refinement p of a such that p ∈ p, i.e.,

1. ˆ V is admissible, i.e., ˆ VL[p] ⪯ V [p] ⪯ ˆ VU[p] for each abstract operator p ∈ A.

The first property ensures that we do not "lose track" of any primitive plans while refining a plan. Plans are only removed from consideration when they are deliberately pruned. The second property ensures that if abstract plans p, p′ ∈ P, where P is a collection of abstract plans, and ˆ VU[p] ≺ ˆ VL[p′ ], then no optimal plan is in p′ and thus the best plan in p is also in the set P ′ = P \{p′ }. Taken together, these properties ensure that if P ′ is the result of refining and pruning a collection of plans P, then for every plan in P there is a plan that is no worse in P ′ . If we start with the set P0 = {Act}, no sequence of refinement and pruning operations will discard an optimal solution. This ensures completeness. To construct planning algorithms, we simply need to choose an order in which to refine and prune, and keep track of bounds to know when we can terminate the search.

Not every admissible abstraction is useful for planning. A good abstraction must be concise: it must be informative enough to enable us to explore the space of plans quickly. In general, designing useful abstractions for a given domain is a complex exercise. In the remainder of this section, we will provide concrete examples of admissible abstractions for a pair of simple continuous planning problems.

4.1 An Abstraction for Navigation

A common problem in robotics is navigating to some specified goal location in a structured environment. Simple heuristics like the Euclidean distance to the goal work well in environments that are cluttered but largely unstructured, where the distance is a good proxy for the true cost. In highly structured environments, however, the Euclidean distance can be quite a bad proxy for cost. Consider the example in figure 3, in which the robot starts just on the other side of a wall from the goal. Using A* with a Euclidean heuristic requires searching almost the entire space.

We can plan more efficiently by taking advantage of structure in the environment. Suppose we have a decomposition of the environment into a finite set of overlapping regions, and we know which regions overlap. Then any plan can be described by the sequence of regions it moves through. We can use this to define an abstraction. Let S = {Ri}, where ∪iRi = X, and let A = A0 ∪{aij : Ri ∩Rj ̸= ∅}∪{Act}, where p ∈ aij if p(t) ∈ Ri∀t ∈ [0, 1) ∧ p(1) ∈ Rj. Define the refinement relation as follows.

In practice, we will not iterate over all possible refinements, but will instead use spatial indices like k-D trees and R-trees to find the operators that are valid from a particular state. It is straightforward to show this satisfies the completeness property.

If the cost function is path length, then we can compute bounds using geometric operations. Executing the action aij from a state in Rk ∩Ri would incur a cost at least as great as the set distance inf{‖x - x′ ‖ : x ∈ Ri ∩ Rk, x′ ∈ Ri ∩ Rj}. If the intersections between sets are small and well-separated, this lower bound will be an accurate estimate. This has the effect of heuristically guiding the search towards the next region, allowing us to perform a search in the (small) space of abstract plans rather than the (large) space of primitive plans. The Euclidean heuristic can deal with things like clutter and unstructured obstacles, while the abstraction can take advantage of structure in the environment.

Note that we have made no reference to the shape of the regions, nor even to their connectedness. If regions can be disconnected, abstract operators can have no upper bound, which can lead the search to be inefficient. If we additionally require the regions to be convex, then we can use the Hausdorff distance between sets as an upper bound. Executing the action aij from a state in Rk ∩ Ri would incur a cost no greater than the Hausdorff distance dH(Ri ∩ Rk,Ri ∩ Rj), where

Convexity is quite a strong requirement. In a cluttered environment, a convex representation may need to contain many regions. We can relax the requirement of convexity, and generalize to costs besides path length, by defining ϵ-convexity. A region R is ϵ-convex if

ϵ-convex regions are "nearly" convex, because the shortest path connecting any two points is only a bit longer than a straight line. For example, a region cluttered with convex obstacles is π/2-convex for a point robot.

4.2 An Abstraction for the Door Puzzle

The door puzzle introduced in the introduction combines the motion-planning aspects of navigation with a high-level task planning problem: the choice of which doors to open and in which order. Unlike in the navigation problem, the configuration space for the door problem involves discrete components: X ⊂ R2 × {0, 1}N , where where N is the number of doors. We use the same region-based abstraction to guide the search for motion plans, and construct a relaxed representation of the effects of toggling switches in PDDL by omitting geometric constraints like collision. Using this representation, we can quickly compute a partial ordering on the sequence of switches that need to be pressed in order to reach the goal. For example, in figure 2, the path to the goal is blocked by six doors. Before we can move towards the goal, we must move to and press each of the six switches. This leaves us with the task of computing a lower bound on the cost to reach and toggle each switch.

We can find such a bound in two steps. First, we construct a directed graph whose vertices are the possible effects of executing each operator, and whose edges have weights that lower bound the cost of executing each operator. This reduces the problem of finding a lower bound to solving a travelling salesperson problem (TSP). While it is believed that solving a TSP requires exponential time, we can compute a lower bound on the cost of the optimal solution by computing a minimum spanning tree of the directed graph-and this is a computation that can be done in polynomial time with standard methods. Although this bound neglects possible interactions between the operators, it is admissible; in fact, it is an admissible special case of the more general (and inadmissible) hadd heuristic [Haslum and Geffner, 2000]. We can use this bound to guide the search for a more detailed motion plan.

5 Acyclic Approximate Angelic Search

Next, we present the approximate angelic A* search algorithm (AAA*), an algorithm for near-optimal planning using an admissible abstraction. AAA* is a reformulation and extension of the angelic hierarchical A* algorithm developed by [Marthi et al., 2008]. This algorithm is effectively a best-first forward search over abstract plans. It accepts an abstraction and a positive weight w ≥ 1, and maintains a queue of plans to expand. The algorithm repeatedly removes from the queue the plan with the lowest lower bound on the cost to reach the goal (lines 8-12). It then constructs a set of child plans by selecting one operator from the plan and replacing it with its refinements. Any successor plan that cannot possibly contain an acceptable solution is pruned, while any plan that could contain an acceptable solution is added to the priority queue. The algorithm terminates when we remove a plan from the queue that is dominated by a previously expanded primitive plan.

The primary data structure maintained by our algorithm is a tree. Each node in the tree represents a plan as the concatenation of a predecessor plan p- and an operator a. Nodes store the following information:

• an abstract operator a,
• the predecessor plan p-,
• the parent plan, fromwhich this plan was refined,
• the base plan BASE(p), which is used in choosing refinements, and
• upper and lower bounds on the valuation of the plan represented by the node.

The root of the tree is a node that contains no operator, predecessor, or base, and whose upper and lower valuation bounds are zero at the start state and infinite elsewhere.

[Marthi et al., 2008] showed this algorithm will return the optimal refinement of the top-level operator Act after a finite number of iterations, provided the lower bound on the cost of every operator is greater than zero. We provide two key modifications. First, instead of expanding the plan with the smallest lower bound, we order the queue with a priority that is no greater than w times the lower bound on the cost a plan. This allows us to exchange optimality for approximate optimality and an accelerated search, in much the same fashion as weighted A* [Pohl, 1970]. Inflating the lower bound may accelerate search by providing a more accurate estimate of the true value of an abstract plan. This is especially true in domains where formulating an abstract plan is difficult: inflating our lower bounds can allow us to focus our search on a single, reasonable abstract plan, rather than considering every possible abstract plan.

Second, the original formulation of angelic A* required strictly positive lower bounds on the cost of any operator. In discrete problems, this is reasonable restriction, but it presents challenges in continuous problems. For example, suppose we have a plan consisting of two operators aij ◦ ai′ j ′ from our navigation abstraction. If the destination regions intersect-if Rj ∩ R′j ̸= ∅-then the largest possible lower bound for the valuation of ai′ ,j ′ is zero. This phenomenon can lead to a zero-cost cycle: a sequence of operators that can optimistically returns to a given state with zero cost. Even positive cost-cycles are problematic, if the lower bound l on the cost of a cycle is much smaller than the upper bound u:

the algorithm can only prune a plan if it executes the cycle ⌈u/l⌉ times. Unfortunately, we cannot simply discard any abstract plan with a cycle: the optimal plan may leave and return to an abstract state if the state is non-convex. Typically, this indicates a poor choice of abstraction, but we can deal with such edge cases while still avoiding cycles with a minor modification to the algorithm.

We define an acyclic plan as any plan p that cannot be partitioned into two plans p0 ◦ p1 such that ˆ VL[p0] ⪯ ˆ VL[p] (algorithm 1, lines 53-58). If when computing the successors of a plan p, we find the extension pext would create a deferred plan when propagated on top of BASE(p), we do not add p ◦ pext to the set of successors. Instead, we add (BASE(p), pext) to the set of deferred plans (algorithm 1, line 29). When any descendent of p is expanded, we consider activating any deferred extension of p by propagating it on top of the descendent plan. If the resulting plan is no longer acyclic, we add it to the set of successors (line 36). This ensures that only acyclic plans will ever be added to the queue of plans without sacrificing completeness.

We state the following theorem without proof; a proof of this theorem, along with proofs of admissibility for the abstractions presented in section 4, are available in an extended version of this paper. 1

Theorem1. If the abstraction A is admissible and a feasible plan exists, then AAA* returns a sequence of primitive operators with cost no greater than w · c∗ ({xs},Xg) in finite time.

Corollary 1. Let cn = C[SEARCH(An)] be a random variable equal to the cost of the path returned by AAA*. If the set of primitive operators A0,n is asymptotically optimal (equation 5), then for any ϵ > 0,

6 Results

We implemented AAA* and the abstractions described in sections 4.1 and 4.2 in the Python programming language. We

1 https://arxiv.org/abs/1806.00805

Algorithm 1 Approximate Angelic A*

1: function SEARCH(abstraction (S,A, ¯R, ˆ V ), weight w) 2: root = (∅, ∅, ∅, {(xs, xs, 0, 0)}) 3: p∗ = ∅ 4: BOUND(∅) = ˆ V [ACT] 5: p0 = PROPAGATE(root, [ACT]) 6: Q = {p0} 7: while |Q| > 0 do 8: p = arg min{KEY(p, w) : p ∈ Q} 9: if PRIMITIVE(p∗ ) and ˆ VU[p∗ ] ≺ ˆ VL[p] then 10: return p∗ 11: else 12: Q ← Q \ {p} 13: S ← SUCCESSORS(p) 14: for p′ ∈ S do 15: if ˆ VU[p′ ](x0,Xg) < ˆ VU[p∗ ](x0,Xg) then 16: p∗ ← p′ 17: Q ← Q ∪ S 18: return ∅ 19: function SUCCESSORS(plan node p) 20: ▷ D is a global variable, initially set to ∅. 21: POST(BASE(p)) = {s′ : (s, s′ , l, u) ∈ ˆ V [BASE(p)]} 22: S = ∅ 23: a = OPERATOR(HEAD(p)) 24: for p′ : (a, p′ ) ∈ ¯R, ∃s ∈ POST(BASE(p)) : HEAD(p′ )∩ s ̸= ∅ do 25: pref ← PROPAGATE(BASE(p), p′ ◦ EXT(p)) 26: if ˆ VL[pref ](xs, Xg) < ∞ then 27: if ACYCLIC(pref , ∅) then S ← S ∪ {pref } 28: else 29: D ← D ∪ {(BASE(p), EXT(pref ))} 30: pa ←p 31: while BASE(PARENT(pa)) ̸= ∅ do 32: pa ← BASE(PARENT(pa)) 33: for pext : (pa, pext) ∈ D do 34: pref ← PROPAGATE(BASE(p), pext) 35: if ACYCLIC(pref , ∅) and ˆ VL[pref ] < ∞ then 36: S ← S ∪ {pref } 37: return S 38: function PROPAGATE(base node p, list pext) 39: b←p 40: while pext is not empty do 41: a ← POP(pext) 42: if a is more primitive than OPERATOR(p) then 43: b ← p 44: p← (a, p, b, ˆ V [p ◦ a]) 45: if ˆ V [p] = ∅ then return ∅ 46: else if BOUND(pext) ≺ ˆ VL[p] then return ∅ 47: else BOUND(pext) ← BOUND(pext) ∪ ˆ V [p] 48: return A 49: function KEY(node p, weight w ∈ R≥1) 50: p- ← PREDECESSOR(p) 51: if p = ∅ then return 0 52: else return min(KEY(p-) + w( ˆ VL[p] - ˆ VL[p-]), ˆ VU [p]) 53: function ACYCLIC(plan nodes p, p′ ) 54: p- ← PREDECESSOR(p) 55: if p = ∅ then return true 56: else if p′ = ∅ then 57: return ACYCLIC(p-, ∅) ∧ ACYCLIC(p-, p) 58: else return ¬( ˆ VL[p] ⪯ ˆ VL[p′ ]) ∧ ACYCLIC(p-, ∅)

(a) A*

(b) Acyclic Angelic A*

Table 1: Quantitative performance on a problem instance in the navigation domain. The discretized state space includes 104 sampled configurations. We see that abstraction and approximation result expanding fewer plans and exploring fewer states, yielding a faster search and optimal or nearly optimal results.

then compared the performance of the planner with the original angelic A* search algorithm [Marthi et al., 2008] and with a search without abstraction using A*.

In the navigation domain, we constructed a random discretization with 104 states. Examples of the search trees constructed by A* and by AAA* are given in figure 3. By using the abstraction, the algorithm can avoid exploring large parts of the configuration space. Our quantitative results bear this out: using abstraction allows us to reduce the number of states explored by a factor of three and the number of plans considered by several orders of magnitude.

Using abstraction in the door puzzle domain resulted in even larger speedups. Even in easy problem instances with only a few doors, search without abstraction quickly became infeasible (figure 4). Using abstraction reduced the number of states explored by orders of magnitude. However, the unmodified angelic search spent a great deal of time exploring plans with cycles. By deferring these plans, our algorithms were able to reduce the number of plans expanded by an order of magnitude. In fact, only our algorithm was able to solve problem instances with more than ten doors. We were able to find 2-optimal plans for instances with up to 32 doors and 104 sampled configurations (corresponding to a discretized state space with approximately 40 trillion states). Unfortunately, software limitations prevented us from experimenting on states with more than 32 doors.

7 RelatedWork

There is a long history of using abstraction to solve robotic planning problems [Nilsson, 1984; Lozano-P´erez et al., 1987]. Many authors [Alami et al., 1990; Sim´eon et al., 2004] have employed our underlying approach of searching for paths through a graph of configurations connected by feasible motion plans. Practical algorithms often overcome the high computational cost of searching these planning graphs using clever heuristics. For example, aSyMov [Cambon et al., 2009] and FFRob [Garrett et al., 2016] both employ the fastforward heuristic, augmented with information derived from the geometric and kinematic computation. Like these approaches, our work is built atop a heuristically-guided search; however, angelic semantics allow us to define upper bounds which can be used to prune away abstract plans, and allow for admissible hierarchies of arbitrary depth.

Our definition of abstract plans is closely related to the notion of "plan skeletons" considered by several authors [Erdogan and Stilman, 2013; de Silva et al., 2013; Lozano-P´erez and Kaelbling, 2014]. Plan skeletons fix a sequence of operators but leave continuous parameters undefined. There are many approaches to determining the feasibility of a given skeleton; for example, [Toussaint, 2015] used continuous optimization techniques to search for optimal values of the realvalued variables. [Lozano-P´erez and Kaelbling, 2014] fixed a discretization of the continuous variables then find feasible values by formulating and solving a constraint satisfaction problem. [Lagriffoul et al., 2014] used linear programming to find valid values of the free variables or prove that none exist. The primary difference between our approach and these plan skeletons is the choice of formalism. By defining our abstract operators as implicitly defined sets of primitive motion plans, we can reason about plans at varying levels of abstraction in a unified way, which is essential to the generality of our guarantees.

Other approaches to task and motion planning use a representation of geometric information that is amenable to the search techniques of classical AI. For example, [Dornhege et al., 2010] modeled geometric information as predicates to be resolved by solving motion planning problems during the task planning process. More recently, [FerrerMestres et al., 2017] showed that in some domains all geometric information could be represented compactly in planning languages more expressive than PDDL, avoiding the need to make geometric queries during the planning process. Other authors [Erdem et al., 2011; Srivastava et al., 2013; Dantam et al., 2016] used the task planner as a partial or approximate representation of the underlying geometric task, which could be improved during search. For instance, [Erdem et al., 2011] used a high-level task planner to find an optimal task plan, then used a motion planner to attempt to find a kinematically feasible primitive solution to that task plan. If no feasible solution was found, additional kinematic constraints were extracted from the motion planner and provided to the task planner, and the process was repeated.

Many authors have devised planning algorithms tailored to more specific task and motion planning domains. For example, the problem of navigation among movable obstacles has long been of practical interest, and probabilistically complete solutions have been known since 2008 [Stilman and Kuffner, 2008; Nieuwenhuisen et al., 2008]. Planning for non-prehensile manipulation has been addressed by [Dogar and Srinivasa, 2011] and by [Barry et al., 2013]. Our work could provide a new analytical tool with which to study these special classes of problems, and perhaps formulate new algorithms with stronger performance guarantees.

8 Conclusions

We have defined conditions on an abstraction that allow us to accelerate planning while preserving the ability to find an optimal or near-optimal solution to complex motion planning problems. We motivate these conditions by deriving two admissible abstractions and showing they improve the efficiency of search without adversely affecting the quality of the resulting solutions. We view this work as a proof of concept, demonstrating that a good abstraction can render optimal planning feasible even on large problems. The classical planning community has developed several powerful families of admissible heuristics [Haslum and Geffner, 2000]; by reformulating these heuristics to employ angelic abstractions, we may be able to obtain optimal or near-optimal solutions to practical manipulation planning problems.

Acknowledgements

This research was sponsored by Northrop Grumman and by the Robotics Collaborative Technology Alliance (RCTA) of the US Army. Their support is gratefully acknowledged.