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


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

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



    Erscheinungsdatum :

    2012-01-01



    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    629



    Exploiting GPUs for multi-agent path planning on grid maps

    CAGGIANESE, GIUSEPPE / ERRA, UGO | BASE | 2012

    Freier Zugriff

    A space decomposition method for path planning of loop linkages

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

    Freier Zugriff

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

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

    Freier Zugriff

    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