Multi-Agent Path Finding Per Partes: Automatic Warehouses

Abstract

This thesis proposes a new partitioning method for the online Multi-Agent Pickup and Delivery (MAPD) problem in a large automatic warehouse. The method divides the workspace into independent regions and introduces transfer zones as controlled hand-off points for tasks spanning multiple regions. Agents operate within their assigned regions and transfer tasks via these designated transfer zones. This design limits the scope of path planning to local subproblems. The algorithm is implemented and tested in a realistic simulation. Experiments assess the feasibility and performance of the approach across a broad spectrum of team sizes and partition counts.

Tato diplomová práce představuje novou metodu rozdělení prostoru pro online problém Multi-Agent Pickup and Delivery (MAPD) ve velkém automatickém skladišti. Metoda rozčleňuje pracovní plochu na nezávislé regiony a zavádí transferové zóny jako kontrolované předávací body pro úkoly zasahující do více regionů. Agenti operují ve svých přidělených regionech a úkoly předávají prostřednictvím těchto zón. Tento návrh omezuje rozsah plánování tras na lokální podproblémy. Algoritmus byl implementován a otestován v realistické simulaci. Experimenty hodnotí proveditelnost a výkonnost navrženého přístupu v široké škále velikostí týmů a počtu regionů.