Highways in Warehouse Multi-Agent Path Finding: A Case Study

Vojtěch Rybář, Pavel Surynek

2022

Abstract

Orchestrating warehouse sorting robots each transporting a single package from the conveyor belt to its destination is a NP-hard problem, often modeled Multi-agent path-finding (MAPF) where the environment is represented as a graph and robots as agents in vertices of the graph. However, in order to maintain the speed of operations in such a setup, sorting robots must be given a route to follow almost at the moment they obtain the package, so there is no time to perform difficult offline planning. Hence in this work, we are inspired by the approach of enriching conflict-based search (CBS) optimal MAPF algorithm by so-called highways that increase the speed of planning towards on-line operations. We investigate whether adding highways to the underlying graph will be enough to enforce global behaviour of a large number of robots that are controlled locally. If we succeed, the slow global planning step could be omitted without significant loss of performance.

Paper Citation

in Harvard Style

Rybář V. and Surynek P. (2022). Highways in Warehouse Multi-Agent Path Finding: A Case Study. In Proceedings of the 14th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART, ISBN 978-989-758-547-0, pages 274-281. DOI: 10.5220/0010845200003116

in Bibtex Style

@conference{icaart22,
author={Vojtěch Rybář and Pavel Surynek},
title={Highways in Warehouse Multi-Agent Path Finding: A Case Study},
booktitle={Proceedings of the 14th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,},
year={2022},
pages={274-281},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0010845200003116},
isbn={978-989-758-547-0},
}

in EndNote Style

TY - CONF

JO - Proceedings of the 14th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,
TI - Highways in Warehouse Multi-Agent Path Finding: A Case Study
SN - 978-989-758-547-0
AU - Rybář V.
AU - Surynek P.
PY - 2022
SP - 274
EP - 281
DO - 10.5220/0010845200003116