A Star - Shortest Path Algorithm (Repast Simphony)

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

A Star - Shortest Path Algorithm (Repast Simphony)

Gerardo Leo
Greetings, 

In my model I have to simulate an evacuation from a building.
I have already written a post asking information about how to integrate the building's map, and the final decision was to read my map from a .pgm file, creating a value layer.

The algorithm needs two inputs, the "start" point and a "goal" point: AStar (start, goal).

Then I need to get:

1) the agent's start position when the model has been initialized; 
2) the goal position, reading it from my map (.pgm file, where the exit corresponds to the number 3, for example).

In this way I can obtain the shortest path, but:

3) how can I use it to move the agents to the exit ? 

I hope someone could help me with these three points. 
 
Thank you very much, best. 
Gerardo 

------------------------------------------------------------------------------

_______________________________________________
Repast-interest mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/repast-interest
Reply | Threaded
Open this post in threaded view
|

Re: A Star - Shortest Path Algorithm (Repast Simphony)

Tatara, Eric R.
There's a good amount of literature on building evacuation models, so I'd suggest looking there to see what algorithms are commonly used.  There are a few fundamental approaches.  The first scenario is when the agent knows the exact series of shortest paths to take to evacuate the building.  For example, move to the room doorway, then move to the hallway doorway, then move to the building exit doorway.  You might use a basic queue structure at each entry/exit point to simulate what happens when agents bunch up at the doorway and need to wait some time to leave.  The more complex evacuation models tend to use a physics-based approach to simulate agent bunching at points that restrict movement.  The second scenario is when the agent does not know the shortest path, for example if it is in an unknown environment such that the agent needs to explore.  This is exactly like a maze-solving algorithm and there are numerous publications in the robotics and AI literature on the topic.

The basic code elements in Repast are:

To get the agent's current position: GridPoint point = grid.getLocation(this);

To move the agent: grid.moveTo(this, x, y)

The goal position would need to be enumerated in some way in the input file.  Perhaps a unique value in the PGM file could indicate goals and/or sub-goals.  If you can indicate doorways in the PGM file with specific values, the agent's could use those as a series of goals.  For example, an agent would always try to move from its current position to a sub-goal doorway position, and then move to the next goal after it reaches any sub-goal.  The doorway sub-goals would need to be ordered by priority (also possible to indicate in PGM) so that an agent would know the proper order of building exit.

eric

Eric Tatara, PhD, PE
Software Engineer
Global Security Sciences Division
Argonne National Laboratory

From: Gerardo Leo [[hidden email]]
Sent: Tuesday, September 13, 2016 10:11 PM
To: [hidden email]
Subject: [Repast-interest] A Star - Shortest Path Algorithm (Repast Simphony)

Greetings, 

In my model I have to simulate an evacuation from a building.
I have already written a post asking information about how to integrate the building's map, and the final decision was to read my map from a .pgm file, creating a value layer.

The algorithm needs two inputs, the "start" point and a "goal" point: AStar (start, goal).

Then I need to get:

1) the agent's start position when the model has been initialized; 
2) the goal position, reading it from my map (.pgm file, where the exit corresponds to the number 3, for example).

In this way I can obtain the shortest path, but:

3) how can I use it to move the agents to the exit ? 

I hope someone could help me with these three points. 
 
Thank you very much, best. 
Gerardo 

------------------------------------------------------------------------------

_______________________________________________
Repast-interest mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/repast-interest
Reply | Threaded
Open this post in threaded view
|

Re: A Star - Shortest Path Algorithm (Repast Simphony)

Gerardo Leo
Hello Eric, thanks for your quick replay.

I read different papers about this topic and the most used algorithms are "A Star" and "Dijkstra".
My idea is to use the A Star as step method for the security agents (they know the right path), the other agents can fallow them or explore the map in order to find the path by themselves.

In the PGM file the exit corresponds to the number 3, I am also thinking to create the object "Exit" as I did for the "Wall" in order to avoid the collisions.

Asking how to move the agents, I meant how to use the grid.moveTo(this, x, y) to make them fallow the shortest path (calculated using the A Star) to reach the exit.

If for example if I use as input two fixed point on the map:

Coordinate start = new Coordinate(x, y);
Coordinate goal = new Coordinate(x, y);


where "Coordinate" is a small class used to get x and get y (using getX and getY)

and then I print the path I can see it and the algo seems to work well:

AStar (Griglia, start, goal);   //Shortest path
System.out.println (Griglia); // Griglia is a class where I indicate the obstacles and the walkable path, reading the matrix from the pgm file




But, of course, I need to move my agents right along this path.  

Thank you very much.
Gerardo


Tatara, Eric R. wrote
There's a good amount of literature on building evacuation models, so I'd suggest looking there to see what algorithms are commonly used.  There are a few fundamental approaches.  The first scenario is when the agent knows the exact series of shortest paths to take to evacuate the building.  For example, move to the room doorway, then move to the hallway doorway, then move to the building exit doorway.  You might use a basic queue structure at each entry/exit point to simulate what happens when agents bunch up at the doorway and need to wait some time to leave.  The more complex evacuation models tend to use a physics-based approach to simulate agent bunching at points that restrict movement.  The second scenario is when the agent does not know the shortest path, for example if it is in an unknown environment such that the agent needs to explore.  This is exactly like a maze-solving algorithm and there are numerous publications in the robotics and AI literature on the topic.

The basic code elements in Repast are:

To get the agent's current position: GridPoint point = grid.getLocation(this);

To move the agent: grid.moveTo(this, x, y)

The goal position would need to be enumerated in some way in the input file.  Perhaps a unique value in the PGM file could indicate goals and/or sub-goals.  If you can indicate doorways in the PGM file with specific values, the agent's could use those as a series of goals.  For example, an agent would always try to move from its current position to a sub-goal doorway position, and then move to the next goal after it reaches any sub-goal.  The doorway sub-goals would need to be ordered by priority (also possible to indicate in PGM) so that an agent would know the proper order of building exit.

eric

Eric Tatara, PhD, PE
Software Engineer
Global Security Sciences Division
Argonne National Laboratory