# Free Space Detection Algorithm Using Object Tracking for Autonomous Vehicles
## 1 Introduction  
In order for an autonomous vehicle to travel stably in various environments, it is important to recognize obstacles around the vehicle. In particular, in an environment in which lanes are not recognized while driving or in a road environment in which a precise map is not built, a path must be created by detecting an obstacle-free space, that is, a free space to generate a driving path. Many papers deal with free space detection. In previous papers, there are many cases of detecting free space using only the location information of obstacles. In this case, the behavior of the surrounding obstacles cannot be predicted, meaning there is a high possibility of creating an inefficient path in terms of safety. Assume that there is an obstacle traveling in the opposite lane of the traveling vehicle. In this environment, if the free space is detected in units of frames using only the location information, it will be detected as a free space that can travel up to the opposite lane area because it does not know which direction the obstacle is traveling in. In this case, there is a possibility of creating a driving route in the opposite lane, and the collision risk is increased. If it is possible to know at what speed and direction the surrounding obstacles are moving with respect to the driving vehicle, then more efficient path generation will be possible. In this paper, to solve this problem and increase the efficiency of path generation in free space, we propose a new algorithm for detecting free space based on the speed information of obstacles. The data were acquired using a LiDAR (light detection and ranging) sensor mounted on the actual vehicle, the speed of the obstacle was calculated through the object tracking process, and the free space was divided into four areas according to the speed. For comparison with the previous algorithm, a driving route was generated according to the free space detection result. By comparing the path generated by the previous method and the proposed method, it is confirmed that a more efficient path is generated with the proposed method. Recently, various studies on autonomous vehicles have been conducted in various fields. There are papers on various signal processing methods of LiDAR sensors mainlyused in autonomous vehicles [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21; 22; 23; 24]. Among them, there are many papers that presented research on free space sensing. Free space detection is being studied not only for the study of autonomous vehicle driving, but also in various fields such as the recognition of a parking space or the driving of an aircraft [25; 26; 27]. Among them, the research trends in the detection of free space in autonomous vehicles are as follows [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12]. Often, a camera or LiDAR sensor is used, or both sensors are used, to recognize the space and obstacles around the vehicle. These sensors recognize the surrounding space and detect a drivable free space free from obstacles. In this process, existing papers often detected empty space using only the location data of obstacles. [PERSON] et al. [1] used a laser scanner to recognize the surroundings and process signals in units of frames to understand the surrounding environment of a driving vehicle. Using these static data, the ground and obstacles are recognized, and the free space is expressed in a simplified polygonal form. [PERSON] et al. [2] used LiDAR and camera sensors to detect free space and speed bumps. This method detects based on static data and does not take into account the speed of obstacles. [PERSON] [3] used LiDAR sensor data to detect free space, in which free space was also detected without information about the speed of the obstacle. Many previous studies used static data without considering the speed of obstacles [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12]. Free space detection for autonomous driving must also be considered in dynamic environments.