## 2 The SOCP Control Policy  
A new method for solving collision and deadlock problems in multi-AGV systems is proposed in [2] by presenting its specification with proof of correctness. The method is adapted from the general approach introduced by [PERSON] [14]. In the following, for the sake of consistency, the essential features of the method will be presented, which will allow, on the one hand, to understand its principles and, on the other hand, to modify it in such a way that its efficiency can be improved for a specific type of use case. Consider a manufacturing facility in which a set of transport tasks \(T=\{t_{d}:1\leq d\leq R\}\) is performed by an AGV system denoted as \(V=\{v_{e}:1\leq e\leq N\}\). The transportation area in automated manufacturing plants can be partitioned into non-overlapping zones (squares) \(Z=\{z_{i}:1\leq i\leq M\}\). A function \(OC:Z\to V\cup\{0\}\) is introduced. A zone \(z_{i}\) is occupied by AGV \(v_{e}\) if \(OC(z_{i})=v_{e}\). Notation \(OC(z_{i})=0\) denotes that a zone \(z_{i}\) is empty (free). The zone \(z_{i}\) is sufficiently large that an AGV \(v_{e}\) can be entirely within it, and at most one AGV can be in each zone (square) at the same time. Furthermore, when performing an elementary transport operation denoted as \(z_{i}\to z_{i+1}\), an AGV cannot occupy more than these two zones simultaneously. The set of zones is divided into two subsets \(ZR\) and \(ZP\), each of them corresponding respectively to route generating elements and parking spaces. The route elements create a network of guide paths. A path is thus a finite sequence of transitions through neighboring zones. The transport task requires that each vehicle passes through a series of zones in a collision-free manner, starting at the parking place, transporting goods from the pick-up points to the delivery points, and finishing at the parking place. All AGVs in the system may not change the guide paths determined before the start of each new transport task. The guide path of the transportation system \(GP=z_{1},z_{2},..,z_{i},z_{i+1},..,z_{s}\) is a sequence of the \(ZR\) set of zones that consists of lanes and crossings. In addition, parking places are also used in the transportation system, but they are not elements of paths. Each parking place situated in a zone \(z_{u}\in ZP\) is neighboring at least one guide path zone \(z_{i}\in ZR\), and an AGV can move from its parking place to the neighboring zones and vice versa. Consider the deadlock phenomenon from the point of view of the lane types of the guided path. They are either unidirectional \(ZU=\{z_{j}:z_{i}\to z_{j}\to z_{k},i\
eq k,\{z_{i},z_{j},z_{k}\}\in ZR\}\) or bidirectional \(ZB=\{z_{b}:z_{b}\
otin ZU,1\leq b\leq|ZR|\}\). The unidirectional zone has only one predecessor and one successor (see Figure 1). Taking deadlock into account, it is important to point out an important difference between the two basic types of lanes. A unidirectional lane of a path is called deadlock-free because the execution of the elementary transportation operation \(z_{i}\to z_{i+1}\) in this lane cannot lead to deadlock. The bidirectional lanes do not have this property, so they are called deadlock risk lanes. Moreover, the same quality applies to intersections, so they are treated as deadlock risk zones and belong to the set \(ZB\). The guide path can be split into logical segments consisting of deadlock-free zones in which the AGV can move unidirectionally, and logical segments consisting of deadlock-risk zones that are bidirectional, e.g., in which the AGV can move in both directions. In addition, intersections are always deadlock-risk zones. All individual segments are assumed to be maximal (not contained within a larger segment), which means that they alternate in the path. Thus, the guide path \(GP=SS_{1},SS_{2},..,SS_{l},SS_{l+1},..,SS_{q}\) can be partitioned into alternating subsequences consisting of deadlock-free segments \(SS_{l}=\{z_{j}:z_{j}\in ZU\}\) and deadlock-risk segments \(SS_{l+1}=\{z_{j}:z_{j}\in ZB\}\).