# How Self-Driving Cars Find Clear Paths Between Objects > This patent describes a method for vehicles, especially self-driving ones, to use lidar data and a 3D grid to precisely identify open spaces between obstacles, helping them navigate safely. - **Patent:** US 10733420 - **Original title:** Systems and methods for free space inference to break apart clustered objects in vehicle perception systems - **Owner:** GM Global Technology Operations - **Granted:** 2020 - **Status:** Active - **Times cited:** 1 - **Field:** automotive, ai_ml, software, telecommunications ## What it does The patent details a system for a vehicle to find clear paths between objects using a lidar system and a 3D map called a "voxel grid." First, the vehicle's computer retrieves this voxel grid, which is like a stack of tiny cubes representing the space around the vehicle (Claim 1). Lidar beams are then traced through these cubes. Each cube, or "voxel," gets a score based on whether a lidar beam passed through it (a "first characteristic" like 'clear'), didn't pass through (a "second characteristic" like 'unknown'), or stopped at it (a "third characteristic" like 'occupied') (Claims 1, 4-5). The system then looks at vertical "columns" of these cubes and finds the longest continuous sequence of cubes that maximizes a score, indicating the most likely clear path (Claim 1). For example, if a column of voxels has clear spaces above occupied spaces, the system identifies the clear section. Finally, based on the length and height (elevation) of this clear section, each column is classified with a "free space level" and presented as an image (Claim 1), helping the vehicle understand where it can drive. ## What it does NOT cover - Does not cover systems that identify free space using only 2D data without a 3D voxel grid around the vehicle. - Does not cover methods that classify free space without specifically identifying a 'max subarray' of contiguous elements in a column. - Does not cover systems that don't assign scores to voxels based on lidar beam interaction (e.g., clear, unknown, occupied) within the voxel grid. - Does not cover methods that classify free space without considering both the identified subarray length for the column and the identified elevation for the column. - Does not cover systems that rely solely on radar or camera data for free space identification without using lidar beams as described. ## The clever bit The novelty lies in how it systematically scores individual 3D points (voxels) based on lidar interaction and then uses a "max subarray" algorithm on vertical columns to find the most significant contiguous free space. This allows for a robust determination of clear paths even when objects are clustered. ## Real-world examples 1. Autonomous driving systems 2. Robotics navigation 3. Advanced Driver-Assistance Systems (ADAS) 4. Self-driving trucks ## Why it matters This technology is crucial for autonomous vehicles to accurately perceive their surroundings and make safe driving decisions. By precisely identifying free space, a self-driving car can distinguish between closely packed objects, like parked cars or pedestrians, and find a safe path through them. This helps prevent collisions and enables smoother navigation in complex environments, directly impacting the reliability of self-driving systems. ## Frequently asked questions ### What does How Self-Driving Cars Find Clear Paths Between Objects cover? This patent describes a method for vehicles, especially self-driving ones, to use lidar data and a 3D grid to precisely identify open spaces between obstacles, helping them navigate safely. ### Who owns patent US 10733420? GM Global Technology Operations owns this patent, granted in 2020. ### When does this patent expire? This patent is expected to expire on November 21, 2037, when the invention enters the public domain. ### What is patent US 10733420 cited by? This patent has been cited by 1 later patents that build on its ideas. ### What problem does this patent solve? This technology is crucial for autonomous vehicles to accurately perceive their surroundings and make safe driving decisions. By precisely identifying free space, a self-driving car can distinguish between closely packed objects, like parked cars or pedestrians, and find a safe path through them. This helps prevent collisions and enables smoother navigation in complex environments, directly impacting the reliability of self-driving systems. ### What does this patent NOT cover? Does not cover systems that identify free space using only 2D data without a 3D voxel grid around the vehicle. **Full plain-English explainer:** https://patentbrief.org/patent/us/10733420/systems-and-methods-for-free-space-inference-to-break-apart-clustered-objects-in **Original patent:** https://patents.google.com/patent/US10733420 --- _Source: PatentBrief — https://patentbrief.org. Patent facts are from public records; the plain-English explanation is PatentBrief's._ ## Related patents Semantically similar inventions in the PatentBrief corpus: - [How Autonomous Cars Process Sensor Data for Driving](https://patentbrief.org/patent/us/20220161815/autonomous-vehicle-system) — Intel's 2020 patent describes a system for autonomous vehicles that cleans and standardizes data from various sensors before using it to perceive the environment and make driving decisions. - [How to Combine Wide-Angle LiDAR Depth with Standard Camera Images](https://patentbrief.org/patent/us/11543533/systems-and-methods-for-wide-angle-lidar-using-non-uniform-magnification-optics) — This patent describes a method for combining a wide-angle depth map from a LiDAR sensor, which has unevenly spaced pixels, with a standard camera image by first correcting the depth map's pixel distribution and then merging the two for a complete view. - [How Car Factories Calibrate LIDAR Sensors for Self-Driving Cars](https://patentbrief.org/patent/us/11391826/vehicle-lidar-sensor-calibration-system) — This patent describes a system for car factories to precisely adjust a vehicle's LIDAR sensors using special floor and wall targets, ensuring they accurately map the world for features like self-driving. - [How Car Safety Systems Turn Off When Sensors Disagree](https://patentbrief.org/patent/us/11702088/vehicular-driving-assist-system-with-sensor-offset-correction) — This patent describes a car safety system that uses both a camera and a radar sensor to detect objects, and if their detections don't match up, it can disable parts of the driving assistance for safety. - [How Autonomous Trucks Predict and Handle Tire Blowouts](https://patentbrief.org/patent/us/20210181737/prevention-detection-and-handling-of-the-tire-blowouts-on-autonomous-trucks) — This patent describes how an autonomous vehicle uses real-time sensor data, road conditions, and a dynamic model to predict tire failure and take corrective actions like adjusting its path or pulling over.