Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

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

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 8374))

Included in the following conference series:

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 obstacle configurations. 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.

Similar content being viewed by others

Keywords

References

  1. Bleiweiss, A.: GPU accelerated pathfinding. In: Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware, GH 2008, Aire-la-Ville, Switzerland, pp. 65–74. Eurographics Association (2008)

    Google Scholar 

  2. Botea, A., Müller, M., Schaeffer, J.: Near Optimal Hierarchical Path-Finding. Journal of Game Development 1(1), 7–28 (2004)

    Google Scholar 

  3. Erra, U., Caggianese, G.: Real-time Adaptive GPU multi-agent path planning, vol. 2, ch. 22, pp. 295–308. Morgan Kaufmann Publishers Inc. Computing Gems Jade Edition edition (2011)

    Google Scholar 

  4. Harish, P., Narayanan, P.J.: Accelerating large graph algorithms on the GPU using CUDA. In: Aluru, S., Parashar, M., Badrinath, R., Prasanna, V.K. (eds.) HiPC 2007. LNCS, vol. 4873, pp. 197–208. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  5. Hart, P., Nilsson, N., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics 4(2), 100–107 (1968)

    Article  Google Scholar 

  6. Holte, R.C., Perez, M.B., Zimmer, R.M., MacDonald, A.J.: Hierarchical A*: searching abstraction hierarchies efficiently. In: Proceedings of the Thirteenth National Conference on Artificial Intelligence, AAAI 1996, vol. 1, pp. 530–535. AAAI Press (1996)

    Google Scholar 

  7. Katz, G.J., Kider Jr., J.T.: All-pairs shortest-paths for large graphs on the GPU. In: Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware, GH 2008, Aire-la-Ville, Switzerland, pp. 47–55. Eurographics Association (2008)

    Google Scholar 

  8. Kider, J., Henderson, M., Likhachev, M., Safonova, A.: High-dimensional planning on the GPU. In: 2010 IEEE International Conference on Robotics and Automation (ICRA), pp. 2515–2522 (May 2010)

    Google Scholar 

  9. Kirk, D.B., Hwu, W.-M.W.: Programming Massively Parallel Processors: A Hands-on Approach, 1st edn. Morgan Kaufmann Publishers Inc., San Francisco (2010)

    Google Scholar 

  10. Nickolls, J., Buck, I., Garland, M., Skadron, K.: Scalable parallel programming with CUDA. Queue 6(2), 40–53 (2008)

    Article  Google Scholar 

  11. Shekhar, S., Fetterer, A., Goyal, B.: Materialization trade-offs in hierarchical shortest path algorithms. In: Scholl, M.O., Voisard, A. (eds.) SSD 1997. LNCS, vol. 1262, pp. 94–111. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

  12. Stefan, E., Damian, S.: Parallel state space search on the GPU. In: International Symposium on Combinatorial Search, SoCS (2009)

    Google Scholar 

  13. Sturtevant, N.R.: Memory-efficient abstractions for pathfinding. In: Proceedings of the Third Artificial Intelligence and Interactive Digital Entertainment Conference, Stanford, California, USA, June 6-8, pp. 31–36. The AAAI Press (2007)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Matematica, Informatica ed Economia, Università della Basilicata, Italy

    Giuseppe Caggianese & Ugo Erra

Authors
  1. Giuseppe Caggianese

    You can also search for this author inPubMed Google Scholar

  2. Ugo Erra

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Rechen- und Kommunikationszentrum, RWTH Aachen, Seffenter Weg 23, 52074, Aachen, Germany

    Dieter an Mey

  2. TU Vienna, 1040, Vienna, Austria

    Michael Alexander

  3. RWTH Aachen University, Seffenter Weg 23, 52074, Aachen, Germany

    Paolo Bientinesi  & Carsten Clauss  & 

  4. University Magna Graecia of Catanzaro, 88100, Catanzaro, Italy

    Mario Cannataro

  5. Inria Rennes - Bretagne Atlantique, 35042, Rennes, France

    Alexandru Costan  & Christine Morin  & 

  6. University of Innsbruck, 6020, Innsbruck, Austria

    Gabor Kecskemeti

  7. Department of Computer Science, University of Pisa, 56126, Pisa, Italy

    Laura Ricci

  8. Universitat Politècnica de València, 46022, València, Spain

    Julio Sahuquillo

  9. LLNL, USA

    Martin Schulz

  10. Dipartimento di Informatica, Università di Salerno, 84084, Salerno, Italy

    Vittorio Scarano

  11. Tennessee Tech University and Oak Ridge National Laboratory, 38505, Cookeville, TN, USA

    Stephen L. Scott

  12. Technische Universität München, 80333, Munich, Germany

    Josef Weidendorfer

Rights and permissions

Copyright information

© 2014 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Caggianese, G., Erra, U. (2014). Parallel Hierarchical A* for Multi Agent-Based Simulation on the GPU. In: an Mey, D.,et al. Euro-Par 2013: Parallel Processing Workshops. Euro-Par 2013. Lecture Notes in Computer Science, vol 8374. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-54420-0_50

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp