Evaluation Files: Multilayer Graph Partitioning for Enabling a Decentralized Path Planning for Large and Heterogeneous AGV Fleets

Project Description This repository contains the evaluation files from “Multilayer Graph Partitioning for Enabling a Decentralized Path Planning for Large and Heterogeneous AGV Fleets”. First, an overview of the folder structure is given. Followed by an Overview of the used parameter values from MAGPart. Afterward, additional background information for each topology is presented. Folder Structure Each evaluated topology is contained in a separate folder (e.g. /Topo-1, /Topo-1-2-3, ...). The topologies Topo-1, Topo-2, Topo-3 and Topo-4 are single-layer topologies, whereby the remaining topologies are multilayer topologies and are constructed by combinations of the single-layer topologies. For example, the topology Topo-1-2-3-4 results from combining the topologies Topo-1, Topo-2, Topo-3 and Topo-4. Each folder of one topology contains (1) the boxplots for each evaluation metric, (2) the results from applying different Graph Partitioning (GP) algorithms and (3) an overview of the frequencies and workloads of edges. The “deviation” boxplots correspond to DEV metric and the “routes_frequencies” boxplots correspond to the RF metric mentioned in our paper. Additionally, the boxplots from an overlap metric O ∈ [0,1] are listed for each topology. The overlap metric measures the intersection area between overlapping Bounding Boxes (BBs) divided by the intersection area between overlapping BBs from different domains. Thus, the metric is zero if no BBs from different domains overlap and one if all overlapping BBs correspond to different domains. A lower overlap value is desirable, to reduce the communication between domains. Since the metrics RF and DEV strive to maximize their value, we invert the value from the overlap metric to achieve a uniform representation. Note that the boxplots result from the averaged values from ten executions of our pipeline. For each applied GP algorithm (Girvan-Newman, Infomap, MAGPart, Metis, Modularity-Maximization and Spectral-Clustering) in our pipeline, the results are contained in corresponding folders. Each folder contains a PDF file, where the topology and the resulting domains are visualized. The domains are visualized in different colors. Additionally, the value of the quality function and the number of domains k is given in the filename. The number of domains is only given if the GP algorithm (i.e. Girvan-Newman, Metis, Spectral-Clustering) requires the number of domains as parameter. To achieve a comparable result, the values of the parameters max_v and max_d from MAGPart are set to infinity, since the sizes of the domains and the number of domains cannot be set for all GP algorithms. The values and description of all utilized parameters by MAGPart are given in the table below. MAGPart Parameters This table highlights all parameters used by MAGPart, while providing the used value, the value range and a description. Parameter Used Value Value Range Description Matching Algorithm Maximum Weight Matching Any matching algorithm The matching algorithm which is used in the coarsening phase to contract vertices. γ 0,6 R The resolution for computing the modularity in the quality function. λ 1,0 [0,1] The workload scaling factor to scale the workload in the pre-processing phase. θ 0,35 [0,1/2] The ratio of removed vertices before and after an iteration in the coarsening phase. max_d INF N The maximal number of allowed domains to be created. max_v INF N The maximal number of nodes to be added to a domain. Background of the topologies Topo-1: This topology and the routes of AGVs were created manually to represent the possible layout from a warehouse with three spatially separated areas. Topo-2: This topology models the area of a building used for testing purposes with AGVs. The routes of the AGVs were distributed manually to result in three Hotspots, which are not spatially separated. Topo-3: This topology models another possible layout from a warehouse. At the top left goods are received and transported between production, Storage and Shipping. Outgoing goods are transported to the bottom left. The routes of AGVs were created manually, such that AGVs mainly traverse in the upper or in the lower half of the topology. Few AGVs traverse between the top and lower half. Topo-4: This topology was modeled based on the layout from a warehouse. The topology's center contains a storage area, whereas the outer sections are used for loading ingoing and outgoing goods. Routes of the AGVs were sampled randomly with a bias to mainly pass through the top or the lower half of the topology. Topology Topo-1 Topo-2 Topo-3 Topo-4 Topo-2-3 Topo-2-4 Topo-1-2-3 Topo-1-2-3-4 Vertices 304 213 475 1845 688 2058 992 2837 Edges 515 431 1040 3976 1921 5555 2278 7882

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.