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


    Access

    Download


    Export, share and cite



    Title :

    Exploiting GPUs for multi-agent path planning on grid maps



    Publication date :

    2012-01-01



    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    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

    Free access


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

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