L 1 shortest paths among polygonal obstacles in the plane

We present an algorithm for computingL ₁ shortest paths among polygonal obstacles in the plane. Our algorithm employs the “continuous Dijkstra” technique of propagating a “wavefront” and runs in timeO(E logn) and spaceO(E), wheren is the number of vertices of the obstacles andE is the number of “events.” By using bounds on the density of certain sparse binary matrices, we show thatE =O(n logn), implying that our algorithm is nearly optimal. We conjecture thatE =O(n), which would imply our algorithm to be optimal. Previous bounds for our problem were quadratic in time and space. Our algorithm generalizes to the case of fixed orientation metrics, yielding anO(n?^?1/2 log² n) time andO(n?^?1/2) space approximation algorithm for finding Euclidean shortest paths among obstacles. The algorithm further generalizes to the case of many sources, allowing us to compute anL ₁ Voronoi diagram for source points that lie among a collection of polygonal obstacles.     

Time-minimal paths amidst moving obstacles in three dimensions

A path-planning problem is considered in the presence of moving polygonal obstacles in three dimensions. A particle is to be moved from a given initial position to a destination position amidst polygonal disjoint barriers moving along known linear trajectories. The particle can move in any direction in space with a single constraint that it cannot move faster than a given speed bound. All obstacles are slowly moving, i.e., their speeds are strictly slower than the maximum speed of the particle. The destination point is also permitted to move along a known trajectory and is assumed to be collision-free at all times. Three properties are stated and proved for a time-minimal path amidst moving polygonal barriers. A few extensions are considered, including piecewise linear motions of the obstacles.     

L1 shortest paths among polygonal obstacles in the plane

We present an algorithm for computingL ₁ shortest paths among polygonal obstacles in the plane. Our algorithm employs the continuous Dijkstra technique of propagating a wavefront and runs in timeO(E logn) and spaceO(E), wheren is the number of vertices of the obstacles andE is the number of events. By using bounds on the density of certain sparse binary matrices, we show thatE =O(n logn), implying that our algorithm is nearly optimal. We conjecture thatE =O(n), which would imply our algorithm to be optimal. Previous bounds for our problem were quadratic in time and space.Our algorithm generalizes to the case of fixed orientation metrics, yielding anO(n^–1/2 log² n) time andO(n^–1/2) space approximation algorithm for finding Euclidean shortest paths among obstacles. The algorithm further generalizes to the case of many sources, allowing us to compute anL ₁ Voronoi diagram for source points that lie among a collection of polygonal obstacles.Partially supported by a grant from Hughes Research Laboratories, Malibu, California and by NSF Grant ECSE-8857642. Much of this work was done while the author was a Ph.D. student at Stanford University, under the support of a Howard Hughes Doctoral Fellowship, and an employee of Hughes Research Laboratories.     

Minimum-link paths among obstacles in the plane

Given a set of nonintersecting polygonal obstacles in the plane, thelink distance between two pointss andt is the minimum number of edges required to form a polygonal path connectings tot that avoids all obstacles. We present an algorithm that computes the link distance (and a corresponding minimum-link path) between two points in timeO(Eα(n) log² n) (and spaceO(E)), wheren is the total number of edges of the obstacles,E is the size of the visibility graph, and α(n) denotes the extremely slowly growing inverse of Ackermann's function. We show how to extend our method to allow computation of a tree (rooted ats) of minimum-link paths froms to all obstacle vertices. This leads to a method of solving the query version of our problem (for query pointst).     

Minimum-link paths among obstacles in the plane

Given a set of nonintersecting polygonal obstacles in the plane, thelink distance between two pointss andt is the minimum number of edges required to form a polygonal path connectings tot that avoids all obstacles. We present an algorithm that computes the link distance (and a corresponding minimum-link path) between two points in timeO(E(n) log² n) (and spaceO(E)), wheren is the total number of edges of the obstacles,E is the size of the visibility graph, and (n) denotes the extremely slowly growing inverse of Ackermann's function. We show how to extend our method to allow computation of a tree (rooted ats) of minimum-link paths froms to all obstacle vertices. This leads to a method of solving the query version of our problem (for query pointst).Joseph Mitchell was partially supported by NSF Grants IRI-8710858 and ECSE-8857642, and by a grant from Hughes Research Laboratories. This work was begun while Günter Rote and Gerhard Woeginger were at the Freie Universität Berlin, Fachbereich Mathematik, Institut für Informatik, and it was partially supported by the ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM). Gerhard Woeginger acknowledges the support by the Fonds zur Förderung der Wissenschaftlichen Forschung, Projekt S32/01.     

