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 :

The third algorithm is taken from the following paper:

View original post 116 more words

About Khuram Ali

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

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

  1. Awesome! Really awesome! Great work! 🙂

  1. Pingback: Dynamic Programming – Edit Distance | Khuram Ali

Leave a Reply

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

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

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: