Multi-Agent Pickup and Delivery with Task Deadlines

- Introducing deadlines into pickup and delivery tasks of multi-agent systems

Multi-agent systems arise in many real-world applications. There are many scenarios that tasks have pickup and delivery locations and individual deadlines so that the number of tasks completed by their deadlines should be maximized.

We adopt an integrated approach that conducts task assignment and path planning together, with high computational efficiency and effectiveness. The key features of our approach include:

1. Integrated: joint task assignment and path planning
2. Efficiency: enhanced by a number of bounding and pruning techniques
3. Effectiveness: verified through experimental evaluations

Previous work did not consider individual task deadlines, and task assignment and path planning were separated.

We tested our model in two simulated warehouses: a 21 x 35 grid with 50 agents, and a 33 x 46 grid with 180 agents.

To evaluate the performance of our framework for different emergency levels of tasks, we introduce a parameter phi. When phi increases, the task deadlines are looser, so that more tasks can be completed before deadlines theoretically. 

In the baseline algorithm, which is in dashed lines, we skip the agent selection phase and select the agent with the minimum flexibility directly. It can be observed that our framework has an improvement in the success ratio of tasks meeting deadlines in both warehouses compared to the baseline algorithm.

Improvement in runtime can also be observed compared to the baseline that does not apply bounding and pruning techniques.

Our framework can be applied to warehouse management, robot control, aircraft towing and mobile office service, where task deadline should be considered in the planning.

Warehouse management [https://unsplash.com/photos/sczNLg6rrhQ]

Robot control [https://unsplash.com/photos/DiTiYQx0mh4]