## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
Figure 5 shows some example instances for a range of graph sizes. Note, the visualizations of benchmark graphs in Figures 5 and 6 were generated using Clingraph [14], [[https://github.com/potassco/clingraph](https://github.com/potassco/clingraph)]([https://github.com/potassco/clingraph](https://github.com/potassco/clingraph)) (accessed on 1 February 2023). The robots, pallet loading bays, and empty pallet storage locations were all placed on the south-most vertices, while the storage locations were placed on the north-most vertices. This ensured that each problem instance required routing over a substantial area of the graph. #### 5.1.2 Industry Benchmark

The industry benchmark consist of six distinct graphs handcrafted by domain experts at Dorabot, a provider of robotic and smart warehouse solutions. The graphs range in shape and size: 31 m \(\times\) 39 m (map0), 55 m \(\times\) 80 m (map1), 105 m \(\times\) 67 m (map2), 28 m \(\times\) 19 m (map3), 28 m \(\times\) 26 m (map4), and 430 m \(\times\) 85 m (map5). The graphs were provided in the OpenStreetMap (OSM) format, [[https://wiki.openstreetmap.org/wiki/OSM_XML](https://wiki.openstreetmap.org/wiki/OSM_XML)]([https://wiki.openstreetmap.org/wiki/OSM_XML](https://wiki.openstreetmap.org/wiki/OSM_XML)) (accessed on 1 February 2022), which we converted to our ASP graph fact format by converting the OSM edges to weighted edge/3 facts while assuming a constant velocity of 1 m/s. For example, an OSM edge that is 1.5 m in length is converted to an edge/3 fact with a weight of 1.5 s (which we represent as 1500 ms to remove the need for floating point numbers). For each graph the allowable loading bay, storage, empty pallet, and robot home vertices were indicated with OSM attributes. In order to support more robots, we added some graph variants that increased the number of robots by turning some unused storage vertices into robot home locations. The maximum allowable robot home vertices for each graph ranged from 2 to 20 robots. For each map-robot configuration we then generated instances (5 instances each) with differing number of jobs from 5 to 40 depending on the capacity of the graph. As previously described, each job consists of two pairs of dependant tasks that constitute a full pallet delivery and its corresponding replacement empty pallet

Figure 5: Example synthesized warehouse graphs. Circular green vertices indicate robot home locations. Square red vertices indicate full pallet pickup locations with a dotted blue arrow pointing to the corresponding storage location. Octagonal red vertices indicate empty pallet pickup locations with a dotted red arrow pointing to the delivery location for the corresponding empty pallet. delivery. The maximum job capacity for each graph varied, with one graph only supporting 15 jobs (60 distinct tasks), some supporting 20 jobs (80 distinct tasks), others supporting 30 jobs (120 distinct tasks), and finally two supporting 40 jobs (160 distinct tasks). Overall this produced 215 distinct problems instances. See Figure 6 for an example instance from each of the warehouse graphs. Figure 6: Example instances for the real-world warehouse graph. Circular green vertices indicate robot home locations. Square red vertices indicate full pallet pickup locations with a dotted blue arrow pointing to the corresponding storage location. Octagonal red vertices indicate empty pallet pickup locations with a dotted red arrow pointing to the delivery location for the corresponding empty pallet. Note, that at the maximum number of task and robots some of the generated problem instances are potentially larger than what might be required in a real-world setting. However, our intention in generating this wide range of problem instances, from those with a relative few number of tasks to those with a large number of tasks, has been to explore the performance limits of our encodings. ### Encodings Variants

In this sub-section we outline the different encoding variants used for the experiments.