[1S1-IS-3] Agents

[1S1-IS-3-02] Non-Grid Multiagent Pathfinding via Combining Learning-based Method and Search-based Method

〇Shiyao Ding¹, Hideki Aoyama², Donghui Lin¹ (1. Kyoto University, 2. Panasonic Coroporation)

Working-in-progress

キーワード：Multi-agent pathfinding, Multi-agent reinforcement learning, Drone delivery

Most prior work on Multiagent path finding (MAPF), a problem of identifying a group of collision-free paths for multiple agents, was on grid graphs, assumed agents' actions are only four directions (up, down, right, left) or wait. We study here a new MAPF problem that does not rely on such assumptions and is more generally on a non-grid graph. Some algorithms for solving traditional MAPF can also be applied to this new problem, which can be categorized two types: search-based method and learning-based method. However, the challenges created by the non-grid feature, such as large state/action space hinder to apply either of two types methods. Thus, we propose a third approach that combines MARL algorithm and search method, can accelerate the learning process. Specifically, one part of the agents’ pathfinding is solved according to predefined rules. Then, based on the pathfinding results, the other part of the agents are further trained by MARL. This can accelerate the learning process. Finally, the experimental results show our proposed method to be more effective than some existing algorithms.