# Free Space Detection Algorithm Using Object Tracking for Autonomous Vehicles
## 2 Materials and Methods
### Grid Map  
Figure 4a is the circular grid map method used in [1], and Figure 4b is the trapezoidal grid map method proposed in this paper. A grid map is applied to recognize the surrounding environment of the vehicle and detect free space. As shown in Figure 4a, the grid map used in the previous paper is in the shape of a circle. In the circular grid map, the center of the circle is fixed in absolute coordinates, the radius of the circle is determined according to the speed of the driving vehicle, and the position of the vehicle on the circle is determined according to the heading of the vehicle. As the speed of the vehicle increases, the radius  
Figure 1: DBSCAN clustering: (**a**) raw data of LidAR sensor that recognized two obstacles; (**b**) data with noise removed; (**c**) data of two clustered obstacles.  
Figure 2: Multi-layer clustering: (**a**) classification of data that recognize the same obstacle in each layer, and 3 single layers that recognize the same obstacle are shown in 3D; (**b**) representation of all 3D data on a 2D plane; (**c**) representation as square data for data simplification.  
increases, and the vehicle's position on the circle becomes opposite when moving forward and backward.  
The newly proposed trapezoidal grid map is shown in Figure 4b. The height of the trapezoid is determined according to the speed of the vehicle, and the lower and upper sides of the trapezoid are determined according to the vehicle heading. As the speed is high and the heading is small, the trapezoid has a long and narrow shape, and if the speed is low and the heading angle is large, the trapezoid shows a short and wide shape. The trapezoidal shape is used because it can reduce the use of unnecessary cells and reflects the vehicle yaw angle better than the circular shape.  
\[US=|HD|\times a+b_{1} \tag{1}\]  
\[BS=|HD|\times a+b_{2} \tag{2}\]  
\[H=V/c+d \tag{3}\]  
Equations (1)-(3) are equations for the proposed trapezoidal grid map generation. \(US\) is the upper side of the trapezoid(m), \(BS\) is the base of the trapezoid(m), and \(H\) is the height of the trapezoid(m). \(HD\) is the vehicle's heading (deg), and \(V\) is the vehicle's speed (kph).  
\(a\), \(b_{1}\), \(b_{2}\), \(c\), and \(d\) are constant values. a is a constant value for converting the heading value expressed in deg units to the base of the trapezoid in m units, \(b_{1}\) is the minimum value of the upper side of the trapezoid (\(US\)), and \(b_{2}\) is the minimum value of the base of the trapezoid (\(BS\)). When the heading of the vehicle is zero, the length of the upper side \(US\) of the trapezoid is \(b_{1}\), and the length of the base side \(BS\) is \(b_{2}\).  
\[R=V\times e+f \tag{4}\]  
Figure 4: **(a) Circular grid map of previous paper [1]. (b) Proposed trapezoidal grid map. R is the radius of the circle. US is the upper side of the trapezoid. BS is the base of the trapezoid. H is the height of the trapezoid.**  
Figure 3: Object tracking. Obstacle position change with time (t) change: (a) examples of obstacles when t = 1; (b) examples of obstacles when t = 2; (c) examples of obstacles when t = 3.  
Equation (4) is a simplified formula for generating a prototype grid map used in previous papers. \(R\) is the radius of the circle (m) and \(V\) is the speed of the vehicle (kph). \(e\) and \(f\) are constant values. \(e\) is a constant value for converting the vehicle speed value expressed in kph units to the radius of the circle in m units, and \(f\) is the minimum value of the radius (\(R\)). The length of the \(R\) is f when the vehicle speed is zero.