We study the problem of finding shortest paths in the plane among h convex obstacles, where the path is allowed to pass through (violate) up to k obstacles, for 𝑘≤ℎ. Equivalently, the problem is to find shortest paths that become obstaclefree if k obstacles are removed from the input. Given a fixed source point s, we show how to construct a map, called a shortest kpath map, so that all destinations in the same region of the map have the same combinatorial shortest path passing through at most k obstacles. We prove a tight bound of 𝛩(𝑘𝑛) on the size of this map, and show that it can be computed in 𝑂(𝑘2𝑛log𝑛) time, where n is the total number of obstacle vertices.
more »
« less
An Exact Geometry–Based Algorithm for Path Planning
Abstract A novel, exact algorithm is presented to solve the path planning problem that involves finding the shortest collisionfree path from a start to a goal point in a twodimensional environment containing convex and nonconvex 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 obstaclefree 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 multiobjective path planning), a representative heuristic algorithm, as well as RRT (rapidlyexploring random tree) and PRM (probabilistic road map), two wellknown probabilistic algorithms. Time complexity is known for classic algorithms, so the presented algorithm is compared analytically.
more »
« less
 Award ID(s):
 1739333
 NSFPAR ID:
 10301491
 Date Published:
 Journal Name:
 International Journal of Applied Mathematics and Computer Science
 Volume:
 28
 Issue:
 3
 ISSN:
 20838492
 Page Range / eLocation ID:
 493 to 504
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacleavoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. Previously, Hershberger and Suri (in SIAM Journal on Computing , 1999) gave an algorithm of O(n log n ) time and O(n log n ) space, where n is the total number of vertices of all obstacles. Recently, by modifying Hershberger and Suri’s algorithm, Wang (in SODA’21) reduced the space to O(n) while the runtime of the algorithm is still O(n log n ). In this article, we present a new algorithm of O(n+h log h ) time and O(n) space, provided that a triangulation of the free space is given, where h is the number of obstacles. The algorithm is better than the previous work when h is relatively small. Our algorithm builds a shortest path map for a source point s so that given any query point t , the shortest path length from s to t can be computed in O (log n ) time and a shortest s  t path can be produced in additional time linear in the number of edges of the path.more » « less

We consider the problem of motion planning in the presence of uncertain obstacles, modeled as polytopes with Gaussiandistributed 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 collisionfree 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

null (Ed.)The main objective of an unmanned aerial vehicle (UAV) path planning is to generate a flight path that links a start point to an endpoint in an indoor space avoiding obstacles. Path planning is essential for many reallife applications such as an autonomous car, surveillance mission, farming robots, unmanned aerial vehicles package delivery, space exploration, and many others. To create an optimal path, we need to adopt a specific criterion to minimize the distance the UAV must travel such as the Euclidean distance. In this paper, we provide our initial idea of creating an optimal path for indoor UAV using both A* and the Late Acceptance Hill Climbing (LAHC) algorithms. We are adopting an indoor search environment with various complexity and utilize the Probabilistic Roadmap algorithm (PRM) as a search space for both algorithms. The basic idea following PRM is to generate random sample points in the space and search these points for an optimal path. The developed results show that the LAHC algorithm outperforms the A* algorithm.more » « less

null (Ed.)Robot motion planning is one of the important elements in robotics. In environments full of obstacles, it is always challenging to find a collisionfree and dynamically feasible path between the robot's initial configuration and goal configuration. While many motion planning algorithms have been proposed in the past, each of them has its pros and cons. This work presents a benchmark which implements and compares existing planning algorithms on a variety of problems with extensive simulation. Based on that, we also propose a hybrid planning algorithm, RRT*CFS, that combines the merits of samplingbased planning methods and optimizationbased planning methods. The first layer, RRT*, quickly samples a semioptimal path. The second layer, CFS, performs sequential convex optimization given the reference path from RRT*. The proposed RRT*CFS has feasibility and convergence guarantees. Simulation results show that RRT*CFS benefits from the hybrid structure and performs robustly in various scenarios including the narrow passage problems.more » « less