Ederer, I. (2022). Enhancing meta-agent conflict-based search for the multi-agent pathnding problem with informed merging and heuristics [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2022.98487
The multi-agent pathfinding (MAPF) problem is a planning problem with the goal to find paths for multiple agents. These paths allow them to concurrently navigate from their individual starting points to their goal points. The paths need to be conflict free, which means the agents are not allowed to occupy the same space at the same time. The optimization aspect of the MAPF variant we focus on is t...
The multi-agent pathfinding (MAPF) problem is a planning problem with the goal to find paths for multiple agents. These paths allow them to concurrently navigate from their individual starting points to their goal points. The paths need to be conflict free, which means the agents are not allowed to occupy the same space at the same time. The optimization aspect of the MAPF variant we focus on is to find a solution where the sum of the lengths of the paths is minimized. Computer games, traffic control with autonomous vehicles, and autonomous warehouse robots are real world scenarios where the MAPF problem is relevant, as non-conflicting paths for multiple agents need to be found. In this thesis we aim to improve an algorithm called conflict-based search (CBS), which is designed to solve the MAPF problem optimally, by iteratively resolving conflicts in a best-first search. Especially, we focus on the variant which is able to form meta-agents, which are groups of agents for which paths are searched for in a coupled manner. We provide strategies to find advantageous assignments to form meta-agents prior to the search process of CBS. Our first approach is to provide merging strategies based on pairwise symmetries. For the second approach we use machine learning. Instead of finding the meta-agent assignments ourselves, we train a machine learning model to predict beneficial merge candidates. Our last proposed improvements are heuristic functions which are capable of handling meta-agents. These heuristics are designed to decrease the number of high level node expansions needed to find a valid solution by calculating an informed estimate of the cost of getting from a specific node to a target node. As our approaches are designed as extensions to an already existing algorithm, we compare our solutions to the base version in a computational study. We evaluate them based on the runtimes, the resulting success rates, and where suitable on the number of expanded high level nodes. For these experiments we choose MAPF instances which are based on either four-connected grids of size 20 x 20, or on real world scenarios taken from the online repository for MAPF instances. We present the effects of our proposed merging strategies and heuristics in a computational study. The merging strategy based on rectangle conflicts, provides a substantial improvement of the success rate, the fraction of solved instances within a given time limit, on the empty map. The merging approaches using machine learning models to predict whether a pair of agents should be merged upfront do not increase the success rates overall, but only could slightly reduce the runtimes on empty maps. In the end, we could not achieve sufficient prediction precision. On the other hand, enhancing multi-agent CBS with heuristics based on multi-value decision diagrams together with rectangle conflict based merging algorithms substantially decreases the average number of high level node expansions needed to find valid solutions for the instances based on real world scenarios. Additionally, the additional work to calculate the heuristics often pays off and instances are solved faster.