Multi-Agent Path Finding with Time Windows: Preliminary Results

Jianqi Gao (Harbin Institute of Technology (Shenzhen), Qi Liu (Harbin Institute of Technology (Shenzhen), Shiyu Chen (Harbin Institute of Technology (Shenzhen), Kejian Yan (Harbin Institute of Technology (Shenzhen), Xinyi Li (Harbin Institute of Technology (Shenzhen), Yanjie Li (Harbin Institute of Technology (Shenzhen)

Abstract

We formalize the problem of multi-agent path finding with time windows (MAPF-TW). The optimization objective is to maximize the average customer satisfaction for all agents when they reach their respective goal vertices without path conflicts. We first prove that solving MAPF-TW optimally is NP-hard. We then reduce the MAPF-TW problem into a multi-commodity flow problem and propose an integer linear programming (ILP) model. Next, we propose the conflict-based search with time windows (CBS-TW) for the MAPF-TW problem, which is also optimal. Finally, we conduct simulation experiments on two different maps with random obstacles.