Task Assignment and Path Planning for Capacitated Agents Engaged in Lifelong Pickup and Delivery Tasks

Date

2025-8-06

Author

Çilden, Evren

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

315
views

0
downloads

Cite This

A recent problem that originates from the domain of automated warehouses is the Multi-Agent Pickup and Delivery (MAPD), the lifelong version of the classical Multi-Agent Path Finding (MAPF) problem, where agents continuously receive tasks for picking up an item and delivering it to a predefined location. In the original version of the MAPD problem, agents are allowed to carry only one item at a time. This thesis studies MAPD for capacity-enhanced agents (MAPDC) that can collect or deliver packages on their routes. Two novel algorithms are proposed, which plan non-conflicting routes for capacitated agents engaged in continuous pickup and delivery tasks. This thesis argues that a combined task assignment and path planning solution can increase system throughput to a notable extent and explores task assignment strategies aiming to reduce the total time required to complete a series of pickup and delivery tasks. The thesis introduces heuristics for assigning tasks with destinations closer to agent's planned waypoints, thoroughly tested across diverse simulation setups. The experimental results demonstrate that improved task assignments can significantly enhance the solution quality for the MAPDC problem.

Subject Keywords

Multi-Agent Path Finding, Multi-Agent Pickup and Delivery, Heuristic Search, Task Assignment

URI

https://hdl.handle.net/11511/115547

Collections

Graduate School of Natural and Applied Sciences, Thesis