# improved_results_for_minimum_constraint_removal__f68e395c.pdf

Improved Results for MINIMUM CONSTRAINT REMOVAL

Eduard Eiben Algorithms and Complexity Group, TU Wien, Vienna, Austria & Dept. of Informatics, Univ. of Bergen, Norway eduard.eiben@uib.no

Jonathan Gemmell, Iyad Kanj, Andrew Youngdahl School of Computing, De Paul University, Chicago, USA, {jgemmell,ikanj,ayoungda}@cdm.depaul.edu

Given a set of obstacles and two designated points in the plane, the MINIMUM CONSTRAINT REMOVAL problem asks for a minimum number of obstacles that can be removed so that a collision-free path exists between the two designated points. It is a well-studied problem in both robotic motion planning and wireless computing that has been shown to be NP-hard in various settings. In this work, we extend the study of MINIMUM CONSTRAINT REMOVAL. We start by presenting reﬁned NP-hardness reductions for the two cases: (1) when all the obstacles are axes-parallel rectangles, and (2) when all the obstacles are line segments such that no three intersect at the same point. These results improve on existing results in the literature. As a byproduct of our NP-hardness reductions, we prove that, unless the Exponential-Time Hypothesis (ETH) fails, MINIMUM CONSTRAINT REMOVAL cannot be solved in subexponential time 2o(n), where n is the number of obstacles in the instance. This shows that signiﬁcant improvement on the brute-force 2O(n)-time algorithm is unlikely. We then present a subexponential-time algorithm for instances of MINIMUM CONSTRAINT REMOVAL in which the number of obstacles that overlap at any point is constant; the algorithm runs in time 2O(

N), where N is the number of the vertices in the auxiliary graph associated with the instance of the problem. We show that signiﬁcant improvement on this algorithm is unlikely by showing that, unless ETH fails, MINIMUM CONSTRAINT REMOVAL with bounded overlap number cannot be solved in time 2o(

N). We describe several exact algorithms and approximation algorithms that leverage heuristics and discuss their performance in an extensive empirical simulation.

Introduction A fundamental problem in robot motion planning is to move a robot from a starting position to a ﬁnal position while avoiding collision with a given set of obstacles. This problem is generally referred to as the piano-mover s problem. If a collision-free path does not exist, one naturally seeks a path that collides with the minimum number of obstacles. In this paper, we study a variant of the piano mover s problem, referred to as the MINIMUM CONSTRAINT REMOVAL problem, deﬁned as follows:

Copyright c 2018, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

MINIMUM CONSTRAINT REMOVAL Given: A set I of polygonal obstacles in the plane and two designated points s and t. Goal: Compute a subset of obstacles S I of minimum cardinality such that there is an obstacle-free path in the plane between s and t w.r.t. the obstacles in I\ S. In addition to its applications in robotics, the problem has been studied extensively, motivated by applications in wireless computing, under the name BARRIER COVERAGE or BARRIER RESILIENCE. In such applications, we are given a ﬁeld covered by sensors (assumed to be simple geometric shapes), and the goal is to compute a minimum set of sensors that need to fail so that an entity can move undetected between two given sites (Alt et al. 2011; Tseng and Kirkpatrick 2012; Chan and Kirkpatrick 2014; Kumar, Lai, and Arora 2005; Yang 2012). The MINIMUM CONSTRAINT REMOVAL problem was also formulated as a graph problem (Chan and Kirkpatrick 2014; Hauser 2014). For an instance I of the problem, the auxiliary graph of I, GI, is deﬁned as follows. Consider the plane subdivision whose regions are determined by the intersections of the obstacles in I. For each region, associate a vertex in GI representing the set of obstacles intersecting at that region if any, and an empty set otherwise; add an edge between two vertices iff the corresponding regions share an edge. See Figure 1. Clearly, GI is a plane graph since it is the dual graph of a plane subdivision. The problem then reduces to computing a path in GI between the vertices corresponding to s and t, such that the total number of obstacles represented by the vertices on this path is minimum. MINIMUM CONSTRAINT REMOVAL was studied by many researchers in Wireless Computing, AI, and Computational Geometry (Alt et al. 2011; Tseng and Kirkpatrick 2012; Chan and Kirkpatrick 2014; Kumar, Lai, and Arora 2005; Yang 2012; Erickson and La Valle 2013; Hauser 2014). Alt et al. (Alt et al. 2011) showed that the problem is NP-hard when the obstacles are line segments such that no three intersect at the same point. Independently, Yang (Yang 2012), in his Ph.D. dissertation, showed the NPhardness of the problem when the obstacles are line segments. This result was reﬁned independently by Tseng and Kirkpatrick (Tseng and Kirkpatrick 2012) who showed that the problem is NP-hard even when the obstacles are line segments of unit length. The more general graph problem

The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18)

Figure 1: Illustration of the regions determined by a set of obstacles (placed within a bounding box) and its auxiliary graph, with a highlighted optimal path crossing one obstacle.

