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.

What it 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.

What it doesn't 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.

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.

Real-world examples

• 1.Autonomous driving systems
• 2.Robotics navigation
• 3.Advanced Driver-Assistance Systems (ADAS)
• 4.Self-driving trucks