## 3 Double-Layer Corridor
### Dynamic-Layer Corridor  
Collision avoidance between robots is ensured by dynamic-layer corridors. Similar to the static-layer corridor, the minimum safe distance between the robots needs to be obtained. Let the position of the robot \(m\) and \(n\) be multivariate Gaussian random variables \(\mathbf{p}_{m,k}\sim\mathcal{N}(\widetilde{\mathbf{p}}_{m,k},\Sigma_{m,k})\), \(\mathbf{p}_{n,k}\sim\mathcal{N}(\widetilde{\mathbf{p}}_{n,k},\Sigma_{n,k})\). Then \(\mathbf{p}_{m,k}-\mathbf{p}_{n,k}\) is also a Gaussian random variable, i.e., \(\mathbf{p}_{m,k}-\mathbf{p}_{n,k}\sim\mathcal{N}(\widetilde{\mathbf{p}}_{m,k}-\widetilde {\mathbf{p}}_{n,k},\Sigma_{m,k}+\Sigma_{n,k})\). The collision probability is given by Equation (22). \[\mathcal{P}(\mathbf{x}_{m,k}\
otin C_{inter,mn,k})=\int_{\|p_{m}-q_{d}\|<d_{m}}p( \mathbf{p}_{m,k}-\mathbf{p}_{n,k})d(\mathbf{p}_{m,k}-\mathbf{p}_{n,k}) \tag{22}\]  
Similarly, according to Lemma 1 and Lemma 2, Equation (23) can be acquired. \[\eta_{mn,k}^{T}(\widetilde{\mathbf{p}}_{m,k}-\widetilde{\mathbf{p}}_{n,k})\geq d_{mn, k}+\Psi^{-1}(1-2\delta_{r})\sqrt{2\eta_{mn,k}^{T}(\Sigma_{m,k}+\Sigma_{n,k}) \eta_{mn,k}} \tag{23}\]  
In Equation (23), \(\eta_{mn,k}=(\widetilde{\mathbf{p}}_{m,k}-\widetilde{\mathbf{p}}_{n,k})/\|\widetilde {\mathbf{p}}_{m,k}-\widetilde{\mathbf{p}}_{n,k}\|\) and \(d_{mn}=d_{m}+d_{n}\). The minimum safe distance between robot \(m\) and robot \(n\) is acquired based on Equation (23). However, ignoring the velocity of the robots may result in the collision avoidance condition (23) not being satisfactory. Generally, the problem is addressed by the velocity obstacle method [12; 13; 14; 15]. However, the constraint obtained by the velocity obstacle method is nonconvex. [PERSON] et al. adopted the constant velocity assumption to predict short trajectories of robots and simplified the constraint by ensuring that the predicted trajectories do not collide [26]. Therefore, let \(\mathbf{v}_{m}\) and \(\mathbf{v}_{n}\) be the velocities of robot \(m\) and robot \(n\), respectively. After a very short time \(\Delta t_{s}\), the position of robot \(m\) is \(\mathbf{p}_{m}^{\prime}\sim\mathcal{N}(\widetilde{\mathbf{p}}_{m}^{\prime},\Sigma_{m})\), \(\widetilde{\mathbf{p}}_{m}^{\prime}=\widetilde{\mathbf{p}}_{m}+\mathbf{v}_{m}\Delta t_{s}\), and the position of robot \(n\) is \(\mathbf{p}_{n}^{\prime}\sim\mathcal{N}(\widetilde{\mathbf{p}}_{n}^{\prime},\Sigma_{n})\), \(\widetilde{\mathbf{p}}_{n}^{\prime}=\widetilde{\mathbf{p}}_{n}+\mathbf{v}_{n}\Delta t_{s}\). \(\mathbf{p}_{m}^{\prime}-\mathbf{p}_{n}^{\prime}\), which is needed to satisfy Equation (24). \[\eta_{mn,k}^{T}{}^{\prime}(\widetilde{\mathbf{p}}_{m,k}^{\prime}- \widetilde{\mathbf{p}}_{n,k}^{\prime})\geq d_{mn}+\Psi^{-1}(1-2\delta_{r})\sqrt{2 \eta_{mn,k}^{T}{}^{\prime}(\Sigma_{m,k}+\Sigma_{n,k})\eta_{mn,k}}^{\prime}, \tag{24}\] \[\eta_{mn}^{T}{}^{\prime}(\widetilde{\mathbf{p}}_{m}^{\prime}- \widetilde{\mathbf{p}}_{n}^{\prime})\geq d_{mn}+\Psi^{-1}(1-2\delta_{r})\sqrt{2 \eta_{mn}^{T}{}^{\prime}(\Sigma_{m}+\Sigma_{n})\eta_{mn}{}^{\prime}}\]  
In Equation (24), \(\eta_{mn,k}^{T}=(\widetilde{\mathbf{p}}_{m,k}^{\prime}-\widetilde{\mathbf{p}}_{n,k}^{ \prime})/\|\widetilde{\mathbf{p}}_{m,k}^{\prime}-\widetilde{\mathbf{p}}_{n,k}^{ \prime}\|\). Figure 2: The boundary of the static-layer corridor. The vertex \(ver\in V\) is the free grid of the map and the edge (\(ver_{i}\), \(ver_{j}\)) represents that the gird \(ver_{j}\) is a neighbor of the grid \(ver_{i}\). The ICBS planner works in two levels. At the high level, the constraint tree is built to resolve potential conflicts. At the low level, the hybrid A* planner is utilized to replace the A* planner. The kinematics of the robot is considered during the planning process and discrete paths are planned for robots with the constraints of the constraint tree. The procedure is as follows. First, the hybrid A* planner searches paths for each robot with no constraints. Second, the constraint tree checks for conflicts between the paths of every two robots.