was considered by several researchers, including (Chan and Kirkpatrick 2014; Hauser 2014), and it is well known to be NP-hard (for instance, see (Hauser 2014) for a proof). Hauser (Hauser 2014) implemented and tested several algorithms for MINIMUM CONSTRAINT REMOVAL. In this paper, we continue the study of the MINIMUM CONSTRAINT REMOVAL problem. We ﬁrst consider the complexity of the problem, and show the following: (1) MINIMUM CONSTRAINT REMOVAL is NP-hard even if all the obstacles are axes-parallel rectangles. (2) MINIMUM CONSTRAINT REMOVAL is NP-hard even if all the obstacles are line segments such that no three intersect at the same point. The results in (1) and (2) reﬁne and improve the earlier work on the problem. More speciﬁcally, the result in (1) answers an open question posed in (Erickson and La Valle 2013). Even though the result in (2) was obtained earlier by Alt et al. (Alt et al. 2011), the NP-hardness reduction we use to prove (2) is more reﬁned than the reduction used in (Alt et al. 2011). In particular, the reduction we use implies the ETH results in (3) and (5) below, and those cannot follow from the reduction in (Alt et al. 2011); this is because our reduction results in a linear number of obstacles, as opposed to the quadratic number of obstacles resulting from their reduction. As a byproduct of the reductions used to derive the above NP-hardness results, we obtain the following: (3) Unless the Exponential-Time Hypothesis (ETH) fails, MINIMUM CONSTRAINT REMOVAL cannot be solved in subexponential time 2o(n), where n is the number of obstacles in the instance. The result in (3) shows that signiﬁcant improvement on the 2O(n)-time brute-force algorithm is unlikely, as ETH is a standard hypothesis for proving lower bounds (Aghighi et al. 2016; de Haan, Kanj, and Szeider 2015; Lokshtanov, Marx, and Saurabh 2011), which states that the satisﬁability of k CNF formulas (for k 3) is not solvable in subexponentialtime 2o(n), where n is the number of variables in the formula.

We then design algorithms for the NP-hard restriction of CONSTRAINT REMOVAL to instances in which no more than a constant number b of obstacles overlap at the same point, denoted b-OVERLAP MINIMUM CONSTRAINT REMOVAL, for any integer-constant b 2. We show that: (4) There is a subexponential-time algorithm for b-OVERLAP MINIMUM CONSTRAINT REMOVAL that runs in time 2O(

N), where N is the number of the vertices in the auxiliary graph associated with the instance; and (5) unless ETH fails, b-OVERLAP MINIMUM CONSTRAINT REMOVAL cannot be solved in time 2o(

N). The result in (4) gives a subexponential-time algorithm for b-OVERLAP MINIMUM CONSTRAINT REMOVAL w.r.t. the number of obstacles n, for instances in which the number of regions N, equivalently vertices in GI, is o(n2). Finally, we implement several exact and approximation algorithms and provide extensive empirical simulation results to compare their performance for varying sizes of n. Heuristics are proposed to improve performance.

Hardness Results

In this section, we consider the decision version of MINIMUM CONSTRAINT REMOVAL, denoted CONSTRAINT REMOVAL, in which we are given a set I of obstacles, two points s and t, and k N, and we need to decide if there is an s-t path that intersects at most k obstacles in I. First, we start by showing that CONSTRAINT REMOVAL remains NP-hard even when the obstacles are axes-parallel rectangles; this answers an open question in (Erickson and La Valle 2013). Second, we show how our reduction can be modiﬁed to yield a reduction in which the obstacles are line segments such that no three of them intersect at the same point; this corrects the claim in (Erickson and La Valle 2013) stating that MINIMUM CONSTRAINT REMOVAL becomes trivial when the obstacles intersect only pairwise. As we mentioned in the previous section, the NP-hardness result for the line segments case was obtained earlier (Alt et al. 2011); however, the NP-hardness reduction we use is more reﬁned. To obtain the hardness results, we reduce from an NP-hard restriction of the MAXIMUM NEGATIVE 2SATISFIABILITY problem. An instance of MAXIMUM NEGATIVE 2-SATISFIABILITY is given as a pair (F, m ), where m N and F is a Boolean formula on n variables and m clauses. The question is to decide whether F has a satisfying assignment that satisﬁes at least m clauses. The NP-hard restriction of MAXIMUM NEGATIVE 2-SATISFIABILITY we use, denoted R-MN2Sat, satisﬁes the following properties: (1) Each clause in the formula F is either a unit clause containing a positive literal {xi}, or a binary clause containing two negative literals; (2) the unit clauses in F are precisely the clauses {xi}, for each variable xi in F; and (3) the number of both positive and negative occurrences of each variable is at most 4. A consequence of (3) is that the number of clauses m in F is at most n + 3n/2 3n. It can be easily shown that R-MN2Sat is NP-hard via a straightforward reduction from INDEPENDENT SET on graphs of maximum degree at most 3. It is well known, and follows from (Johnson and Szegedy 1999), that unless ETH fails, INDEPEN-

