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).


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Efficient Motion Planning Under Obstacle Uncertainty with Local Dependencies


    Additional title:

    Springer Proceedings in Advanced Robotics


    Contributors:

    Conference:

    International Workshop on the Algorithmic Foundations of Robotics ; 2022 ; , MD, USA June 22, 2022 - June 24, 2022



    Publication date :

    2022-12-15


    Size :

    17 pages





    Type of media :

    Article/Chapter (Book)


    Type of material :

    Electronic Resource


    Language :

    English





    Obstacle Accommodation Motion Planning

    Shan, Y. / Koren, Y. | British Library Conference Proceedings | 1993


    Motion Planning Under Uncertainty

    Valasek, John / Agha-Mohammadi, Ali-Akbar / Kumar, Sandip et al. | AIAA | 2012



    Motion Planning in Obstacle Rich Environments

    Kim, Sung Hyun / Bhattacharya, Raktim | AIAA | 2009