A state-of-the-art review on topology and differential geometry-based robotic path planning—part I: Planning under static constraints

Abstract

Autonomous robotics has permeated several industrial, research and consumer robotic applications, of which path planning is an important component. The path planning algorithm of choice is influenced by the application at hand and the history of algorithms used for such applications. The latter is dependent on an extensive conglomeration and classification of path planning literature, which is what this work focuses on. Specifically, we accomplish the following: typical classifications of path planning algorithms are provided. Such classifications rely on differences in knowledge of the environment (known/unknown), robot (model-specific/generic), and constraints (static/dynamic). This classification however, is not comprehensive. Thus, as a resolution, we propose a detailed taxonomy based on a fundamental parameter of the space, i.e. its ability to be characterized as a set of disjoint or connected points. We show that this taxonomy encompasses important attributes of path planning problems, such as connectivity and partitioning of spaces. Consequently, path planning spaces in robotics may be viewed as simply a set of points, or as manifolds. The former can further be divided into unpartitioned and partitioned spaces, of which the former uses variants of sampling algorithms, optimization algorithms, model predictive controls, and evolutionary algorithms, while the latter uses cell decomposition and graph traversal, and sampling-based optimization techniques.This article achieves the following two goals: The first is the introduction of an all-encompassing taxonomy of robotic path planning. The second is to streamline the migration of path planning work from disciplines such as mathematics and computer vision to robotics, into one comprehensive survey. Thus, the main contribution of this work is the review of works for static constraints that fall under the proposed taxonomy, i.e., specifically under topology and manifold-based methods. Additionally, further taxonomy is introduced for manifold-based path planning, based on incremental construction or one-step explicit parametrization of the space.