Sampling-Based Robot Motion Planning

In recent years, robots play an active role in everyday life: medical robots assist in complex surgeries; search-and-rescue robots are employed in mining accidents; and low-cost commercial robots clean houses. There is a growing need for sophisticated algorithmic tools enabling stronger capabilities for these robots. One fundamental problem that robotic researchers grapple with is motion planning—which deals with planning a collision-free path for a moving system in an environment cluttered with obstacles.^13,29

To a layman, it may seem the wide use of robots in modern life implies that the motion-planning problem has already been solved. This is far from true. There is little to no autonomy in surgical robots and every owner of a house-cleaning robot has experienced the highly simplistic (and often puzzling) routes taken by the robot.

Roughly speaking, the complexity^a of a motion-planning problem is primarily governed by two factors: The dimension of the configuration space (C-space)—a space defined by the parameters needed to describe the robot’s position and orientation, and the tightness of the environment—informally, an environment is said to be tight if the robot is required to move with little or no clearance^b from the obstacles.

State-of-the-art motion-planning algorithms can efficiently construct paths for low-complexity problems (that is, either problems whose C-space is low-dimensional or problems that do not contain narrow passages). However, as the complexity increases, their running time may grow in an exponential fashion (exponential in the dimension of the C-space or in the clearance of the path that the robot needs to move along^13,25).

Moreover, algorithms that produce high-quality paths^c with optimality guarantees²¹ require additional overhead both in terms of running time and memory consumption when compared to the basic version of these algorithms.

In this article, I provide insight on why planning (high-quality) paths for complex robotic systems is computationally challenging. Specifically, after providing algorithmic background, we examine general computational challenges that arise in motion planning. This is done by examining sampling-based methods, a common approach to address the motion-planning problem, and considering the different algorithmic building blocks that are used to design such planners and their unique computational challenges. This article focuses on the simple problem of rigid-body planning, but highlights challenges and approaches that occur when extending such algorithms to more complex settings.

There have been several earlier overviews of the robot motion-planning problem (for example, LaValle²⁶). However, these were written before the seminal work of Karaman and Frazzoli on asymptotically optimal motion planning.²¹ While there are some overlaps between this article and the aforementioned papers, there is a large focus on the implications of asymptotical-optimal motion planning to fundamental computational questions. In this article, I highlight new problems (such as those introduced by human-robot interaction) as well as reach out to other communities (such as the machine learning community and the computer-hardware community) for potential ways to revolutionize the field.

Back to Top

Algorithmic Background

Problem statement. In its basic form, the motion-planning problem is to find a collision-free path for a robot or a moving object R in a workspace W cluttered with static obstacles. The spatial pose of R, or the configuration of R, is uniquely defined by some set of parameters, the degrees of freedom (DOFs) of R. The set of all robot configurations X is termed the C-space of the robot, and decomposes into the disjoint sets of free and forbidden configurations, namely X_free and X_forb, respectively. It is common to rephrase the motion-planning problem as the problem of moving R from a start configuration to a target configuration in a path fully contained within X_free.

To better understand the notion of C-spaces, consider a polygonal robot moving in the plane. If the robot is only allowed to translate, then it suffices to use a two-dimensional reference point to describe the location of the robot. Thus, both the workspace W and the C-space X are subsets of ℝR². If we allow the robot to rotate as well, then we need to add another parameter to describe the orientation of the robot. In this case we have that W ⊂ ℝ² while X ⊂ ℝ² x [0, 2π) (see Figure 1). The dimension of the C-space (namely the number of DOFs) may be arbitrarily high. Consider, for example, a robot, which is comprised of n spatial links, where a rotational joint connects each two consecutive links. Here, we need a three-dimensional point to describe the position of one of the robot’s endpoints and n – 1 two-dimensional parameters to describe the angle formed between each two consecutive links.

Figure 1. (a) Translating and rotating polygonal robot R (blue) and one polygonal obstacle (light red). (b) Corresponding configuration (yellow point) and obstacle in the C-space ℝ² x [0, 2π).

The configuration-space formalism was introduced in the late 1970s. Soon after, the first general algorithm for solving the motion-planning problem was proposed, with running time that is doubly exponential in the number of DOFs. Singly exponential-time algorithms have followed, but are generally considered too complicated to be implemented in practice Unfortunately, there is little hope to asymptotically reduce the exponential running times of these algorithms as the general problem was already shown by Reif to be PSPACE-Hard in the late 1970s. Additional hardness results have followed for different versions of the problem (for a complete description of exact methods and hardness results, see Halperin et al.¹³ and references within).

Facing the aforementioned hardness results, the community has mostly considered approaching the general problem with heuristic and approximate schemes.^25,29 Arguably, the most widely used approach to address the motion-planning problem is via sampling-based methods.

Sampling-based methods. One reason why the motion-planning problem is computationally hard is due to the complexity of computing obstacles in C– space. However, testing if one specific configuration is collision-free or not, an operation referred to as “collision detection,” is a relatively straightforward task that can be answered efficiently in the workspace. Using collision detection allows separating the motion-planning problem from the particular geometric and kinematic models of the robot. Furthermore, while the general motion-planning problem is computationally hard, computing a local path connecting two close-by configurations and then validating if this path is collision-free is, relatively speaking, a straightforward task. Following these key insights, sampling-based motion-planning algorithms abstract the robot as a point in the C-space X and plan a path in this space. The structure of X is then studied by constructing a graph