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

  • Algorithm
  • Multiagent
  • Polynomial
  • Path planning
  • Pathfinding

• Graduation date

  Fall 2011

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/R3M340

• 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.