Multi-agent pathfinding in the crowded environment with obstacles: Algorithms and experimentation system.

Saved in:

Bibliographic Details
Title:	Multi-agent pathfinding in the crowded environment with obstacles: Algorithms and experimentation system.
Authors:	Hudziak, Mariusz¹, Pozniak-Koszalka, Iwona¹, Koszalka, Leszek¹ leszek.koszalka@pwr.edu.pl, Kasprzak, Andrzej¹
Source:	Journal of Intelligent & Fuzzy Systems. 2017, Vol. 32 Issue 2, p1561-1573. 13p.
Subjects:	Parallel scheduling (Computer scheduling), Sequential scheduling, Parallel algorithms, Distributed algorithms, Algorithmic randomness
Abstract:	The objective of this paper is to give a tool for the practical users, looking for the efficient way for solving pathfinding problem, concerning planning the best paths for the simultaneously moving agents in the crowded environment with obstacles. The proposed approach is based on the two-stage approach. In the first stage, a navigation mesh for passable regions in rectangular 2D environment is created using Quad-trees algorithm. In the second stage, a path is found for each agent present in environment using Dijkstra or A* algorithm. To find efficient paths in crowded environment, density information for each passable region is stored. Density information is further mapped on graph edges along with the distance values. The key point is that the moving agents reevaluate their paths accordingly to the re-planning strategy. Three strategies are considered: (i) periodical re-planning, (ii) periodical with initial re-planning, and (iii) the proposed way called event-driven re-planning. The created and implemented experimentation system can be adopted by the practical user for testing the twostage combinations of algorithms. The results of investigations, based on simulation experiments made with this system, presented in the paper, showed that the proposed approach is promising. [ABSTRACT FROM AUTHOR]
	Copyright of Journal of Intelligent & Fuzzy Systems is the property of Sage Publications Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

Description
Abstract:	The objective of this paper is to give a tool for the practical users, looking for the efficient way for solving pathfinding problem, concerning planning the best paths for the simultaneously moving agents in the crowded environment with obstacles. The proposed approach is based on the two-stage approach. In the first stage, a navigation mesh for passable regions in rectangular 2D environment is created using Quad-trees algorithm. In the second stage, a path is found for each agent present in environment using Dijkstra or A* algorithm. To find efficient paths in crowded environment, density information for each passable region is stored. Density information is further mapped on graph edges along with the distance values. The key point is that the moving agents reevaluate their paths accordingly to the re-planning strategy. Three strategies are considered: (i) periodical re-planning, (ii) periodical with initial re-planning, and (iii) the proposed way called event-driven re-planning. The created and implemented experimentation system can be adopted by the practical user for testing the twostage combinations of algorithms. The results of investigations, based on simulation experiments made with this system, presented in the paper, showed that the proposed approach is promising. [ABSTRACT FROM AUTHOR]
ISSN:	10641246
DOI:	10.3233/JIFS-169150