The complexity of the free space for motion planning amidst fat obstacles

The complexity of motion planning algorithms highly depends on the complexity of the robot's free space, i.e., the set of all collision-free placements of the robot. Theoretically, the complexity of the free space can be very high, resulting in bad worst-case time bounds for motion planning algorithms. In practice, the complexity of the free space tends to be much smaller than the worst-case complexity. Motion planning algorithms with a running time that is determined by the complexity of the free space therefore become feasible in practical situations. We show that, under some realistic assumptions, the complexity of the free space of a robot with any fixed number of degrees of freedom moving around in ad-dimensional Euclidean workspace with fat obstacles is linear in the number of obstacles. The complexity results lead to highly efficient algorithms for motion planning amidst fat obstacles.Research is supported by the Dutch Organization for Scientific Research (NWO) and partially supported by the ESPRIT III BRA Project 6546 (PROMotion).     

A new algorithm for shortest paths among obstacles in the plane

We introduce a new algorithm for computing Euclidean shortest paths in the plane in the presence of polygonal obstacles. In particular, for a given start points, we build a planar subdivision (ashortest path map) that supports efficient queries for shortest paths froms to any destination pointt. The worst-case time complexity of our algorithm isO(kn log² n), wheren is the number of vertices describing the polygonal obstacles, andk is a parameter we call the illumination depth of the obstacle space. Our algorithm usesO(n) space, avoiding the possibly quadratic space complexity of methods that rely on visibility graphs. The quantityk is frequently significantly smaller thann, especially in some of the cases in which the visibility graph has quadratic size. In particular,k is bounded above by the number of different obstacles that touch any shortest path froms.Partially supported by NSF Grants IRI-8710858 and ECSE-8857642 and by a grant from Hughes Research Laboratories, Malibu, CA.     

Dynamic path planning for a planar articulated robot arm moving amidst unknown obstacles

This work is concerned with planning collision-free paths for a robot arm moving in an environment filled with unknown obstacles, where any point of the robot body is subject to collision. To compensate for the uncertainty, the system is provided with sensory feedback information about its immediate surroundings. In such a setting, which presents significant practical and theoretical interest, human intuition is of little help, and designing algorithms with proven convergence thus becomes an important task. We show that, given the target position, local feedback information is sufficient to guarantee reaching a global objective (the target position) and present a nonheuristic algorithm which generates reasonable—if, in general, not optimal—collision-free paths. In this approach, the path is being planned continuously (dynamically), based on the arm's current position and on the sensory feedback. Here, a case of a planar arm with two revolute joints is studied. No constraints on the shape of the robot links or the obstacles are imposed. The general idea is to reduce the problem of motion planning to an analysis of simple closed curves on the surface of an appropriate two-dimensional manifold.     

Shortest polygonal paths in space

A classical problem of geometry is the following: given a convex polygon in the plane, find an inscribed polygon of shortest circumference. In this paper we generalize this problem to arbitrary polygonal paths in space and consider two cases: in the “open” case the wanted path of shortest length can have different start and end point, whereas in the “closed” case these two points must coincide. We show that finding such shortest paths can be reduced to finding a shortest path in a planar “channel”. The latter problem can be solved by an algorithm of linear-time complexity in the open as well in the closed case. Finally, we deal with constrained problems where the wanted path has to fulfill additional properties; in particular, if it has to pass straight through a further point, we show that the length of such a constrained polygonal path is a strictly convex function of some angle α, and we derive an algorithm for determining such constrained polygonal paths efficiently.     

Nonholonomic distance to polygonal obstacles for a car-like robot of polygonal shape

This paper shows how to compute the nonholonomic distance between a polygonal car-like robot and polygonal obstacles. The solution extends previous work of Reeds and Shepp by finding the shortest path to a manifold (rather than to a point) in configuration space. Based on optimal control theory, the proposed approach yields an analytic solution to the problem.     

An augmented Voronoi roadmap for 3D translational motion planning for a convex polyhedron moving amidst convex polyhedral obstacles