DENT SET on graphs of maximum degree at most 3 is not solvable in time 2o(n), where n is the number of vertices in the graph. It follows from the reduction from INDEPENDENT SET to R-MN2Sat that, unless ETH fails, R-MN2SAT is not solvable in time 2o(n). This result will be employed to derive lower-bound results on the subexponential-time complexity of MINIMUM CONSTRAINT REMOVAL. We start with this simple observation: Observation 1. Any truth assignment to an instance F of RMN2Sat that satisﬁes m clauses can be transformed into an assignment that satisﬁes at least m clauses in F including all binary clauses.

Figure 2: Illustration for the proof of Theorem 2 for F = x1 x2 x3 x4 ( x1 x4) ( x2 x3) ( x3 x1).

Axes-parallel Rectangles Let RECTANGLE-CONSTRAINT REMOVAL be the restriction of CONSTRAINT REMOVAL to instances in which each obstacle is an axes-parallel rectangle. Theorem 2. RECTANGLE-CONSTRAINT REMOVAL is NPhard.

Proof. We give a polynomial-time reduction from R-MN2Sat to the decision version of RECTANGLECONSTRAINT REMOVAL. We highlight the main differences between the current reduction and that in (Erickson and La Valle 2013). See Figure 2 for illustration. Let (F, m ) be an instance of R-MN2Sat, where F has n variables x1, . . . , xn and m clauses C1, . . . , Cm. Let m1 =

n be the number of unit clauses in F, and m2 = m n be the number of remaining (binary) clauses. To construct the instance (I, k) of RECTANGLE-CONSTRAINT REMOVAL, as in (Erickson and La Valle 2013), we start by enforcing a schema that any valid path must be conﬁned within. We ﬁrst outline a rectilinear region R, whose boundary is shown in black in Figure 2. This region consists of an open rectangular region containing the starting point s (green); a rectilinear corridor C that runs vertically and then makes three left turns; a set of rectangular-like boxes intersecting C in their middle, each enclosing a black rectangle; and an open rectangular region containing the destination point t (burgundy). For each variable xi, we associate two boxes, Bi and B i, of the same shape and size, laid out horizontally and symmetrically on opposite ends of the vertical part of corridor C (before C turns). We call the Bi s and B i s variable-boxes. The Bi s appear on the top and run in decreasing horizontal dimension, and the B i s appear on the bottom and run in increasing horizontal dimension. The order in which the Bi s appear is the opposite order of the B i s. Each Bi (resp. B i) contains a black rectangle inside, subdividing it into an upper and a lower part, and creating a left passage and a right passage from its upper to its lower part. For each binary clause Cj, we associate a box BCj that we call a clausebox; the clause-boxes are placed towards the end of C, just before the destination point t, and are laid out vertically. To place the obstacles of I in R, we start by ﬁxing two integer-constants: c1 > 4 and c2 > c1 n + 3m. To simplify the presentation of the proof, we will assign (in the proof) integer weights to certain obstacles to indicate an overlaying of the weight-many distinct identical-shape obstacles. Intuitively, the obstacles will be placed so that the portion of the path traversing the variable-boxes corresponds to an assignment of the variables in F, where traversing the left (resp. right) side of box Bi corresponds to assigning xi to TRUE (resp. FALSE); the other portion of the path, traversing the clause-boxes, can be done in such a way that if a literal has been assigned TRUE by the ﬁrst portion of the path, the clauses containing the literal can be traversed at no additional cost. To conﬁne the path to the interior of region R, we form the boundary of R by placing axes-parallel rectangular obstacles (shown in the same black color as the boundary), each of weight c2, along this boundary so that they only (pairwise) overlap (in small squares) to form the corners of R; this ensures that the cost of crossing the boundary of R exceeds the required budget k, which will be speciﬁed shortly. Similarly, each black rectangle outlined inside a box in R, whose role is to block the direct passage of a path from one box to the next without setting the truth assignment of the variable associated with the ﬁrst box, is formed using an axes-parallel rectangular obstacle of weight c2; this way, the desired path cannot intersect any of these internal rectangles. We refer to the obstacles of weight c2 as heavy obstacles. For each binary clause Cj in F, we arbitrarily order the two (negative) literals in Cj as ﬁrst and second. For each literal xi and clause Cj such that xi is the ﬁrst (resp. second) literal in Cj, we create an axes-parallel rectangular obstacle of weight 1 (orange) that intersects the right side of box Bi (resp. B i) including the internal rectangle, without

