The Provable Virtue of Laziness in Motion Planning

1 Introduction

The simplest motion planning model [Halperin et al., 2017; LaValle, 2006] involves a robot system R moving in a workspace W ∈ {R2 , R3 } cluttered with obstacles O. Given an initial placement s and a target placement t of R, we wish to determine whether there exists a collision-free motion of R connecting s and t, and, if so, to plan such a motion.

Typically, R is abstracted as a point, or a configuration, in a high-dimensional space called the configuration space X, where each configuration maps R to a specific placement in W [Lozano-Perez, 1983]. The configuration space is subdivided into the free and forbidden spaces, corresponding to placements of R that are free or that intersect with an obstacle, respectively. Since the general motion-planning problem is PSPACE-hard [Hopcroft et al., 1984], a common approach is to use sampling-based algorithms [Kavraki et al., 1996; Hsu et al., 1999; LaValle and Kuffner, 1999; Karaman and Frazzoli, 2011]. These algorithms approximate X via a discrete graph G called a roadmap. Vertices in G correspond to sampled configurations in X, and edges in G correspond to local paths (typically straight lines). Approximately solving the motion-planning problem thus reduces to the problem of Testing if a vertex or an edge of G is collision free requires one or more geometric tests called collision detection. Arguably, collision detection in general, and edge evaluation in particular, are the most time-consuming operations in sampling-based algorithms [LaValle, 2006; Choset et al., 2005]. Thus, path planning on G differs from traditional search algorithms such as Dijkstra [1959] or A* [Hart et al., 1968], where the graph is typically implicit and large, but edge evaluation is trivial compared to search. Indeed, much recent work in motion planning focuses on evaluating the edges of G lazily, that is, assuming that the edges do not intersect with the obstacles O [Bohlin and Kavraki, 2000; Hauser, 2015; Dellin and Srinivasa, 2016; Salzman and Halperin, 2015; Choudhury et al., 2017; Mandalika et al., 2018; Mandalika et al., 2019].

∗ See the full version of this paper [Haghtalab et al., 2018] for proofs and additional material.

In a recent paper, Dellin and Srinivasa [2016] present a unifying formalism for shortest-path problems where edge evaluation dominates the running time of the algorithm. Specifically, they define and investigate a class of algorithms termed Lazy Shortest Path (LazySP), which run any shortest-path algorithm on G followed by evaluating the edges along that shortest path. The algorithms are differentiated by an edge selector function, which chooses the edges the algorithm evaluates along the shortest path. Dellin and Srinivasa show that several prominent motion-planning algorithms are captured by LazySP, using a suitable choice of this selector. Furthermore, they evaluate the algorithm empirically on a wide range of edge selectors and scenarios and show that, using this approach, nontrivial problems can be solved within seconds.

LazySP was proposed as an algorithm that attempts to minimize the overall number of edges evaluated (or queried) in the process of solving a given motion-planning problem. A natural question to ask is

... what is the query complexity of LazySP, and is its query complexity the best possible?

In other words, can we bound the number of edges evaluated by LazySP as a function of the complexity of the roadmap G? And are there algorithms not in this class that have lower query complexity?

To address these questions, we need to explicitly model how queries are answered. We start in Section 3 by considering the deterministic setting, where the set of collision-free edges is determined upfront. Our first result establishes that, in this model, it is optimal to always test edges along the shortest path, i.e., in every instance there is an edge selector for which LazySP is optimal. Although the edge selector in question requires full access to the set of collision-free edges, so the real-world implications of this result are limited, it does provide a theoretical underpinning for the idea of restricting queries to shortest paths, which lies at the heart of LazySP.

In practice, we are interested in a slightly more complex model, which we call the probabilistic setting. Here, each edge is endowed with a probability of being in collision - a common assumption in motion planning (see, e.g., Choudhury et al. 2016)-and we are interested in policies that minimize the query complexity, that is, policies that minimize the expected number of steps until the algorithm finds the shortest path or declares that no path exists. We first show that there are instances where LazySP is suboptimal, regardless of the edge selector. In a nutshell, we describe a delicate construction where initially querying edges that are not on the shortest path provides valuable information for subsequent queries.

