Department of Computer Engineering

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.