We consider a variant of the classical shortest-path problem in the presence of polygonal obstacles, in which the motion planner has the ability to remove some of the obstacles to reduce the s-t path length. Formally, let P = {P 1 , . . . , P h } be a set of h pairwise-disjoint polygonal obstacles in R 2 with n vertices, and let c i > 0 be the cost of removing the obstacle
Computing Shortest Paths in the Plane with Removable Obstacles P i for i = 1, . . . , h. For a path π in R 2 , we define its cost, denoted by c(π), to be the sum of the costs of obstacles intersecting π, and its length, denoted by π , to be its Euclidean length. Given two points s, t ∈ R 2 and a budget C > 0, we wish to compute a path from s to t of minimum length whose cost is at most C. This obstacle-removing shortest path generalizes the classical obstacle-avoiding shortest path problem, by giving the planner an option of essentially "tunneling" through obstacles at some cost. Besides an interesting problem in its own right, it is also a natural formulation of tradeoffs in some motion planning settings. For instance, it might be beneficial to remove a few critical blockages in a workspace to significantly shorten an often traveled path, just as an urban commuter may strategically pay money to use certain toll roads or bridges to avoid traffic obstacles. In general, our model with removable obstacles is useful for applications where one can adapt the environment to enable better paths such as urban planning or robot motion planning in a warehouse setting. The problem also generalizes the recent work on obstacle-violating paths [18,25], in which the planner is allowed to enter the forbidden space (obstacles) a fixed number of time. For instance, in [25], a shortest s-t path inside a simple polygon is desired, but the path is allowed to travel outside the polygon once. In [18], a shortest path among disjoint convex polygonal obstacles is desired, but is allowed to travel through at most k obstacles. The latter problem is also an obstacle-removing shortest path where at most k obstacles can be removed, namely, each obstacle removal has cost 1 and planner's budget is k. We will call this the cardinality version of the obstacle-removal to distinguish it from our cost-based model of obstacle removal.
The obstacle removal problem also has a natural connection to path planning under uncertainty. Imagine, for instance, a workspace with n obstacles, the presence of each obstacle is a random event. That is, the presence of the ith obstacle is determined by a Bernoulli trial with (independent) probability β i . A natural approach to planning a s-t path in such a workspace is to search for a path that is both short and obstacle-free with high probability. Given a desired probability of success β, we can ask: what is the shortest path from s to t that is obstacle free with probability at least β. This problem is easily transformed into our obstacle removal problem where the obstacle probabilities are mapped to obstacle removal cost, and β is mapped to the cost budget C.
Our results. We first show that the obstacle-removing shortest path problem is NP-hard for polygonal obstacles in the plane, even if obstacles are vertical line segments by reducing the well-known Partition problem to it. This is in contrast with the cardinality version of the problem, which can be solved exactly in O(k 2 n log n) time [18].
Our main result is a fully-polynomial time approximation scheme (FPTAS) when each obstacle is a convex polygon. We first define the notion of the viability graph G, which is an extension of the well-known visibility graph [11,13], for geometric paths that can cross obstacles. Using the viability graph, we present a simple algorithm that returns a path with length at most the optimal 1 but cost at most (1 + ǫ)C. The approximation algorithm, while simple, has a worst-case time complexity Θ( n 3 ǫ polylog(n)). Then, we develop a framework for a more efficient and practical approximation algorithm, which also results in a number of related results. Specifically, for any constant ǫ > 0, we can compute a (1 + ǫ)-approximate shortest path whose total removal cost is at most (1 + ǫ)C in time O nh ǫ 2 log n log n ǫ , where h is the number of obstacles and n is the total number of vertices in the obstacles. The main idea behind the improvement is to construct a sparse viability graph, with only O( n ǫ log n) edges. This approximation scheme immediately gives a corresponding result for the uncertain model of obstacles (see Section 5). The approximation scheme, as a byproduct, also solves the exact L 1 norm shortest path problem in the cardinality model of obstacle removal: that is, in O(kn log 2 n) time, we can decide which k obstacles to remove for the shortest s-t path, which is roughly a factor of k faster than the L 2 -norm result of [18]. Alternatively, we can also decide which k obstacles to remove so that the shortest s-t path has length at most (1 + ǫ) times optimal in O( kn ǫ log 2 n) time. This is again faster than the result from [18] for constant ǫ, if k = Ω(log n).
We
The problem of computing a shortest path in the presence of polygonal obstacles in the plane is a very well studied problem in computational geometry. See the books [16,31], survey paper [27], recent papers [5,8,9,10,20], and references therein for a sample of results. In the classical shortest path problem, obstacles are impenetrable, that is, the shortest path must avoid all the obstacles. Our problem considers a more general scenario where the obstacles can be removed by paying some cost and falls in the broad category of geometric optimization problems where some constraints can be violated [2,17,26,30].
Our problem is also closely related to the problem of computing a shortest path through weighted polygonal regions [23,24,28] where the length of a path is defined as the weighted sum of Euclidean or L 1 lengths of the subpaths within each region. However, in our setting there is only a one-time fixed cost for passing through a region, and therefore does not depend on the length of the subpath that lies inside the region.
The stochastic formulation of our problem is also related to some shortest path problems under uncertainty [14,15,22,29]. However, these results assume existence of a graph whose edges have either an existence probability or a distribution over their lengths. In contrast, our definition is purely geometric where the existence of obstacles is an uncertain event. Our problem can also be seen as a variant of geometric bi-criteria shortest path problem [1,4,33,34,35], as our objective is to compute the shortest path with a constraint on the total cost of obstacles that we remove.
Finally, for most geometric shortest path problems, there are efficient data structures to answer shortest path queries. For instance, the shortest path map [19] has linear size and can answer Euclidean shortest path queries with a fixed source in O(log n) time. If both s, t are part of the query, quadratic space data structures [7,21] exist for L 1 shortest path queries and super quadratic space data structures [12] for L 2 shortest path queries. Similar results exist for rectilinear shortest path queries among disjoint weighted rectilinear and convex obstacles [6,7], and for bi-criteria shortest path problems [4,33,35].
Overall, our algorithms entail new techniques because (i) in our problems, paths are allowed to pass through obstacles, (ii) the cost function in our bi-criteria optimization can be quite general and not necessarily a metric. S WAT 2 0 1 8
uv , where c(u, v) is the cost of the segment uv. In the worst-case G has Θ(n 2 ) edges. It is important to note that the cost of a path π st in a viability graph is defined as the sum of the costs of its edges, whereas the cost of π st in the plane is defined as sum of costs of all obstacles that it goes through. Moreover, the cost of a path in the plane is at most its cost in the viability graph. If the path crosses each obstacle at most once (which is the case for shortest path among convex obstacles), these two costs are the same.
The following algorithm shows how to compute an approximately optimal path in this viability graph. The main idea is that we construct copies of the vertices and the edges of G to convert the multi-objective problem to a single-objective problem.
Let κ = min C mini ci , h . To simplify the approximation error analysis, we first scale all the costs by κ/C, so that the new target cost is κ. We now construct an auxiliary graph
ǫ edges, whose edges only have the length parameter but not the cost parameter, as follows. We create
Then, for each edge (u, v) ∈ E with cost c and for each 0 ≤ i ≤ ⌈2κ/ǫ⌉, we add the edge (u i ǫ 2 , v j ǫ 2 ), where j ≤ ⌈2κ/ǫ⌉ is the maximum integer with j ǫ 2 ≤ i ǫ 2 + c. All these edge copies have the same length as edge (u, v)-the cost parameter is now implicitly encoded in the edge copies. Finally we add two new vertices s and t in G ′ and connect them to all s i and t i respectively with zero length edges, for 0 ≤ i ≤ ⌈2κ/ǫ⌉. We now find the minimum length path π from s to t in G ′ , say, using Dijkstra's algorithm, and argue that π is our approximation path. ◮ Theorem 3. Let P be a set of h convex obstacles with n vertices, s, t be two obstacle vertices, and C ∈ R be a parameter. Let L * also be the length of the shortest s-t path with cost at most C, and let G = (V, E) be a viability graph induced by this workspace. If there exists a path π * of length at most αL * with α ≥ 1 and cost at most C in the graph G, then a s-t path π with length at most αL * and cost at most
, where κ = min C mini ci , h and 0 < ǫ < 1 is a parameter.
Proof. First, we construct the auxiliary graph G ′ as described above. Next, we construct a path π ′ in G ′ corresponding to the path π * in G by mapping edges of π * to edges in G ′ . More precisely, let e = (s, v) be the first edge in π * and let c e be its cost. Now let c = 0 and c ′ be the value obtained by rounding down c e to the nearest multiple of ǫ 2 . We map e to the edge (s c , v c ′ ) in G ′ . Setting c = c ′ , we repeat the process for all edges in π * . This gives us the path π ′ in G ′ that has the length same as that of π * (at most αL * ). Clearly, the s-t path π computed using Dijkstra's algorithm on G ′ must also have length at most αL * . Moreover, since (scaled) rounded cost of any s-t path in G ′ is at most κ, the rounded cost of π is also at most κ. Now we only need to bound its original (pre-rounded) cost.
Let C R be the true (pre-rounded) cost of the path π in the plane and C A its rounded cost in G ′ . The approximation error in the cost (due to rounding) is at most ǫ/2 for each obstacle that π passes through, and so if k is the number of obstacles π crosses, we have the
We can bound k by considering the following two cases. If κ = C/ min i c i , the minimum cost of an obstacle is 1, and so for each obstacle crossed, the path π incurs a cost of least 1 -ǫ/2. Therefore,
Otherwise, we have κ = h, which trivially implies k ≤ κ since h is the total number of obstacles.
In conclusion, we have C R ≤ (1 + ǫ)κ, whose pre-scaled value is If G is the viability graph constructed in this section then it always contains the shortest s-t path with cost at most C, i.e. α = 1. Hence, by applying Theorem 3 to G we get a path of at most the optimum length and cost at most (1 + ǫ)C in Ω( n 3 ǫ ) time. In the next section, we show that if we also allow an (1 + ǫ) approximation of the path length, we can improve the running time by roughly an order of magnitude.
In this section, we describe our algorithm for sparsifying the graph G = (V, E). We augment the graph by adding some vertices so that the number of viability edges can be sharply reduced, while approximately preserving the path lengths within the cost budget. Throughout the following discussion, we will respect the cost budget C, and only allow the path lengths to increase slightly. With that in mind, we use the notation d G (u, v) to denote the length of the shortest path in G from u to v whose cost is at most C. In this section we only use the definition of the cost of a path with respect to a viability graph. Recall that the cost of a path in a graph is the sum of the costs of the edges in the path.
Our sparse graph H ǫ = (X ǫ , T ǫ ) is defined for any ǫ > 0, with V ⊆ X ǫ , and satisfies the following two conditions:
We construct H ǫ in two stages. In the first stage we construct a graph H = (X, Γ) with
Next, we make O(1/ǫ) "copies" of H and combine them to construct H ǫ . Once the graphs H and H ǫ are constructed, we use the machinery of the previous section, namely Theorem 3, to efficiently find the approximately optimal shortest path within the cost budget.
Recall that all the obstacles in our input are convex, and therefore the shortest path in G does not cross the boundary of an obstacle more than twice. To avoid degenerate cases, we assume that all obstacle vertices are in general position, namely, no three vertices are collinear and all obstacles have non-zero area. We can, therefore, simplify the problem by replacing all the obstacles by their constituent boundary segments, where each obstacle vertex is assigned to its incident segment in the clockwise order. We now allocate the "obstacle removal" cost to these segments as follows: if c i is the removal cost of obstacle i, then we allocate cost c i /2 to each boundary segment of obstacle i. This ensures that any shortest path crossing the ith obstacle incurs a cost of c i , while allowing us to reason about the geometry of just line segment obstacles.
We describe the construction of the sparse viability graph by explaining how to sparsify the "neighborhood" of an obstacle vertex, say, p. That is, we show which additional vertices are added and which viability edges are incident to p in the final sparse graph H. To simplify the discussion, we assume that p is at the origin, and we only discuss the edges incident to p that lie in the positive (north-east) quadrant; the remaining three quadrants are processed in the same way.
In this subsection we describe the construction of H = (X, Γ) such that |X|, |Γ| = O(n log n), and
For a segment pq we use pq 1 to denote its L 1 -length, i.e., pq 1 = |x p -x q | + |y p -y q |, where p = (x p , y p ) and q = (x q , y q ). For a polygonal path π = p 0 p 1 . . . p k , we use π 1 to clip off the region of R ′ pq that lies above l w . More precisely, this gives us the quadrilateral R ′′ pq = R ′ pq \ A(l w ), where we use A(s) for the region above segment s. Finally, we define the convex polygon
, where s ′ p , s ′ q are the subsegements of s p , s q respectively that lie inside the quadrilateral R ′′ pq . From the set of obstacle vertices that lie inside or on the boundary of T pq , we choose the vertex r to be the one that minimizes the area of the triangle ∆prq, or equivalently, be the one that has the minimum distance from the segment pq. Observe that the boundary of region T pq contains the obstacle vertex w, so we will always find one such r. It is easy to see that the triangle ∆prq is a subset of T pq and does not contain an obstacle vertex or else it would not have the minimum area. It remains to show that there cannot be an obstacle segment that crosses both pr and rq. To this end, let l r be a line parallel to pq passing through r. Observe that the region T ′ pq = T pq \ A(l r ), i.e., the region in T pq that lies below l r , cannot contain an obstacle vertex by the choice of r. So any obstacle segment s j that crosses both pr and rq must intersect ∂R ′ pq at either the vertical segment between p and s p or the horizontal segment between s q and q which is a contradiction. (See also Figure 4.) ◭ Finally, we prove the main result of this section. ◮ Lemma 7. Let (p, q) be an edge in G with cost c(p, q). There is a path π pq ∈ H such that π pq 1 = pq 1 and c(π pq ) ≤ c(p, q). Moreover, the path π pq lies in the region R pq .
Proof. We prove this by induction on the number of obstacle vertices in the region R pq . Our base case is when the region R pq does not contain an obstacle vertex. Applying Lemma 5 gives us the desired path π pq in H. For the inductive step, let j be the number of obstacle vertices in the region R pq and assume that the lemma holds for all edges (u, v) such that the region R uv contains i < j obstacle vertices. Using Lemma 6 we find an intermediate vertex r such that pr 1 + rq 1 = pq 1 and c(p, r) + c(r, q) ≤ c(p, q). This gives us two disjoint subregions R pr ⊂ R pq and R rq ⊂ R pq each with at least one less obstacle vertex than the region R pq . By our induction hypothesis, we get the disjoint subpaths π pr from p to r and π rq from r to q in H. We then join these two paths at vertex r to obtain path π pq that lies within the region R pq . Moreover, we have that π pq 1 = π pr 1 + π rq 1 = pr 1 + rq 1 = pq 1 and c(π pq ) = c(π pr ) + c(π rq ) ≤ c(p, r) + c(r, q) ≤ c(p, q). ◭
We now describe how to use the preceding construction to define our final sparse graph H ǫ .
A direction in R 2 can be represented as a unit vector u ∈ S 1 . Let N ⊂ S 1 be a set of O(1/ǫ) unit vectors such that the angle between two consecutive points of N is at most ǫ. For each u ∈ N, we construct a graph H u by running the algorithm in Section 4.1 but regarding u to be the y axis -i.e., by rotating the plane so that u becomes parallel to the y-axis and measure L 1 -distance in the rotated plane. Set H ǫ = u∈N H u . Notice that the number of vertices and edges in
The following lemma follows easily by the discussion above.
From the above lemma, it follows that the graph H ǫ preserves pairwise shortest path distances within a factor of (1 + ǫ) and at most the same cost with graph G. Let L * be the length of the shortest s-t path in the plane that has cost at most C. Since there exists a s-t path of length at most L * and cost at most C in the viability graph G, there exists a s-t path in H ǫ of length (1 + ǫ)L * and the same cost. Applying Theorem 3 with α = (1 + ǫ) on H ǫ gives the following result. ◮ Theorem 9. Let P be a set of h convex polygonal obstacles with n vertices, s, t be two obstacle vertices and C ∈ R be a parameter. If L * is the length of the shortest s-t path with cost at most C, a s-t path with length at most (1 + ǫ)L * and cost at most (1 + ǫ)C can be computed in O( nh ǫ 2 log n log n ǫ ) time.
We now describe a near-linear space data structure to answer approximate distance queries from a fixed obstacle vertex s subject to the obstacle removal budget in O( 1 ǫ log 2 n) time. The data structure is then extended to handle two-point shortest path queries in O( 1 ǫ 2 log 2 n) time with near-quadratic space.
The key idea relies on the following observation. Without loss of generality, assume that the points s and t lie in the exterior of all obstacles and let us also assume that s, t were part of the input. Now consider the shortest s-t path in the graph H ǫ and let t ′ be the vertex preceding t in this path. It is easy to see that t ′ must be a Steiner vertex (projection or bypass) as there are no direct edges in H ǫ between two input vertices that do not lie on the same obstacle. All such edges must cross some split line at Steiner vertices. Therefore, the last edge (t ′ , t) in the path is the segment obtained by projecting t on some split line ℓ. Now, suppose we have precomputed the paths to all Steiner vertices on all split lines, then we can find the shortest path to t by simply finding the neighbor of t ′ on ℓ. Using Lemma 4, we know that t can be projected on O( 1 ǫ log n) split lines, which gives O( 1 ǫ log n) choices for ℓ.
Preprocessing. We apply the algorithm preceding Theorem 3 on the graph H ǫ that we constructed in the previous section. More precisely, first we multiply the cost of all obstacles by h/C so that the target cost becomes h. Next we create an auxiliary graph H ′ ǫ with O( h ǫ ) copies of each vertex in H ǫ . Running Dijkstra's algorithm on H ′ ǫ with source s computes a shortest path to each vertex in H ′ ǫ . Now for each vertex v in H ǫ , we maintain arrays dist v , pred v each with size 1 + h ǫ = O( h ǫ ). We store the length of the shortest path found by Dijkstra's algorithm from s to v iǫ (i-th copy of vertex v) at dist v (i) and its predecessor in pred v (i). In addition, for each direction u ∈ N that we defined in the previous section we maintain two data structures:
A segment tree [3] based data structure S u that we also used in Section 4.1 to compute the cost of an axis aligned segment in O(log n) time.
A balanced search tree T u over all the vertical (resp. horizontal) split lines, which is basically the recursion tree corresponding to the algorithm from Section 4.1. More precisely, the root of T u is the split line ℓ m (at the median x-coordinate x m ), and the left and right children are the split lines added during recursive processing of points to the left and right of ℓ m respectively.
Moreover, for every split line ℓ, we maintain a search tree over all the Steiner vertices that lie on ℓ. Overall, our data structure consists of all arrays dist v , pred v , O(
In this section, we consider a stochastic model of obstacles where the existence of each obstacle P i ∈ P is an independent event with known probability β i . That is, P i is part of the input with probability β i and is not part of the input with probability 1 -β i . We define the probability of path π st as Pi∈S (1 -β i ) where S ⊆ P is the set of obstacles that this path goes through (assuming they did not exist). In such a setting, our goal is to compute the approximate shortest path that has probability more than a given threshold β ∈ (e -1 , Let L β denote the length of the shortest path from s to t with probability at least β. We convert the multiplicative costs to additive costs by setting c i = -ln(1 -β i ) for each obstacle and setting C = -ln β. Using Theorem 9, we find a path π st with length L(π st ) ≤ (1 + ǫ)L β and cost c(π st ) ≤ (1 + ǫ)C. It can be shown that π st has probability at least (1 -ǫ)β. ◮ Theorem 12. Let P be a set of h convex polygonal obstacles with n vertices, where each obstacle P i ∈ P exists independently with a probability β i , s, t be two obstacle vertices and β ∈ (e -1 , 1] be a parameter. If L β is the length of the shortest s-t path with probability at least β, a s-t path with length at most (1 + ǫ)L β and probability at least (1 -ǫ)β can be computed in O( nh ǫ 2 log n log n ǫ ) time.
Most likely path. We now consider the following question -given a bound L on the length of the path, what is the s-t path with maximum probability? We need a bound on the path length or else there is always a path of probability 1. To answer this question, we can again take negative logarithms of probabilities to transform into an additive cost model and construct the graph H ǫ as before. Now instead of applying Theorem 3 on H ǫ , we construct a new graph H * ǫ that is exactly the same as H ǫ , but with length and cost parameters on edges interchanged. More precisely, for an edge e ∈ H ǫ with length l e and cost c e , we have an edge e * ∈ H * ǫ with length c e and cost l e . Next we apply Theorem 3 on the graph H * ǫ with C = (1 + ǫ)L, and scale all costs with a parameter O( n Cǫ log n), such that the target cost is scaled to O( n ǫ log n). We choose this value because a shortest path in H ǫ can have O( n ǫ log n) edges. This gives us the following result. ◮ Theorem 13. Let P be a set of h convex obstacles with n vertices, s, t be two obstacle vertices, and L ∈ R be a parameter. If β M is the maximum probability of a path from s to t with length at most L, a path π st with length at most (1 + ǫ)L and probability at least β M can be computed in O( n 2 ǫ 3 log 2 n log n ǫ ) time.
S WAT 2 0 1 8
The optimal length is always with respect to the budget C.