Programming language: C++11 and newer
Multi-agent path planning (MAPP) using the A* algorithm. This implementation is based on the Aalto CS-E4800 Artificial Intelligence course, where I was a teaching assistant.
The problem comprises of a two-dimensional grid, where there are set of agents (each with its own location and goal) and optionally, a set of walls representing locations where no agent can be.
Personal motivation: I am making a state machine generator program (QT + Python), which generates code from a state diagram drawn by the user. The user interface needs A* in order to reorganize the arrows, when a state is dragged around.
| Class | Description | Location |
|---|---|---|
| Wall | A grid location where no agent can be located at any time. Walls should not be added at any agent's goal coordinates. | Wall.hpp |
| Agent | An intelligent agent, moving in a two-dimensional grid from a starting position towards its goal (final position). In multi-agent problems such as this one, there can be more than one single agent pursuing its goal at any time in the grid. | Agent.hpp, Agent.cpp |
| MAPPGridState | The state-space representation of a grid comprises of a vector of MAPPGridStates, each such state representing a collection of agents and their current positions on the grid, together with the total cost which took to reach the state, and the state heuristic -the estimated cost to reach the goal state-. The cost of moving from one state to the successor (next) state is always 1, since in this representation only one agent can move per state transition. The state heuristic is computed as the sum of all individual heuristics of the agents. | MAPPGridState.hpp, MAPPGridState.cpp |
| Namespace | Description | Location |
|---|---|---|
| heuristic | Contains a function that computes the heuristic of an agent, ie. the estimate of the distance from the current location to the goal. It is enouraged to add more heuristics -if required by the problem- in this namespace. | heuristic.hpp, heuristic.cpp |
| Astar | Contains the actual A* algorithm, used to search the state-space and retrieve the best state trajectory that solves the problem. | Astar.hpp, Astar.cpp |
| File | Description |
|---|---|
| porting.hpp | For easily porting the standard library-based implementation to other frameworks (such as QT). |
| main.cpp | For demonstrating the usage of the Astar program in a practical scenario. |
| test/AstarTests.cpp | Unit tests that shall pass after any modification that is made to the program. |
In order to compile and run the program, run the following commands:
make
./output
make clean
In order to run the unit tests, run the following commands from the Astar folder.
cmake --build build --config Debug --target all -- -j 6
cd build
ctest -j6 -C Debug -T test --output-on-failure
Or, you can open the project with Visual Studio Code and run the tests from the status bar, CMake Tools extension is needed.
For more details on Google Test with VS Code, watch : https://youtu.be/Lp1ifh9TuFI