Multi Agent Path Planning

This project explores advanced motion planning for multi-robot systems by implementing the M algorithm* in Python. Conducted as an independent study (ENSE699) under the supervision of Dr. Michael Otte at the University of Maryland, the work focused on solving the "curse of dimensionality" inherent in multi-agent pathfinding.

The Algorithm: M* Standard coupled planners (like A*) search the full joint configuration space of all robots, which grows exponentially with every added agent. M* mitigates this using a technique called Subdimensional Expansion.

• Dynamic Coupling: The algorithm initially plans for each robot separately (decoupled).

• Local Dimensionality: It only couples robots (increasing the search space dimensionality) when a specific robot-robot collision is detected.

• Optimality: Unlike pure decoupled approaches, M* guarantees completeness and finds minimal cost paths.

Implementation & Benchmarking: I developed a custom Python simulation environment using Pygame for visualization and NumPy for array manipulation.

• Scalability: Successfully simulated collision-free pathfinding for swarms of up to 7 robots in crowded grid environments.

• Performance: Benchmarked M* against a standard Coupled A* implementation. The results demonstrated that M* significantly reduces computation time by exploring a lower-dimensional search space, only expanding dimensions where interactions actually occur.