## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
It introduced the _asprilo_ framework for experimental studies of MAPF problems, and thus, presented several scenarios and step-based encodings. These encodings, however, cannot deal with weighted graph (grid) or robots of different sizes. Experimental evaluation of various encodings was presented but for rather short makespan (\(\leq\)40) that is well below the need of problems considered in this paper. The paper [45] exploited a step-based encoding of MAPF and described different improvements to the generic encoding that helps reducing the size of the grounding of a problem. It also utilized parallel plans and used clingo with multiple threads to compute solutions. Similar to [43], the experiments shown in this paper implies a much smaller size of maps that does not meet the need of our applications. The paper [44] employed an approach to solving TAPF problems. Focusing on the warehouse problem, the approach consists of three steps. First, it creates a simplified graph by combining nodes together. Second, it solves the problem on the simplified map. Third, it uses the solution in the second step as the skeleton to compute the final solution. This allows for the system to scale up quite well, being able to solve problems with more than 1,5 millions nodes. In our view, the path-based encoding of the present paper is similar in the spirit of this approach as it attempts to first creates multiple segments of the solution and then combining them to get the final solution. It is worth noting that all of the aforementioned approaches to solving MAPF are centralized. The paper [46] proposed a distributed ASP-based MAPF solver. More scalable and efficient distributed MAPF-solvers can be found in [47; 48; 49]. ## 7 Conclusions

A warehouse delivery problem consists of a set of robots that undertake delivery jobs within a warehouse as a response to events. A solution to this problem consists of a collision-free schedule of robot movements and actions that ensures that all delivery jobs are satisfied and each robot is returned to its docking station. The formulation and solution to this problem originates from an industrial collaboration between the two companies Dorabot, China, and Potassco Solutions, Germany. We report on the principles underlying formalizing and solving industrial-scale warehouse delivery problems, and in particular, we show how this problem can be efficiently solved through the application of ASP extended with difference constraints. ASP is used for conflict detection, routing and serialization, while difference constraints provide the scheduling. This separation of scheduling from the core ASP encoding is crucial to the efficient handling of fine-grained, sub-second, robot movements. The industrial scale of the warehouse delivery problem required taking a novel approach that diverges from related research in the field, such as solving the MAPF problem. Specifically, warehouses can be large and irregular shaped, making them unsuited to the purely grid-based layout that is commonly used in the literature. Instead, we model the warehouse as a weighted directed graph, with vertices representing the meaningful locations and navigation waypoints along the graph, while the weighted edges capture the minimum travel times between vertices. This allows us to adjust the granularity of modeling based on the usage of the different areas within the warehouse. For example, areas such as storage bins may require very fine-grained sub-second robot movements, while other areas, such as corridors, may only require coarse grained movements. By varying the density of the vertices in the graph we were able to capture these differing navigational requirements. Finally, to ensure collision-free navigation we allow vertices to be grouped into conflict zones, which can be fine-tuned based on the density requirements of the graph. Developing an efficient ASP-based solution to the warehouse delivery problem involved a multi-staged process.