The design and implementation of theoretically-sound robot motion planning algorithms is challenging. Within the framework of resolution-exact algorithms, it is possible to exploit soft predicates for collision detection. The design of soft predicates is a balancing act between easily implementable predicates and their accuracy/effectivity. In this paper, we focus on the class of planar polygonal rigid robots with arbitrarily complex geometry. We exploit the remarkable decomposability property of soft collision-detection predicates of such robots. We introduce a general technique to produce such a decomposition. If the robot is an m-gon, the complexity of this approach scales linearly in m. This contrasts with the O(m^3) complexity known for exact planners. It follows that we can now routinely produce soft predicates for any rigid polygonal robot. This results in resolution-exact planners for such robots within the general Soft Subdivision Search (SSS) framework. This is a significant advancement in the theory of sound and complete planners for planar robots. We implemented such decomposed predicates in our open-source Core Library. The experiments show that our algorithms are effective, perform in real time on non-trivial environments, and can outperform many sampling-based methods.


    Access

    Download


    Export, share and cite



    Title :

    Soft Subdivision Motion Planning for Complex Planar Robots


    Contributors:
    Zhou, Bo (author) / Chiang, Yi-Jen (author) / Yap, Chee (author)

    Publication date :

    2018-01-01



    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    004 / 629




    Robust motion planning for non-holonomic robots with planar geometric constraints

    Tajvar, Pouria / Varava, Anastasiia / Kragic, Danica et al. | BASE | 2022

    Free access

    Motion planning of mobile robots

    Larin, V.B. | IEEE | 2004


    Motion Planning for Serpentine Robots

    Henning, Wade / Hickman, Frank / Choset, Howie | ASCE | 1998


    Collaborative motion planning of humanoid robots

    Balland, Olivier | BASE | 2014

    Free access

    Motion planning techniques for humanoid robots

    FERRARI, PAOLO | BASE | 2021

    Free access