A coordinated scheduling approach for task assignment and multi-agent path planning

Abstract

Path finding is an essential problem in multi-agent systems, widely employed in warehousing and logistics. However, most of the current studies focus on the problem of assigning one agent with one task in a period, which may hinder the efficiency of path planning of the systems when facing multi-tasks. To address this problem, we propose a multi-layer planner, under which a co-scheduling method for multi-agent with batch tasks and path planning in a continuous workspace is proposed. In the task allocation layer of the framework, a standard Genetic Algorithm (GA) is adopted, which optimizes the allocation of task sets, and minimizes the path lengths and the probability of conflicts. Secondly, an Improved Car-Like Conflict-Based Search (ICL-CBS) algorithm is presented as the conflict resolution layer to reduce the runtime. Finally, ICL-CBS and the Spatiotemporal Hybrid-State A* (SHA*) algorithm are jointly used to determine multi-agent paths in the path planning layer. We conduct experiments and compare our method with the baseline algorithm on random obstacles and practical scenarios. The results show that our method effectively improves the efficiency of multi-task completion, and alleviates the computational burden of underlying path planning. Specifically, our method has less runtime.

Keywords

• Multi-agent system
• Task allocation
• Multi-agent path finding
• Genetic algorithm