## 3 Warehouse Delivery Problem  
A warehouse consists of a physical space divided into meaningful locations; such as loading bays, storage bins, and robot parking stations. We model these locations as the vertices of a graph with the edges between vertices representing the paths that the robots can take. Robots navigate through the graph picking up items from one vertex and delivering them to another. The robots themselves have physical dimensions, and this imposes its own restrictions. We model these restrictions as conflict constraints, and ensure that only one robot can be located at a given vertex at a time. Additionally, some vertices are close enough together that a collision would occur if more than one of them were occupied. So we broaden our notion of conflict constraints to encompass groups of vertices. Beyond overly close but even unconnected vertices, it should be noted that a conflict group cannot simply be calculated from the weights of the paths that connect the vertices in the graph. Two vertices may be an adequate distance apart as determined by the weights assigned to the edges, but may nevertheless be part of a conflict group because of their close proximity within the physical warehouse.  
To make the warehouse delivery problem more concrete, we consider a simplified example warehouse in Figure 1. This warehouse consists of two robots \(r_{1}\) and \(r_{2}\), with their corresponding parking stations (i.e., their home vertices) \(h_{1}\) and \(h_{2}\), and two truck loading bays, \(l_{1}\) and \(l_{2}\). In our scenario, items are loaded and moved around on pallets. The robots must transport full pallets from the loading bays to their storage locations, but also deliver replacement empty pallets to the loading bays for future arrivals. The empty pallets are collected from the empty pallet location \(p_{1}\). Finally, there are two storage locations \(s_{1}\) and \(s_{2}\), which are in close proximity to each other and therefore cannot both be accessed by the robots at the same time.  
Each of these physical locations are the endpoints of a graph, which can then be reached via a set of waypoints. For example, the robot \(r_{1}\) that is located at \(h_{1}\) can reach the loading bay \(l_{2}\) by traveling along the path \(h_{1},w_{3},w_{4},w_{8},l_{2}\). The edges between the vertices are not equally spaced and we model the movement of robots in terms of the minimum time required to travel between connected vertices. Modelling edge weights as minimum travel times provides the flexibility to consider robots that can slow down where necessary. This can be important to bridge the abstraction divide between high-level task planning and low-level robot motion control; where a robot that can slow down between waypoints, rather than simply stopping at waypoints, can reduce the wear on parts and battery life. For the sake of the example, we consider a minimum travel time granularity of seconds while noting that our approach can deal with an arbitrary time granularity.  
Mirroring the physical restrictions on the storage locations, the connected waypoints \(w_{5}\) and \(w_{6}\), that connect to these storage location, are also in close proximity to each other and therefore must only be accessed by a single robot at a time.  
Finally, it should be noted that our example scenario in Figure 1 considers the warehouse graph as undirected, with robots being able to move in either direction along the edges. However, this is not a restriction of our approach, and it can be useful to model directed edges. Besides physical constraints that may enforce navigation in one direction only, directed edges can also be used by the warehouse designers to impose additional structural constraints. For example, the major thoroughfares of a warehouse could be divided into directed \"highways\" which could improve the solving performance while maintaining the efficiency of navigation.