skip to main content


Title: Hardness of Motion Planning with Obstacle Uncertainty in Two Dimensions

We consider the problem of motion planning in the presence of uncertain obstacles, modeled as polytopes with Gaussian-distributed faces (PGDFs). A number of practical algorithms exist for motion planning in the presence of known obstacles by constructing a graph in configuration space, then efficiently searching the graph to find a collision-free path. We show that such an exact algorithm is unlikely to be practical in the domain with uncertain obstacles. In particular, we show that safe 2D motion planning among PGDF obstacles is [Formula: see text]-hard with respect to the number of obstacles, and remains [Formula: see text]-hard after being restricted to a graph. Our reduction is based on a path encoding of MAXQHORNSAT and uses the risk of collision with an obstacle to encode variable assignments and literal satisfactions. This implies that, unlike in the known case, planning under uncertainty is hard, even when given a graph containing the solution. We further show by reduction from [Formula: see text]-SAT that both safe 3D motion planning among PGDF obstacles and the related minimum constraint removal problem remain [Formula: see text]-hard even when restricted to cases where each obstacle overlaps with at most a constant number of other obstacles.

 
more » « less
Award ID(s):
1763311
PAR ID:
10546944
Author(s) / Creator(s):
 ;  
Publisher / Repository:
SAGE Publications
Date Published:
Journal Name:
The International Journal of Robotics Research
Volume:
40
Issue:
10-11
ISSN:
0278-3649
Format(s):
Medium: X Size: p. 1151-1166
Size(s):
p. 1151-1166
Sponsoring Org:
National Science Foundation
More Like this
  1. null (Ed.)
    Abstract A novel, exact algorithm is presented to solve the path planning problem that involves finding the shortest collision-free path from a start to a goal point in a two-dimensional environment containing convex and non-convex obstacles. The proposed algorithm, which is called the shortest possible path (SPP) algorithm, constructs a network of lines connecting the vertices of the obstacles and the locations of the start and goal points which is smaller than the network generated by the visibility graph. Then it finds the shortest path from start to goal point within this network. The SPP algorithm generates a safe, smooth and obstacle-free path that has a desired distance from each obstacle. This algorithm is designed for environments that are populated sparsely with convex and nonconvex polygonal obstacles. It has the capability of eliminating some of the polygons that do not play any role in constructing the optimal path. It is proven that the SPP algorithm can find the optimal path in O(nn r2 ) time, where n is the number of vertices of all polygons and n ̓ is the number of vertices that are considered in constructing the path network (n ̓ ≤ n). The performance of the algorithm is evaluated relative to three major classes of algorithms: heuristic, probabilistic, and classic. Different benchmark scenarios are used to evaluate the performance of the algorithm relative to the first two classes of algorithms: GAMOPP (genetic algorithm for multi-objective path planning), a representative heuristic algorithm, as well as RRT (rapidly-exploring random tree) and PRM (probabilistic road map), two well-known probabilistic algorithms. Time complexity is known for classic algorithms, so the presented algorithm is compared analytically. 
    more » « less
  2. We investigate the problem of recovering jointly [Formula: see text]-rank and [Formula: see text]-bisparse matrices from as few linear measurements as possible, considering arbitrary measurements as well as rank-one measurements. In both cases, we show that [Formula: see text] measurements make the recovery possible in theory, meaning via a nonpractical algorithm. In case of arbitrary measurements, we investigate the possibility of achieving practical recovery via an iterative-hard-thresholding algorithm when [Formula: see text] for some exponent [Formula: see text]. We show that this is feasible for [Formula: see text], and that the proposed analysis cannot cover the case [Formula: see text]. The precise value of the optimal exponent [Formula: see text] is the object of a question, raised but unresolved in this paper, about head projections for the jointly low-rank and bisparse structure. Some related questions are partially answered in passing. For rank-one measurements, we suggest on arcane grounds an iterative-hard-thresholding algorithm modified to exploit the nonstandard restricted isometry property obeyed by this type of measurements. 
    more » « less
  3. null (Ed.)
    Given two points s and t in the plane and a set of obstacles defined by closed curves, what is the minimum number of obstacles touched by a path connecting s and t? This is a fundamental and well-studied problem arising naturally in computational geometry, graph theory (under the names Min-Color Path and Minimum Label Path), wireless sensor networks (Barrier Resilience) and motion planning (Minimum Constraint Removal). It remains NP-hard even for very simple-shaped obstacles such as unit-length line segments. In this paper we give the first constant factor approximation algorithm for this problem, resolving an open problem of [Chan and Kirkpatrick, TCS, 2014] and [Bandyapadhyay et al., CGTA, 2020]. We also obtain a constant factor approximation for the Minimum Color Prize Collecting Steiner Forest where the goal is to connect multiple request pairs (s1, t1), . . . , (sk, tk) while minimizing the number of obstacles touched by any (si, ti) path plus a fixed cost of wi for each pair (si, ti) left disconnected. This generalizes the classic Steiner Forest and Prize-Collecting Steiner Forest problems on planar graphs, for which intricate PTASes are known. In contrast, no PTAS is possible for Min-Color Path even on planar graphs since the problem is known to be APX- hard [Eiben and Kanj, TALG, 2020]. Additionally, we show that generalizations of the problem to disconnected obstacles in the plane or connected obstacles in higher dimensions are strongly inapproximable assuming some well-known hardness conjectures. 
    more » « less
  4. Rectilinear forms of snake-like robotic locomotion are anticipated to be an advantage in obstacle-strewn scenarios characterizing urban disaster zones, subterranean collapses, and other natural environments. The elongated, laterally narrow footprint associated with these motion strategies is well suited to traversal of confined spaces and narrow pathways. Navigation and path planning in the absence of global sensing, however, remains a pivotal challenge to be addressed prior to practical deployment of these robotic mechanisms. Several challenges related to visual processing and localization need to be resolved to to enable navigation. As a first pass in this direction, we equip a wireless, monocular color camera to the head of a robotic snake. Visiual odometry and mapping from ORB-SLAM permits self-localization in planar, obstacle strewn environments. Ground plane traversability segmentation in conjunction with perception-space collision detection permits path planning for navigation. A previously presented dynamical reduction of rectilinear snake locomotion to a non-holonomic kinematic vehicle informs both SLAM and planning. The simplified motion model is then applied to track planned trajectories through an obstacle configuration. This navigational framework enables a snake-like robotic platform to autonomously navigate and traverse unknown scenarios with only monocular vision. 
    more » « less
  5. This article considers the problem of finding a shortest tour to visit viewing sets of points on a plane. Each viewing set is represented as an inverted view cone with apex angle [Formula: see text] and height [Formula: see text]. The apex of each cone is restricted to lie on the ground plane. Its orientation angle (tilt) [Formula: see text] is the angle difference between the cone bisector and the ground plane normal. This is a novel variant of the 3D Traveling Salesman Problem with Neighborhoods (TSPN) called Cone-TSPN. One application of Cone-TSPN is to compute a trajectory to observe a given set of locations with a camera: for each location, we can generate a set of cones whose apex and orientation angles [Formula: see text] and [Formula: see text] correspond to the camera’s field of view and tilt. The height of each cone [Formula: see text] corresponds to the desired resolution. Recently, Plonski and Isler presented an approximation algorithm for Cone-TSPN for the case where all cones have a uniform orientation angle of [Formula: see text]. We study a new variant of Cone-TSPN where we relax this constraint and allow the cones to have non-uniform orientations. We call this problem Tilted Cone-TSPN and present a polynomial-time approximation algorithm with ratio [Formula: see text], where [Formula: see text] is the set of all cone heights. We demonstrate through simulations that our algorithm can be implemented in a practical way and that by exploiting the structure of the cones we can achieve shorter tours. Finally, we present experimental results from various agriculture applications that show the benefit of considering view angles for path planning.

     
    more » « less