Multi Agent System (MAS)

With r3159 a Multi Agent System (MAS) has been added to PALM. It can be used to simulate the movement of pedestrians (e.g. in urban areas).

Click on any icon below to get to the respective part of the documentation.

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 .

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*-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.

Social Forces

Agent movement and close-range interaction is implemented using a modified Social Force Model. The implementation uses concepts from the original Social Force Model (Helbing, 1995) and an extension of it for close-rage collision prediction and avoidance (Karamouzas et. al, 2014).
The Social Forces approach is based on the idea that pedestrian movement is results from forces exerted on the pedestrian by its surroundings and goals. These forces can be either repulsive or attractive. Repulsive forces are associated with obstacles such as buildings, trees or other pedestrians. The current goal of each pedestrian exerts an attractive force on it. The resulting force on a pedestrian α is the sum of all attractive and repulsive forces,

The forces considered here are repulsion by obstacles and other pedestrians as well as the acceleration term driving the pedestrian toward its target.

The repulsion by an obstacle B is defined as

with the repulsive potential

In the MAS, U₀ is repuls_wall and R_B is sigma_rep_wall.

The repulsion by another pedestrian β is defined as

with the repulsive potential

In the MAS, V₀ is repuls_agent and R_β is sigma_rep_agent. This agent repulsive force is only used if α and β are already colliding (i.e. two circles with centers at the respective agents' position with radius radius_agent are intersecting). Otherwise, a collision avoidance force according to (Karamouzas et. al, 2014) is calculated:

Here, τ is the time until, given the current trajectory, a collision between the two pedestrians would occur, τ₀ = 3 s and k is a constant to sets the units with a value of 1.5 m² kg.

The acceleration force

describes the tendency of a pedestrian to accelerate toward its target. Here, τ_α is a relaxation time (tau_accel_agent) that describes how quickly the pedestrian approaches v₀ its desired walking speed with the direction to its current target, e.

The pedestrian's walking speed is given by

with a simple Euler-forward method used for time-integration.

Examples

For an example job to get to know the agent model, have a look at
trunk/EXAMPLES/agents

NAMELIST group name: prepro_par

Parameter Name	FORTRAN Type	Default Value	Explanation
flag_2d	L	.F.	Flag to force usage of 2d-buildings. If set to .T., this flag forces the usage of buildings_2d even if buildings_3d is available. See here for information on topography and building input.
internal_buildings	L	.F.	Flag to control usage of buildings within courtyards. By default, buildings completely surrounded by another building are excluded from the visibility graph as pedestrians can neither reach nor leave enclosed areas such as courtyards. If internal_buildings = .T., buildings within courtyards are allowed. The resulting navigation nodes can, however, never be connected to nodes outside of the courtyard. In such cases, be sure to set the target of a agent group originating inside a courtyard also within that same courtyard.
tolerance_dp	R * 3	1.41, 0.7, 0.35	Tolerance for simplification of building polygons during preprocessing. Each building is stored as a counter-clockwise sorted polygon. Initially each building polygon consists of all inner and outer corners of the PALM topography as vertices. Due to the rastered nature of this grid this may be a very large number of vertices. The Douglas-Peucker-Algorithm (Hershberger and Snoeyink, 1994) is used to reduce the number of vertices. This algorithm recursively approximates a polygon section as a straight line connecting the end points of that section. If the greatest distance between this line and any vertex between the end points is smaller than tolerance_dp, the approximation is accepted and all vertices in between are deleted. Otherwise, the segment is split into two segments at the vertex of greatest distance and the process is repeated. tolerance_dp is internally multiplied with SQRT( dx*dy ). If a building is left with less than 4 vertices after simplification using tolerance_dp(0), it is reset and the process is repeated with tolerance_dp(1), then tolerance_dp(2), if necessary. NOTE: The APT-P produces an ASCII output-file topo.txt. The polygon data is stored in this file. After execution of the tool, please check the polygon representation. If you are not satisfied, adjust tolerance_dp and rerun the tool.

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
• Karamouzas, I., Skinner, B., Guy, S.J. 2014. Universal Power Law Governing Pedestrian Interactions. Pyhsical Review Letters, 113, 238701. ​doi