Multi-Agent Path Finding with Formation (MAPF-F)

Project Overview

Exploring Multi-Agent Path Finding with Formation (MAPF-F): My dissertation, completed during my BSc in Computer Science at the University of Birmingham, dives into the fascinating world of multi-agent path finding (MAPF). This field is crucial for robotics and AI, aiming to plan collision-free paths for multiple agents—like robots—moving from start to goal locations in a shared environment. I introduced a twist called MAPF-F, where groups of robots must maintain a fixed square formation while moving, simulating tasks like carrying large objects in warehouses.

Adapting Conflict-Based Search (CBS)

MAPF-F builds on the Conflict-Based Search (CBS) algorithm, a two-level method that finds optimal paths for individual agents. I adapted CBS to handle groups by modifying its high-level and low-level processes. At the high level, it detects and resolves conflicts—like vertex collisions (two agents targeting the same spot) or swap conflicts (agents swapping positions)—for both single robots and groups. At the low level, I tweaked the A* search to ensure all four corners of a group stay conflict-free, treating agents as obstacles once they reach their goals.

Real-World Applications and Results

The motivation behind MAPF-F is practical: think warehouse robots moving oversized items like fridges or beds while allowing smaller robots to pass underneath, boosting efficiency. Tests on grid maps (e.g., a 10x7 map with obstacles) showed the algorithm works, though its runtime grows with more groups, sometimes struggling with complex scenarios. Results suggest potential, but optimizing it further could unlock broader applications, like 3D path planning or dynamic formations.