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


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Efficient Motion Planning Under Obstacle Uncertainty with Local Dependencies


    Weitere Titelangaben:

    Springer Proceedings in Advanced Robotics


    Beteiligte:
    LaValle, Steven M. (Herausgeber:in) / O’Kane, Jason M. (Herausgeber:in) / Otte, Michael (Herausgeber:in) / Sadigh, Dorsa (Herausgeber:in) / Tokekar, Pratap (Herausgeber:in) / Axelrod, Brian (Autor:in) / Shimanuki, Luke (Autor:in)

    Kongress:

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



    Erscheinungsdatum :

    15.12.2022


    Format / Umfang :

    17 pages





    Medientyp :

    Aufsatz/Kapitel (Buch)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch





    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