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.
Introduction
The problem of finding a path in the area with obstacles is popular. It is often present in many areas. Examples exist in fields of robotics - autonomous robot moving in the known or unknown environment, games - agents moving in virtual environment or crowd simulations. In many cases solving pathfinding problem should be as efficient as possible. For example, in games pathfinding is “competing” with graphics rendering and other non-GPU work for CPU resources. If pathfinding takes too much CPU resources, real-time performance could not be possible. For this reason pathfinding algorithms are simplified leading to unnatural game agent’s movement. Currently the big part of scene rendering is moved to GPU, leaving more space for more efficient pathfinding algorithms. Another example is crowd simulation wherein large crowd is steered through environment. Lot of CPU resources may be needed for this task and real-time simulation may not be achieved if overly demanding algorithms will be used.
The aim of this paper is to solve the problem of finding a path for many agents [14] in the crowded environment with obstacles - focusing on avoiding congested regions. We are looking not for the shortest path but the fastest path, where congested regions penalize agents by slowing them down, so the shortest path is not always the fastest.
In proposed solution pathfinding algorithms are combined with re-planning algorithms, into whole solution (overall algorithm) along with graph generation algorithm. The two notions are important: the navigation mesh and the density. The navigation mesh is created from a given environment. The main idea of navigation mesh is to represent passable regions of the environment by logical abstraction, which can be further used for graph generation. Information about density is used by re-planning algorithms. The density of the crowd is measured in navigation mesh regions and it is measured as the number of the agents per square meter [16]. Higher the crowd density slower agents speed in region [4]. The agents are planning their paths avoiding crowded regions. It is done by applying the density information, which is practically computed as the overall size of agents in a given area divided by the total area size. In such an approach agents may have different sizes. When a new agent enters the region, then the density value is increased. When agent leaves region, then the density is decreased. The actual density information in each region is stored, and then mapped on the edge of the graph which goes into region. In this way the graph weights are changing over time along with changing density in crowded regions. The re-planning strategies are used to adapt to the changing environment. Aim of the overall solution is better utilization of different routes and faster average agents speed.
The graph from environment could be created in many different ways. The first approach is by creating navigation mesh and then connecting, mesh regions in chosen way. One example of such a method is Quad-trees algorithm [8] and connecting centers of generated regions to form a graph. The approach being part of wider group of way-points methods is called Probabilistic Roadmap Method (PRM) [11]. This method uses chosen probability distribution to put vertices on passable area. Then vertices are connecting using for example k-nearest neighbor’s algorithm to form a graph. In this paper the first approach was chosen.
In the second part of the proposed solution, a pathfinding algorithm is used. The most known pathfinding algorithms are: Dijkstra algorithm described in [11] and A* approach presented in [9], which were used in the overall solution. In modern use, pathfinding algorithms have to cope with new problems, e.g., growing size of environment on which they are used. The larger the environment the more computations are needed to find a path. Few approaches try to deal with this problem and among them is HPA* algorithm which is 10 times faster than A* algorithm, while paths found by that algorithm are within 1% worse than optimal [3]. To cope with changing density re-planning algorithm should be used.
The interesting approach with the usage of density information in crowded environment is presented in [16]. It is based on generating a navigation mesh with medial axis and Explicit Corridor Map data structure [6], what allows for steering agents through environment using periodical re-planning strategies. In this paper, the two known re-planning strategies are considered: periodical re-planning and periodical with initial re-planning, and a new algorithm called event-driven re-planning is proposed. When agents are moving through crowded environment it is likely that in some places density will be high and traffic jams will occur. Such a situation is understandable because pathfinding algorithms look for the shortest path and do not take congestion into consideration. In the real-world such congestion leads to slowing down of moving agents [4], and causes longer time for agent to reach their goal. In Fig. 1 the agents take only the shortest route and such behavior leads to congestion. In this work, we use the collected information about the density for steering agents more naturally through environment, while still keeping good path length and low computation time of algorithms. In Fig. 2, the desired behavior of agents is presented. Agents are not only moving on the shortest path, but also are taking longer detours to avoid the congestion and good re-planning should achieve such a result.
To evaluate the considered combinations of algorithms, the experimentation system consisted of three modules: Drawing, Navigation Mesh generation, and Multi-agent pathfinding simulation was designed.
The first module is responsible for the creation of an environment with obstacles. In the second module, the navigation mesh and graph are formed. The third module allows observing the real-time simulation of moving agents and collecting data needed to calculate the introduced indices of performance.
The problem considered in the paper is an extension of the problem studied by the authors of this paper in [10]. Good algorithmic solutions to pathfinding problems have commercial significance. The practical users are therefore faced with a bewildering choice: which algorithm serves them best? After all, theoretical claims are not always reliable in practice [5, 15].
The created experimentation system described in this paper (being a supplementation of the scope of paper [10] and an extension of idea presented in [12]) offers the practical users help in deciding which pathfinding and re-planning algorithm is the best for their needs. Its modularity makes it relatively easy for users to: compare the actual performances of the algorithms in common tasks; optimize their parameters; apply constraints.
The new investigations (two scenarios) were presented in Section 5, comparing to paper [10]. Also, a new analysis of computation time of the best re-planning algorithm was provided, showing that it may be used in real-time simulation or games.
The rest of the paper is organized as follows. Section 2 provides a statement of the considered problem. Section 3 describes the implemented algorithms. The experimentation system is presented in Section 4. The results of the comparative analysis of the properties of algorithms, based on simulations, are given in Section 5. Final conclusions and suggestions for further research appear in Section 6.
Problem statement
The considered problem can be formulated in the following way:
In Equation (3), the parameter curspeed (a, t) is divided by the number of iterations. A current speed of a-th agent is computed using Equation (4).
The density DEN depends on the number of agents present in a current region and the size of a region. The changes in time are also considered.
The proposed approach to solving the formulated problem is composed of three parts: (i) generation of navigation mesh and graph, (ii) pathfinding, and (iii) path re-planning. The density information is stored in regions created by navigation mesh algorithm. When a new agent enters the region or an agent leaves region then the density is increased or decreased accordingly to agent’s size, respectively. Recent density information in each region is stored and mapped on the edge of the graph which goes into region. This way the pathfinding algorithm seeks for path using modified weights. Such a way of storage and mapping on graph edges was successfully applied in [16]. Path needs to be recomputed because it is no longer valid after some time. New crowded regions could have emerged. To deal with this problem re-planning strategies are used to adapt to the changing environment. Overall solution leads to better utilization of different routes and faster agents speed.
Algorithm for mesh and graph navigation
Input environment is rectangular area with set of impassable rectangular obstacles. This area is firstly split, using Quad-trees algorithm, into smaller passable regions. Idea of this algorithm is to recursively split regions on which any obstacles are present or until the smallest size of region is reached. Practically depth of recursion is limited by size of smallest mesh element or number of recursions. This limitation protects from creating too small mesh elements. Also, Quad-trees algorithm is modified to have three levels of recursive splitting even when no obstacle is present. Such a modification leads to creation of more graph edges, but gives more possibilities to find more diverse path. After splitting centers of regions are connected using nearest k-neighbors strategy [7]. If connection leads through obstacle it is discarded. In such a way graph is created with vertices as centers and edges as connections. Weights on the edges are set as Euclidean distance between centers.
In the beginning the input area is treated as the first parameter R. Set of obstacles O is provided as the second parameter. As an output of QUADTREE function, arrays Out of passable regions are returned. The SPLIT function (an output) provides four regions of a half width and a half height of an input region.
The implemented Quad-trees algorithm can be described in pseudo-code as Algorithm 1.
In the beginning the input area is treated as the first parameter R. Set of obstacles O is provided as the second parameter. As an output of QUADTREE function, arrays Out of passable regions are returned. The SPLIT function (an output) provides four regions of a half width and a half height of an input region.
In the next step, pathfinding algorithms [15] are used to find a path for agents. Two algorithms can be used: Dijkstra algorithm for finding the shortest path in graph without negative weights, and a version of A* algorithm with Euclidean distance to the goal. Dijkstra or A* seeks for the shortest path from start to goal points without using density information. Paths are further stored and used by every new agent appearing in the region. These paths are reevaluated accordingly to re-planning strategy.
Path re-planning
The shortest route found by pathfinding algorithm and taken by agents, could lead to congestion in regions. Because agents decrease their speed when entering the congested region, these regions should be avoided. It can be done with one of the following re-planning strategies: Periodical re-planning, Periodical with the initial re-planning, Event-driven re-planning.
Algorithm for periodical re-planning
When re-planning strategy emits a signal that an agent should re-plan its path, then the used (A* or Dijkstra) algorithm is finding a new path with a new start point (a current position of an agent). Moreover, the current densities in regions are used to steer agents through environment. However, periodical re-planning strategy can re-plan paths after some time interval. The
This strategy is a little modification of the previous strategy. Each agent is re-planning its path on the start point. Such approach gives more diverse paths of agents from the beginning, because of density information. The previous assumptions about input parameters of the function also apply to
The strategies presented in sub-sections 3.4 and 3.5 are relatively simple and they are not time consuming. However, these strategies yield re-planning of agents paths in uncontrollable manner. Path re-planning may occur when there is no such a need or not occur when it is needed for some agent. The advantage of this approach is no need for deciding which agents should re-plan its path and use computation time mainly on pathfinding algorithms.
The main focus in these strategies has to be put on the number of agents which re-plan their paths in each run of re-planning. The aim is to balance computational time of overall algorithm which highly depends on pathfinding algorithm and the quality of the founded paths.
This strategy (Algorithm 4) is based on the specific events that may occur in the environment. The function
Function IsRegionOnPath (a, r) checks whether a path of a current agent a leads through a given region r. Function DistanceToRegion (a, r) computes the distance from a position of a given current agent to the center of the region r.
The overall multi-agent algorithm consists of: Quad-trees and nearest k-neighbors algorithm to build a graph, Algorithm A* or Dijkstra algorithm to find a path, Re-planning algorithm performed along with periodical re-planning or periodical with initial re-planning or event-driven re-planning as a strategy to signal path re-planning.
In edges of a graph the information about density is stored with information about distance between vertices. Each time the density in navigation mesh changes and density information in graph is updated. These values are used by Dijkstra and A* algorithms when searching for a path. In Section 5, various compositions of multi-agent algorithms arestudied.
Experimentation system
The designed and implemented computer experimentation system for simulating and solving multi-agent pathfinding problem consists of three parts: Drawing, NavMesh (Navigation mesh generation), and PathFinding (Multi-agent pathfinding).
Drawing area
Main aim of this part is to create area with obstacles. It is assumed that all obstacles have rectangular shape. Also the area is rectangular with given width and height. Following functionalities areprovided: Creating an area with given width and height. Saving and loading area with obstacles. Drawing obstacles on new or loaded area.
In Drawing part the obstacles can be added into area (or removed) using the mouse. The created map can be stored and further loaded to theapplication.
Navigation mesh generation
In this part on previously generated area with obstacles, navigation mesh using Quad-trees algorithm is generated. The following functionalities are given: Creating navigation mesh using Quad-trees algorithm with a given resolution (size of the smallest mesh element). Generating graph from navigation mesh and connecting centers of mesh elements. Using nearest k-neighbors strategy.
In NavMesh part, the Quad-tree mesh can be generated. Minimum Height and Minimum Width parameters limit the height and width of the smallest mesh element. When Quad-tree algorithm is ran then Quad-tree mesh is generated and further graph is created.
Multi-agent pathfinding
After generation of navigation mesh and graph, the system is ready to solve the multi-agent pathfinding problem. The following functionalities are provided: A* or Dijkstra algorithm can be chosen as pathfinding algorithm. Addition of start points and goal points to the graph using nearest 1-neighbor strategy. Algorithm can be run with and without replanning methods. Three re-planning methods can be chosen: event-driven, periodical or periodical with initial re-planning. Visualization of agents and current density of mesh primitives in real-time. Possibility of changing parameters of algorithms and environment should be provided.
In PathFinding tab experiments can be performed using selected algorithms. Experiments can be conducted with or without real-time simulation. Pathfinding algorithms and appropriate re-planning strategy can be chosen. The parameters StartPoint and EndPoint can be selected on a given environment.
The parameters available for tuning are: AgentSize - agent size which influences density in mesh. DensityDistEvent - distance from the dense region used by event-driven re-planning strategy. DensityMod - one of two functions: (can be chosen as linear and nonlinear for graph density computation). DensityTriggerTh - threshold value for density in region. If density is higher then set threshold event-driven re-planning marks this region as dense. SecToTime - for changing agents’ speed (by changing time conversion between seconds and iterations). Higher its value - faster the speed of agents.
AgentSize and DensityMod parameters influence how density in region is changing graph weights. DensityDistEvent and DensityTriggerTh influence event-driven re-planning algorithm. Lower the DensityDistEvent lower re-planning frequency and computation time per iteration, but less diverse routes taken by agents, which could lead to longer average time of travelling. Lower the DensityTriggerTh higher occurrence of dense regions and higher possibility to re-plan path by the agent.
Simulation overview
An example of simulation - to illustrate the behavior of agents on Medium with Narrow Passage environment (environment is described in Section 5) is presented in Fig. 3. In this figure, the subsequent six phases of the simulation of agents behavior in real-time for A* and periodical with initial re-planning strategy are shown (agents are presented as dots, obstacles as green rectangles, and red filled rectangles represent congestion in a region). Quad-tree mesh can be seen with connected graph in the background. In Fig. 3(a) agents are moving through narrow passage and density is increasing.
In Fig. 3(b) agents are moving through longer routes, because of change of density inpassage.
In Fig. 3(c) congestion occurs in narrow passage.
In Fig. 3(d) again can be seen that agents because of previous congestion take longer routes. Agents again are moving shorter path leading through narrow passage in Fig. 3(e).
It can be seen, in Fig. 3(f), that congestion problem occurs again in narrow passage. Agents are changing their behavior depending on density in regions. It may confirm that re-planning strategy is effective.
The system gives opportunities for performing simulation experiments in ‘automatic’ manner for various combinations of algorithms, and for displaying the obtained solutions as well.
Investigation
Experiment design
In experiments the number of 12,000 agents was put in the environment. Three agents, one for each pair of start and end points, were considered in any iteration. The Dijkstra and the A* algorithms were used as reference, because all re-planning algorithms were used on the top of them. This way advantages and disadvantages of using re-planning algorithm may be easily seen in form of lower traveling time and higher computation load.
The following combinations of the algorithms were tested: D - Dijkstra algorithm without path re-planning strategy – used as benchmark for comparison (reference), D/Per - Dijkstra algorithm with periodical path re-planning strategy, D/PerInit - Dijkstra algorithm with periodical initial path re-planning strategy, D/Event - Dijkstra algorithm with event-driven re-planning strategy, A* - A* algorithm without path re-planning strategy used as benchmark for comparison (reference), A*/Per - A* algorithm with periodical path re-planning strategy, A*/PerInit - A* algorithm with periodical initial path re-planning strategy, A*/Event - A* algorithm with event-driven re-planning strategy.
avCT: The average computation time of single algorithm iteration. pthR: The amount of runs of pathfinding algorithms (Dijkstra or A*). maxA: The maximum number of simultaneous agents present in the environment. AvrA: The average number of simultaneous agents (for more than 1500 agents) present in the environment. TrvTMs: The average travelling time of agents (in ms) for three pairs of start and end points.
In order to properly simulate the behavior of agents in the environment, the important assumption was made - the density in a region should not lower the speed of agents to zero, because such a situation could lead to stalling and in consequence some agents could never reach their goals. Therefore, the overcrowded places were treated as the obstacles that should be avoided. Experimentation system parameters for all experiments were the same. Parameters were chosen in non-systematic way and possibly may need further investigations, but such an investigation is out of scope of this work. Main focus was on comparison of different algorithm combination in the same experimentation system parameters.
Three created 2D environments were taken into consideration as the experimental scenarios:
Big - the area of the size 1920×1080 pixels with many rectangular obstacles and possible routes from start to goal point (see Fig. 4). Such an environment shows diversity of routes taken by agents.
Medium and Medium with Narrow Passage - the two areas of the size 1920×1080 pixels. The first environment (Fig. 9) shows behavior of agents when dense regions occur in many different places. The second environment (Fig. 7) was created to show usage of density information of re-planning algorithm when narrow corridor is present and the shortest path goes through it for many agents.
Big environment – algorithms’ comparison
In Fig. 4, the created area of the Big environment with regular obstacles is shown. The obtained results, i.e., measured and computed indices of performance which may characterize the tested algorithms, are given in Table 1.
It may be observed that the most efficient re-planning algorithm is periodical initial re-planning. The total number of runs of pathfinding algorithm pthR confirm it (in both cases, for Dijkstra and A* algorithm).
In Fig. 5, the checked columns represent the four most efficient multi-agent pathfinding algorithms in case of travelling time of agents TrvT. The best are event-driven and periodical with initial re-planning. It can be also seen in Fig. 6 that event-driven re-planning needs much more computation time than other algorithms.
Finally, it may be concluded that the periodical with initial re-planning was the best re-planning strategy for Big environment, when both the time of travelling and the computation time are considered.
Medium environment with narrow passage: Algorithms’ comparison
This environment was created to examine algorithms behavior when the shortest path to the target leads through narrow corridor and other paths to goal are much longer.
In Fig. 7, the created area for Medium environment with narrow passage and obstacles is shown.
In Table 2, the results for Medium with Narrow Passage environment can be seen. This environment examines efficiency of algorithms in using density information. If agents take longer detour avoiding congested corridor then can reach goal with shorter time, but only slightly shorter.
Like in the case of Big environment the least time consuming re-planning strategy is periodical with initial re-planning. Travelling time TrvT in this case is the best for periodical with initial re-planning in Dijkstra case and event-driven re-planning in A* case. It can be seen that it is opposite situation to previous one presented in Section 5.1. In this case Dijkstra algorithm with periodical initial re-planning gave the best travelling time results. It may be observed (Fig. 8) that TrvT is the best for event-driven and periodical with initial re-planning.
However, TrvT did not differ as much as in case of Big environment. It can be explained by environment in which longer detours are needed when narrow passage is congested, so taking longer detours is not so beneficial.
Medium environment – algorithms’ comparison
In Fig. 9, the created Medium environment with obstacles is shown.
In opposite to Fig. 7 there is no remarkable narrow passage in the middle.
In Table 3 the obtained values of the indices of performance are presented. The best values are blackened. In Fig. 10 travelling time TrvT of agents is presented. It can be seen that event-driven re-planning and periodical with initial re-planning gave a much better results than periodical re-planning and reference algorithms.
In Medium environment congestion could occur in many regions. However, two the best re-planning strategies (D/Per/Init and A*/Per/Init) solved the problem of congestion efficiently.
It may be observed (Fig. 11) that for avCT periodical re-planning strategy gave slightly better result in case of A* than periodical with initial re-planning strategy.
Taking into consideration both TrvT and avCT it can be concluded that for Medium environment the best re-planning strategy is periodical with initial re-planning.
Influence of pathfinding part on effectiveness of the overall algorithm
In Fig. 12, time of travelling TrvT in relation to the number of additional runs of pathfinding algorithm (a part of the overall algorithm) is presented.
In the legend, the notion ‘nreplan’ (n = 0, 1, 2, 3) means nth additional algorithm runs, and A* concern the situation without any re-planning strategy. It can be seen in Fig. 12, that without additional re-planning runs (0replan), the TrvT of agents was increased by about 1000 ms, comparing to the 3replan. Comparing to Fig. 13, it can be observed that when no additional re-planning (0replan) is added the computation time avCT was dropped by 9 ms per iteration.
It can also be observed that periodical with initial re-planning algorithm could be tuned to deal with problems when resources are limited. A practical example could be games with high fps number. For 25 fps application, 40 ms is an upper limit for pathfinding, rendering graphics, and other tasks, so resources for pathfinding algorithm are limited. By worsening periodical with the initial re-planning algorithm 32 ms are left for these other tasks. It should be noted, that avCT could be even shorter because only one core was busy on 100% when algorithm was working and the second CPU core was idle. It can be expected that multi-core design speed up should be greater.
Conclusion and final remarks
In the paper, re-planning algorithms were combined with two algorithms: A* and Dijkstra. Combination with A* gave slightly lower computation time and comparable travelling time of agents. The best results were obtained by periodical with initial replanning algorithm for which the travelling time of agents and the computation time were the best in almost all cases. The re-planning algorithm can be also tuned to lower computation time or decrease travelling time of agents. Also it was observed that better performance can be reached by a proper tuning of algorithms, e.g., done by changing the number of pathfinding algorithm runs. Also usage of other CPU cores could give good speed up of the overall algorithm.
It is worth to be mentioned that the event-driven re-planning algorithm designed by the authors may improve agents travelling time. Event-driven re-planning gives possibility for further improvement by modifying its parameters. In experimentation system DensityDistEvent parameter could be modified to change frequency of re-planning events and DensityTriggerTh may be changed to modify when region is interpreted as dense. These parameters give user more control over tradeoff between computation time and agents travelling time.
During experiments it was observed that agents (in any environment with obstacles) tend to cluster into groups. In Fig. 14 such a situation is presented, where a lot of slowly moving groups emerged after some time of simulation.
When such a group is created then the congestion in narrow passages will likely occur and consequently increasing agents travelling time. One solution to this problem may be an algorithm, which could recognize such a group and re-plan agent’s path within group with some randomness. This approach may lower number of groups and speed up travelling time of agents.
The authors are planning in the further research to focus on: (i) the implementation of a new re-planning algorithm which allows avoiding agents clustering, e.g., a combination of event-driven re-planning with periodical with initial re-planning which is anticipated to give higher ability to control agent’s behavior and may be used to cope with this problem; (ii) the implementation of other pathfinding algorithms as a part of the overall algorithm, e.g., HPA*, which could lead to significantly lower computation time, and tried to apply the approach presented in [13]; (iii) the adaptation of the new ideas described in [1, 2, 1, 2].
Footnotes
Acknowledgments
This work was supported by the statutory funds of the Department of Systems and Computer Networks, Faculty of Electronics, Wroclaw University of Science and Technology, Wroclaw, Poland.