Joint Optimization of Multi-Agent Task Allocation and Path Planning for Continuous Pickup and Delivery Tasks

Abstract

The multi-agent pickup and delivery problem is central to coordinating multiple agents in real-world applications such as warehouse automation, urban logistics, and robotic delivery networks, where efficient task assignment and pathfinding are vital for maximizing production efficiency. However, existing approaches often struggle to seamlessly integrate task allocation with path planning while also failing to address the demands of continuous pickup and delivery tasks, resulting in suboptimal performance and limited scalability in dynamic environments. To address these problems, we first introduce a novel task allocation approach, which constructs a cost matrix to satisfy pickup and delivery timing constraints for tasks and employs a Mixed-Integer Linear Programming (MILP) model to compute a task assignment matrix queue. Next, the CBS-TAPF framework is proposed, which constructs search forests for tasks and paths to address the joint optimization of task allocation and path planning. This framework is further extended to Continuous Multi-Agent Pickup and Delivery (CMAPD) tasks by dynamically updating the task allocation matrix queue, enhancing robustness and adaptability for real-world, sustained scenarios. Finally, through simulation and real-world experiments, we validated the effectiveness of the proposed methods. The experimental results demonstrate its superiority across diverse environments, ensuring robust performance in various operational scenarios.