AAAI Publications, Workshops at the Twenty-Sixth AAAI Conference on Artificial Intelligence

Font Size: 
Independence Detection for Multi-Agent Pathfinding Problems
Trevor Scott Standley

Last modified: 2012-07-15


Problems that require multiple agents to follow non-interfering paths from their current states to their respective goal states are called multi-agent pathfinding problems (MAPFs). In previous work, we presented Independence Detection (ID), an algorithm for breaking a large MAPF problem into smaller problems that can be solved independently. Independence Detection is complete and can be used in combination with both optimal and approximation algorithms. This paper serves as an introduction to Independence Detection and aims to clarify its details.


Cooperative pathfinding; Multi-agent pathfinding; Pathplanning; path planning

Full Text: PDF