MPAS – Multi-agent Path-finding Algorithms Simulator
For my final project at Ben Gurion university I created a simulator for testing and examining the behavior of different path finding algorithms for multiple agents.
What this basically means is, if you have a grid map with obstacles and lets say 2 cars traveling from their respective start point to goal, the algorithm will find the cheapest path for both cars such that they do not collide.
By cheapest path I mean that the sum of paths for all the cars will be the minimum possible.
There are currently 3 algorithms implemented in the simulator:
- Simple A-star
- Cooperative A-star
- Independence Detection A-Star
The first one is the basic A-star algorithm but taking account more than one unit (this one gets very slow as the numbers of agents increases)
The second algorithm is taken from the following paper : http://webdocs.cs.ualberta.ca/~lanctot/files/papers/cooppf-WHCA.pdf
The third algorithm is taken from the following paper: http://trevorstandley.appspot.com/Standley_AAAI10.pdf
View original post 116 more words