Adapting the Conflict-based Search Algorithm for Alternative Objectives

Hledání cesty pro více agentů (MAPF) je důležitým typem problému plánování v umělé inteligenci. Existuje mnoho aplikací MAPF a každá aplikace má své vlastní priority, což dává MAPF mnoho různých variací. S rostoucím zájmem vědců o toto téma byly vyvinuty nové algoritmy pro řešení různých variací MAPF v posledních letech. Konfliktní vyhledávání (CBS) je jedním z těchto algoritmů, který je v současné době nejmodernějším řešením řešení instancí MAPF pomocí objektivní funkce součtu nákladů. V tomto článku budeme diskutovat o tom, jak přizpůsobit CBS pro objektivní funkci značky makespan, emprické srovnání obtížnosti řešení instancí MAPF s CBS v rámci součtu nákladů a objektivních funkcí značky a způsoby, jak zlepšit chování CBS pomocí objektivní funkce značkypanpan. Experimentální výsledky ukazují, že řešení usnadňuje řešení než řešení součtu nákladů, a je možné upravit algoritmus pro objektivní funkci tak, aby se dosáhlo lepšího výkonu.The Multi-Agent Path Finding (MAPF) is an important type of planning problem in artificial intelligence. There are many applications of MAPF and each application has its own priorities, which gives MAPF many different variations. With the increasing interest of researchers on this topic, new algorithms developed for solving different variations of MAPF in the recent years. Conflict Based Search (CBS) is one of those algorithms, which is currently the state-of-art for solving MAPF instances with sum-of-cost objective function. In this paper, we will discuss how to adapt CBS for makespan objective function, emprical comparison of the difficulty of solving MAPF instances with CBS under sum-of-costs and makespan objective functions, and ways to improve the behaviour of CBS with makespan objective function. Experimental results show that solving makespan is easier than solving sum-of-costs, and it is possible to adjust the algorithm for the objective function to obtain better performance