Multi-agent path planning on grid maps is a challenging problem and has numerous real-life applications ranging from robotics to real-time strategy games and non-player characters in video games. A* is a cost-optimal forward search algorithm for path planning which scales up poorly in practice since both the search space and the branching factor grow exponentially in the number of agents. In this work, we propose an A* implementation for the Graphics Processor Units (GPUs) which uses as search space a grid map. The approach uses a search space decomposition to break down the forward search A* algorithm into parallel independently forward sub-searches. The solution offer no guarantees with respect to completeness and solution quality but exploits the computational capability of GPUs to accelerate path planning for many thousands of agents. The paper describes this implementation using the Compute Unified Device Architecture (CUDA) programming environment, and demonstrates its advantages in GPU performance compared to GPU implementation of Real-Time Adaptive A*.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Exploiting GPUs for multi-agent path planning on grid maps



    Erscheinungsdatum :

    2012-01-01



    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    629



    HD maps: Exploiting OpenDRIVE potential for Path Planning and Map Monitoring

    Diaz-Diaz, Alejandro / Ocana, Manuel / Llamazares, Angel et al. | IEEE | 2022


    Path planning on grid maps with unknown goal poses

    Tanzmeister, Georg / Friedl, Martin / Wollherr, Dirk et al. | IEEE | 2013


    GPU Accelerated Multi-agent Path Planning Based on Grid Space Decomposition

    CAGGIANESE, GIUSEPPE / ERRA, UGO | BASE | 2012

    Freier Zugriff


    Exploiting Multi-Layer Grid Maps for Surround-View Semantic Segmentation of Sparse LiDAR Data

    Bieder, Frank / Wirges, Sascha / Janosovits, Johannes et al. | IEEE | 2020