Sampling-Based Methods for Motion Planning with Constraints

By Zachary K. Kingston, Mark Moll, Lydia E. Kavraki. 2018

225 citations recorded by the source corpus.

Robots with many degrees of freedom (e.g., humanoid robots and mobile manipulators) have increasingly been employed to accomplish realistic tasks in domains such as disaster relief, spacecraft logistics, and home caretaking. Finding feasible motions for these robots autonomously is essential for their operation. Sampling-based motion planning algorithms are effective for these high-dimensional systems; however, incorporating task constraints (e.g., keeping a cup level or writing on a board) into the planning process introduces significant challenges. This survey describes the families of methods for sampling-based planning with constraints and places them on a spectrum delineated by their complexity. Constrained sampling-based methods are based on two core primitive operations: ( a) sampling constraint-satisfying configurations and ( b) generating constraint-satisfying continuous motion. Although this article presents the basics of sampling-based planning for contextual background, it focuses on the representation of constraints and sampling-based planners that incorporate constraints.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Control and Systems Engineering, Robotics & Control

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Control and Systems Engineering

In Robotics & Control

Citations in the corpus

Habitat 2.0: Training Home Assistants to Rearrange their Habitat (2021, background): “[72] Zachary Kingston, Mark Moll, and Lydia E Kavraki.”
Mesh Manifold Based Riemannian Motion Planning for Omnidirectional Micro Aerial Vehicles (2021, methodology): “Note that RRT*-Pro is evaluated on analytic geometries in [10], which makes geometric lookups and Jacobian calculation more efficient, whereas here it suffers from more expensive operations on a mesh map.”
ReKep: Spatio-Temporal Reasoning of Relational Keypoint Constraints for Robotic Manipulation (2024, background): “Motion planning algorithms use geometric constraints to compute feasible trajectories that avoid obstacles and achieve goals [55–60].”
Integrated Task and Motion Planning (2020, background): “See (36, 37) for a comprehensive survey of these techniques.”