So, in the probabilistic setting, LazySP is just a proxy for the (presumably intractable) optimal policy, but is it a good proxy? We answer this question in the positive. Our main result is that the query complexity of LazySP (with an edge selector satisfying a certain connectivity property) is bounded by O(n/p) edge evaluations with high probability, where n is the number of vertices in G, and p is the minimum probability on any edge. We complement this result with an Ω(n/p) lower bound that holds for every algorithm that is guaranteed to be correct. We conclude that, from a worst-case viewpoint, LazySP is, in fact, (asymptotically) optimal.

2 Model

An instance of our problem is given by a multigraph 1 G = (V,E) whose set of vertices includes a source vertex s and a target vertex t. We say that a graph G′ = (V,E′ ) is a subgraph of G if E′ ⊆ E. Given a graph G = (V, E) and a subgraph G′ = (V, E′ ) of G, an oracle OG G′ is a function that takes as input an edge e ∈ E and returns YES if e ∈ E′ , and NO otherwise. When G is clear from the context, we suppress it in this notation.

In the path-finding problem, an algorithm ALG is given a graph G and an oracle OG′ . The goal of the algorithm is to find the shortest s-t path in G′ . Since G′ is not revealed to the algorithm directly, the algorithm has to query OG′ on specific edges of G to find a path. That is, ALG(G,OG′) issues a sequence of edge queries to OG′ , and upon termination, returns an s-t path or decides that none exists. To ground this model in the context of a motion-planning algorithm, the graph G is lazily constructed and can have edges that are in collision while the subgraph G′ contains only collision-free edges.

For an algorithm to be correct, we require that it correctly identifies a shortest s-t path in G′ , or that it certify that none exists (by invalidating every possible path), for any G and G′ ⊆ G. Therefore, a correct algorithm can only terminate

1 We deal with multigraphs, rather than simple graphs, mostly for ease of exposition; see [Haghtalab et al., 2018] for a discussion of this point. We simply refer to G as a graph hereinafter.

Algorithm 1: LAZYSPf

input: Graph G and oracle OG′ Qn ← ∅ // in-collision evaluated edges Qy ← ∅ // collision-free evaluated edges while there exists 2 a shortest s-t path P in E \ Qn do if P ⊆ Qy then return P e ← f(P,Qy,Qn) // select edge along P if OG′ (e) = YES then Qy ← Qy ∪ {e} else Qn ← Qn ∪ {e} end return ∅;

when the solution it provides continues to be correct even if the responses to unqueried edges are selected adversarially. More formally, let Q ⊆ E be the set of edges queried by a correct algorithm ALG on G and OG′ . Let Qy = Q ∩ E′ and Qn = Q \ E′ be the set of queried edges that, respectively, belong and do not belong to G′ . Then ALG can terminate only if there is a shortest s-t path in G′ , denoted P ∗ , such that P ∗ ⊆ Qy, and there is no s-t path in (V,E \ Qn) that is shorter than P ∗ . If no path exists, then ALG can terminate only if there is no s-t path in (V, E \ Qn).

Clearly, an algorithm that first queries all edges in E, thereby fully constructing G′ , and only then finds the shortest s-t path, is a correct algorithm. However, such an algorithm may use a large number of queries, some of which may be unnecessary. In this paper, we are interested in algorithms that find a shortest s-t path using a minimal number of queries. We denote the number of queries that ALG makes on input G and OG′ by cost(ALG(G,OG′)).

We are especially interested in the LazySP class of algorithms, introduced by Dellin and Srinivasa [2016]. Any algorithm in the class LazySP is determined by an edge selector, which, informally, decides which edge to query on a given s-t path. Formally, let P be the set of all s-t paths in G. An edge selector is a function f : P × 2E × 2E → E that takes any s-t path P ∈ P, a subset of queried edges Qy that are in E′ , and a subset of queried edges Qn that are not in E′ , and returns an edge e ∈ P \ Q. For example, a Forward edge selector returns the first unqueried edge in P . See [Dellin and Srinivasa, 2016] for examples of edge selectors.

Given an edge selector f, the corresponding LAZYSPf ∈ LazySP is described in Algorithm 1. At a high level, LAZYSPf , in a given time step, considers a candidate shortest s-t path P over all those edges whose existence has not yet been ruled out by the oracle. Then, it uses the edge selector to query an unqueried edge e ∈ P. It updates the set of queried edges and repeats. At any point, if the edges of path P that is currently under consideration are all verified, the algorithm terminates and returns P . If no viable s-t paths remain, the algorithm terminates and certifies that no s-t path exists in G′ .

