Top

Published in:

2019 | OriginalPaper | Chapter

Path-Finding with a Full-Vectorized GPU Implementation of Evolutionary Algorithms in an Online Crowd Model Simulation Framework

Author : Anton Aguilar-Rivera

Published in: Computational Science – ICCS 2019

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This article introduces a path-finding method based on evolutionary algorithms and a fully vectorized GPU implementation of it. The algorithm runs on real-time and it can handle dynamic obstacles in maps of arbitrary size. The experiments show the proposed approach outperforms other traditional path-finding algorithms (e.g. A*). The conclusions present further improvement possibilities to the proposed approach like the application of multi-objective algorithms to represent full crowd models.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Event-Oriented Keyphrase Extraction Based on Bi-clustering Model

next chapter Analysing the Trade-Off Between Computational Performance and Representation Richness in Ontology-Based Systems

Algfoor, Z.A., Sunar, M.S., Kolivand, H.: A comprehensive study on pathfinding techniques for robotics and video games. Int. J. Comput. Games Technol. 2015, 7 (2015)

Bera, A., Manocha, D.: REACH - realtime crowd tracking using a hybrid motion model. In: 2015 IEEE International Conference on Robotics and Automation (ICRA), pp. 740–747. IEEE (2015)

Bezanson, J., Edelman, A., Karpinski, S., Shah, V.B.: Julia: a fresh approach to numerical computing. SIAM Rev. 59(1), 65–98 (2017)MathSciNetCrossRef

Cui, H., Zhang, H., Ganger, G.R., Gibbons, P.B., Xing, E.P.: GeePS: scalable deep learning on distributed GPUs with a GPU-specialized parameter server. In: Proceedings of the Eleventh European Conference on Computer Systems, p. 4. ACM (2016)

Gong, Y.-J., et al.: Distributed evolutionary algorithms and their models: a survey of the state-of-the-art. Appl. Soft Comput. 34, 286–300 (2015)CrossRef

Ijaz, K., Sohail, S., Hashish, S.: A survey of latest approaches for crowd simulation and modeling using hybrid techniques. In: 17th UKSIMAMSS International Conference on Modelling and Simulation, pp. 111–116 (2015)

Jaros, J.: Multi-GPU island-based genetic algorithm for solving the knapsack problem. In: 2012 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8. IEEE (2012)

Johansson, A., Helbing, D.: Pedestrian flow optimization with a genetic algorithm based on Boolean grids. In: Waldau, N., Gattermann, P., Knoflacher, H., Schreckenberg, M. (eds.) Pedestrian and Evacuation Dynamics 2005, pp. 267–272. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-47064-9_23CrossRef

Jacques Jr., J.C.S., Musse, S.R., Jung, C.R.: Crowd analysis using computer vision techniques. IEEE Signal Process. Mag. 27(5), 66–77 (2010)

10.

Malcolm, J., Yalamanchili, P., McClanahan, C., Venugopalakrishnan, V., Patel, K., Melonakos, J.: ArrayFire: a GPU acceleration platform. In: Modeling and Simulation for Defense Systems and Applications VII, vol. 8403, p. 84030A. International Society for Optics and Photonics (2012)

11.

Naderan-Tahan, M., Manzuri-Shalmani, M.T.: Efficient and safe path planning for a mobile robot using genetic algorithm. In: IEEE Congress on Evolutionary Computation, CEC 2009, pp. 2091–2097. IEEE (2009)

12.

Nowotniak, R., Kucharski, J.: GPU-based tuning of quantum-inspired genetic algorithm for a combinatorial optimization problem. Bull. Pol. Acad. Sci. Tech. Sci. 60(2), 323–330 (2012)

13.

Pan, X., Han, C.S., Dauber, K., Law, K.H.: A multi-agent based framework for the simulation of human and social behaviors during emergency evacuations. Ai Soc. 22(2), 113–132 (2007)CrossRef

14.

Papadopoulou, E., Zavershynskyi, M.: The higher-order Voronoi diagram of line segments. Algorithmica 74(1), 415–439 (2016)MathSciNetCrossRef

15.

Pospichal, P., Jaros, J., Schwarz, J.: Parallel genetic algorithm on the CUDA architecture. In: Di Chio, C., et al. (eds.) EvoApplications 2010, Part I. LNCS, vol. 6024, pp. 442–451. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-12239-2_46CrossRef

16.

Song, B., Wang, Z., Sheng, L.: A new genetic algorithm approach to smooth path planning for mobile robots. Assem. Autom. 36(2), 138–145 (2016)CrossRef

17.

Valenzuela-Rendón, M.: The virtual gene genetic algorithm. In: Cantú-Paz, E., et al. (eds.) GECCO 2003, Part II. LNCS, vol. 2724, pp. 1457–1468. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-45110-2_18CrossRefMATH

18.

Vigueras, G., Lozano, M., Orduna, J.M., Grimaldo, F.: A comparative study of partitioning methods for crowd simulations. Appl. Soft Comput. 10(1), 225–235 (2010)CrossRef

19.

Wang, K., Shen, Z., et al.: A GPU-based parallel genetic algorithm for generating daily activity plans. IEEE Trans. Intell. Transp. Syst. 13(3), 1474–1480 (2012)CrossRef

20.

Zhong, J., Hu, N., Cai, W., Lees, M., Luo, L.: Density-based evolutionary framework for crowd model calibration. J. Comput. Sci. 6, 11–22 (2015)CrossRef

Title: Path-Finding with a Full-Vectorized GPU Implementation of Evolutionary Algorithms in an Online Crowd Model Simulation Framework
Author: Anton Aguilar-Rivera
Publisher: Springer International Publishing
Book: Computational Science – ICCS 2019
Print ISBN: 978-3-030-22749-4

Electronic ISBN: 978-3-030-22750-0

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-22750-0_17

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner