In this work, we describe a Parallel Hierarchical A* (PHA*) for path-finding in real-time using the Graphics Processor Units (GPUs). The technique aims to find potential paths for many hundreds of agents by building an abstraction graph of the input map in an off-line phase and then using this representation to speed up the path-finding during the on-line phase. The approach is appropriate in the case of scenarios based on grid maps and is independent on a specific topology. In addition, we propose also a strategy to obtain smooth paths during the search. We show that this approach fits well with the programming model of the GPUs, enabling searching for many hundreds of agents in parallel in real-time applications such as simulations. The paper describes this implementation using the Compute Unified Device Architecture programming environment, and demonstrates its advantages in terms of performance and quality of the paths founded comparing PHA* with a GPUs implementation of Real-Time Adaptive A* and the classic A* algorithm.

Parallel Hierarchical A* for Multi Agent-based Simulation on the GPU

ERRA, UGO;CAGGIANESE, GIUSEPPE
2014-01-01

Abstract

In this work, we describe a Parallel Hierarchical A* (PHA*) for path-finding in real-time using the Graphics Processor Units (GPUs). The technique aims to find potential paths for many hundreds of agents by building an abstraction graph of the input map in an off-line phase and then using this representation to speed up the path-finding during the on-line phase. The approach is appropriate in the case of scenarios based on grid maps and is independent on a specific topology. In addition, we propose also a strategy to obtain smooth paths during the search. We show that this approach fits well with the programming model of the GPUs, enabling searching for many hundreds of agents in parallel in real-time applications such as simulations. The paper describes this implementation using the Compute Unified Device Architecture programming environment, and demonstrates its advantages in terms of performance and quality of the paths founded comparing PHA* with a GPUs implementation of Real-Time Adaptive A* and the classic A* algorithm.
2014
978-3-642-54419-4
File in questo prodotto:
File Dimensione Formato  
padabs2013.pdf

accesso aperto

Descrizione: Versione finale pre-print.
Tipologia: Documento in Pre-print
Licenza: DRM non definito
Dimensione 1.11 MB
Formato Adobe PDF
1.11 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11563/58670
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 4
social impact