# Free Space Detection Algorithm Using Object Tracking for Autonomous Vehicles
## 2 Materials and Methods
### Free Space Detection (FSD)  
As shown in Figure 5, the free space is represented by segmentation. The authors of [1] used a method to represent free space by extracting free space boundary cells from the grid map, as shown in Figure 5a, and simplifying the polygons connecting the cells. Since this paper focuses on classifying the free space area according to the behavior of obstacles, it would be more appropriate to express it in a divided way rather than a polygon, as shown in Figure 5b. Figure 5 shows the different free space detection methods. In the figure, the gray squares represent a vehicle in motion, and the three blue squares represent obstacles. The direction of movement of the obstacle is indicated by an arrow, and the obstacle drawn with a black rectangle instead of an arrow indicates that it is stationary. Figure 5a shows a free space detection method used in previous papers, representing free space with polygons. Figure 5b is the method proposed in this paper, which represents free space as a segment. Figure 5b shows the separated free space area in color. It has a different meaning depending on the segment color. Green is the space where you can drive because there are no obstacles in front, yellow is the space where you can drive with obstacles, orange is where the obstacle is stationary or you are driving at a lower speed than the ego vehicle, meaning it is impossible to drive, and red is the direction the obstacle is moving. Conversely, if the vehicle is traveling at a high speed, it is impossible to drive, and there is a collision risk. Even if it is detected as a free space, the free space is detected and classified to reflect that there is a space where driving is impossible. Segments are classified according to the perceived speed of the obstacle. If an obstacle is driving in the opposite direction to the vehicle being driven, there is a collision risk with the obstacle when creating a path and driving in this space, even if there is a free space in the direction of the obstacle. Conversely, if there is not enough free space due to the obstacle, but the obstacle is traveling in the same direction as the currently traveling vehicle and at a higher speed, this space will become a drivable space. As shown in Table 2 the free space is classified according to the driving possibility by dividing the cases where the behavior of the obstacles is different into four categories. In Table 2, the divided free space is represented by a total of four expressions: CA (completely able to drive), A (able to drive), UA (unable to drive), and CUA (completely unable to drive). Figure 5: Free space detection with polygon and free space detection with segments: (**a**) polygon method of previous paper; (**b**) proposed segmentation method. In Table 2, the relative speed of the obstacle (S) is the relative speed between the driving vehicle and the obstacle. First, if there are no obstacles in the segmented segment, the segment is divided into a completely drivable area (CA; completely able to drive). Second, if there is an obstacle in the segment, but the relative speed of the obstacle is greater than or equal to 0, it is classified as an able to drive area (A; able to drive). Even if there is an obstacle near the front, if the relative speed is greater than or equal to 0, the collision risk is low even if the vehicle continues driving without avoiding the obstacle. Third, when the relative speed of the obstacle is less than 0 and greater than the value obtained by multiplying the vehicle speed by -1, the area is classified as an unable to drive area (UA; unable to drive). This means that the obstacle and the vehicle are driving in the same direction, and the vehicle is driving faster than the obstacle. In this case, when driving in this segment, there is a collision risk with obstacles, meaning it is classified as an impossible area. Fourth, if the relative speed is less than the vehicle speed multiplied by \(-1\), it is classified as a completely unable to drive area (CUA; completely unable to drive).