Solving multi-agent pathfinding problems in polynomial time using tree decompositions

  • Author / Creator
    Khorshid, Mokhtar
  • Multi-agent pathfinding problems involve finding plans for agents that must travel from their start locations to their targets without colliding. Recent work produced a number of algorithms to solve the problem as well as an ample supply of related theory. This work is based on a related work that studied the feasibility of multi-agent pathfinding problems on trees. Our work takes this further to actually provide a constructive proof of how to solve multi-agent pathfinding problems in a tree and culminates in a novel approach that called tree-based agent swapping strategy (TASS). I also provide a family of algorithms that decompose graphs to trees. Experimental results showed that TASS can find solutions to multi-agent pathfinding problems on a highly crowded tree with 1000 nodes and 996 agents in less than 3 seconds. Further experiments compared TASS with other modern contending algorithms and the results were very favorable.

  • Subjects / Keywords
  • Graduation date
    Fall 2011
  • Type of Item
  • Degree
    Master of Science
  • DOI
  • License
    This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.