## 2 Problem Statement
### Collision Avoidance Constraints  
Collision avoidance constraints are the most complicated part of the path planning problem. In this work, an occupancy grid map is used to represent the environment, and the collision between the planned path and the obstacles can be evaluated. Here, we present two types of collision avoidance constraints: a binary occupancy grid map-based constraint and a cost occupancy map-based collision avoidance preference. 1. Binary occupancy grid map. The binary occupancy grid map \(\mathbf{M}_{E}\) is a grid map that contains information about road edges, passable areas, and obstacles to represent the environment [20]. In a binary occupancy map, each grid contains the probability of believing that there is an obstacle or not. So, the possible states of each grid are \(0\)_for Free_ or \(1\)_for Occupied_. The grid occupancy of static obstacles can be directly projected onto the occupancy grid map by setting the corresponding grid to \(1\). Before projecting a dynamic obstacle onto a map, its grid occupancy should be evaluated. A simple and efficient time to collision (TTC) based approach is used to evaluate dynamic obstacles. For a given dynamic obstacle located at \(\mathbf{X}_{\mathbf{o}}=[x_{\mathbf{o}},\ y_{\mathbf{o}}]\) on the road, its motion velocity is \(v_{\mathbf{o}}\), velocity direction is \(\theta_{\mathbf{o}}\). Its location in the Frenet coordinate system is \(\mathbf{p}_{\mathbf{o}}(s_{\mathbf{o}},d_{\mathbf{o}})\). \(v\) represents the speed of the ego vehicle at the current time \(t_{0}\). If the TTC (time to collision) time between the vehicle and the obstacle is \(\Delta t\), \(\Delta t\) can be obtained through Equation (3):  
\[\Delta t=\frac{s_{\mathbf{o}}-s_{\mathbf{o}}-l_{\mathbf{o}}}{v-v_{\mathbf{o}}} \tag{3}\]  
where \(l_{o}\) is the distance from the obstacle location point to the closest point on the obstacle to the ego vehicle. If \(\Delta t\leq 0\), there will be no collision. All the dynamic obstacles on the road should be evaluated. Those \(\Delta t>0\) are considered threatening, and those with the minimum \(\Delta t\) are considered the most threatening one. \(\Delta t_{min}\) represents the minimum \(\Delta t\) from those obstacles with \(\Delta t>0\). All the locations of dynamic obstacles should be transformed into virtual locations at time \(t+\Delta t_{min}\) and then projected onto the occupancy grid map. The virtual obstacle location of the dynamic obstacle under the Cartesian system at time \(t+\Delta t_{min}\) can be calculated by  
\[\mathbf{X}_{\mathbf{\mathrm{o}}}^{\prime}=[x_{\mathrm{o}}+v_{\mathrm{o}}\Delta t_{min} \sin\theta_{\mathrm{o}},\;y_{\mathrm{o}}+v_{\mathrm{o}}\Delta t_{min}\cos\theta _{\mathrm{o}}] \tag{4}\]  
As shown in Figure 3b, the red square is the predicted location of virtual dynamic obstacle at time \(t_{0}+\Delta t_{min}\). After all the elements (road edges, static obstacles, dynamic obstacles, etc.) are projected onto the occupancy grid map, the environmental model is established. Similarly, the occupancy relationship brought about by the path can also be projected onto the occupancy map. The vehicle projection \(\mathbf{M}_{V}\left(t\right)\) on the planned path at time \(t\) can be obtained. The result of \(\parallel M_{E}\circ M_{V}\left(t\right)\parallel\left(\text{\textdegree is an operator that multiplies the elements at the corresponding position in two matrices) can be used for identifying whether the vehicle projection \(\mathbf{M}_{V}\left(t\right)\) on the planned path at time \(t\) intersects the non-passable area in \(\mathbf{M}_{E}\). If the result equals to zero, there will be no collision; otherwise, a collision occurs. 1. Cost occupancy map. The cost occupancy grid map \(\mathbf{M}_{C}\) is a grid map with different cost values, it is used for describing the cost value brought by multiple factors. An example of \(\mathbf{M}_{C}\) is shown in Figure 4[21]. It is quite like \(\mathbf{M}_{E}\).