## 1 Introduction  
A warehouse delivery problem consists of a set of robots that undertake delivery jobs as a response to events. A delivery consists of an item that is picked up at one location, then taken to and put down at another location. The robots are required to navigate autonomously along the paths of the warehouse while ensuring that they do not collide with each other. Finally, a robot is assigned to its own docking station where it is parked when not otherwise engaged. When tackling a warehouse delivery problem it is reasonable to consider a number of different types of deliveries that can take place within such a warehouse. For example, in our concrete application scenario, we consider the movement of storage pallets. In this scenario, robots deliver loaded and unloaded pallets. Items that arrive at a warehouse's loading bay are deposited onto pallets, and these loaded pallets must be delivered to specified storage locations. However, it is also necessary for a replacement empty pallet to be delivered to the loading bay for use with any new arriving items. In order to provide a general framework for solving these different delivery scenarios, we model a task as simply being an action that must be undertaken by a robot at a specific location within the warehouse. So the job of a robot delivering an item from one location to another, is modeled as consisting of two distinct, but dependent, tasks. Firstly, a task to navigate to a source location and pick up the item, and secondly, a task to navigate to a destination location and put down the item. The nature of these different tasks, and the dependencies between them, is captured within a task graph. In order to maintain generality, we model the physical layout of the warehouse as a directed graph, with vertices capturing various locations and waypoints within the warehouse. The vertices are connected by weighted edges, with the weight representing the minimum travel times between vertices. Solving the warehouse delivery problem can be divided into two interdependent components, one dealing with task allocation and sequencing and another handling robot routing and scheduling. From the task graph, the tasks are assigned to distinct robots and a task sequence is established for each robot. Once the task assignments and sequences are determined, the routes are calculated. The routes have to ensure that the robots visit their assigned task locations in the correct order, are capable of executing the task at said locations, and the robots' movements along these routes has to be scheduled to ensure there are no collisions. However, the routing and scheduling can in turn affect the satisfiability of the task assignment, and hence these parts cannot be considered in isolation. Of course, finding a satisfying solution to a problem is only one aspect of tackling a warehouse delivery problem. We also have to consider the quality of the solution as well as the time taken to find that solution. Firstly, we consider the traditional optimization criteria of makespan minimization. However, many warehouse delivery problems need to be solved in an online setting, with some degree of non-determinism, and where planning (or replanning) must occur as new items arrive at the warehouse. Such a setting requires plans to be computed in near real-time so that they can be immediately executed. Consequently, it can often be unrealistic to focus purely on finding optimal plans. Instead, a \"good enough\" solution found quickly may be preferable to waiting for the optimal solution to be calculated. With this in mind, we consider quality measures other than makespan minimization. In particular, we consider constraint-based criteria that can satisfy domain specific quality measures and lead to satisfactory, albeit non-optimal, solutions computed in a timely manner. This work originates from an industrial collaboration between the two companies Dorabot, China, and Potassco Solutions, Germany; it reports on the principles underlying a solution to solving real-world warehouse delivery problems.