Let us conclude this section with an example of the execution of LAZYSP with the forward edge selector, which also illustrates some of the terminology introduced earlier. Figure 1 shows the set of vertices V = {s, t, a, b, c, d, e} shared by G and G′ , as well as two types of edges: those in E′ , shown as solid edges, and those in E \ E′ , shown as dashed edges. The order in which edges are queried is shown as labels on the edges. This order on edge queries is induced by evaluating shortest paths in the following order: sat, sabt, scdt, sabdt, and sabdet.

2 If there are multiple s-t paths of the same length, the algorithm breaks ties according to a consistent tie-breaking rule.

3 The Deterministic Setting

In this section, we consider the problem of using a minimum number of edge queries to find a shortest s-t path, or verifying that no s-t path exists, when a subgraph G′ ⊆ G is deterministically chosen (but not revealed to the algorithm).

In more detail, let G = (V,E) be a graph, and let G′ = (V,E′ ) be a subgraph of G. Recall that cost(ALG(G,OG′)) denotes the number of edge queries ALG makes on graph G when oracle responses are according to graph G′ . Our first result asserts that the class LazySP is optimal in this setting, in the sense that for any correct algorithm there is a LAZYSP algorithm (with a specific edge selector) that finds the shortest path using at most as many queries.

Theorem 1. For any graph G and G′ ⊆ G, and any correct algorithm ALG, there exists ALG′ ∈ LazySP such that

We can alternatively interpret Theorem 1 in a model where LAZYSP may be equipped with an omniscient edge selector that has full access to G′ . In particular, this omniscient edge selector can compute Q∗ , which, by the way, requires solving an NP-hard variant of SET COVER. Even though the algorithm already knows G′ , it still has to issue queries as it must certify that P ∗ is indeed the shortest path (if an s-t path exists).

Clearly, an omniscient edge selector is impractical. The significance of Theorem 1, therefore, is mostly conceptual. It suggests that the restriction that algorithms must always query edges on the current shortest path is not a barrier to optimality. This gives theoretical justification for the LazySP class. However, as we shall see shortly, the message is more nuanced when the outcomes of queries are randomized.

4 The Probabilistic Setting

Let p ∈ (0, 1) be the probability that any given edge in G exists in G′ . We denote by G′ ∼p G the process of generating a random graph G′ = (V, E′ ) from G by allowing each e ∈ E to belong to E′ with probability p, independently. We suppress p in this notation when it is clear from the context.

Here, a subgraph G′ = (V, E′ ) ∼p G is realized according to edge probability p, but it is not revealed to the algorithm. As before, the algorithm receives G and OG′ as input, and uses OG′ to verify whether an edge exists. The goal of the algorithm is to minimize the expected number of edge queries over G′ ∼p G, such that it correctly either (i) returns a path that is the shortest s-t path in G′ , or (ii) certifies that there is no s-t path in G′ . Note that, although the expected number of queries an algorithm issues is taken over G′ ∼ G, the correctness condition must hold for every G′ .

4.1 Suboptimality of LazySP

Our next result asserts that the class of algorithms LazySP does not always include an optimal query policy, which minimizes the expected number of queries. At a high level, the reason behind this is that, in some graphs, querying a few edges that are not on the shortest path can identify the most important regions of the graph, which should be explored next. To see this, consider the graph in Figure 2. In this graph, the arcs marked by A and B each include multi-edge structures shown in Figures 3 and 4, respectively. Structures A and B are designed so that arcs labeled by B are much longer than A, so any LAZYSP algorithm starts by querying the arcs labeled by A.

We compare the cost of any LAZYSP ∈ LazySP (for an arbitrary edge selector) to that of an algorithm ALG defined as follows. ALG first queries all the edges in the multi-edge structures B on arcs sb and at. There are two cases:

1. A path exists in both of the structures sb and at, or in neither one: In this case, ALG calls LAZYSP on the original graph.
2. There is a path in exactly one of the sb or at structures: Without loss of generality (by symmetry) assume that at has a path. Then, ALG queries the edges in structure A on sa, ab and bt in order, until it verifies that at least one of these structures does not have a path or all do.

