Extended Increasing Cost Tree Search for Non-Unit Cost Domains

Extended Increasing Cost Tree Search for Non-Unit Cost Domains

Thayne T. Walker, Nathan R. Sturtevant, Ariel Felner

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 534-540. https://doi.org/10.24963/ijcai.2018/74

Multi-agent pathfinding (MAPF) has applications in navigation, robotics, games and planning. Most work on search-based optimal algorithms for MAPF has focused on simple domains with unit cost actions and unit time steps. Although these constraints keep many aspects of the algorithms simple, they also severely limit the domains that can be used. In this paper we introduce a new definition of the MAPF problem for non-unit cost and non-unit time step domains along with new multiagent state successor generation schemes for these domains. Finally, we define an extended version of the increasing cost tree search algorithm (ICTS) for non-unit costs, with two new sub-optimal variants of ICTS: epsilon-ICTS and w-ICTS. Our experiments show that higher quality sub-optimal solutions are achievable in domains with finely discretized movement models in no more time than lower-quality, optimal solutions in domains with coarsely discretized movement models.
Keywords:
Agent-based and Multi-agent Systems: Multi-agent Planning
Heuristic Search and Game Playing: Heuristic Search
Agent-based and Multi-agent Systems: Coordination and Cooperation
Heuristic Search and Game Playing: Combinatorial Search and Optimisation
Planning and Scheduling: Distributed;Multi-agent Planning
Robotics: Multi-Robot Systems