NDLI: Exploiting GPUs for multi-agent path planning on grid maps

Content Provider	IEEE Xplore Digital Library
Author	Caggianese, G. Erra, U.
Copyright Year	2012
Description	Author affiliation: Dipartimento di Ingegneria e Fisica dell'Ambiente, Università degli Studi della Basilicata, Potenza, Italy (Caggianese, G.) \|\| Dipartimento di Matematica e Informatica, Università degli Studi della Basilicata, Potenza, Italy (Erra, U.)
Abstract	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^{∗}.$
Starting Page	482
Ending Page	488
File Size	1833542
Page Count	7
File Format	PDF
ISBN	9781467323598
e-ISBN	9781467323628
DOI	10.1109/HPCSim.2012.6266962
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-07-02
Publisher Place	Spain
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Real time systems Tiles Instruction sets $A^{∗}$ algorithm Bismuth Grid maps Path planning Planning Path-finding Graphics processing unit Search space decomposition GPU acceleration
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Research on GPU-Based Real-Time MTF Compensation Algorithm

GPU accelerated face detection

A Scalable Tridiagonal Solver for GPUs

A Real Time Augmented Reality System Using GPU Acceleration

GPU accelerated real time polarimetric image processing through the use of CUDA

Improving the Performance of a Ray Tracing Algorithm Using a GPU

Exploiting GPU On-chip Shared Memory for Accelerating Schedulability Analysis

Using GPU With CUDA to Accelerate MoM-Based Electromagnetic Simulation of Wire-Grid Models

CUDA accelerated illumination preprocessing on GPUs

Exploiting GPUs for multi-agent path planning on grid maps

Similar Documents

Research on GPU-Based Real-Time MTF Compensation Algorithm

GPU accelerated face detection

A Scalable Tridiagonal Solver for GPUs

A Real Time Augmented Reality System Using GPU Acceleration

GPU accelerated real time polarimetric image processing through the use of CUDA

Improving the Performance of a Ray Tracing Algorithm Using a GPU

Exploiting GPU On-chip Shared Memory for Accelerating Schedulability Analysis

Using GPU With CUDA to Accelerate MoM-Based Electromagnetic Simulation of Wire-Grid Models

CUDA accelerated illumination preprocessing on GPUs

Exploiting GPUs for multi-agent path planning on grid maps