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.
Original patent title: “Systems and methods for free space inference to break apart clustered objects in vehicle perception systems”
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. Granted to GM Global Technology Operations in 2020 with 23 claims and 1 forward citation, and it is expected to expire in 2037.
Coverage
What does this patent actually cover?
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 (ClaimclaimA numbered sentence at the end of a patent that legally defines what the inventor owns. The most important section.Read more → 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') (ClaimsclaimsThe numbered statements at the end of a patent that legally define what the inventor owns.Read more → 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.
The gap
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.
- 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.
These exclusions are unique to PatentBrief — derived from the actual claim language, not patent-office boilerplate.
Key facts
What made this novel
The noveltynoveltyThe requirement that an invention be different from anything publicly known before its priority date.Read more → 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.
The Patent Drawing
Schematic visualization of the patent's claim structure. Hand-drawn diagrams in progress for each landmark patent.
Where you've seen this
Real-world examples
Autonomous driving systems
Robotics navigation
Advanced Driver-Assistance Systems (ADAS)
Self-driving trucks
Why it matters
The bigger picture
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.
Filed
November 21, 2017
Granted
August 4, 2020
Market context
Who's building on this
Companies in this space
GM Global Technology Operations, the assigneeassigneeThe entity that owns the patent — usually the inventor's employer or a company.Read more →, is deeply involved in autonomous vehicle development through its Cruise subsidiary. Other major automotive companies like Waymo (Alphabet), Argo AI (Ford/VW), and Mobileye (Intel) are also developing similar perception systems for self-driving cars that rely on accurate free space detection.
Market impact
This patent contributes to the foundational technology for autonomous driving, enabling vehicles to better understand their environment. It helps to refine the perception stack, which is critical for safety and reliability, and could influence how self-driving systems are designed to interpret complex scenes with multiple, closely spaced objects. Accurate free space detection is a key enabler for wider adoption of self-driving features.
Claim 1 — Plain English
What this patent covers
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.
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.
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.
Patent timeline
Application submitted to the patent office
Application published, typically 18 months after filing
Patent officially issued
Patent enters public domain
PatentBrief Score
Impact Score
Early stage
Citation count
6/40
Early citations
Claim breadth
15/20
Broad claimsclaimsThe numbered statements at the end of a patent that legally define what the inventor owns.Read more →
Recency
10/20
Granted 5–10 years ago
Assignee scale
0/20
Independent or smaller assigneeassigneeThe entity that owns the patent — usually the inventor's employer or a company.Read more →
PatentBrief Impact Score — based on citation count, claim breadth, recency, and assignee scale. Not a legal assessment.
Heuristic Value Estimate
What this patent might be worth
$59K – $187K
Midpoint $117K · 11.2 yr remaining · industry ×1.5
Heuristic only — blends forward/backward citation counts, claim scope, time remaining, litigation history, and CPC-derived industry baseline. Real valuations need a professional appraisal.
Claim text not yet imported for this patent
The original legal language
Original claims
23 claims as filed with the patent office.
Concepts involved
Citations
Patent lineage
Cite this patent
Liu, M. (2020). How Self-Driving Cars Find Clear Paths Between Objects (U.S. Patent No. 10,733,420). U.S. Patent and Trademark Office. https://patentbrief.org/patent/us/10733420/systems-and-methods-for-free-space-inference-to-break-apart-clustered-objects-in
Auto-generated from the patent record. Double-check author order and the issue date against the official USPTO document before submitting.
Embed
Add this patent to your site
Drop this plain-English patent card into any blog post or article — free, no signup. It always links back to the full breakdown here.
<div data-patentlens-widget data-patent-number="US10733420"></div> <script src="https://patentbrief.org/embed.js" async></script>
Stay in the loop
Get a weekly digest of new patents.
One email per week. No spam. Unsubscribe anytime.
Keep exploring
Related patents you should know
US 4683195 · 1987
How to Make Billions of Copies of a DNA Segment
This patent describes the Polymerase Chain Reaction (PCR), a method to rapidly create many copies of a specific piece of DNA or RNA, enabling its detection and analysis.
Cetus Corp
US 8697359 · 2014
How to Edit Genes in Human Cells Using an Engineered CRISPR System
This patent describes an engineered CRISPR-Cas9 system for precisely cutting DNA in eukaryotic cells to change how genes work, opening the door for gene editing in complex organisms.
Massachusetts Institute of Technology
US 7657849 · 2010
How the iPhone's Slide-to-Unlock Gesture Works
Apple's 2010 patent describes unlocking a device by dragging a specific graphical image across the touchscreen along a predefined path, a gesture that became iconic with the original iPhone.
Apple Inc
US 4733665 · 1988
How Doctors Implant a Permanent Stent Using a Balloon
This patent describes the method for placing a permanent, expandable wire mesh tube inside a blood vessel or other body tube using a balloon-tipped catheter to widen it and keep it open.
Expandable Grafts Partnership
US 4965188 · 1990
How to Make Many Copies of a DNA Piece with Heat
This patent describes the Polymerase Chain Reaction (PCR) method, a technique to make millions of copies of a specific DNA segment using a heat-resistant enzyme and repeated temperature changes.
Cetus Corp
US 4235871 · 1980
How to Encapsulate Active Materials in Lipid Bubbles Efficiently
This patent describes a method for trapping biologically active substances inside tiny, multi-layered fat bubbles called liposomes, using a specific water-in-oil emulsion and gel-forming process to improve how much material gets captured.
Individual
Semantically similar
You might also find these interesting
US 20220161815 · Intel
How Autonomous Cars Process Sensor Data for Driving
US 11543533 · 2023 · Leddartech
How to Combine Wide-Angle LiDAR Depth with Standard Camera Images
US 11391826 · 2022 · Magna Electronics
How Car Factories Calibrate LIDAR Sensors for Self-Driving Cars
US 11702088 · 2023 · Magna Electronics
How Car Safety Systems Turn Off When Sensors Disagree
More to explore
More in Energy & Clean Tech
US RE49155 · 2022 · Halliburton Energy Services Inc
Electric or Natural Gas Blending and Pumping for Oil Wells
US 11436484 · 2022 · Nvidia Corp
Nvidia's Method for Training Self-Driving Car AI in Simulations
US 11840398 · 2023 · Titan Trailers Inc
How Titan Trailers Builds Stronger, Smoother Cargo Containers
US 2708656 · 1955
How the First Nuclear Reactor Works
New to patents?
Common Questions
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.
Same assignee
More from GM Global Technology Operations
Patent monitoring