## 2 Preliminaries  
The layout consists of a fully known, grid-like workspace where AGVs carry out point-to-point transportation tasks. Hence, we may find there pick-up stations, drop-off stations, and parking stations, all of them linked by aisles. In turn, aisle intersections are known as crossing points. The following assumptions are considered:  
Figure 2: (**Top**): Motion in a sparse discretization. (**Bottom**): Motion in a dense discretization. **Assumption 1**. : _Every station is linked to a single crossing point of the grid through an aisle, and every crossing node is linked to, at most, one station._  
**Assumption 2**. : _There are, at least, as many parking stations as deployed AGVs._  
**Assumption 3**. : _Aisles may be traveled bi-directionally, but only one AGV is allowed at a time in an aisle._  
Generically, the workspace is discretized as in Figure 1: Each zone represents a physical area, and it may either contain a station or just be an intermediate point of an aisle. This discretized layout is then modeled as a graph \(G=(N,E)\), with nodes representing zones and edges representing links between adjacent zones. Namely, the node and edge sets are denoted, respectively, as \(N=\{N_{i},1\leq i\leq n_{N}\}\), \(n_{N}\) being the total number of nodes, and \(E=\{E_{ij}\); \(\forall N_{i},N_{j}\) adjacent\(\}\). In turn, \(R=\{R_{i}\), \(i=1\ldots n_{R}\}\) denotes the set of \(n_{R}\) AGVs, \(R_{i}\), deployed in the FMS. In this framework, a task is considered as a node-to-node displacement, understood as follows: Basic transportation jobs consist of moving loads from pick-up nodes to drop-off nodes. In the case an AGV currently at a parking slot undertakes a job, the assignment is divided into a minimum of two tasks: from the parking node to the pick-up node, and from the pick-up node to the drop-off node. Once this is completed, depending on the specific traffic control algorithm and the pending job list, a final move from the drop-off node to the parking slot might be ordered as well. In any case, once a task is assigned, a shortest route between the initial and final nodes is computed and delivered to the AGV. **Definition 1**. : _A task for AGV \(R_{i}\) consists of an ordered sequence of \(n_{R_{i}}\) adjacent nodes to be followed, i.e., \(T_{i}=\big{(}T_{ij}\big{)}_{1\leq j\leq n_{R_{i}}}\), where each \(T_{ij}\) stands for a specific graph node._  
**Remark 1**. : \(T_{ij}\) _is used to sequentially index the nodes of a task. As an example, if task \(T_{2}\) goes though nodes \(N_{6}\), \(N_{4}\), and \(N_{9}\), \(T_{2}=(T_{21},T_{22},T_{23})=(N_{6},N_{4},N_{9})\)._  
**Definition 2**. : _The states of \(R_{i}\) can be as follows: (a) idle (\(S_{i}=0\)): ready to accept a new task; (b) resuming (\(S_{i}=1\)): moving between two adjacent nodes; (c) waiting (\(S_{i}=2\)): \(R_{i}\) is at a node, waiting to be allocated to the next one; (d) resolving (\(S_{i}=3\)): undergoing a conflict resolution._  
AGV motion works on a permit basis as follows: \(R_{i}\) running task \(T_{i}\) and currently located at node \(T_{ij}\) requests permission to proceed to \(T_{ij+1}\). If granted, \(R_{i}\) leaves \(T_{ij}\), which becomes free, reserves \(T_{ij+1}\), and proceeds towards it. As conflicts may arise when AGVs compete for the same resources, zone control-based approaches grant permits according to the occupancy of shared routes and/or nodes. This yields the following definitions:  
**Definition 3**. : _The state of a node \(N_{i}\), denoted as \(SN_{i}\), is given by the number of AGVs occupying or reserving it._  
**Definition 4**. : _Assume that \(R_{i}\) is performing task \(T_{i}\) and it is currently located at node \(T_{ij}\). Its residual route is the sequence of nodes of \(T_{i}\) that remain to be visited, including \(T_{ij}\). Namely, \(L_{i}=\{T_{ik}\}_{j\leq k\leq n_{r}}\)._  
**Definition 5**. : _The shared route of \(R_{i}\) is the subset of nodes of \(L_{i}\) that also belong to the residual route of any other AGV.