Minimum Risk Motion Planning (MRMP) has been shown to remain NP-Hard even under the conditions that lead to the practical efficiency of sampling-based and grid-based motion planning algorithms [25]. However, the hardness proof does not eliminate the importance of finding a practical solution to this problem. In this paper we identify a parameter which directly controls the hardness of MRMP. We present experiments that suggest this parameter is small for many practical MRMPs and present an algorithm guaranteed to efficiently yield high-quality solutions whenever this parameter is small. When the parameter is large, the algorithm fails gracefully—it returns a solution with bounded suboptimality. We also explore a connection between our work and previous work on the minimum constraint removal problem (MCR).
Efficient Motion Planning Under Obstacle Uncertainty with Local Dependencies
Springer Proceedings in Advanced Robotics
International Workshop on the Algorithmic Foundations of Robotics ; 2022 ; , MD, USA June 22, 2022 - June 24, 2022
15.12.2022
17 pages
Aufsatz/Kapitel (Buch)
Elektronische Ressource
Englisch
Obstacle Accommodation Motion Planning
British Library Conference Proceedings | 1993
|Motion Planning Under Uncertainty
AIAA | 2012
|Motion Planning in Obstacle Rich Environments
AIAA | 2009
|