Using Value Abstraction for Optimal Multi-Agent Pathfinding with Increasing Cost Tree Search Master Thesis

Increasing Cost Tree Search is a promising approach to multi-agent pathfinding problems, but like all approaches it has to deal with a huge number of possible joint paths, growing exponentially with the number of agents. We explore the possibility of reducing this by introducing a value abstraction to the Multi-valued … See more

Increasing Cost Tree Search is a promising approach to multi-agent pathfinding problems, but like all approaches it has to deal with a huge number of possible joint paths, growing exponentially with the number of agents. We explore the possibility of reducing this by introducing a value abstraction to the Multi-valued Decision Diagrams used to represent sets of joint paths. To that end, we introduce a heat map to heuristically judge how collision-prone agent positions are and present how to use and possibly refine abstract positions in order to still find valid paths.

See less