Lifelong Multi-Agent Path Finding in A Dynamic Environment

In tradition, the problem of Multi-Agent Path Finding is to find paths for the agents without conflicts, and each agent execute one-shot task, a travel from a start position to its destination. However, making just one planning for the agents may not satisfy the requirement in dynamic environments such as logistics sorting center, where the paths of the agents may constantly need to be adjusted according to the incoming tasks. The challenging issue is to dynamically adjust the already planned paths while make planning for the agents ready to execute new incoming tasks. In this paper, we formulate it into Dynamic Multi-Agent Path Finding (DMAPF) problem, the goal of which is to minimize the cumulative cost of paths. To solve this problem, we propose an algorithm called Lifelong Planning Conflict-Based Search (LPCBS), which can efficiently and optimally make planning for the new incoming tasks while adjusting the already planned paths. Experiment results show that the LPCBS performs much better than the existing works in each planning.