## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
They can be classified into different groups based on their search techniques such as conflict-based search (CBS) or prioritized planning (PBS)) or the solution quality such as optimal, bounded-optimal, or suboptimal solutions of MAPF. Conflict-Based Search (CBS) is proposed in [21]. In this approach, the high-level search identifies constraints between plans of agents generated by a low-level \(A^{*}\) search. These conflicts are then resolved using the low-level searches for new plans for a subset of conflicted agents. CBSH2-RTC [19] is the state-of-the-art version of CBS and is well known for its performance compared to other optimal MAPF solvers. Enhanced CBS (EBCS) [28] relaxes the optimal criteria in CBS and returns suboptimal solutions whose costs are bounded by some user-defined factor by replacing the optimal search in different levels of CBS with focal search that uses an admissible heuristic for bounding the solution cost at the higher-level and another heuristic in guiding the search. EECBS [27] is an improved version of EBCS by replacing the high-level search in ECBS with Explicit Estimation Search [29] and uses online learning to guide the search. PBS [30] is a suboptimal MAPF solver that uses the idea of prioritized planning [31]. In this approach, agents are assigned different priorities and those with lower priority need to avoid having any conflict with higher-priority agents. PBS adopts a lazy exploration method that allows it to considers a total priority orderings. PBS is not complete solver. In recent years, several extensions of the MAPF problem have been introduced. These extensions focus on the assumptions made in the classical MAPF. For example, _combined Target Assignment and Path Finding (TAPF)_, where agents are partitioned into teams and each team is given a set of targets that they need to reach, is considered in [32]. Deadlines of tasks are addressed in [33]. MAPF problem with delay probabilities have been described by [34]. Lifelong MAPF is considered in [35]. The paper [36] investigates MAPF with continuous time, which removes the assumption that transitions between nodes are uniform. A SAT-based solver described in the paper [37] can also deal with this extension. SMT-based MAPF solver for MAPF with continuous time and geometric agents is described in [38]. Issueof unexpected delays of agents is considered in [39]. This paper introduces the notion of \(k\)-robust MAPF plan, which can still be successfully executed when at most \(k\) delays happen and investigate \(pk\)-robots MAPF plan, a probabilistic extension of \(k\)-robust MAPF plan. A somewhat more realistic version of MAPF, which allows agents to exchange packages and transfer payload, is considered by [40]. Discussion of the problems where robots have kinematic constraints can be found in the paper [41]. As we have mentioned above, the present paper addresses two assumptions in the classical MAPF problem, the disregard for robot size and the equal-distance between neighbors. Among these extensions, our work has some similarity to the _multi- agent pickup and delivery_ (MAPD) problem, introduced in [35], in which one agent might have to complete many pickup-then-delivery tasks in an online setting. The warehouse delivery problem considered in this paper requires each robot completes at most one pickup-then-delivery task. Its natural extension will be the MAPD problem and we leave it for the future. The present paper provides an ASP-based approach to solving an extension of MAPF problem and therefore is strongly related to ASP-based encodings proposed in [42; 43; 44; 45]. Among these works, reference [42] considers the classical MAPF, while reference [45] solves the sum-of-cost variant of MAPF, and [43; 44] tackles a more generalized MAPF problem. None of these works, however, consider robots with sizes that can block multiple vertices or graphs with non-uniform distances between vertices as in this paper. The paper [43] discussed the MAPF problem in the context of a warehouse with picking stations, shelfs, orders, and quantities.