This paper concerns the development of a piecewise linear Voronoi roadmap for translating a convex polyhedron in a three-dimensional (3-D) polyhedral world. In general the Voronoi roadmap is incomplete for motion planning, i.e., it can have several disjoint components in one connected component of free space. An analysis of the roadmap shows that incompleteness is caused by the occurrence of the following simple geometric structure: a polygon in the Voronoi surface containing one or more polygons inside it. We formally bring out the details of this geometric structure and give an efficient augmentation of the roadmap that makes it complete. We show that the roadmap has size e = O(n²Q²l²), where n is the total number of faces on the obstacles, Q is the total number of obstacles and l is the number of faces on the moving object. We also present an algorithm to construct the roadmap in O((n + Ql)e + Q²log Q) time.     

On robotic optimal path planning in polygonal regions with pseudo-Euclidean metrics.

This paper presents several results on some cost-minimizing path problems in polygonal regions. For these types of problems, an approach often used to compute approximate optimal paths is to apply a discrete search algorithm to a graph G(epsilon) constructed from a discretization of the problem; this graph is guaranteed to contain an epsilon-good approximate optimal path, i.e., a path with a cost within (1 + epsilon) factor of that of an optimal path, between given source and destination points. Here, epsilon > 0 is the user-defined error tolerance ratio. We introduce a class of piecewise pseudo-Euclidean optimal path problems that includes several non-Euclidean optimal path problems previously studied and show that the BUSHWHACK algorithm, which was formerly designed for the weighted region optimal path problem, can be generalized to solve any optimal path problem of this class. We also introduce an empirical method called the adaptive discretization method that improves the performance of the approximation algorithms by placing discretization points densely only in areas that may contain optimal paths. It proceeds in multiple iterations, and in each iteration, it varies the approximation parameters and fine tunes the discretization.     

Shortest noncrossing paths in plane graphs

Let G be an undirected plane graph with nonnegative edge length, and letk terminal pairs lie on two specified face boundaries. This paper presents an algorithm for findingk noncrossing paths inG, each connecting a terminal pair, and whose total length is minimum. Noncrossing paths may share common vertices or edges but do not cross each other in the plane. The algorithm runs in timeO(n logn) wheren is the number of vertices inG andk is an arbitrary integer.     

Motion planning in the presence of movable obstacles

Most motion planning algorithms have dealt with motion in a static workspace, or more recently, with motion in a workspace that changes in a known manner. We consider the problem of finding collision-free motions in a changeable workspace. That is, we wish to find a motion for an object where the object is permitted to move some of the obstacles. In such a workspace, the final positions of the movable obstacles may or may not be part of the goal. In the case where the final positions of the obstacles are specified, the general problem is shown to be PSPACE-hard. In the case where the final positions of the obstacles are unspecified, the motion planning problem is shown to be NP-hard. Algorithms that run inO(n ³) time are presented for the case where there is only one movable obstacle in a polygonal environment withn corners and the object to be moved and the obstacle are convex polygons of constant complexity.     

Shortest paths of bounded curvature in the plane

Given two oriented points in the plane, we determine and compute the shortest paths of bounded curvature joining them. This problem has been solved recently by Dubins in the no-cusp case, and by Reeds and Shepp otherwise. We propose a new solution based on the minimum principle of Pontryagin. Our approach simplifies the proofs and makes clear the global or local nature of the results.     

Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape

The problem of path planning for an automaton moving in a two-dimensional scene filled with unknown obstacles is considered. The automaton is presented as a point; obstacles can be of an arbitrary shape, with continuous boundaries and of finite size; no restriction on the size of the scene is imposed. The information available to the automaton is limited to its own current coordinates and those of the target position. Also, when the automaton hits an obstacle, this fact is detected by the automaton's tactile sensor. This information is shown to be sufficient for reaching the target or concluding in finite time that the target cannot be reached. A worst-case lower bound on the length of paths generated by any algorithm operating within the framework of the accepted model is developed; the bound is expressed in terms of the perimeters of the obstacles met by the automaton in the scene. Algorithms that guarantee reaching the target (if the target is reachable), and tests for target reachability are presented. The efficiency of the algorithms is studied, and worst-case upper bounds on the length of generated paths are produced.Supported in part by the National Science Foundation Grant DMC-8519542.     

Finding rectilinear least cost paths in the presence of convex polygonal congested regions

This paper considers the problem of finding the least cost rectilinear distance path in the presence of convex polygonal congested regions. We demonstrate that there are a finite, though exponential number of potential staircase least cost paths between a specified pair of origin–destination points. An upper bound for the number of entry/exit points of a rectilinear path between two points specified a priori in the presence of a congested region is obtained. Based on this key finding, a “memory-based probing algorithm” is proposed for the problem and computational experience for various problem instances is reported. A special case where polynomial time solutions can be obtained has also been outlined.