Multilayer Graph Partitioning to Enable a Decentralized Path Planning for Large and Heterogeneous AGV Fleets

In recent years, automated guided vehicles (AGVs) have become more and more important in production facilities. Especially the increasing number of AGVs in a fleet poses various challenges for centralized path planning approaches. To be prepared for future requirements and to overcome these challenges, one feasible approach is the decentralization of the path planning. For this purpose, decentralization is applied to a graph-based path planning by splitting the planning problem into multiple subgraphs, such that the path planning for AGVs can be performed in parallel.In this paper we propose a solution that enables the splitting of graphs for heterogeneous AGV fleets into workload optimized domains. This contains a generic pipeline to prepare a multilayer graph to apply various partitioning algorithms. Additionally, this pipeline considers the balancing of routing requests and the spatial shapes of AGV fleets to optimize the domains for a decentralized path planning. Furthermore, we present a multilevel partitioning algorithm and an evaluation of workload optimized domain creation for heterogeneous AGV fleets.