Multi-Agent Pickup-and-Delivery in a Distributed Baggage Handling System

Abstract

Baggage handling systems in airports are generally over-designed and only need to work at full capacity for a couple of months during their lifetime. To cope with varying demand, flexible baggage handling systems are being developed which use Automated Guided Vehicles (AGV) to handle a required capacity. These AGVs transport bags throughout the baggage hall by optimally getting assigned bags to pick up and finding optimal, conflict-free paths to their destinations. Generally, in such systems or other warehousing applications, these two processes, task assignment and path finding, are optimized separately. This research therefore proposes a hybrid online Multi-Agent Pickup-and-Delivery (MAPD) algorithm that jointly optimizes both. To achieve this, two existing algorithms have been combined. First, the Improved Distributed Market-Based algorithm (IDMB) is used to provide optimal task assignment by letting AGVs
communicate with each other. Second, to provide coordination, we implemented Enhanced Conflict-Based Search with Task Assignment (ECBS-TA). ECBS-TA, however, only lets AGVs attend to one task whereafter the algorithm stops. We therefore modified it into a lifelong version, letting the AGVs continuously move between pickup and drop-off points, to function as an MAPD algorithm. A Multi-Agent System (MAS) has been created and implemented in a conceptual baggage hall using highways to guide the AGVs. To analyse the hybrid MAPD algorithm, it has been compared to two other algorithms in which task assignment and path
finding are performed separately. The analysis indicated that the hybrid MAPD solution was able to deliver better operational capacity at the expense of scalability. Its runtimes were found to be higher, but overall still ensured real-time applicability.