Tag Archives: Path Planning

A unifying framework for path planning in real-time (mainly for UAVs) and a nice summary of the state-of-the-art in modern path planning

M. Murillo, G. SánchezL. GenzelisL. Giovanini, A Real-Time Path-Planning Algorithm based on Receding Horizon Techniques, Journal of Intelligent & Robotic Systems, September 2018, Volume 91, Issue 3–4, pp 445–457, DOI: 10.1007/s10846-017-0740-1.

In this article we present a real-time path-planning algorithm that can be used to generate optimal and feasible paths for any kind of unmanned vehicle (UV). The proposed algorithm is based on the use of a simplified particle vehicle (PV) model, which includes the basic dynamics and constraints of the UV, and an iterated non-linear model predictive control (NMPC) technique that computes the optimal velocity vector (magnitude and orientation angles) that allows the PV to move toward desired targets. The computed paths are guaranteed to be feasible for any UV because: i) the PV is configured with similar characteristics (dynamics and physical constraints) as the UV, and ii) the feasibility of the optimization problem is guaranteed by the use of the iterated NMPC algorithm. As demonstration of the capabilities of the proposed path-planning algorithm, we explore several simulation examples in different scenarios. We consider the existence of static and dynamic obstacles and a follower condition.

A new variant of A* that is more computationally efficient

Adam Niewola, Leszek Podsedkowski, L* Algorithm—A Linear Computational Complexity Graph Searching Algorithm for Path Planning, Journal of Intelligent & Robotic Systems, September 2018, Volume 91, Issue 3–4, pp 425–444, DOI: 10.1007/s10846-017-0748-6.

The state-of-the-art graph searching algorithm applied to the optimal global path planning problem for mobile robots is the A* algorithm with the heap structured open list. In this paper, we present a novel algorithm, called the L* algorithm, which can be applied to global path planning and is faster than the A* algorithm. The structure of the open list with the use of bidirectional sublists (buckets) ensures the linear computational complexity of the L* algorithm because the nodes in the current bucket can be processed in any sequence and it is not necessary to sort the bucket. Our approach can maintain the optimality and linear computational complexity with the use of the cost expressed by floating-point numbers. The paper presents the requirements of the L* algorithm use and the proof of the admissibility of this algorithm. The experiments confirmed that the L* algorithm is faster than the A* algorithm in various path planning scenarios. We also introduced a method of estimating the execution time of the A* and the L* algorithm. The method was compared with the experimental results.

A new spatial transformation for planning mobile robot trajectories that guarantees a solution and also time requirement satisfaction

S. G. Loizou, The Navigation Transformation, IEEE Transactions on Robotics, vol. 33, no. 6, pp. 1516-1523, DOI: 10.1109/TRO.2017.2725323.

This work introduces a novel approach to the solution of the navigation problem by mapping an obstacle-cluttered environment to a trivial domain called the point world, where the navigation task is reduced to connecting the images of the initial and destination configurations by a straight line. Due to this effect, the underlying transformation is termed the “navigation transformation.” The properties of the navigation transformation are studied in this work as well as its capability to provide-through the proposed feedback controller designs-solutions to the motion- and path-planning problems. Notably, the proposed approach enables the construction of temporal stabilization controllers as detailed herein, which provide a time abstraction to the navigation problem. The proposed solutions are correct by construction and, given a diffeomorphism from the workspace to a sphere world, tuning free. A candidate construction for the navigation transformation on sphere worlds is proposed. The provided theoretical results are backed by analytical proofs. The efficiency, robustness, and applicability of the proposed solutions are supported by a series of experimental case studies.

State of the art of symbolic planning, particularly the one that optimizes some cost, and a novel approach

Álvaro Torralba, Vidal Alcázar, Peter Kissmann, Stefan Edelkamp, Efficient symbolic search for cost-optimal planning, Artificial Intelligence, Volume 242, January 2017, Pages 52-79, ISSN 0004-3702, DOI: 10.1016/j.artint.2016.10.001.

In cost-optimal planning we aim to find a sequence of operators that achieve a set of goals with minimum cost. Symbolic search with Binary Decision Diagrams (BDDs) performs efficient state space exploration in terms of time and memory. This is crucial in optimal settings, in which large parts of the state space must be explored in order to prove optimality. However, the development of accurate heuristics for explicit-state search in recent years have left symbolic search techniques in a secondary place. In this article we propose two orthogonal improvements for symbolic search planning. On the one hand, we analyze and compare different methods for image computation in order to efficiently perform the successor generation on symbolic search. Image computation is the main bottleneck of symbolic search algorithms so an efficient computation is paramount for efficient symbolic search planning. On the other hand, we study how to use state-invariant constraints to prune states in symbolic search. This is essential in regression search but it is yet to be exploited in symbolic search planners. Experiments with symbolic bidirectional uniform-cost search and symbolic A ⁎ search with PDBs show remarkable performance improvements on most IPC benchmark domains. Overall, with the help of our improvements, symbolic bidirectional search outperforms explicit-state search with state-of-the-art heuristics such as LM-cut across many different domains.

Survey and taxonomy of path planning algorithms

Thi Thoa Mac, Cosmin Copot, Duc Trung Tran, Robin De Keyser, Heuristic approaches in robot path planning: A survey, Robotics and Autonomous Systems, Volume 86, 2016, Pages 13-28, ISSN 0921-8890, DOI: 10.1016/j.robot.2016.08.001.

Autonomous navigation of a robot is a promising research domain due to its extensive applications. The navigation consists of four essential requirements known as perception, localization, cognition and path planning, and motion control in which path planning is the most important and interesting part. The proposed path planning techniques are classified into two main categories: classical methods and heuristic methods. The classical methods consist of cell decomposition, potential field method, subgoal network and road map. The approaches are simple; however, they commonly consume expensive computation and may possibly fail when the robot confronts with uncertainty. This survey concentrates on heuristic-based algorithms in robot path planning which are comprised of neural network, fuzzy logic, nature-inspired algorithms and hybrid algorithms. In addition, potential field method is also considered due to the good results. The strengths and drawbacks of each algorithm are discussed and future outline is provided.