Then, it returns the shortest s-t path on the edges whose existence has been verified by the queries, or certifies that no s-t path exists.

It is not hard to see that ALG demonstrates the required guarantees for a correct algorithm, i.e., upon its termination it correctly certifies that there is no s-t path or returns the shortest s-t path in the realized graph.

Let us provide an overview of why ALG queries fewer edges than any LAZYSP algorithm in expectation. The structures A and B are designed so that structure A requires more queries than structure B. Additionally, structure A almost certainly fails to have a path, while structure B has a path with a probability close to 1 2 . Note that such a graph almost certainly does not have a path, so a large fraction of E[cost(ALG(G,OG′))] comes from the effort required to invalidate possible s-t paths.

In the first case of ALG (a path exists in both ab and at, or in neither one), it queries more edges than LAZYSP. However, we argue that ALG uses much fewer queries in its second case. The probability of existence of a path in structure B is chosen so that the second case happens with significant probability (almost 12 ), in which case the overall savings in the analysis of the second case bring down the total expected cost of ALG compared to LAZYSP.

In slightly more detail, the crux of the proof is the case where sb does not have a path and at has a path (an example of the second case of ALG). To invalidate all possible s-t paths, it suffices to certify that structure A on sa does not have a path. Therefore, ALG terminates after querying only one A structure, with high probability, in addition to querying two B structures on sb and at. On the other hand, LAZYSP does not know which one of sb or at has a path, so with probability at least 1 2 it first queries some A structure other than sa, in which case it has to also query and verify that no path exists in sa. Therefore, LAZYSP has to query 1.5 A structures in expectation. We design structures A and B so that half the cost of checking an additional A structure is much larger than the initial cost that ALG invests in querying edges in two B structures.

The next theorem formalizes the foregoing discussion.

Theorem 2. There is a graph G = (V, E) and p ∈ (0, 1) for which the optimal query policy is not in LazySP.

4.2 Query Complexity Bounds

The previous section implies that algorithms in LazySP may be suboptimal in the probabilistic setting. Nevertheless, it may still be possible to give satisfying worst-case guarantees with respect to the performance of algorithms in this class. This is exactly what we do next.

Specifically, we show that any algorithm in LazySP (with an edge selector satisfying a certain property) uses O(n/p)

queries, where n = |V |, w.h.p. We then show that there is a graph where no correct path-finding algorithm terminates within ω(n/p) queries. Taken together, these results show that no other algorithm can hope to do significantly better than algorithms in LazySP over all underlying graphs.

In our upper bound, we focus on edge selectors that choose an unqueried edge between two connected components formed by the validated queried edges.

Definition 1. An edge selector f : P×2E ×2E is connective if for any P ∈ P and edge sets Qy and Qn, f(P, Qy, Qn) returns an edge e ∈ P \(Qy ∪Qn) that connects two connected components of the subgraph (V,Qy).

Let us provide an overview of why the forward edge selector (Section 2) used with a LAZYSP algorithm that breaks ties in favor of paths with more verified edges is connective. Note that at any time the set of verified edges forms a connected component around vertex s. Moreover, by the same reasoning behind Dijkstra [1959], if a vertex v is in that connected component, the shortest s-v path in G′ has been found. Now, refer to Figure 5, and consider the path P1, v, v′ ,R, for two vertices v and v′ that are already reachable from s (i.e., P1 ⊆ Qy and P2 ⊆ Qy), and R ⊆ E \ Q. Then LAZYSP would prefer the path P2, R, because |P2| ≤ |P1| + 1 (as it is the shortest path to v′ ), and P2 is fully verified. We conclude that LAZYSP with the forward edge selector never queries an edge within a connected component.

We now turn to deriving a rigorous upper bound on the number of edges queried by any LAZYSP algorithm with a connective edge selector. In terms of implications, we view this theorem as our main result.

Theorem 3. For any δ > 0, p ∈ (0, 1), graph G with n vertices, and a connective edge selector f, with probability at least 1- δ,

In the next theorem, we provide a matching lower bound for the number of queries that any correct path finding algorithm requires.

Theorem 4. For all p ∈ (0, 1) and n > 15, there exists a graph G with n vertices such that for any correct path-finding algorithm ALG,