## 2 Task Allocation and Dispatching
### Linear Sum Assignment Problem  
The formulation as a Linear Sum Assignment Problem (LSAP) [37; 38] can be used as an alternative method to the SMP described above. The probability that vehicles have to cross their ways in order to pick up tasks nearby, intersecting with paths of other vehicles (c.f. Figure 1(a)), can be reduced with the LSAP formulation compared to SMP. We found this effect described in the literature (e.g., [PERSON], 1999). However, how much this effect actually influences the overall performance in a continuous AMR-based application is not well studied. Figure 1(b) provides numbers to the example. The matrix shows the distance measures for the combinations, that would be used as the cost function. The highlightedcombination would be picked by the algorithm according to the derived preference lists produced in Figure 1(c). According to the overall sum of travelled distance, the inverted combination would represent a (globally) more efficient solution to the problem.  
In fact, we found that other authors have used this approach before to address the AGV dispatching problem [21, 23, 24]. In particular, the approach presented by [PERSON] et al. [23] shares similarity to the one described below, in that they also formulate the problem as an assignment problem and use the same reassignment policy as defined with MOD STTF, i.e., to consider both _idle_ and _uncommitted_ vehicles eligible for dispatching.  
Here, we start with a cost matrix that is populated with the distances \(\tau_{ij}\) between the agents \(a_{i}\) and the move requests \(r_{j}\). The objective is to find the optimal assignment of agents to move requests, in order to minimise the overall sum of distance travelled. It is commonly formulated as a zero-one linear programming problem, e.g.,  
\[\min\sum_{i=1}^{n}\sum_{j=1}^{n}\tau_{ij}x_{ij}\qquad\quad\text{ with }\ x_{ij}\begin{cases}1&\text{if agent $i$ is assigned to move request $j$}\\ 0&\text{otherwise}\end{cases}\]  
such that  
\[\sum_{i=1}^{n}x_{ij}=1 j=1,2,\ldots,n\] \[\sum_{j=1}^{n}x_{ij}=1 i=1,2,\ldots,n\] \[x_{ij}\in\{0,1\} i,j=1,2,\ldots,n\]  
One popular solution approach is by using the so called _Hungarian method_, which is what most authors state to use. For our application, we found the implementation provided by the _scipy_ library [40] very useful, which claims to provide an implementation based on the _Jonker-Volgenant algorithm_[41].  
Additional flexibility or adjustments to the application scenario are commonly added by extending the function that is used for the population of the cost matrix. Thereby the approach can incorporate more complex constraints or requirements, such as due dates, load balancing etc.  
Figure 2: Example configuration that demonstrates navigation conflicts due to task assignment based on STTF rule (solid arrows). The assignment would favour matches based on individual preference, instead of globally optimal sum of travel times (dashed arrows). The cost matrix and preference lists associated to the example are given. The combination that results from the greedy assignment based on the STTF rule (highlighted) is globally suboptimal.  
We implemented the reassignment mechanism and the idle behaviour in the same way as described in the previous Section 2.2. That is, vehicles can be released or reassigned until their assignment is committed, which happens when they reach a specified threshold distance. We also employed the same approach to idle vehicle positioning as described there. That is, unassigned vehicles are sent to a central parking location to await future incoming move requests.