Proving motion planning infeasibility is an important part of a complete motion planner. Common approaches for high-dimensional motion planning are only probabilistically complete. Previously, we presented an algorithm to construct infeasibility proofs by applying machine learning to sampled configurations from a bidirectional sampling-based planner. In this work, we prove that the learned manifold converges to an infeasibility proof exponentially. Combining prior approaches for sampling-based planning and our converging infeasibility proofs, we propose the term asymptotic completeness to describe the property of returning a plan or infeasibility proof in the limit. We compare the empirical convergence of different sampling strategies to validate our analysis.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Exponential Convergence of Infeasibility Proofs for Kinematic Motion Planning


    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 :

    18 pages





    Type of media :

    Article/Chapter (Book)


    Type of material :

    Electronic Resource


    Language :

    English






    The Feasible Infeasibility of Activity Scheduling

    Garling, T. | British Library Conference Proceedings | 2004


    KINEMATIC MOTION PLANNING WITH REGIONAL PLANNING CONSTRAINTS

    CHEREPINSKY IGOR / DING XUCHU / SANE HARSHAD S | European Patent Office | 2020

    Free access

    Kinematic motion planning with regional planning constraints

    CHEREPINSKY IGOR / DING XUCHU / SANE HARSHAD S | European Patent Office | 2018

    Free access