MPAS – Multi-agent Path-finding Algorithms Simulator

Amit Ofer

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

Advertisements

About Khuram Ali

Programming... Programming and Programming...!!!

Posted on April 26, 2013, in Algorithms, Artificial Intelligence. Bookmark the permalink. 2 Comments.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: