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

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 two-stage 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.