intersecting any other variable-boxes, and intersects the top (resp. bottom) of the clause-box corresponding to Cj (including the internal rectangle) without intersecting any other clause-boxes (see Figure 2). These obstacles ensure that a path that sets a literal xi to TRUE can traverse Cj at no additional cost. For each positive clause {xi}, we place an axesparallel rectangular obstacle of weight 1 (yellow) in the right side of Bi so that any path setting xi to false intersects this obstacle. We call all these (orange plus yellow) obstacles incidency obstacles. For each variable xi, we add two axes-parallel rectangular obstacles (purple), each of weight c1. The ﬁrst obstacle intersects the left sides of Bi and B i without intersecting any other variable-boxes, and the second intersects the right sides of these boxes; these obstacles, referred to as consistency obstacles, are used to ensure that we do not set both a variable and its negation to TRUE. Finally, for each xi, let pi be the number of occurrences of xi in F; we place pi many weight-1 axes-parallel rectangular obstacles (blue), referred to as balancing obstacles, in the left side of Bi. Let k = c1 n+2m2 +m1 (m m2), and note that k < c2. This completes the construction of the instance (I, k) of RECTANGLE-CONSTRAINT REMOVAL. We claim that (F, m ) is a yes-instance iff (I, k) is. We ﬁrst draw the following observations. (1) By the choice of c2, any path that intersects at most k obstacles cannot intersect a heavy obstacle, and hence, must stay within R. (2) Any path corresponding to a consistent assignment intersects exactly n consistency obstacles. Suppose that F has a truth assignment τ that satisﬁes at least m clauses. By Observation 1, we can assume that τ satisﬁes the m2 binary clauses in F and at least m m2 unit clauses. Consider the s-t path P in R that travels through the right side of boxes Bi and B i, for each variable xi assigned FALSE by τ, and through the left side of these boxes otherwise; and for each satisﬁed binary clause, P travels through the part of the clause-box intersecting the incidency obstacle corresponding to a satisﬁed literal in the clause. We claim that P intersects at most k obstacles. To see this, note that by observation (2), this path intersects exactly n consistency obstacles, for a total cost of c1 n. Second, for each Bi, regardless of whether P traverses the left or right passage in Bi, P crosses the number of occurrences of xi many balancing obstacles, plus one incidency obstacle if P traverses the right side of Bi, and hence τ does not satisfy the unit clause {xi}. It follows that the total number of obstacles that P intersects in its variable truth-setting portion is equal to the total number of occurrences of negative literals in F, which is 2m2, plus the total number of unit clauses that are dissatisﬁed by τ, which is at most m1 (m m2). Since τ satisﬁes all binary clauses, no additional cost is incurred in the remaining portion of P. It follows that P intersects a total of at most c1 n+2m2 +m1 (m m2) = k obstacles. Conversely, let P be an s-t path that intersects at most k obstacles. By observation (1), P lies inside R. Since P has to go through each of the n variable-boxes, for each i [n], if P traverses the left (resp. right) side of Bi, then we can assume, without loss of generality, that P traverses the left (resp. right) side of B i. This assumption can be justiﬁed as

follows. If P traverses the left side (resp. right side) of Bi but then traverses the right side (resp. left side) of B i, then it would incur an additional cost of c1 > 4. Since the ultimate gain/saving from such a switch is the number of occurrences of xi in F, which is at most 4 < c1, rerouting P so that it traverses the same side of B i as Bi decreases the cost, and results in an alternative path that is cheaper than P. We can also assume that P incurs no additional cost in its second portion that traverses the clause-boxes. This assumption can be justiﬁed as follows. Suppose that P intersects a new obstacle while traversing the clause-box of a clause Cj. Pick a literal xi Cj. Then P must have traversed the left passage of Bi. If we reroute P so that it traverses the right passages of Bi and B i instead, then it is easy to see that the cost of the truth-setting portion of P due to this rerouting can increase by at most 1 due to the incidency obstacle corresponding to {xi} in the right part of Bi that the path has now to intersect. However, this additional cost is annulled since the new path now traverses Cj at no cost. With the above assumptions in mind, consider now the truth assignment τ that assigns xi to TRUE iff P traverses the left side of Bi. Then τ is consistent. The path P intersects: c1 n many consistency obstacles, a total of 2m2 many balancing obstacles, an incidency obstacle for each box Bi that P traverses its right side, and intersects no new obstacles in its portion that traverses the clause-boxes. Since P intersects at most k obstacles, it follows that the number of variable-boxes that P traverses their right side is at most k c1 n 2m2 = m1 (m m2). Therefore, τ dissatisﬁes at most m1 (m m2) unit clauses, and hence satisﬁes at least m m2 unit clauses. Since τ satisﬁes all m2 binary clauses, τ satisﬁes a total of at least m clauses.

Figure 3: Illustration for the proof of Theorem 3 for F = x1 x2 x3 x4 ( x1 x4) ( x2 x3) ( x3 x1).

Straight-line Segments For an instance I of CONSTRAINT REMOVAL, deﬁne the overlap number of I to be the maximum number of obstacles whose intersection is nonempty. Let LINE-CONSTRAINT REMOVAL be the restriction of CONSTRAINT REMOVAL to instances in which each obstacle is a line segment. Theorem 3. LINE-CONSTRAINT REMOVAL, restricted to instances whose overlap number is at most 2, is NP-hard.

