In this work, we describe a simple and powerful method to implement real-time multi-agent path-finding on Graphics Processor Units (GPUs). The technique aims to find potential paths for many thousands of agents, using the A* algorithm and an input grid map partitioned into blocks. We propose an implementation for the GPU that uses a search space decomposition approach to break down the forward search A* algorithm into parallel independently forward sub-searches. We show that this approach fits well with the programming model of GPUs, enabling planning for many thousands of agents in parallel in real-time applications such as computer games and robotics. The paper describes this implementation using the Compute Unified Device Architecture 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 :

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



    Publication date :

    2012-01-01



    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    629



    Exploiting GPUs for multi-agent path planning on grid maps

    CAGGIANESE, GIUSEPPE / ERRA, UGO | BASE | 2012

    Free access

    A space decomposition method for path planning of loop linkages

    Porta, Josep M. / Cortés, Juan / Ros, Lluís et al. | BASE | 2007

    Free access

    Multi-UAV Path Planning and Following Based on Multi-Agent Reinforcement Learning

    Xiaoru Zhao / Rennong Yang / Liangsheng Zhong et al. | DOAJ | 2024

    Free access

    Deep Reinforcement Learning for Image-Based Multi-Agent Coverage Path Planning

    Xu, Meng / She, Yechao / Jin, Yang et al. | IEEE | 2023


    Centralized and Distributed Path Planning for Multi-Agent Exploration

    Giardini, Giovanni / Kalmar-Nagy, Tamas | AIAA | 2007