Probabilistic motion planning for non-Euclidean and multi-vehicle problems
Preprint
Abstract
Trajectory planning tasks for non-holonomic or collaborative systems are naturally modeled by state spaces with non-Euclidean metrics. However, existing proofs of convergence for sample-based motion planners only consider the setting of Euclidean state spaces. We resolve this issue by formulating a flexible framework and set of assumptions for which the widely-used PRM*, RRT, and RRT* algorithms remain asymptotically optimal in the non-Euclidean setting. The framework is compatible with collaborative trajectory planning: given a fleet of robotic systems that individually satisfy our assumptions, we show that the corresponding collaborative system again satisfies the assumptions and therefore has guaranteed convergence for the trajectory-finding methods. Our joint state space construction builds in a coupling parameter $1\leq p\leq \infty$, which interpolates between a preference for minimizing total energy at one extreme and a preference for minimizing the travel time at the opposite extreme. We illustrate our theory with trajectory planning for simple coupled systems, fleets of Reeds-Shepp vehicles, and a highly non-Euclidean fractal space.
Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- Bicycle paths, elasticae and sub-Riemannian geometryNonlinearity, 2021
- Roadmaps for Robot Motion Planning with Groups of RobotsCurrent Robotics Reports, 2021
- Searching Multiple Approximate Solutions in Configuration Space to Guide Sampling-Based Motion PlanningJournal of Intelligent & Robotic Systems, 2020
- Motion Planning by Sampling in Subspaces of Progressively Increasing DimensionJournal of Intelligent & Robotic Systems, 2020
- Effcient Nearest-Neighbor Search for Dynamical Systems with Nonholonomic ConstraintsSpringer Proceedings in Advanced Robotics, 2020
- Subdimensional expansion for multirobot path planningArtificial Intelligence, 2015
- Sampling-Based Robot Motion Planning: A ReviewIEEE Access, 2014
- Control of Nonholonomic Systems: from Sub-Riemannian Geometry to Motion Planning2014
- Sampling-based optimal motion planning for non-holonomic dynamical systems2013
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996