Proof. As in the proof of Theorem 2, we reduce from RMN2Sat. The reduction is very similar to that in Theorem 2, except for the shapes and layout of the obstacles, as we no longer can overlay obstacles since we need to keep the overlap number at most 2. Let (F, m ) be an instance of R-MN2Sat, where F has n variables x1, . . . , xn and m clauses C1, . . . , Cm. We refer to Figure 3 for illustration. We create the same region R as in the proof of Theorem 2, whose boundary is outlined in black in Figure 3. We use line-segments to mimic the rectangles used in the proof of Theorem 2. We describe how this is done for each obstacle-type used in that proof. Let c1, c2 be the constants deﬁned in the proof of Theorem 2. To form the boundary of R in the instance I of LINE-CONSTRAINT REMOVAL, we mimic the heavy obstacles forming the boundary of R with c2 many nested boundaries, each formed using a sequence of distinct line-segment obstacles. We start by overlaying a distinct line-segment obstacle along each edge of the boundary of R. We then create c2-many nested copies of R, each using a distinct set of obstacles, so that the path remains conﬁned within the innermost copy of R, as going out of the nested regions would incur a cost of c2. See Figure 4 for illustration of the nesting around a box Bi. The inner rectangle subdividing a box Bi is created by nesting c1 + 5 many rectangles, each created using 4 distinct line segments forming its sides; any path going directly through this rectangle and avoiding both the left and right passages of Bi, would incur a cost higher than going through either of the two passages, and hence, could be replaced by a path that sets a truth value for xi. To mimic the consistency obstacles, we replace each of the c1 overlayed rectangles used in the formation of the consistency obstacle for xi, with a bundle of c1-many distinct vertical-segment obstacles (of the same length) intersecting only boxes Bi and B i (see Figures 3 and 4). Note that some points in R are the intersection points of an obstacle forming the (nested) boundary of R with an obstacle that is part of a consistency obstacle. Such points have overlap number 2, but no point in R has overlap number larger than 2. We refer to any point in R that has overlap number 2 as an intersection point of R. To mimic the rectangular balancing obstacles in Bi, each balancing obstacle is replaced with a vertical line-segment obstacle, located on the same side of Bi, and blocking the passage of any path going through that side. To ensure that the overlapping number stays at most two, we place each of the balancing line-segment obstacles in such a way that none of its endpoints is an intersection point in R. It is easy to see that this can always be done with the proper placement of these line-segment obstacles.

Finally, to place the incidency obstacles, for each literal xi and clause Cj such that xi is the ﬁrst (resp. second) literal in clause Cj, we create a line-segment obstacle that intersects the right part of box Bi (resp. B i) at non-intersection points in R, and the top (resp. bottom) part of the clause-box corresponding to Cj at non-intersection points in R. For each positive clause {xi}, we place a vertical line-segment obstacle that blocks the right side of Bi such that its endpoints are non-intersection points in R. All these obstacles are placed in such a way that no three line-segment obstacles intersect at the same point. Again, it is not difﬁcult to see that this can be done with a proper layout of the boundary or R, and the placement of these obstacles. The constructed instance I has an overlap number at most 2. We deﬁne k = c1 n + 2m2 + m1 (m m2). Similar arguments to the ones made in the proof of Theorem 2 show that (F, m ) is a yes-instance of R-MN2Sat iff (I, k) is a yes-instance of LINE-CONSTRAINT REMOVAL.

Figure 4: Illustration of the nesting used to conﬁne the path.

Corollary 4. Unless ETH fails, LINE-CONSTRAINT REMOVAL restricted to instances whose overlap number is at most 2 cannot be solved in time 2o(

N), where N is the number of regions in the input instance.

Proof. Consider the NP-hardness reduction in the proof of Theorem 3. This reduction maps an instance of R-MN2SAT to an instance of LINE-CONSTRAINT REMOVAL of overlap number at most 2. It is not difﬁcult to verify that the number of regions in the instance I of LINE-CONSTRAINT REMOVAL produced is quadratic in the number of variables n of the R-MN2Sat formula. It follows that an algorithm for LINE-CONSTRAINT REMOVAL that runs in time 2o(

N) would give an algorithm for R-MN2Sat that runs in time 2o(n), and this would imply that ETH fails.

Corollary 5. Unless ETH fails, CONSTRAINT REMOVAL restricted to instances whose overlap number is at most 2 cannot be solved in time 2o(n), where n is the number of obstacles in the input instance.

Proof. Consider the NP-hardness reduction in the proof of Theorem 3, but instead of using a linear number of linesegment obstacles to form each layer of the boundary of R, form the layer using a single rectilinear obstacle that is the union of all these segments. It is easy to verify that the modiﬁed reduction results in O(n) obstacles, where n is the number of variables in the instance of R-MN2SAT. It follows that

an algorithm for CONSTRAINT REMOVAL restricted to instances whose overlap number is at most 2 that runs in time 2o(n) would give an algorithm for R-MN2Sat that runs in time 2o(n), and this would imply that ETH fails.

