## 2 Task Allocation and Dispatching
### Modified Shortest Travel Time First  
The Modified Shortest Travel Time First (MOD STTF) algorithm was originally proposed by [PERSON] and [PERSON] [20]. Therein, the STTF rule is employed, which was presented and investigated earlier by [PERSON] and [PERSON] [26]. By this rule, the priority for an assignment is given by the remaining distance an agent needs to travel in order to pick up a load, such that the lowest estimated travel time always wins the assignment.  
The modification that was later added (i.e., the MOD part in the name) revolves around the concept of uncommitted assignment; thereby agents could be assigned a task tentatively. They would then start to travel towards the assigned pick up location, but could be reassigned to other tasks or released by other agents, that become available later at a closer distance. The window during which this reassignment can occur is denoted as _uncommitted travel_. It is open until the remaining empty travel distance falls below a configurable threshold value, at which point the agent is then committed to the assignment. If this value is set to an infinite positive value we obtain the standard STTF dispatching (without reassignment) as a special case. If there are no constraints regarding navigation capabilities or computational performance to consider, it seems sensible to set it to zero to always allow reassignment in favour of a better match. This is intended to react to:  
* New loads or move requests that are added, which the agent could reach quicker,
* Or likewise other agents that become available, which are able to pick up and execute the task earlier than the agent that was originally (tentatively) assigned to it.  
According to the original formulation, if a new move request is added, one of the unassigned vehicles is assigned according to the STTF rule. The current task assignment shall be revisited for each agent individually whenever certain events occur, i.e.,  
* An agent completes its task or is released from an uncommitted task,
* An agent passes by certain locations while it is not committed to a task.  
While they acknowledge the performance could potentially be improved by more frequent reevaluation of the rule, they argue the benefit would not justify the additional complexity.  
As can be seen from the above described trigger mechanism for the re-evaluation of dispatching decisions, the method is designed around applications that fit an event-based model, e.g., due to navigation constraints imposed onto the agents. This assumption does not hold for our target application of an AMHS facilitating free-ranging autonomous mobile robots (AMR). Our target application uses a microscopic agent-based model. Therefore, the agents ability to change their path is not restricted to discrete locations, so the dispatching decisions do not need to be synchronised to these events either. Additionally, the exact point where a vehicle _\"travels through a station or intersection\"_ is hard to track in this environment and can not be detected precisely. Therefore, we opted to implement the triggering mechanism based on timer events, and reconsider the assignment for all unassigned and uncommitted agents simultaneously instead of asynchronously for individual agents. Thus, to apply the method to the domain of AMR, the algorithm is adapted based on two different formulations, the Stable Marriage Problem (SMP) and the Linear Sum Assignment Problem (LSAP). The following subsections present the specific methods.