Version 5 (modified by sward, 6 years ago) (diff) |
---|
Multi Agent System (MAS)
The embedded Multi Agent System (MAS) allows for the modeling of pedestrian movement in complex (urban) terrain. The following text provides an overview of the model's functionality as well as underlying concepts. This will cover the topics of creating a visibility graph, pathfinding, and Social Forces for collision avoidance.
For a list of input parameters, see agent_pararmeters.
Navigation
This section contains information concerning agent navigation. This includes preprocessing and online steps .
Visibility graph
Prior to a simulation using the MAS navigation information for the agents must be preprocessed. The result is a navigation mesh (visibility graph) that agents can use to find their way around obstacles toward their target.
Concept
For agents to be able to find a path through an area containing obstacles (such as a city) some sort of graph is needed on which pathfinding can be performed. Such a graph consists of nodes that indicate physical locations and connections between these nodes annotated with a cost to travel between the two nodes.
The concept used here is called "visibility graph". It hinges on the idea that pedestrians use outer corners of obstacles to navigate. All spaces that pedestrians will not or cannot cross, such as buildings, trees, certain types of streets, etc are considered obstacles. The agent will walk toward the next visible corner on their way to their final target, make a turn, and walk toward the next corner. Thus, the nodes are the obstacle corners and a connection is established between two nodes if they are in view of each other and given the cost of the direct distance between the two.
To produce this data,
1) the PALM building topographhy is converted to polygons (one per obstacle) containing all convex and cocave corners as vertices.
2) The polygon data is simplified using the Douglas-Peucker algorithm (Hershberger and Snoeyink, 1994). To adjust the rate of simplification, see tolerance_dp.
3) All remaining convex polygon vertices are added to the graph as nodes.
4) Connections are established between each pair of nodes that are visible by each other. The associated cost is set to the direct distance.
5) The polygon and graph data is output to a Fortran binary file that can be read by PALM.
Creating the visibility graph
A tool separate from PALM has been developed to calculate the visibility graph. It is a standalone Fortran program (find it at UTIL/nav_mesh/nav_mesh.f90).
The usage of this tool is subject to chage! The following description is preliminary!
1) Copy nav_mesh.f90 to the INPUT-folder of your JOB.
2) Compile it, including your NetCDF-libraries. At IMUK the command is (replace the paths according to your local NetCDF installation):
ifort -cpp -I /muksoft/packages/netcdf4_hdf5parallel/4411c_443f/hdf5-1.10.0-patch1/mvapich2-2.3rc1/intel/2018.1.163/include/ \\ -L /muksoft/packages/netcdf4_hdf5parallel/4411c_443f/hdf5-1.10.0-patch1/mvapich2-2.3rc1/intel/2018.1.163/lib -D__netcdf -lnetcdf -lnetcdff nav_mesh.f90
3) Make sure your Input folder contains the relevant topography information in either an ASCII- or NetCDF-file (see here).
4) Make sure your Input folder contains the _p3d-file. In it, if necessary, specify the namelist &prepro_par with the parameters flag_2d, internal_buildings and tolerance_dp.
5) Execute the program
./a.out
This will create a file <job_identifier>_nav. This is a Fortran binary file that contains the polygon and visibility graph data and will be read by PALM during the simulation. As long as the area and resulution of the model domain do not change this file can be reused.
Pathfinding
During the simulation each agent receives target coordinates (see at_x and at_y). Each agent must then find a path from its current position to its target using the visibility graph. This is accomplished using the A*(A-star)-algorithm which is a well-known fast pathfinding algorithm (click here for a thorough explanation). For this,
- the agent's current position and its target are added to the visibility graph,
- the shortest path between these two points is calculated,
- the navigation points are shifted outward from the obstacle corner to a random position along a "gate" (see corner_gate_start and corner_gate_width) to avoid collisions with obstacles or other agents,
- pathfinding is run again with each successive pair of navigation points along the path to avoid intersection of path sections with obstacles resulting from the outward shift,
- finally, the resulting path is stored in the agent object as a series of intermittent targets.
Each agent calculates the direction toward its next intermittet target during each agent time step. It will accelerate toward those coordinates. Once the agent has come close enough (dist_to_int_target) to them, the next intermittent target is chosen. When the final target is reached, the agent is deleted.
Recalculation of an agent's path occurs when
- the agent has deviated too far (max_dist_from_path) from its current path or
- the path counter has reached its maximum and the target is not yet reached. This can occur because for the purpose of conservation of memory each agent can store a maximum of 15 intermittent targets.
While pathfinding is run on the visibility graph,
L, u∗ as well as
NAMELIST group name: prepro_par
Parameter Name | FORTRAN Type | Default Value | Explanation |
---|---|---|---|
flag_2d | L | .F. |
Flag to force usage of 2d-buildings. |
internal_buildings | L | .F. |
Flag to control usage of buildings within courtyards. |
tolerance_dp | R * 3 |
1.41, |
Tolerance for simplification of building polygons during preprocessing. |
References
- Helbing, D., Molnar, P. (1995). Social force model for pedestrian dynamics. Physical review E, 51(5), 4282. doi
- Hershberger, J., Snoeyink, J. 1994. An O(nlogn) implementation of the Douglas-Peucker algorithm for line simplification. SCG '94 Proceedings of the tenth annual symposium on Computational geometry. 383-384. doi
Attachments (11)
- pathfinding_berlin.gif (6.1 MB) - added by sward 6 years ago.
-
color_scheme.png
(10.0 KB) -
added by sward 6 years ago.
Color scheme for the buttons
-
lm_mono_caps_10_font.zip
(41.5 KB) -
added by sward 5 years ago.
Caps font for buttons
- button_template.pptx (64.4 KB) - added by sward 5 years ago.
- button_a_star.png (50.0 KB) - added by sward 5 years ago.
- button_code_structure.png (63.9 KB) - added by sward 5 years ago.
- button_ex_setup.png (54.5 KB) - added by sward 5 years ago.
- button_input.png (52.8 KB) - added by sward 5 years ago.
- button_output.png (63.1 KB) - added by sward 5 years ago.
- button_prepro.png (64.9 KB) - added by sward 5 years ago.
- button_social_force.png (76.3 KB) - added by sward 5 years ago.