Subexponential-time Algorithm For an integer b 2, deﬁne b-OVERLAP MINIMUM CONSTRAINT REMOVAL to be the restriction of MINIMUM CONSTRAINT REMOVAL to instances whose overlap number is at most b. (For b 2, b-OVERLAP MINIMUM CONSTRAINT REMOVAL is NP-hard by Theorem 3.) In this section, we present an algorithm that solves an instance I of b-OVERLAP MINIMUM CONSTRAINT REMOVAL in time 2O(

N), where N is the number of vertices in the auxiliary graph GI. Recall that the number of vertices N in GI is the number of regions determined by the intersections of the n obstacles in I, and hence N = O(n2). Whereas this algorithm does not improve on the brute-force algorithm when the number of regions N is quadratic in the number of obstacles n, it does give a subexponential-time algorithm in terms of n when the number of regions is o(n2), which improves on the brute-force 2O(n)-time algorithm for the problem. By Corollary 4, it is unlikely that b-OVERLAP MINIMUM CON-

STRAINT REMOVAL can be solved in time 2o(

N). The algorithm we present is a divide-and-conquer algorithm, based on a variant of the well-known balanced separator theorem for planar graphs (Lipton and Tarjan 1979). This variant theorem (Miller 1986) states that the vertex-set of a triangulated plane graph on N vertices can be partitioned into three parts A, B, S such that: (1) S is a cycle separating A from B and |S|

8N; (2) |A| 2N/3 and |B| 2N/3; and (3) A is interior to S and B is exterior to S (w.r.t. the plane embedding). The reason why we use this variant theorem, as opposed to the celebrated planar separator theorem (Lipton and Tarjan 1979), is that for the problem under consideration, this variant theorem allows for a more efﬁcient enumeration of the separator, as will be discussed later. Our algorithm follows the approach in Woeginger et al. (Deineko, Klinz, and Woeginger 2006), for computing a Hamiltonian path in a planar graph on N vertices in time 2O(

N). There are complications, however, that are particular to b-OVERLAP MINIMUM CONSTRAINT REMOVAL. We describe below how to deal with these complications. Consider an instance I of b-OVERLAP MINIMUM CONSTRAINT REMOVAL on n obstacles, and let GI be its auxiliary graph. We assign each obstacle in I a distinct representative color and assume that each vertex v in GI is colored by the color-set representing the obstacles forming the region of v. As in (Deineko, Klinz, and Woeginger 2006), we add edges to GI so that the resulting graph is a triangulation, and then apply the cycle separator theorem (Miller 1986) to partition the vertex-set of the resulting graph into A, B, S; the added edges are removed afterwards, and play no role other than determining A, B, S. As in (Deineko, Klinz, and Woeginger 2006), the algorithm maintains a conﬁguration, which is a tuple, and an auxiliary graph stipulating a partial ordering that the current enumeration dictates on the path vertices. We skip these de-

tails since they are very similar to those in (Deineko, Klinz, and Woeginger 2006), and highlight those that are particular to b-OVERLAP MINIMUM CONSTRAINT REMOVAL. After computing A, B, S, we enumerate every subset of S, as the subset of vertices that are contained in the path, P, we seek. For each enumerated subset F, we enumerate every subset of colors C that appear both on vertices in S \ F and on P. We then remove all colors in S from GI, and mark every vertex containing a color that is in S \ F but not in C as forbidden . Afterwards, the color-set appearing on vertices in A is disjoint from that appearing on vertices in B, because the colors that appear in both A and B must appear in S (the vertices on which the same color appears induce a connected subgraph of GI), and those colors have been removed. The number of enumerations so far is at most 2O(

N). Fix such an enumeration. Next, we need to enumerate the order in which P traverses the vertices in F. Enumerating all permutations of the vertices in F will not result in a 2O(

N)-time algorithm. Instead, we adopt a similar enumeration method to the one in Woeginger et al. (Deineko, Klinz, and Woeginger 2006), which is based on the following observation. Suppose for now that the order in which P visits the vertices in F has been revealed. For any two nonadjacent vertices u, v in F V (P), say that u and v are A-consecutive (resp. B-consecutive) on P if the subpath of P between u and v, excluding u and v, is contained in A (resp. in B). Let EA F F (resp. EB F F) be the set of edges between A-consecutive (resp. B-consecutive) vertices (these edges are not in GI). The algorithm makes two recursive calls, one on GI[A S] + EB after modifying the auxiliary structure so that to enforce the order imposed by EA and EB, and the other on GI[B S] + EA after modifying the auxiliary structure so that to enforce the order imposed by EA and EB. The algorithm returns an s-t path that is the concatenation of a path having the minimum number of colors resulting from the recursive call on GI[A S]+EB, with a path having the minimum number of colors resulting from the recursive call on GI[B S] + EA. The recursion stops when the instance size reaches a suitable small number. Now, to enumerate EA and EB efﬁciently without enumerating all permutations of F, we observe the following. Since each edge in EA corresponds to a path in A interior to the cycle S, the edges in EA are embeddable inside S, and hence EA is a subset of edges of the edge-set of a triangulation of S. It is well known that the number of triangulations of S is 2O(|S|) = 2O(

N) (e.g., see (Michaels and Rosen 2007)[Theorem 6, Chapter 7]), and these triangulations can be easily enumerated in time 2O(

N). Since each triangulation contains O(|S|) many edges, the number of subsets of edges in any triangulations is also 2O(

N). Therefore, the total number of subsets of edges of triangulations of S is 2O(|S|) 2O(

N). It follows that the number of subsets EA that need to be enumerated is 2O(

N), and they can be enumerated in time 2O(

N). Similarly, the number of subsets EB that need to be enumerated is 2O(

N), and they can be enumerated in time 2O(

N). After enumerating

EA and EB, we can enumerate the ﬁrst and last vertices in F that P visits. Knowing these vertices and EA and EB is sufﬁcient to know the order in which P traverses F. Clearly, the number of enumerations is still 2O(

N). In conclusion, the number of enumerations needed to divide the instance of size N into two, each of size at most 2N/3 + O(

N). This gives a recurrence relation T(N) = 2O(

N)T(2N/3), where T(N) is the running time of the algorithm (plus an additive polynomial term), whose solution is T(N) = 2O(

Theorem 6. b-OVERLAP MINIMUM CONSTRAINT REMOVAL can be solved in time 2O(

N), and unless ETH fails, it cannot be solved in time 2o(

N), even when the obstacles are line segments.

Proof. The upper bound follows from the algorithm above. The lower bound follows from Corollary 4.

Experimental Evaluation In this section, we experimentally evaluate the performance of Hauser s algorithm (Hauser 2014), several exponential time algorithms and greedy approaches.

Implementations Hauser. Hauser s algorithm explores a state space in which each state is represented as a vertex, v, and the cover of some path P leading from the start, s, to v; the cover is deﬁned as the set of obstacles on P, which if removed, yield an obstacle-free path from s to v. A state corresponding to a vertex v is pruned if its cover is a super-set of the cover of another state corresponding to v. The search ends when no new state can be created. This search is guaranteed to be optimal and Hauser argued that the pruning step eliminates a large number of states making the algorithm more practical. Divide-and-Conquer Algorithm. We implemented the divide-and-conquer algorithm discussed in the previous section combined with some heuristics to speed-up the search. Although the separators we computed were small and nearbalanced, the algorithm itself was computationally infeasible, even for instances with 20 obstacles. Therefore, at this point, this algorithm remains mainly of theoretical interest, and further research on using heuristics to optimize its running time is recommended. Iterative Deepening Search. Iterative deepening search (IDS) is a classic search strategy. In the context of the MINIMUM CONSTRAINT REMOVAL problem, depth-ﬁrst search is performed on the auxiliary graph associated with the input instance, with a limit to how many obstacles are removed. We start this limit at 0, and increase it until a solution is found. IDS is guaranteed to discover an optimal solution, but may be impractical. Selecting which obstacles to remove based on some heuristic is likely to improve the time. In addition to implementing the naive IDS, we implemented two variations of IDS with heuristics: IDS with Minimum Cover Heuristic. At a state in the search corresponding to a vertex v in GI, the search proceeds to the neighbor of v whose cover has minimum car-

dinality until it reaches its limit and then backtracks. The search remains optimal, but in practice is quicker. IDS with Euclidean Distance Heuristic. In this search, the vertices nearest to t are given priority: At a state in the search corresponding to a vertex v in GI, the search proceeds to the neighbor of v whose Euclidean distance to t is minimum until it reaches its limit and then backtracks. Greedy Search. Greedy, or best-ﬁrst, search makes a locally optimal choice as it navigates through the auxiliary graph. Unlike IDS, greedy search explores a single path and does not guarantee an optimal solution. We rely on the same heuristics as in the IDS implementations: Greedy Search with Minimum Cover Heuristic. At a state in the search corresponding to a vertex v in GI, the search proceeds to the neighbor of v whose cover has minimum cardinality. Greedy Search with Euclidean Distance Heuristic. At a state in the search corresponding to a vertex v in GI, the search proceeds to the neighbor of v whose Euclidean distance to t is minimum.

Empirical Results The above algorithms were evaluated on three types of input instances: (1) instances in which the obstacles are polygons; (2) instances in which the obstacles are axes-parallel rectangles; and (3) instances in which the obstacles are line segments. Shapes were generated by selecting random points from a uniform distribution. The results for polygons and rectangles are presented in Figure 5; the results for line segments are similar and omitted for lack of space. For all simulations where n is greater than 50, Hauser s algorithm and IDS quickly become infeasible, requiring several hours to produce a solution. Heuristic-informed IDS, however, remain practical. For instances constructed with 100 random polygons, IDS with the Euclidean distance heuristic (IDS-E) takes on average 31.4 seconds to discover a solution. IDS with the minimum cover heuristic (IDS-MC) requires 28.5 seconds. The greedy algorithms (Greedy-E and Greedy-MC) are much faster (4.4 and 3.2 seconds respectively). The same pattern is observed in simulations with segments and rectangles: Greedy approaches are much more efﬁcient than optimal algorithms with heuristics, which, in turn, are more efﬁcient than naive implementations. To test the limitations of the algorithms, simulations with up to 1000 rectangles were evaluated. The results indicate that simple heuristics can greatly increase the size of instances that optimal and greedy algorithms can tackle. For instance, IDS-E was able to ﬁnd a solution in 684 seconds, while Greedy-E discovered a solution in 277 seconds. While the greedy algorithms with heuristics ran faster than the iterative deepening searches, their solutions are not guaranteed to be optimal. To evaluate the quality of their solutions, we computed the approximation ratio the ratio between the discovered solution and an optimal solution. In all simulations of different shapes and sizes, the approximation ratio was 1 or close to it. This ﬁnding suggests that the solution space for random imputations of the problem is dense and easily navigated by simple heuristics. However, one can construct examples that confound these greedy algorithms,

Figure 5: Average time for the six algorithms on 20 simulations of n random polygons and rectangles.

and from a theoretical perspective, it can be shown that their ratios approach the total number of obstacles.

Conclusions Our study shows that, from the theoretical perspective, MINIMUM CONSTRAINT REMOVAL is a very intractable problem, as it remains computationally hard even when the obstacles have very simple geometric shapes. However, from a practical perspective, the problem seems to be amenable to standard heuristics, and can be solved efﬁciently and accurately for large instances. The major theoretical question left open, and posed in (Erickson and La Valle 2013), is whether MINIMUM CONSTRAINT REMOVAL becomes polynomial-time solvable if we restrict it to instances in which no obstacle intersects more than a constant number of other obstacles. Certainly, this is a natural restriction on the problem that seems to be challenging, and deserves further investigation. From the practical side, it would be interesting to see implementations of the divide-and-conquer algorithm, that lead to an exact algorithm for the problem with a better performance than the exact algorithms implemented in the current work.

Acknowledgments The authors are thankful to the reviewers. Eiben was supported by Pareto-Optimal Parameterized Algorithms (ERC Starting Grant 715744) and by the Austrian Science Fund (FWF, projects P26696 and W1255N23). Gemmell, Kanj, and Yougdahl were supported by De Paul University Academic Initiatives Pool grant #601347.

References Aghighi, M.; B ackstr om, C.; Jonsson, P.; and St ahlberg, S. 2016. Reﬁning complexity analyses in planning by exploiting the Exponential Time Hypothesis. Annals of Mathematics and Artiﬁcial Intelligence 78(2):157 175. Alt, H.; Cabello, S.; Giannopoulos, P.; and Knauer, C. 2011. On some connection problems in straight-line segment arrangements. In Proceedings of Euro CG, 27 30. Chan, D., and Kirkpatrick, D. 2014. Multi-path algorithms for minimum-colour path problems with applications to approximating barrier resilience. Theoretical Computer Science 553:74 90. de Haan, R.; Kanj, I.; and Szeider, S. 2015. On the subexponential-time complexity of CSP. Journal of Artiﬁcial Intelligence Research 52:203 234. Deineko, V.; Klinz, B.; and Woeginger, G. 2006. Exact algorithms for the Hamiltonian cycle problem in planar graphs. Operations Research Letters 34(3):269 274. Erickson, L., and La Valle, S. 2013. A simple, but NP-hard, motion planning problem. In Proceedings of AAAI. AAAI Press. Hauser, K. 2014. The minimum constraint removal problem with three robotics applications. International Journal of Robotics Research 33(1):5 17. Johnson, D., and Szegedy, M. 1999. What are the least tractable instances of Max independent set? In Proceedings of SODA, 927 928. ACM/SIAM. Kumar, S.; Lai, T.; and Arora, A. 2005. Barrier coverage with wireless sensors. In Proceedings of MOBICOM, 284 298. ACM. Lipton, R., and Tarjan, R. 1979. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics 36(2):177 189. Lokshtanov, D.; Marx, D.; and Saurabh, S. 2011. Lower bounds based on the exponential time hypothesis. Bulletin of the EATCS 105:41 72. Michaels, J., and Rosen, K. 2007. Applications of Discrete Mathematics. New York: Mc Graw Hill. Miller, G. 1986. Finding small simple cycle separators for 2-connected planar graphs. Journal of Computer and System Sciences 32(3):265 279. Tseng, K., and Kirkpatrick, D. 2012. On barrier resilience of sensor networks. In Proceedings of ALGOSENSORS, 130 144. Yang, S. 2012. Some Path Planning Algorithms in Computational Geometry and Air Trafﬁc Management. Ph.D. Dissertation, University of New York at Stony Brook.