Vehicle operation using a dynamic occupancy grid

Methods for operating a vehicle in an environment include receiving light detection and ranging (LiDAR) data from a LiDAR of the vehicle. The LiDAR data represents objects located in the environment. A dynamic occupancy grid (DOG) is generated based on a semantic map. The DOG includes multiple grid cells. Each grid cell represents a portion of the environment. For each grid cell, a probability density function is generated based on the LiDAR data. The probability density function represents a probability that the portion of the environment represented by the grid cell is occupied by an object. A time-to-collision (TTC) of the vehicle and the object less than a threshold time is determined based on the probability density function. Responsive to determining that the TTC is less than the threshold time, a control circuit of the vehicle operates the vehicle to avoid a collision of the vehicle and the object.

FIELD OF THE INVENTION

This description relates generally to operation of vehicles and specifically to vehicle operation using a dynamic occupancy grid.

BACKGROUND

Operation of a vehicle from an initial location to a final destination often requires a user or a vehicle's decision-making system to select a route through a road network from the initial location to a final destination. The route may involve meeting objectives, such as not exceeding a maximum driving time. A complex route can require many decisions, making traditional algorithms for autonomous driving impractical.

SUMMARY

Methods for operating a vehicle in an environment include using one or more processors of the vehicle to receive light detection and ranging (LiDAR) data from one or more LiDARs of the vehicle. The LiDAR data represents one or more objects located in the environment. The one or more processors generate a dynamic occupancy grid (DOG) based on a semantic map of the environment. The DOG includes multiple grid cells. Each grid cell represents a portion of the environment. For each grid cell, the one or more processors generate a probability density function based on the LiDAR data. The probability density function represents a first probability that the portion of the environment represented by the grid cell is occupied by an object. The one or more processors determine that a time-to-collision (TTC) of the vehicle and the object is less than a threshold time based on the probability density function. Responsive to determining that the TTC is less than the threshold time, a control circuit of the vehicle operates the vehicle to avoid a collision of the vehicle and the object.

In another aspect, one or more processors of a vehicle generate a dynamic occupancy graph representing a drivable area along a trajectory of the vehicle. The dynamic occupancy graph includes at least two nodes and an edge connecting the two nodes. The two nodes represent two adjacent spatiotemporal locations of the drivable area. The one or more processors generate a particle distribution function of multiple particles based on LiDAR data received from one or more LiDARs of the vehicle. The multiple particles represent at least one object in the drivable area. The edge of the dynamic occupancy graph represents motion of the at least one object between the two adjacent spatiotemporal locations of the drivable area. The one or more processors determine a velocity of the object relative to the vehicle based on the particle distribution function. The one or more processors determine a TTC of the vehicle and the at least one object based on the particle distribution function. Responsive to determining that the TTC is less than a threshold time, the one or more processors transmit a collision warning to a control circuit of the vehicle to avoid a collision of the vehicle and the at least one object.

In another aspect, one or more processors of a vehicle receive sensor data from one or more sensors of the vehicle. The sensor data has a latency. Responsive to determining that the latency is less than a threshold latency, the one or more processors execute a cyclic redundancy check on the sensor data. Responsive to determining that the sensor data passes the cyclic redundancy check, the one or more processors determine a discrete, binary occupancy probability for each grid cell of a dynamic occupancy grid using an inverse sensor model of the one or more sensors based on the sensor data. The occupancy probability denotes whether a portion of an environment in which the vehicle is operating is occupied by an object. The one or more processors determine a particle density function based on the occupancy probability using a kinetic function. Responsive to determining that the particle density function indicates that a TTC between the vehicle and the object is less than a threshold TTC, the one or more processors transmit a deceleration request to a control circuit of the vehicle.

In another aspect, one or more processors of a vehicle operating in an environment generate a DOG based on first LIDAR data received from a LIDAR of the vehicle. A particle filter executed by the one or more processors extracts a waveform from the DOG. The waveform includes a variation of an intensity of the LiDAR data with a phase of light of the LiDAR. The one or more processors match the waveform against a library of waveforms extracted from historical LiDAR data reflected from one or more objects to identify that the first LiDAR data is reflected from a particular object of the one or more objects. The one or more processors update the waveform based on second LiDAR data received from the LiDAR of the vehicle after the first LiDAR data is received. The one or more processors determine a range rate of the vehicle and the particular object based on the updated waveform. A control circuit of the vehicle operates the vehicle to avoid a collision with the particular object based on the range rate of the vehicle and the particular object.

These and other aspects, features, and implementations can be expressed as methods, apparatus, systems, components, program products, means or steps for performing a function, and in other ways.

These and other aspects, features, and implementations will become apparent from the following descriptions, including the claims.

DETAILED DESCRIPTION

In the drawings, specific arrangements or orderings of schematic elements, such as those representing devices, modules, instruction blocks and data elements, are shown for ease of description. However, it should be understood by those skilled in the art that the specific ordering or arrangement of the schematic elements in the drawings is not meant to imply that a particular order or sequence of processing, or separation of processes, is required. Further, the inclusion of a schematic element in a drawing is not meant to imply that such element is required in all embodiments or that the features represented by such element may not be included in or combined with other elements in an embodiment.

Several features are described hereafter that can each be used independently of one another or with any combination of other features. However, any individual feature may not address any of the problems discussed above or might only address one of the problems discussed above. Some of the problems discussed above might not be fully addressed by any of the features described herein. Although headings are provided, information related to a particular heading, but not found in the section having that heading, may also be found elsewhere in this description. Embodiments are described herein according to the following outline:1. General Overview2. System Overview3. Autonomous Vehicle Architecture4. Autonomous Vehicle Inputs5. Autonomous Vehicle Planning6. Autonomous Vehicle Control7. Autonomous Vehicle Operation Using a dynamic occupancy grid (DOG)8. Processes for Autonomous Vehicle Operation Using a DOG
General Overview

This document presents methods, systems, and apparatuses for operating an autonomous vehicle (AV) using a dynamic occupancy grid (DOG). The DOG is a representation of the characteristics of objects and free space in the environment of the AV. The environment of the AV is represented as a grid or mesh that is referred to as the DOG. The DOG is a two-dimensional (2D) surface or a three-dimensional (3D) volume divided into a series of contiguous grid cells or grid cubes. Each grid cell or grid cube is assigned a unique identifier and used for spatial indexing of the environment of the AV. Spatial indexing refers to storing and querying data in a data structure that represents objects defined in a geometric space, for example, the environment of the AV. One or more objects and free space in the environment of the AV are modeled as a collection of particles in the DOG, similar to how fluids are modeled in field theory-based fluid dynamics. The particles are instantiated as representations of the objects and free space. The particles are tracked by updating time-varying particle density functions across the DOG, and the updated particle density functions are used to determine probabilities of occupancy of the grid cells or grid cubes. The AV is operated in accordance with the probabilities of occupancy of the grid cells or grid cubes. For example, the AV can determine a time-to-collision (TTC) with respect to an object modeled in the DOG and perform a maneuver to avoid the collision.

The advantages and benefits of tracking objects and free space using the embodiments described include tracking the objects at a higher resolution with a reduced computational complexity, compared to traditional methods that track individual grid cells. For example, tracking the time-varying particle density functions described can be performed with a reduced computational burden because there is no need to account for individual particles within a given grid cell of the DOG. Because particles can be defined and tracked for free space, the disclosed embodiments allow for tracking of free-space, which improves the navigation capabilities of AVs. Moreover, through the selection of parameters that describe the velocities and forces of objects, occluded or partially visible objects can be tracked by analyzing the corresponding particle density functions.

System Overview

FIG.1is a block diagram illustrating an example of an autonomous vehicle100having autonomous capability, in accordance with one or more embodiments.

As used herein, the term “autonomous capability” refers to a function, feature, or facility that enables a vehicle to be partially or fully operated without real-time human intervention, including without limitation fully autonomous vehicles, highly autonomous vehicles, and conditionally autonomous vehicles.

As used herein, an autonomous vehicle (AV) is a vehicle that possesses autonomous capability.

As used herein, “vehicle” includes means of transportation of goods or people. For example, cars, buses, trains, airplanes, drones, trucks, boats, ships, submersibles, dirigibles, etc. A driverless car is an example of a vehicle.

As used herein, “trajectory” refers to a path or route to operate an AV from a first spatiotemporal location to second spatiotemporal location. In an embodiment, the first spatiotemporal location is referred to as the initial or starting location and the second spatiotemporal location is referred to as the destination, final location, goal, goal position, or goal location. In some examples, a trajectory is made up of one or more segments (e.g., sections of road) and each segment is made up of one or more blocks (e.g., portions of a lane or intersection). In an embodiment, the spatiotemporal locations correspond to real world locations. For example, the spatiotemporal locations are pick up or drop-off locations to pick up or drop-off persons or goods.

As used herein, “sensor(s)” includes one or more hardware components that detect information about the environment surrounding the sensor. Some of the hardware components can include sensing components (e.g., image sensors, biometric sensors), transmitting and/or receiving components (e.g., laser or radio frequency wave transmitters and receivers), electronic components such as analog-to-digital converters, a data storage device (such as a RAM and/or a nonvolatile storage), software or firmware components and data processing components such as an ASIC (application-specific integrated circuit), a microprocessor and/or a microcontroller.

As used herein, a “scene description” is a data structure (e.g., list) or data stream that includes one or more classified or labeled objects detected by one or more sensors on the AV vehicle or provided by a source external to the AV.

As used herein, a “road” is a physical area that can be traversed by a vehicle, and may correspond to a named thoroughfare (e.g., city street, interstate freeway, etc.) or may correspond to an unnamed thoroughfare (e.g., a driveway in a house or office building, a section of a parking lot, a section of a vacant lot, a dirt path in a rural area, etc.). Because some vehicles (e.g., 4-wheel-drive pickup trucks, sport utility vehicles, etc.) are capable of traversing a variety of physical areas not specifically adapted for vehicle travel, a “road” may be a physical area not formally defined as a thoroughfare by any municipality or other governmental or administrative body.

As used herein, a “lane” is a portion of a road that can be traversed by a vehicle and may correspond to most or all of the space between lane markings, or may correspond to only some (e.g., less than 50%) of the space between lane markings. For example, a road having lane markings spaced far apart might accommodate two or more vehicles between the markings, such that one vehicle can pass the other without traversing the lane markings, and thus could be interpreted as having a lane narrower than the space between the lane markings or having two lanes between the lane markings. A lane could also be interpreted in the absence of lane markings. For example, a lane may be defined based on physical features of an environment, e.g., rocks and trees along a thoroughfare in a rural area.

As used herein, an AV system refers to the AV along with the array of hardware, software, stored data, and data generated in real-time that supports the operation of the AV. In an embodiment, the AV system is incorporated within the AV. In an embodiment, the AV system is spread across several locations. For example, some of the software of the AV system is implemented on a cloud computing environment similar to cloud computing environment300described below with respect toFIG.3.

In general, this document describes technologies applicable to any vehicles that have one or more autonomous capabilities including fully autonomous vehicles, highly autonomous vehicles, and conditionally autonomous vehicles, such as so-called Level 5, Level 4 and Level 3 vehicles, respectively (see SAE International's standard J3016: Taxonomy and Definitions for Terms Related to On-Road Motor Vehicle Automated Driving Systems, which is incorporated by reference in its entirety, for more details on the classification of levels of autonomy in vehicles). The technologies described in this document are also applicable to partially autonomous vehicles and driver assisted vehicles, such as so-called Level 2 and Level 1 vehicles (see SAE International's standard J3016: Taxonomy and Definitions for Terms Related to On-Road Motor Vehicle Automated Driving Systems). In an embodiment, one or more of the Level 1, 2, 3, 4 and 5 vehicle systems may automate certain vehicle operations (e.g., steering, braking, and using maps) under certain operating conditions based on processing of sensor inputs. The technologies described in this document can benefit vehicles in any levels, ranging from fully autonomous vehicles to human-operated vehicles.

Referring toFIG.1, an AV system120operates the AV100along a trajectory198through an environment190to a destination199(sometimes referred to as a final location) while avoiding objects (e.g., natural obstructions191, vehicles193, pedestrians192, cyclists, and other obstacles) and obeying rules of the road (e.g., rules of operation or driving preferences).

In an embodiment, the AV system120includes devices101that are instrumented to receive and act on operational commands from the computer processors146. In an embodiment, computing processors146are similar to the processor304described below in reference toFIG.3. Examples of devices101include a steering control102, brakes103, gears, accelerator pedal or other acceleration control mechanisms, windshield wipers, side-door locks, window controls, and turn-indicators.

In an embodiment, the AV system120includes sensors121for measuring or inferring properties of state or condition of the AV100, such as the AV's position, linear velocity and acceleration, angular velocity and acceleration, and heading (e.g., an orientation of the leading end of AV100). Example of sensors121are GNSS, inertial measurement units (IMU) that measure both vehicle linear accelerations and angular rates, wheel sensors for measuring or estimating wheel slip ratios, wheel brake pressure or braking torque sensors, engine torque or wheel torque sensors, and steering angle and angular rate sensors.

In an embodiment, the sensors121also include sensors for sensing or measuring properties of the AV's environment. For example, monocular or stereo video cameras122in the visible light, infrared or thermal (or both) spectra, LiDAR123, RADAR, ultrasonic sensors, time-of-flight (TOF) depth sensors, speed sensors, temperature sensors, humidity sensors, and precipitation sensors.

In an embodiment, the AV system120includes a data storage unit142and memory144for storing machine instructions associated with computer processors146or data collected by sensors121. In an embodiment, the data storage unit142is similar to the ROM308or storage device310described below in relation toFIG.3. In an embodiment, memory144is similar to the main memory306described below. In an embodiment, the data storage unit142and memory144store historical, real-time, and/or predictive information about the environment190. In an embodiment, the stored information includes maps, driving performance, traffic congestion updates or weather conditions. In an embodiment, data relating to the environment190is transmitted to the AV100via a communications channel from a remotely located database134.

In an embodiment, the AV system120includes communications devices140for communicating measured or inferred properties of other vehicles' states and conditions, such as positions, linear and angular velocities, linear and angular accelerations, and linear and angular headings to the AV100. These devices include Vehicle-to-Vehicle (V2V) and Vehicle-to-Infrastructure (V2I) communication devices and devices for wireless communications over point-to-point or ad hoc networks or both. In an embodiment, the communications devices140communicate across the electromagnetic spectrum (including radio and optical communications) or other media (e.g., air and acoustic media). A combination of Vehicle-to-Vehicle (V2V) Vehicle-to-Infrastructure (V2I) communication (and, in an embodiment, one or more other types of communication) is sometimes referred to as Vehicle-to-Everything (V2X) communication. V2X communication typically conforms to one or more communications standards for communication with, between, and among autonomous vehicles.

In an embodiment, the communication devices140include communication interfaces. For example, wired, wireless, WiMAX, Wi-Fi, Bluetooth, satellite, cellular, optical, near field, infrared, or radio interfaces. The communication interfaces transmit data from a remotely located database134to AV system120. In an embodiment, the remotely located database134is embedded in a cloud computing environment200as described inFIG.2. The communication interfaces140transmit data collected from sensors121or other data related to the operation of AV100to the remotely located database134. In an embodiment, communication interfaces140transmit information that relates to teleoperations to the AV100. In an embodiment, the AV100communicates with other remote (e.g., “cloud”) servers136.

In an embodiment, the remotely located database134also stores and transmits digital data (e.g., storing data such as road and street locations). Such data is stored on the memory144on the AV100, or transmitted to the AV100via a communications channel from the remotely located database134.

In an embodiment, the remotely located database134stores and transmits historical information about driving properties (e.g., speed and acceleration profiles) of vehicles that have previously traveled along trajectory198at similar times of day. In one implementation, such data may be stored on the memory144on the AV100, or transmitted to the AV100via a communications channel from the remotely located database134.

Computing devices146located on the AV100algorithmically generate control actions based on both real-time sensor data and prior information, allowing the AV system120to execute its autonomous driving capabilities.

In an embodiment, the AV system120includes computer peripherals132coupled to computing devices146for providing information and alerts to, and receiving input from, a user (e.g., an occupant or a remote user) of the AV100. In an embodiment, peripherals132are similar to the display312, input device314, and cursor controller316discussed below in reference toFIG.3. The coupling is wireless or wired. Any two or more of the interface devices may be integrated into a single device.

Example Cloud Computing Environment

FIG.2is a block diagram illustrating an example “cloud” computing environment, in accordance with one or more embodiments. Cloud computing is a model of service delivery for enabling convenient, on-demand network access to a shared pool of configurable computing resources (e.g. networks, network bandwidth, servers, processing, memory, storage, applications, virtual machines, and services). In typical cloud computing systems, one or more large cloud data centers house the machines used to deliver the services provided by the cloud. Referring now toFIG.2, the cloud computing environment200includes cloud data centers204a,204b, and204cthat are interconnected through the cloud202. Data centers204a,204b, and204cprovide cloud computing services to computer systems206a,206b,206c,206d,206e, and206fconnected to cloud202.

The cloud computing environment200includes one or more cloud data centers. In general, a cloud data center, for example the cloud data center204ashown inFIG.2, refers to the physical arrangement of servers that make up a cloud, for example the cloud202shown inFIG.2, or a particular portion of a cloud. For example, servers are physically arranged in the cloud datacenter into rooms, groups, rows, and racks. A cloud datacenter has one or more zones, which include one or more rooms of servers. Each room has one or more rows of servers, and each row includes one or more racks. Each rack includes one or more individual server nodes. In some implementation, servers in zones, rooms, racks, and/or rows are arranged into groups based on physical infrastructure requirements of the datacenter facility, which include power, energy, thermal, heat, and/or other requirements. In an embodiment, the server nodes are similar to the computer system described inFIG.3. The data center204ahas many computing systems distributed through many racks.

The cloud202includes cloud data centers204a,204b, and204calong with the network and networking resources (for example, networking equipment, nodes, routers, switches, and networking cables) that interconnect the cloud data centers204a,204b, and204cand help facilitate the computing systems'206a-faccess to cloud computing services. In an embodiment, the network represents any combination of one or more local networks, wide area networks, or internetworks coupled using wired or wireless links deployed using terrestrial or satellite connections. Data exchanged over the network, is transferred using any number of network layer protocols, such as Internet Protocol (IP), Multiprotocol Label Switching (MPLS), Asynchronous Transfer Mode (ATM), Frame Relay, etc. Furthermore, in embodiments where the network represents a combination of multiple sub-networks, different network layer protocols are used at each of the underlying sub-networks. In an embodiment, the network represents one or more interconnected internetworks, such as the public Internet.

The computing systems206a-for cloud computing services consumers are connected to the cloud202through network links and network adapters. In an embodiment, the computing systems206a-fare implemented as various computing devices, for example servers, desktops, laptops, tablet, smartphones, Internet of Things (IoT) devices, autonomous vehicles (including, cars, drones, shuttles, trains, buses, etc.) and consumer electronics. In an embodiment, the computing systems206a-fare implemented in or as a part of other systems.

Computer System

FIG.3is a block diagram illustrating a computer system300, in accordance with one or more embodiments. In an implementation, the computer system300is a special purpose computing device. The special-purpose computing device is hard-wired to perform the techniques or includes digital electronic devices such as one or more application-specific integrated circuits (ASICs) or field programmable gate arrays (FPGAs) that are persistently programmed to perform the techniques or may include one or more general purpose hardware processors programmed to perform the techniques pursuant to program instructions in firmware, memory, other storage, or a combination. Such special-purpose computing devices may also combine custom hard-wired logic, ASICs, or FPGAs with custom programming to accomplish the techniques. In various embodiments, the special-purpose computing devices are desktop computer systems, portable computer systems, handheld devices, network devices or any other device that incorporates hard-wired and/or program logic to implement the techniques.

In an embodiment, the computer system300includes a bus302or other communication mechanism for communicating information, and a hardware processor304coupled with a bus302for processing information. The hardware processor304is, for example, a general-purpose microprocessor. The computer system300also includes a main memory306, such as a random-access memory (RAM) or other dynamic storage device, coupled to the bus302for storing information and instructions to be executed by processor304. In one implementation, the main memory306is used for storing temporary variables or other intermediate information during execution of instructions to be executed by the processor304. Such instructions, when stored in non-transitory storage media accessible to the processor304, render the computer system300into a special-purpose machine that is customized to perform the operations specified in the instructions.

In an embodiment, the computer system300further includes a read only memory (ROM)308or other static storage device coupled to the bus302for storing static information and instructions for the processor304. A storage device310, such as a magnetic disk, optical disk, solid-state drive, or three-dimensional cross point memory is provided and coupled to the bus302for storing information and instructions.

In an embodiment, the computer system300is coupled via the bus302to a display312, such as a cathode ray tube (CRT), a liquid crystal display (LCD), plasma display, light emitting diode (LED) display, or an organic light emitting diode (OLED) display for displaying information to a computer user. An input device314, including alphanumeric and other keys, is coupled to bus302for communicating information and command selections to the processor304. Another type of user input device is a cursor controller316, such as a mouse, a trackball, a touch-enabled display, or cursor direction keys for communicating direction information and command selections to the processor304and for controlling cursor movement on the display312. This input device typically has two degrees of freedom in two axes, a first axis (e.g., x-axis) and a second axis (e.g., y-axis), that allows the device to specify positions in a plane.

According to one embodiment, the techniques herein are performed by the computer system300in response to the processor304executing one or more sequences of one or more instructions contained in the main memory306. Such instructions are read into the main memory306from another storage medium, such as the storage device310. Execution of the sequences of instructions contained in the main memory306causes the processor304to perform the process steps described herein. In alternative embodiments, hard-wired circuitry is used in place of or in combination with software instructions.

In an embodiment, various forms of media are involved in carrying one or more sequences of one or more instructions to the processor304for execution. For example, the instructions are initially carried on a magnetic disk or solid-state drive of a remote computer. The remote computer loads the instructions into its dynamic memory and send the instructions over a telephone line using a modem. A modem local to the computer system300receives the data on the telephone line and use an infrared transmitter to convert the data to an infrared signal. An infrared detector receives the data carried in the infrared signal and appropriate circuitry places the data on the bus302. The bus302carries the data to the main memory306, from which processor304retrieves and executes the instructions. The instructions received by the main memory306may optionally be stored on the storage device310either before or after execution by processor304.

The computer system300also includes a communication interface318coupled to the bus302. The communication interface318provides a two-way data communication coupling to a network link320that is connected to a local network322. For example, the communication interface318is an integrated service digital network (ISDN) card, cable modem, satellite modem, or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, the communication interface318is a local area network (LAN) card to provide a data communication connection to a compatible LAN. In some implementations, wireless links are also implemented. In any such implementation, the communication interface318sends and receives electrical, electromagnetic, or optical signals that carry digital data streams representing various types of information.

The network link320typically provides data communication through one or more networks to other data devices. For example, the network link320provides a connection through the local network322to a host computer324or to a cloud data center or equipment operated by an Internet Service Provider (ISP)326. The ISP326in turn provides data communication services through the world-wide packet data communication network now commonly referred to as the “Internet”328. The local network322and Internet328both use electrical, electromagnetic, or optical signals that carry digital data streams. The signals through the various networks and the signals on the network link320and through the communication interface318, which carry the digital data to and from the computer system300, are example forms of transmission media. In an embodiment, the network320contains the cloud202or a part of the cloud202described above.

The computer system300sends messages and receives data, including program code, through the network(s), the network link320, and the communication interface318. In an embodiment, the computer system300receives code for processing. The received code is executed by the processor304as it is received, and/or stored in storage device310, or other non-volatile storage for later execution.

Autonomous Vehicle Architecture

FIG.4is a block diagram illustrating an example architecture400for an autonomous vehicle (e.g., the AV100shown inFIG.1), in accordance with one or more embodiments. The architecture400includes a perception module402(sometimes referred to as a perception circuit), a planning module404(sometimes referred to as a planning circuit), a control module406(sometimes referred to as a control circuit), a localization module408(sometimes referred to as a localization circuit), and a database module410(sometimes referred to as a database circuit). Each module plays a role in the operation of the AV100. Together, the modules402,404,406,408, and410may be part of the AV system120shown inFIG.1. In an embodiment, any of the modules402,404,406,408, and410is a combination of computer software (e.g., executable code stored on a computer-readable medium) and computer hardware (e.g., one or more microprocessors, microcontrollers, application-specific integrated circuits [ASICs]), hardware memory devices, other types of integrated circuits, other types of computer hardware, or a combination of any or all of these things).

In use, the planning module404receives data representing a destination412and determines data representing a trajectory414(sometimes referred to as a route) that can be traveled by the AV100to reach (e.g., arrive at) the destination412. In order for the planning module404to determine the data representing the trajectory414, the planning module404receives data from the perception module402, the localization module408, and the database module410.

The perception module402identifies nearby physical objects using one or more sensors121, e.g., as also shown inFIG.1. The objects are classified (e.g., grouped into types such as pedestrian, bicycle, automobile, traffic sign, etc.) and a scene description including the classified objects416is provided to the planning module404.

The planning module404also receives data representing the AV position418from the localization module408. The localization module408determines the AV position by using data from the sensors121and data from the database module410(e.g., a geographic data) to calculate a position. For example, the localization module408uses data from a global navigation satellite system (GNSS) unit and geographic data to calculate a longitude and latitude of the AV. In an embodiment, data used by the localization module408includes high-precision maps of the roadway geometric properties, maps describing road network connectivity properties, maps describing roadway physical properties (such as traffic speed, traffic volume, the number of vehicular and cyclist traffic lanes, lane width, lane traffic directions, or lane marker types and locations, or combinations of them), and maps describing the spatial locations of road features such as crosswalks, traffic signs or other travel signals of various types.

The control module406receives the data representing the trajectory414and the data representing the AV position418and operates the control functions420a-c(e.g., steering, throttling, braking, ignition) of the AV in a manner that will cause the AV100to travel the trajectory414to the destination412. For example, if the trajectory414includes a left turn, the control module406will operate the control functions420a-cin a manner such that the steering angle of the steering function will cause the AV100to turn left and the throttling and braking will cause the AV100to pause and wait for passing pedestrians or vehicles before the turn is made.

Autonomous Vehicle Inputs

FIG.5is a block diagram illustrating an example of inputs502a-d(e.g., sensors121shown inFIG.1) and outputs504a-d(e.g., sensor data) that is used by the perception module402(FIG.4), in accordance with one or more embodiments. One input502ais a LiDAR (Light Detection and Ranging) system (e.g., LiDAR123shown inFIG.1). LiDAR is a technology that uses light (e.g., bursts of light such as infrared light) to obtain data about physical objects in its line of sight. A LiDAR system produces LiDAR data as output504a. For example, LiDAR data is collections of 3D or 2D points (also known as a point clouds) that are used to construct a representation of the environment190.

Another input502bis a RADAR system. RADAR is a technology that uses radio waves to obtain data about nearby physical objects. RADARs can obtain data about objects not within the line of sight of a LiDAR system. A RADAR system502bproduces RADAR data as output504b. For example, RADAR data are one or more radio frequency electromagnetic signals that are used to construct a representation of the environment190.

Another input502cis a camera system. A camera system uses one or more cameras (e.g., digital cameras using a light sensor such as a charge-coupled device [CCD]) to obtain information about nearby physical objects. A camera system produces camera data as output504c. Camera data often takes the form of image data (e.g., data in an image data format such as RAW, JPEG, PNG, etc.). In some examples, the camera system has multiple independent cameras, e.g., for the purpose of stereopsis (stereo vision), which enables the camera system to perceive depth. Although the objects perceived by the camera system are described here as “nearby,” this is relative to the AV. In use, the camera system may be configured to “see” objects far, e.g., up to a kilometer or more ahead of the AV. Accordingly, the camera system may have features such as sensors and lenses that are optimized for perceiving objects that are far away.

Another input502dis a traffic light detection (TLD) system. A TLD system uses one or more cameras to obtain information about traffic lights, street signs, and other physical objects that provide visual operation information. A TLD system produces TLD data as output504d. TLD data often takes the form of image data (e.g., data in an image data format such as RAW, JPEG, PNG, etc.). A TLD system differs from a system incorporating a camera in that a TLD system uses a camera with a wide field of view (e.g., using a wide-angle lens or a fish-eye lens) in order to obtain information about as many physical objects providing visual operation information as possible, so that the AV100has access to all relevant operation information provided by these objects. For example, the viewing angle of the TLD system may be about 120 degrees or more.

In an embodiment, outputs504a-dare combined using a sensor fusion technique. Thus, either the individual outputs504a-dare provided to other systems of the AV100(e.g., provided to a planning module404as shown inFIG.4), or the combined output can be provided to the other systems, either in the form of a single combined output or multiple combined outputs of the same type (e.g., using the same combination technique or combining the same outputs or both) or different types type (e.g., using different respective combination techniques or combining different respective outputs or both). In an embodiment, an early fusion technique is used. An early fusion technique is characterized by combining outputs before one or more data processing steps are applied to the combined output. In an embodiment, a late fusion technique is used. A late fusion technique is characterized by combining outputs after one or more data processing steps are applied to the individual outputs.

FIG.6is a block diagram illustrating an example of a LiDAR system602(e.g., the input502ashown inFIG.5), in accordance with one or more embodiments. The LiDAR system602emits light604a-cfrom a light emitter606(e.g., a laser transmitter). Light emitted by a LiDAR system is typically not in the visible spectrum; for example, infrared light is often used. Some of the light604bemitted encounters a physical object608(e.g., a vehicle) and reflects back to the LiDAR system602. (Light emitted from a LiDAR system typically does not penetrate physical objects, e.g., physical objects in solid form.) The LiDAR system602also has one or more light detectors610, which detect the reflected light. In an embodiment, one or more data processing systems associated with the LiDAR system generates an image612representing the field of view614of the LiDAR system. The image612includes information that represents the boundaries616of a physical object608. In this way, the image612is used to determine the boundaries616of one or more physical objects near an AV.

FIG.7is a block diagram illustrating the LiDAR system602in operation, in accordance with one or more embodiments. In the scenario shown in this figure, the AV100receives both camera system output504cin the form of an image702and LiDAR system output504ain the form of LiDAR data points704. In use, the data processing systems of the AV100compares the image702to the data points704. In particular, a physical object706identified in the image702is also identified among the data points704. In this way, the AV100perceives the boundaries of the physical object based on the contour and density of the data points704.

FIG.8is a block diagram illustrating the operation of the LiDAR system602in additional detail, in accordance with one or more embodiments. As described above, the AV100detects the boundary of a physical object based on characteristics of the data points detected by the LiDAR system602. As shown inFIG.8, a flat object, such as the ground802, will reflect light804a-demitted from a LiDAR system602in a consistent manner. Put another way, because the LiDAR system602emits light using consistent spacing, the ground802will reflect light back to the LiDAR system602with the same consistent spacing. As the AV100travels over the ground802, the LiDAR system602will continue to detect light reflected by the next valid ground point806if nothing is obstructing the road. However, if an object808obstructs the road, light804e-femitted by the LiDAR system602will be reflected from points810a-bin a manner inconsistent with the expected consistent manner. From this information, the AV100can determine that the object808is present.

Path Planning

FIG.9is a block diagram900illustrating of the relationships between inputs and outputs of a planning module404(e.g., as shown inFIG.4), in accordance with one or more embodiments. In general, the output of a planning module404is a route902from a start point904(e.g., source location or initial location), and an end point906(e.g., destination or final location). The route902is typically defined by one or more segments. For example, a segment is a distance to be traveled over at least a portion of a street, road, highway, driveway, or other physical area appropriate for automobile travel. In some examples, e.g., if the AV100is an off-road capable vehicle such as a four-wheel-drive (4WD) or all-wheel-drive (AWD) car, SUV, pick-up truck, or the like, the route902includes “off-road” segments such as unpaved paths or open fields.

In addition to the route902, a planning module also outputs lane-level route planning data908. The lane-level route planning data908is used to traverse segments of the route902based on conditions of the segment at a particular time. For example, if the route902includes a multi-lane highway, the lane-level route planning data908includes trajectory planning data910that the AV100can use to choose a lane among the multiple lanes, e.g., based on whether an exit is approaching, whether one or more of the lanes have other vehicles, or other factors that vary over the course of a few minutes or less. Similarly, in some implementations, the lane-level route planning data908includes speed constraints912specific to a segment of the route902. For example, if the segment includes pedestrians or un-expected traffic, the speed constraints912may limit the AV100to a travel speed slower than an expected speed, e.g., a speed based on speed limit data for the segment.

In an embodiment, the inputs to the planning module404includes database data914(e.g., from the database module410shown inFIG.4), current location data916(e.g., the AV position418shown inFIG.4), destination data918(e.g., for the destination412shown inFIG.4), and object data920(e.g., the classified objects416as perceived by the perception module402as shown inFIG.4). In an embodiment, the database data914includes rules used in planning. Rules are specified using a formal language, e.g., using Boolean logic. In any given situation encountered by the AV100, at least some of the rules will apply to the situation. A rule applies to a given situation if the rule has conditions that are met based on information available to the AV100, e.g., information about the surrounding environment. Rules can have priority. For example, a rule that says, “if the road is a freeway, move to the leftmost lane” can have a lower priority than “if the exit is approaching within a mile, move to the rightmost lane.”

FIG.10illustrates a directed graph1000used in path planning, e.g., by the planning module404(FIG.4), in accordance with one or more embodiments. In general, a directed graph1000like the one shown inFIG.10is used to determine a path between any start point1002and end point1004. In real-world terms, the distance separating the start point1002and end point1004may be relatively large (e.g., in two different metropolitan areas) or may be relatively small (e.g., two intersections abutting a city block or two lanes of a multi-lane road).

In an embodiment, the directed graph1000has nodes1006a-drepresenting different locations between the start point1002and the end point1004that could be occupied by an AV100. In some examples, e.g., when the start point1002and end point1004represent different metropolitan areas, the nodes1006a-drepresent segments of roads. In some examples, e.g., when the start point1002and the end point1004represent different locations on the same road, the nodes1006a-drepresent different positions on that road. In this way, the directed graph1000includes information at varying levels of granularity. In an embodiment, a directed graph having high granularity is also a subgraph of another directed graph having a larger scale. For example, a directed graph in which the start point1002and the end point1004are far away (e.g., many miles apart) has most of its information at a low granularity and is based on stored data, but also includes some high granularity information for the portion of the graph that represents physical locations in the field of view of the AV100.

The nodes1006a-dare distinct from objects1008a-bwhich cannot overlap with a node. In an embodiment, when granularity is low, the objects1008a-brepresent regions that cannot be traversed by automobile, e.g., areas that have no streets or roads. When granularity is high, the objects1008a-brepresent physical objects in the field of view of the AV100, e.g., other automobiles, pedestrians, or other entities with which the AV100cannot share physical space. In an embodiment, some or all of the objects1008a-bare static objects (e.g., an object that does not change position such as a street lamp or utility pole) or dynamic objects (e.g., an object that is capable of changing position such as a pedestrian or other car).

The nodes1006a-dare connected by edges1010a-c. If two nodes1006a-bare connected by an edge1010a, it is possible for an AV100to travel between one node1006aand the other node1006b, e.g., without having to travel to an intermediate node before arriving at the other node1006b. (When we refer to an AV100traveling between nodes, we mean that the AV100travels between the two physical positions represented by the respective nodes.) The edges1010a-care often bidirectional, in the sense that an AV100travels from a first node to a second node, or from the second node to the first node. In an embodiment, edges1010a-care unidirectional, in the sense that an AV100can travel from a first node to a second node, however the AV100cannot travel from the second node to the first node. Edges1010a-care unidirectional when they represent, for example, one-way streets, individual lanes of a street, road, or highway, or other features that can only be traversed in one direction due to legal or physical constraints.

In an embodiment, the planning module404uses the directed graph1000to identify a path1012made up of nodes and edges between the start point1002and end point1004.

An edge1010a-chas an associated cost1014a-b. The cost1014a-bis a value that represents the resources that will be expended if the AV100chooses that edge. A typical resource is time. For example, if one edge1010arepresents a physical distance that is twice that as another edge1010b, then the associated cost1014aof the first edge1010amay be twice the associated cost1014bof the second edge1010b. Other factors that affect time include expected traffic, number of intersections, speed limit, etc. Another typical resource is fuel economy. Two edges1010a-bmay represent the same physical distance, but one edge1010amay require more fuel than another edge1010b, e.g., because of road conditions, expected weather, etc.

When the planning module404identifies a path1012between the start point1002and end point1004, the planning module404typically chooses a path optimized for cost, e.g., the path that has the least total cost when the individual costs of the edges are added together.

Autonomous Vehicle Control

FIG.11is a block diagram1100illustrating the inputs and outputs of a control module406(e.g., as shown inFIG.4), in accordance with one or more embodiments. A control module operates in accordance with a controller1102which includes, for example, one or more processors (e.g., one or more computer processors such as microprocessors or microcontrollers or both) similar to processor304, short-term and/or long-term data storage (e.g., memory random-access memory or flash memory or both) similar to main memory306, ROM1308, and storage device210, and instructions stored in memory that carry out operations of the controller1102when the instructions are executed (e.g., by the one or more processors).

In an embodiment, the controller1102receives data representing a desired output1104. The desired output1104typically includes a velocity, e.g., a speed and a heading. The desired output1104can be based on, for example, data received from a planning module404(e.g., as shown inFIG.4). In accordance with the desired output1104, the controller1102produces data usable as a throttle input1106and a steering input1108. The throttle input1106represents the magnitude in which to engage the throttle (e.g., acceleration control) of an AV100, e.g., by engaging the steering pedal, or engaging another throttle control, to achieve the desired output1104. In some examples, the throttle input1106also includes data usable to engage the brake (e.g., deceleration control) of the AV100. The steering input1108represents a steering angle, e.g., the angle at which the steering control (e.g., steering wheel, steering angle actuator, or other functionality for controlling steering angle) of the AV should be positioned to achieve the desired output1104.

In an embodiment, the controller1102receives feedback that is used in adjusting the inputs provided to the throttle and steering. For example, if the AV100encounters a disturbance1110, such as a hill, the measured speed1112of the AV100is lowered below the desired output speed. In an embodiment, any measured output1114is provided to the controller1102so that the necessary adjustments are performed, e.g., based on the differential1113between the measured speed and desired output. The measured output1114includes measured position1116, measured velocity1118, (including speed and heading), measured acceleration1120, and other outputs measurable by sensors of the AV100.

In an embodiment, information about the disturbance1110is detected in advance, e.g., by a sensor such as a camera or LiDAR sensor, and provided to a predictive feedback module1122. The predictive feedback module1122then provides information to the controller1102that the controller1102can use to adjust accordingly. For example, if the sensors of the AV100detect (“see”) a hill, this information can be used by the controller1102to prepare to engage the throttle at the appropriate time to avoid significant deceleration.

FIG.12is a block diagram1200illustrating the inputs, outputs, and components of the controller1102, in accordance with one or more embodiments. The controller1102has a speed profiler1202which affects the operation of a throttle/brake controller1204. For example, the speed profiler1202instructs the throttle/brake controller1204to engage acceleration or engage deceleration using the throttle/brake1206depending on, e.g., feedback received by the controller1102and processed by the speed profiler1202.

The controller1102also has a lateral tracking controller1208which affects the operation of a steering controller1210. For example, the lateral tracking controller1208instructs the steering controller1204to adjust the position of the steering angle actuator1212depending on, e.g., feedback received by the controller1102and processed by the lateral tracking controller1208.

The controller1102receives several inputs used to determine how to control the throttle/brake1206and steering angle actuator1212. A planning module404provides information used by the controller1102, for example, to choose a heading when the AV100begins operation and to determine which road segment to traverse when the AV100reaches an intersection. A localization module408provides information to the controller1102describing the current location of the AV100, for example, so that the controller1102can determine if the AV100is at a location expected based on the manner in which the throttle/brake1206and steering angle actuator1212are being controlled. In an embodiment, the controller1102receives information from other inputs1214, e.g., information received from databases, computer networks, etc.

Dynamic Occupancy Grid System

FIG.13is a block diagram illustrating a discretized representation1300of an environment190of the AV100. The environment190and AV100are illustrated and described in more detail with reference toFIG.1. The discretized representation1300is referred to as a dynamic occupancy grid (DOG)1300. In the DOG1300, one or more particles represent an object608or free space in a particular grid cell or grid cube1310. The object608is illustrated and described in more detail with reference toFIG.6. For example, the grid cell or grid cube1305can represent free space (not occupied by an object).

The DOG1300includes a grid map with multiple individual grid cells1305,1310(also referred to as grid cubes when the DOG1300is a three-dimensional (3D) grid). Each grid cell1305,1310(grid cube) represents a unit area (or volume) of the environment190. The DOG1300is generated, updated, and processed by a DOG circuit of the AV100. In an embodiment, the DOG circuit is part of the perception module402, illustrated and described in more detail with reference toFIG.4. In another embodiment, the DOG circuit is part of a safety system (sometimes referred to as a RADAR and camera system) that is independent of the AV stack. The AV stack refers to the navigation system that includes the perception module402and planning module404. In this embodiment, the DOG circuit performs collision prediction independently of the navigation system. The DOG circuit is built using the components illustrated and described in more detail with reference toFIG.3.

In an embodiment, the DOG circuit is configured to update an occupancy probability of such individual grid cells1305,1310. The occupancy probabilities represent likelihoods of presence of one or more of the classified objects608in the individual grid cells1305,1310. An object608can be a natural obstruction191, a vehicle193, a pedestrian192, or another object. The natural obstruction191, a vehicle193, and pedestrian192are illustrated and described in more detail with reference toFIG.1. The occupancy state of each grid cell1305in the DOG1300can be computed, e.g., using a Bayesian filter to recursively combine new sensor measurements with a current estimate of a posterior probability for the corresponding grid cell1305. Example sensors121,122,123are illustrated and described in more detail with reference toFIG.1. The DOG1300is thus dynamically updated with time. The method assumes the environment190is dynamically changing, and the dynamics of the environment190is described by a Newtonian motion model. Therefore, the method estimates not only the occupancy, but also parameters of the dynamical model, such as, for example, velocities or forces.

The DOG1300divides the environment190of the AV100into a collection of individual grid cells1305,1310, and the probabilities of occupancy P1 of individual grid cells1305,1310are computed. In some implementations, the cells1305,1310are generated by dividing a semantic map (or a driving environment) based on a Cartesian grid, a polar coordinate system, a structured mesh, a block structured mesh, or an unstructured mesh. In some implementations, the cells1305,1310are generated by regularly or irregularly sampling a semantic map (or a driving environment), e.g., by an unstructured mesh where the grid cells1305,1310may be triangles, quadrilaterals, pentagons, hexagons, or any other polygon or a combination of various polygons for a 2D mesh. Similarly, the cell1305can be an irregular tetrahedron, a hexahedron, or any other polytope or a combination of polytopes for a 3-dimensional mesh.

In unstructured meshes the relation between the grid cells1305,1310is determined by common vertices that the cells1305,1310may share. For example, two triangles defined as two sets of vertex indices [a, b, c] and [b, c, e] share a common edge which is defined as a line segment between vertices b and c. In some implementations, the cells1305,1310can be described by a dynamic occupancy graph, where each cell1305corresponds to a node and two adjacent cells are characterized by an edge on the dynamic occupancy graph. An example dynamic occupancy graph1400is illustrated and described in more detail with reference toFIG.14. An edge may be assigned a value representing a dynamic interaction (described below) between the linked two nodes/cells. Each grid cell1305can be considered to be in one of two states—occupied or free.

Referring toFIG.13, the probability of a given cell1310being empty is denoted as p(□). The states of the grid cells1305,1310are updated based on sensor observations. This can be done, for example, using an inverse sensor model that assigns a discrete, binary occupancy probability pzt+1(ot+1|zt+1) to each grid cell based on a measurement zt+1at time t+1. The dynamic state of grid cells1305,1310can be addressed, for example, by modeling objects608such as vehicles193or pedestrians192as a collection of particles, akin to how fluid is modeled in field theory-based fluid dynamics. The term particles, as used herein, does not refer to physical units of matter. Rather, the particles represent a set of interacting software components, such that the software components together form a virtual representation of objects608(e.g., vehicles193, pedestrians192, etc.) and free space in the environment190of the AV100. In some implementations, each software component is data that represents an instantiation of a unit of a conceptual object.

Referring again toFIG.13, a magnified inset of the grid cell1310illustrates multiple particles1315representing the contents of the grid cell1110. Each of the particles1315can be associated with one or more parameters that represent the state of the corresponding particle1315. For example, the state of the particle1315can be represented by one or more of: a velocity (velocity along one or more of X direction, Y direction, Z direction), covariances associated with the multiple velocities, and a force acting on the particle1315. Such parameters can account for various dynamic characteristics of the particles1315. For example, a force parameter allows accounting for dynamics along a curved road or that of an accelerating vehicle.

In such field-theory based modeling, the number of particles1315in a particular grid cell1310, or the sum of particle weights in a particular grid cell1310can represent a measure for the occupancy probability of the corresponding grid cell1310. The technology described herein computes the probability of occupancy of the cells1305,1310by tracking statistics of particle density functions. In other words, the states of the grid cells1305,1310in this approach depend on one or more parameters of a joint distribution of the particles as they traverse the grid cells. An Eulerian solver or a Lagrangian solver can be used to determine the time-varying joint distributions by computing solutions to differential equations defined on the one or more particle-dynamics parameters obtained using one or more sensors121,122,123. The resulting updated particle density functions are used in conjunction with forward sensor models associated with the corresponding sensors121,122,123to generate predictions on probability of occupancy of various grid cells.

As described above, the probability of a given cell1310being empty is denoted as p(□). In addition, the technology described herein assumes that for two disjoint volumes □1and □2, the probabilities of their respective occupancies (or that of being empty) are uncorrelated. This can be represented as:
p(□1∪□2)=p(□1)p(□2)  (1)

From these assumptions, −log(p(□) is defined an additive measure on the state space, and a density function ƒ(x) can be defined as being associated with the measure as follows:
p(□)=exp(=∫□ƒ(x)dx)  (2)

This can be interpreted as the probability density function (sometimes referred to as a particle density function) of ∫Vƒ(x)dx number of identically distributed and independent particles inside a volume of the state space. Notably, because particles are considered to be identical, another inherent assumption of the technology described herein is that sensor measurements cannot be used to distinguish between particles. Rather, sensor measurements are defined as a probability of observation γ given a particle is located at x. This measurement can be referred to as a forward sensor model, and denoted as p(γ|x). Also, because sensor data cannot distinguish between particles and the measurements can be taken from only one particle, the probability of observation γ, given the entire volume V of a grid cell in the DOG1300is occupied (a situation that is denoted as ▪, for visual aid purposes) can be denoted as:
p(γ|▪)=∫Vp(γ|x)dx(3)

For autonomous vehicle applications, the particles represent objects608, free space etc., and are considered to be dynamic across the grid cells1305,1310of the DOG100. This is because the environment190for the AV100changes continuously, and the locations of particles with respect to the AV100vary with time. To account for the particle dynamics, the particle density function can be defined on a multi-dimensional phase space. For example, in some implementations, the particle density function can be defined as the function ƒ(t, x, v) in a time-space-velocity coordinate frame. This function can represent a probability density (sometimes referred to as particle density) of finding a particle at time t, at location x, and moving with velocity v. In some implementations, a probability density is empirically inferred from sensor data. In some implementations, a probability density modeled as a known probabilistic distribution (e.g., exponential family) or a mixture of two or more known probabilistic distributions. In some implementations, a probability density may not be modeled as a known distribution, but is purely characterized by sensor data.

In some implementations, other particle dynamic parameters such as a force acting on a particle, velocities along one or more additional directions, or covariances of multiple velocities can be used in the time-varying particle density functions. Because the particles are not stationary, the particle density function evolves over time, and the time-variation of the particle density function can be computed by determining solutions to a set of differential equations defined on the parameters that make up the particle density function. In some implementations, the evolution of the particle density function over time can be modeled using kinetic equations such as Boltzmann equations for the probability density function (sometimes referred to as a particle density function). For example, from fundamental principles of particle number conservation, the following differential equation can be defined:

By evaluating time derivative of positions and velocity, a Boltzmann partial differential equation can be derived as follows:

∂f∂t+v⁢∂f∂x+a⁢∂f∂v=0(5)
The dynamics described in the above equations is based on a Cartesian coordinate system, but it may be generalized on any coordinate systems. In some implementations, when describing the cells and their interactions by a graph, a gradient operator on the graph can be used to capture the Boltzmann equations. To reduce the computational complexity for real-time AV applications, the technology described herein uses an Eulerian solver that computes the solutions to the differential equation using numerical approximation. The Eulerian solver operates by approximating the differential equation as an ordinary differential equation (ODE) with known initial values of a set of parameters, and uses a forward Euler method to predict the values of the parameters at a future time point.

In an embodiment, the DOG circuit determines the particle density function at a particular time point tn. This can be done, for example, using sensor data received from the one or more sensors121,122,123. In some implementations, the sensor data can include RADAR and/or LiDAR data504ahaving information on one or more parameters pertaining to the particles. The LiDAR data504ais illustrated and described in more detail with reference toFIG.5. For example, the parameters can include one or more of a velocity of a particle1315along a particular direction as defined in accordance with a coordinate system governing the discretized representation of the environment190, a force acting on a particle1315, or a location of a particle1315. In some implementations, the DOG circuit determines one or more additional parameters based on the information received from the sensors121,122,123. For example, if information on velocities along multiple directions (e.g., an X direction and Y direction, and possibly also a Z direction, as defined in accordance with a Cartesian coordinate system) is received from the sensors121,122,123, the DOG circuit determines covariances of such velocities.

In some implementations, when the received sensor information includes velocity information along X and Y directions, the DOG circuit generates an observation vector γ that includes the following parameters associated with particle dynamics: the density ρ of particles in a grid cell, velocity components vx, and vy, along x and y directions, respectively, and the corresponding covariances σxx, σxy, and σyy. The covariance terms are used to account for uncertainties in the velocity terms. For notational purposes, the particle density function is represented in this document as ƒ(t, x, v), ƒ(t, x(t), v(t)), as denoted above, or ƒ(t, x, y, v) for two-dimensional DOGS. In an embodiment, a polar coordinate system may be used, and the notation of the density distribution becomes ƒ(t, r, v), where r is the radius of location (x, y).

The observation can then be provided to an Eulerian solver or a Lagrangian solver to determine solutions to differential equations defined on the one or more parameters. The Eulerian solver can include one or more processing devices that are programmed to compute a numerical solution to the differential equations using forward Euler methods. This can include predicting the variations in the different parameters for a future time point tn+1. The Eulerian solver approach reduces the computational complexity compared to traditional processes and generate images with higher quality (e.g., resolution) and dynamic range.

The Eulerian solver predicts the evolution of the various parameters of the particles and provides such predicted values to the DOG circuit for time point tn+1. The DOG circuit calculates the predicted distribution of the particle density function, and generates an updated version of the particle density function ƒ(t, x, y, v). For notational ease though, the particle density function may also represented in this document as ƒ(t, x, v). The particle density function calculated by the DOG circuit can be provided via a feedback loop to the DOG circuit to update the prior distribution.

The DOG circuit also determines the likelihood of a particle location being occupied at the future time point tn+1, given the current observation vector γ (also referred to as the probability of observation, γ). This is calculated as:

p⁡(•x,y❘γ)=p⁡(γ❘•x,y)p⁡(γ❘•x,y)·f⁡(t,x,y,v)(6)
Here, the term

p⁡(γ❘•x,y)p⁡(γ❘•x,y)
represents a forward sensor model and represents the probability of observation γ given that point (x, y) is occupied by an object with velocity v. The forward sensor models for various sensor modalities (e.g., LiDAR, RADAR, vision, and other sensor modalities) can be computed from annotated ground-truth data. The ground truth data can be collected, for example, by collecting the statistics of observations and occupancy information considering both as independent random samples. Such forward sensor models are used by the DOG circuit to condition the joint distribution of the parameters with respect to occupancy. In some implementations, the measurements and occupancy information are drawn from substantially continuous distributions. Such continuous distributions can be approximated by recording histograms by placing observation samples into appropriately spaced bins, and fitting an analytic density function to the discrete histogram.

In some implementations, forward sensor models can also be configured to detect fault conditions in the sensors121,122,123. For example, the ground truth data obtained from such models can be used to determine if the received sensor data is outside a range of expected values for that particular sensor by a threshold amount, and/or if the received data is inconsistent with data received for other sensors. If the sensor data from a particular sensor is determined to be out of the range by the threshold amount, a fault condition may be determined/flagged for that sensor, and the corresponding sensor inputs may be ignored until resolution of the fault condition.

The output generated by the DOG circuit is therefore a Bayesian estimate for the particle density function ƒ(t, x, y, v). In this function, t∈0+, represents time, (x, y) represents the location in a two-dimensional space W, and v∈2is the velocity vector at (x, y). This output may be queried in various ways across the DOG1300. For example, a form of a query is to compute an expected number of particles in a region of phase space plus time:
(Ω⊂0+×W×2).  (7)

In some implementations, this can be computed as:
[N]=∫Ωƒ(t,x,v)dtdxdv(8)

Under the assumptions that particles are distributed identically and independently and the number of particles is very large, this yields that the probability of the region of phase space plus time being empty is given by:
P(empty(Ω))=exp(−[N]=exp(−∫Ωƒ(t,x,v)dtdxdv)  (9)
The technology described herein can therefore be used in tracking not just objects608, but also free space. The planning module404of the AV100uses this information to determine where the AV100can be steered to. The planning module404is illustrated and described in more detail with reference toFIG.4. In some implementations, this information, possibly in conjunction with the information on the objects608that the AV100must steer away from, can improve the control of the AV100, for example, by providing multiple possibilities.

In some implementations, one or more additional quantities can be defined to obtain more information from the particle density function. For example, for a set of points {pi}i=0n, a closed polygon can be defined as a set of points in the world W such that a ray originating at any of this points intersects an odd number of segments:
{[pi=p(i+1)mod n)}i=0n−1(10)
This polygon can be denoted as P. In some implementations, a polygon can represent a grid cell of a discretized representation of an AV environment190. However, notably, because the definition of the polygon is not dependent on any particular grid, the technology described herein can be implemented in a grid-agnostic manner. Further, it may be useful in some cases to define a conditional distribution ƒ(t0, x, v) representing the particle density function at a specific point in time, an unconditional distribution ρ(t, x)=2ƒ(t, x, v) that represents the particle density function in space and time regardless of their velocities, and a combination of both. Such quantities can be used to determine various quantities of interest for the operation of the AV100. For example, the probability of a polygon P being occupied at a particular time to can be computed as:
1−exp(−∫Pρ(t0,x)dx).  (11)

When considering multiple velocities (e.g., velocities along different directions), this can be extended, by defining another polygon Pvin the vector space of velocities. Under this extension the probability of an object608occupying a polygon Pxand travelling with a velocity from Pvis given by:
1−exp(−∫Px×Pvƒ(t0,x,v)dxdv).  (12)

In another example, various other probabilities, such as the probabilities of a space being occupied during a time interval can be computed using the particle density functions described above. Such probabilities, together with labeling on the particles can be used to identify various classified objects608including inanimate objects, persons, and free space, and how they move over time through the discretized representation of AV environment190.

Prior to tracking the particle density functions over the DOG1300, the DOG circuit can define and label particles (pedestrians192, vehicles193, or free space), and assign an initial probability to individual grid cells. In some implementations, each cell is initially assumed to be occupied (e.g., via an assignment of a high probability of occupancy), and later updated based on sensor data. In some implementations, particles can be assigned different colors based on whether they represent objects608(with additional color coding to differentiate between vehicles193or pedestrians192) or free space. In some implementations, particles can be defined, labeled, and updated as interactive software components such as described in the document, Nuss et. al, “A Random Finite Set Approach for Dynamic Occupancy Grid Maps with Real-Time Application,” International Journal of Robotics Research, Volume: 37 issue: 8, page(s): 841-866—the contents of which are incorporated herein by reference.

In an embodiment, the DOG circuit receives LiDAR data504afrom one or more LiDARs502aof the AV100. The LiDAR data504aand LiDAR502aare illustrated and described in more detail with reference toFIG.5. The LiDAR data504arepresents one or more objects608located in the environment190. The DOG circuit generates the DOG1300based on a semantic map of the environment190. The DOG1300includes multiple grid cells1305,1310. Each grid cell1310represents a portion of the environment190. In an embodiment, each grid cell1310is one of a two-dimensional polygon or a three-dimensional polyhedron. In an embodiment, a length of each edge of the grid cell1310is in a range from 1 cm to 1 m. Each 2D grid cell or 3D grid cube is tracked on a centimeter to meter level, such that computation complexity is not exceeded.

In an embodiment, generating the DOG1300includes segregating a semantic map of the environment190into the grid cells1305,1310based on the Cartesian coordinate system. For example, 3D grid cubes are generated by dividing a map (or a driving environment) based on a Cartesian coordinate system or a polar coordinate system. In an embodiment, generating the DOG1300includes segregating the semantic map of the environment190into the grid cells1305,1310based on the polar coordinate system. In an embodiment, the DOG1300is generated based on regular sampling of the semantic map of the environment190. For example, the 3D grid cubes are generated by regularly or irregularly sampling a map or a driving environment. In an embodiment, the DOG1300is generated based on irregular sampling of the semantic map of the environment190.

The classified objects608, as perceived by the perception module402, are positioned on the DOG1300. The DOG1300can include a grid map with multiple individual cubes that each represents a unit volume of the environment190. In an embodiment, generating the DOG1300includes allocating a portion of the LiDAR data504ato more than one grid cell1310. The portion of the LiDAR data504acorresponds to a particular object, say vehicle193. Each object is typically larger than a single grid cube and is distributed over more than one grid cube.

For each grid cell1310, the DOG circuit generates a probability density function (sometimes referred to as a particle density function) based on the LiDAR data504a. The probability density function represents a probability P1 that the portion of the environment190represented by the grid cell1310is occupied by the particular object (vehicle193). The LiDAR point cloud data504ais thus received and distributed over the grid cells1305,1310. The vehicle193is tracked (in the form of a probability density function) as the received LiDAR data504amoves between the grid cells1305,1310over time. The probability density function can further represent a probability P0 that the grid cell1310is free of the vehicle193.

In an embodiment, the DOG circuit updates the DOG1300using recursive Bayesian analysis on the LiDAR data504aover time. The DOG circuit thus continuously or periodically updates occupancy probabilities, P0 and P1, for each 3D grid cube1310(or 2D grid cell) based on LiDAR returns. Pre-computed template waveforms generated using historical LiDAR data can be stored and compared to observed DOG waveforms to determine characteristics of the environment190that the AV100is navigating, as illustrated and described in more detail with reference toFIGS.15and16.

In an embodiment, generating the probability density function includes: responsive to determining that an intensity of a portion of the LiDAR data504a(LiDAR signal intensity) corresponding to the vehicle193is greater than a threshold intensity, identifying the grid cell1310representing the portion of the environment190. In an embodiment, generating the probability density function further includes comprises adjusting the probability P1 that the portion of the environment190is occupied by the vehicle193to greater than zero. When a single LiDAR return is received having intensity above a threshold intensity, the corresponding grid cube1310is identified and set to a value, “occupied”. The LiDAR signal intensity can be measured in units of power or optical power, such as Watts or Joules. In an embodiments, the LiDAR signal intensity is normalized by time (e.g., per second) or by space (e.g., per cm2). In another embodiment, units are not used because the DOG circuit analyzes the relative LiDAR signal levels with respect to noise (corresponding to empty space) or normalizes the LiDAR intensity distribution as a probability density function.

In an embodiment, the probability density function further represents a conditional probability B2 that a portion of the environment190represented by a grid cell (e.g., grid cell1305) will remain occupied by the vehicle193, given that the portion of the environment190represented by the grid cell1305is occupied by the vehicle193. In an embodiment, the probability density function further represents a conditional probability B1 that the portion of the environment190represented by the grid cell1305will remain free of the vehicle193, given that the portion of the environment193represented by the grid cell1305is free of the vehicle193. Thus, if a grid cube1305is free of objects, the probability it will remain free is B1. The probability it will be occupied is 1-B1. Similarly if a grid cube1305is occupied, the probability it will remained occupied is B2.

In an embodiment, the probability that the portion of the environment190represented by the grid cell1310is occupied by the vehicle193is denoted by P1. The DOG circuit generates a second probability density function based on the LiDAR data504a. The second probability density function represents a second probability p2 that the portion of the environment190represented by the grid cell1310is occupied by a pedestrian192. The one or more objects608include the pedestrian192. Each grid cell1310can thus have a different probability distribution for pedestrians192, vehicles193, or other objects. In an embodiment, the LiDAR data504aincludes noise. The DOG circuit determines that the probability P1 for a particular grid cell1310is greater than zero. The DOG circuit determines that the probability P1 for neighboring grid cells of the particular grid cell1310is zero. The LiDAR data504acan thus include noise that forms part of the DOG1300. Thus, one cell1310can be occupied while others around it are free. If nothing is in the surrounding cubes, the occupied cube is set to free to filter the noise out. In an embodiment, the LiDAR data504aincludes noise. The DOG circuit adjusts the probability P1 for the particular grid cell1310to zero.

In an embodiment, generating the probability density function includes transforming the LiDAR data504ainto the probability P1 that the portion of the environment190represented by the grid cell1310is occupied by the vehicle193using a Fourier transform. The LiDAR data504ais measured in the time domain and the grid cells1305,1310are generated in the space domain. The Fourier transform is used to convert the time-domain LiDAR data504ato the space domain (DOG1300)). In an embodiment, generating the probability density function includes recursively combining the LiDAR data504awith a posterior probability that the portion of the environment190represented by the grid cell1310is occupied by the vehicle193using a Bayesian filter. The occupancy state of each grid cell1310is computed using a Bayesian filter to recursively combine new LiDAR measurements with the current estimate of the posterior probability of the grid cell1310.

The DOG circuit determines that a time-to-collision (TTC) of the AV100and the vehicle193is less than a threshold time based on the probability density function. Responsive to determining that the TTC is less than the threshold time, the control module406operates the AV100to avoid a collision of the AV100and the vehicle193. The control module406is illustrated and described in more detail with reference toFIG.4.

In an embodiment, the DOG circuit receives sensor data from one or more sensors121,122,123of the AV100. The sensor data has an associated latency from the time of capture (that can be encoded into the data) as it is transmitted from the sensors121,122,123to the DOG circuit (optionally through the perception module402). Responsive to determining that the latency is less than a threshold latency, the DOG circuit executes a cyclic redundancy check on the sensor data. For example, the DOG circuit checks the quality of the sensor data signals, such as timing (e.g., latency) of the path data or a protocol of the path data. The path data refers to sensor data describing the physical path the AV100is traversing. If the DOG circuit determines that the sensor data is of poor quality, the DOG circuit can send a “failed sensor data” signal to an arbiter module of a safety system or to the AV stack (AV navigation system).

In an embodiment, the DOG1300includes multiple particles. Each particle has a state. In an embodiment, the state includes a first velocity of the particle in an X direction, a second velocity of the particle in a Y direction, and a third velocity of the particle in a Z direction. For example, each of the particles in the DOG1300is associated with parameters that represent the state of the corresponding particle. The state of the particle can be represented by one or more of a velocity along one or more of an X direction, a Y direction, or a Z direction. In an embodiment, the state further includes a covariance associated with the first velocity, the second velocity, and the third velocity. In an embodiment, the state further includes a force acting on the particle. Such parameters can account for various dynamic characteristics of the particles. In an embodiment, the force represents a motion of the AV100along a curved road. For example, a force parameter allows accounting for dynamics along a curved road or that of an accelerating AV100. In an embodiment, the force represents an acceleration of the AV100.

Responsive to determining that the sensor data passes the cyclic redundancy check, the DOG circuit determines a discrete, binary (0or1) occupancy probability for each grid cell1305,1310using an inverse sensor model of the one or more sensors121,122,123based on the sensor data. The binary occupancy probability denotes whether a portion of the environment190in which the AV100is operating is occupied by an object608. The inverse sensor model assigns a discrete, binary occupancy probability to each grid cell1305,1310based on a measurement at time t. In an embodiment, responsive to determining the occupancy probability of each grid cell1305,1310, the DOG circuit determines a motion of the object608based on a change in the occupancy probability. For example, if a grid cell1305,1310represents an occupied portion of the environment190, it will have a stronger LiDAR signal associated with the grid cell1305,1310. If the grid cell1305,1310(portion of the environment190) is not occupied, it will have a weaker LiDAR signal, mainly noise. Thus, the DOG circuit not only determines whether the grid cell1305,1310is occupied, but also infers movement of the occupying object608. First, the DOG circuit determines whether the portion of the environment190is occupied, then it infers motion.

The DOG circuit determines the occupied cell rate (0or1) and a confidence. In an embodiment, the DOG circuit determines an occupancy confidence corresponding to the occupancy probability for each grid cell1305,1310of the DOG1300. In an embodiment, the occupancy confidence is determined based on at least one of a maturity, a flicker, a LiDAR return intensity, or fusion metrics of the sensor data. For example, a collision warning or brake deceleration is triggered based upon a confidence higher than a (calibratible) threshold that includes factors such as maturity, flicker, return intensity, and other fusion metrics. In an embodiment, transmitting the deceleration request is responsive to the occupancy confidence being greater than a threshold occupancy confidence.

The DOG circuit determines a particle density function based on the occupancy probability using a kinetic function. For example, the DOG circuit determines the cube occupancy cumulative distribution function. Evolution of the particle density function over time can be modeled using kinetic equations such as Boltzmann equations for the probability density function. In an embodiment, the particle density function is determined across a multi-dimensional phase space. In an embodiment, the particle density function is determined in a time-space-velocity coordinate frame. This function can represent a probability density of finding a particle at time t, at location1, and moving with velocity v.

Responsive to determining that the particle density function indicates that a TTC between the AV100and the object608is less than a threshold TTC, the DOG circuit transmits a deceleration request to a control circuit406of the AV100. For example, the DOG circuit calculates an associated TTC distribution using a constant velocity model. The DOG circuit calculates a mean TTC and a minimum TTC at a threshold confidence level. The DOG circuit determines whether to command a collision warning and a brake deceleration based on the TTC. Upon detecting a collision threat, the DOG circuit transmits a deceleration request based upon the cell occupancy probability, for example, trigger based upon a probability greater than a (calibratible) threshold probability. In an embodiment, a deceleration of the deceleration request increases as the TTC decreases. For example, the deceleration requests are greater for shorter TTCs. In an embodiment, a deceleration of the deceleration request increases as a speed of the AV100increases. For example, the deceleration requests are to be greater for greater AV100speeds.

FIG.14Aillustrates a drivable area1424, in accordance with one or more embodiments. The drivable area1424includes a road1428along which the AV100can operate. The AV100is illustrated and described in more detail with reference toFIG.1. There are two adjacent spatiotemporal locations1420,1416shown on the road1428inFIG.14A. For example, the AV100can drive from spatiotemporal location1420to spatiotemporal location1416. A trajectory198connects spatiotemporal location1420to adjacent spatiotemporal location1416. The trajectory198is illustrated and described in more detail with reference toFIG.1.

FIG.14Bis a block diagram illustrating a dynamic occupancy graph1400, in accordance with one or more embodiments. The DOG circuit generates a dynamic occupancy graph1400(instead of the DOG1300) representing the drivable area1424along the trajectory198of the AV100. The DOG1300is illustrated and described in more detail with reference toFIG.13. The trajectory198and AV100are illustrated and described in more detail with reference toFIG.1. The drivable area1424is illustrated and described in more detail with reference toFIG.14A. The dynamic occupancy graph1400includes at least two nodes1404,1408and an edge1412connecting the two nodes1404,1408. The two nodes1404,1408represent the two adjacent spatiotemporal locations1420,1416of the drivable area1424including the road1428. The two adjacent spatiotemporal locations1420,1416and the road1428are illustrated and described in more detail with reference toFIG.14A.

In an embodiment, generating the dynamic occupancy graph1400includes allocating a portion of the LiDAR data504ato the at least two nodes1404,1408. The portion of the LiDAR data504acorresponds to an object608. An object is typically larger than a single node and is distributed over more than one node. The dynamic occupancy graph1400is a graphical representation of a DOG, for example, the DOG1300. Each grid cell1305,1310corresponds to a node1404,1408of the graphical representation1400. The grid cells1305,1310are illustrated and described in more detail with reference toFIG.13. The DOG1300cubes can thus be described by the dynamic occupancy graph1400, where each cube corresponds to a node and two adjacent cubes are characterized by an edge1412on the dynamic occupancy graph1400. The edge1412can be assigned a value representing a dynamic interaction between the nodes1404,1408.

In an embodiment, the DOG circuit updates the dynamic occupancy graph1400using recursive Bayesian analysis on the LiDAR data504a. The DOG circuit continuously or periodically updates occupancy probabilities for each node1404,1408based on the LiDAR returns504a. Pre-computed template waveforms generated using historical LiDAR can be stored and compared to the observed dynamic occupancy graph1400waveforms to determine characteristics of the environment190the AV100is navigating in.

The DOG circuit generates a particle distribution function of multiple particles based on LiDAR data504areceived from one or more LiDARs502aof the AV100. The LiDAR data504aand LiDARs502aare illustrated and described in more detail with reference toFIG.5. The multiple particles represent at least one object608in the drivable area1424. The edge1412of the dynamic occupancy graph1400represents motion of the at least one object608between the two adjacent spatiotemporal locations1420,1416of the drivable area. The dynamic state of the nodes1404,1408can be addressed, for example, by modeling objects608such as vehicles193or pedestrians192as a collection of particles. The DOG circuit generates a velocity of the object608relative to the AV100based on the particle distribution function. The modeling is akin to how fluid is modeled in field theory-based fluid dynamics. The term particles, as used herein, do not refer to physical units of matter. Rather, the particles represent a set of interacting variables, forming a virtual representation of objects608, e.g., vehicles193, pedestrians192, or free space in the environment190of the AV100.

In an embodiment, generating the particle distribution function includes adjusting a probability that a portion of the drivable area1424is occupied by the object608to greater than zero. In an embodiment, the DOG circuit updates the particle distribution function based on models of the one or more LiDARs123. For example, the updated particle distribution functions are used in conjunction with forward sensor models associated with the corresponding sensors123to generate predictions on the probability of occupancy of the various nodes1404,1408.

In an embodiment, the DOG circuit validates the velocity of the object608relative to the AV100against RADAR data504breceived using one or more RADARs502bof the AV100. The RADAR data504band RADAR502bis illustrated and described in more detail with reference toFIG.5. The particle distribution function can be a function of seven variables ƒ(x, y, z, vx, vy, vz, t). Here, x refers to the position on the X axis, y refers to the position on the Y axis, z refers to the position on the Z axis, vxrefers to the velocity on the X axis, vyrefers to the velocity on the Y axis, vzrefers to the velocity on the Z axis, and t refers to time. The particle distribution function is thus a number of particles per unit volume having the velocity (vx, vy, vz) at the position r=(x, y, z) at time t. In an embodiment, the DOG circuit monitors a flow of the particles through the dynamic occupancy graph1400based on the LiDAR data504a. Instead of tracking individual particles to determine the occupancy of nodes1404,1408, the DOG circuit monitors the flow of particles through the dynamic occupancy graph1400by determining the probability of occupancy of the nodes1404,1408by tracking statistics of particle distribution functions.

In an embodiment, the DOG circuit determines a state of each node (e.g., node1404) of the dynamic occupancy graph1400based on the particle distribution function. The states of the nodes1404,1408depend on the parameters of the joint distribution of the particles as they traverse the nodes1404,1408. In an embodiment, generating the particle distribution function includes determining a solution to a differential equation defined by a parameter of the particle distribution function. For example, a Eulerian solver is used to determine the time-varying joint distributions by computing solutions to differential equations defined on the one or more particle-dynamics parameters obtained using the one or more sensors121,122,123.

In an embodiment, generating the particle distribution function includes determining a probability that the at least one object608occupies at least one of the two adjacent spatiotemporal locations1420,1416of the drivable area1424. Where the DOG circuit “perceives” targets (object608) along the trajectory198(edge1412), the DOG circuit will “populate” the edge1412as “occupied” with an associated probability. In an embodiment, generating the particle distribution function includes determining a number of the particles per unit volume in at least one of the two adjacent spatiotemporal locations1416,1420of the drivable area1424. Each node1404,1408is a single-particle phase space. Each node1404can contain an occupancy probability, a confidence, or a range rate (how fast is the object608approaching the AV100).

In an embodiment, the DOG circuit determines an observation vector for a node1404of the at least two nodes1404,1408based on the LiDAR data504a. The observation vector includes a density of particles in a corresponding spatiotemporal location (e.g., the spatiotemporal location1416) of the two adjacent spatiotemporal locations1416,1420of the drivable area1424. The particle distribution function specifies a probability of a random variable falling within a particular range of values. This probability is given by the integral of the variable's particle distribution function over the range. That is, the probability is determined as an area under the particle distribution function but above the horizontal axis and between the lowest and greatest values of the range. The particle distribution function is nonnegative everywhere, and its integral over the entire space is equal to 1. In an embodiment, the observation vector further includes a velocity component of the particles in the corresponding spatiotemporal location1416and a covariance of the particle distribution function. The LiDAR data504aincludes velocity information along the X and Y directions. The DOG circuit generates the observation vector that includes the density of the particles in the node1404, the velocity components along the X and Y directions, and the covariances.

The DOG circuit determines a TTC of the AV100and the at least one object608based on the particle distribution function. For example, the dynamic occupancy graph1400represents a one-dimensional view along the forward-intended path (trajectory198) of the AV100. Responsive to determining that the TTC is less than a threshold time, the DOG circuit transmits a collision warning to a control circuit406of the AV100to avoid a collision of the AV100and the at least one object608. The control circuit406is illustrated and described in more detail with reference toFIG.4. In an embodiment, the DOG circuit determines a minimum TTC and a mean TTC of the AV100and the at least one object608based on the particle distribution function. The DOG circuit1300uses a constant acceleration model to determine the minimum and mean TTCs.

In an embodiment, the DOG circuit receives control data from the control circuit406. The control data includes an angle of a steering control102or a steering input1108of the AV100. The steering control102is illustrated and described in more detail with reference toFIG.1. The steering input1108is illustrated and described in more detail with reference toFIG.11. The DOG circuit determines a spatiotemporal location (e.g., the spatiotemporal location1416) of the AV100within the drivable area. In an embodiment, the control data includes an angular velocity of the steering control102. For example, the DOG circuit requests the steering wheel angle and the steering wheel angular velocity from the control module406. The DOG circuit uses the steering wheel parameters to determine where the AV100is located.

In an embodiment, the DOG circuit operates separately and independently of the AV stack for redundancy. In an embodiment, the DOG circuit transmits the collision warning to the control circuit406via an arbiter circuit of the AV100. The DOG circuit also periodically transmits a heartbeat signal to the arbiter circuit. The intent of the heartbeat signal is to communicate that the DOG circuit is functioning or processing as expected, and is not in a hung, crashed, or delayed state. The heartbeat signal can be implemented in different ways. One way is an alternating high and low signal at an expected frequency.

In an embodiment, the dynamic occupancy graph1400is generated in accordance with a coordinate frame of the AV100. For example, the DOG circuit operates within the ego-vehicle's (AV100's) local coordinate frame. In an embodiment, generating the dynamic occupancy graph1400is based on a spatiotemporal location (e.g., the spatiotemporal location1416) of the AV100within the drivable area. For example, the AV100is driving down a road. The DOG circuit receives a trajectory198from the planning module404. The planning module404is illustrated and described in more detail with reference toFIG.4. The DOG circuit examines the width of the AV100within the trajectory198and senses no object608, a faraway object608, or an object608leaving the trajectory198. The DOG circuit generates the dynamic occupancy graph1400having nodes1404,1408having a lower occupancy probability and a larger mean TTC. The DOG circuit transmits a heartbeat message to the arbiter circuit and does not send a brake pre-charge or a deceleration request to the control module406.

FIG.15illustrates a dynamic occupancy grid (DOG) waveform1500representing a pedestrian192, in accordance with one or more embodiments. The pedestrian192is illustrated and described in more detail with reference toFIG.1. The waveform1500is extracted from a DOG (e.g., the DOG1300, illustrated and described in more detail with reference toFIG.13). The DOG1300includes multiple 3D grid cubes (or 2D grid cells)1305,1310.FIG.16illustrates a DOG waveform1600representing a vehicle193, in accordance with one or more embodiments. The vehicle193is illustrated and described in more detail with reference toFIG.1. The waveform1600is extracted from a DOG (e.g., the DOG1300, illustrated and described in more detail with reference toFIG.13).

The DOG circuit generates a DOG (e.g., the DOG1300) based on first LIDAR data504areceived from a LIDAR502aof the AV100. In an embodiment, the LiDAR502aincludes a phased array and the first LiDAR data504aincludes time, frequency, and phase information. The LiDAR502auses a phased array so the returns include time, frequency, and phase of light1508information. The first LIDAR data504aand the LIDAR502aare illustrated and described in more detail with reference toFIG.5. In an embodiment, generating the DOG1300includes fusing sensor data received from sensors121,122of the AV100with the first LIDAR data504ausing Bayesian filtering to represent the pedestrian192across multiple grid cells1305,1310of the DOG1300. The sensors121,122are illustrated and described in more detail with reference toFIG.1. The grid cells1305,1310are illustrated and described in more detail with reference toFIG.13. The DOG circuit uses Bayesian filtering to fuse a variety of sensors121,122,123and represent an object608across multiple grid cells1305,1310. In an embodiment, the DOG1300is generated based on irregular sampling of a semantic map of the environment190.

In an embodiment, each grid cube1305of the multiple grid cubes1305,1310of the DOG1300includes a probabilistic occupancy estimate and a velocity estimate of the pedestrian192. In an embodiment, the DOG1300represents an area within a border of the environment192and each grid cube1305of the multiple grid cubes1305,1310has a width. The grid cubes1303,1310have a static position and a width. The border of the environment190is shifted by the width to keep the moving AV100within a center of the DOG1300. In an embodiment, the DOG circuit adjusts a representation of the border of the environment190within the DOG1300by the width, such that a representation of the pedestrian192is located within the DOG1300.

In an embodiment, the DOG circuit determines a phase shift of the first LiDAR data504a. The first LiDAR data504ais a phase-modulated (varied) signal. The DOG circuit can measure the phase shift in the phase-modulated signal. The DOG circuit includes a particle filter that is executed by one or more processors of the DOG circuit to generate a waveform1500from the DOG1300. A portion of the DOG1300corresponding to an object in the environment190is extracted and stored in an embedded library in the AV100as a labeled waveform. The environment190is illustrated and described in more detail with reference toFIG.1. The waveform1500includes a variation of an intensity1504of the LiDAR data504awith a phase of light1508of the LiDAR502a. In an embodiment, the waveform1500represents the pedestrian192interacting with a second object (e.g., the vehicle193). The embedded system in the AV100stores many possible signal waveforms. The DOG circuit extracts information from the observed waveforms1500,1600and compares the information to stored waveforms to find a match (for example, a pedestrian192, a vehicle193, etc.). The comparisons can detect complex scenarios with multiple road users, e.g., pedestrians192, bikes, and motor vehicles interacting with each other.

The DOG circuit matches the waveform1500against a library of waveforms extracted from historical LiDAR data reflected from one or more objects608to identify that the first LiDAR data504ais reflected from a particular object (the pedestrian192) of the one or more objects608. The one or more objects608are illustrated and described in more detail with reference toFIG.6. The DOG circuit updates the waveform1500based on second LiDAR data (an updated version of the first LiDAR data504a) received from the LiDAR502aof the AV100after the first LiDAR data504ais received. The DOG circuit determines a range rate of the AV100and the pedestrian192based on the updated waveform1500. A control circuit406of the AV100operates the AV100to avoid a collision with the pedestrian192based on the range rate of the AV100and the pedestrian192.

In an embodiment, matching the waveform1500against the library of waveforms includes extracting a feature vector from the waveform1500. The DOG circuit identifies the pedestrian192from the one or more objects608using a machine learning model. Past, pre-computed template waveforms are stored and compared to the observed DOG waveform1500from the LiDAR data504ato determine characteristics of the environment190the AV100is navigating in a computationally efficient manner. In an embodiment, the DOG circuit trains the machine learning model based on feature vectors extracted from the historical LiDAR data. The machine learning model can extract features from an observed waveform1500to compare to a stored waveform. The machine learning model can be trained on the labeled, stored waveforms.

In an embodiment, the DOG circuit determines a probabilistic occupancy distribution and a velocity distribution across the DOG1300disregarding interaction of the historical LIDAR data between the multiple grid cubes1305,1310. The library generation includes multiple steps. The LiDAR returns are converted into the DOG1300. The particle filter estimates the spatial occupancy and velocity distribution. Each grid cube1305is updated independently and no interaction between the multiple grid cubes1305,1310is modeled.

In an embodiment, the particle filter extracts the waveform1600from the DOG1300. The waveform1600includes a variation of the intensity1504of the LiDAR data504awith a distance1604of a particular object (e.g., vehicle193) from the AV100. If a grid cube1305is occupied, the LiDAR data504asignal will have a specific distribution indicating this. If the grid cube1305is not occupied, the grid cube1305will contain noise that will not match the distribution. In the waveform1600, a higher peak1608corresponds to a higher density of reflected points. The Y axis (intensity1504of the LiDAR data504a) corresponds to occupancy probability. Hence, the waveform1600peaks where points of the LiDAR data504aare clustered, indicating a higher probability of the presence of the vehicle193.

In an embodiment, the particle filter extracts a waveform from the DOG1300including a variation of the probabilistic occupancy estimate with the distance1604of the vehicle193from the AV100. The waveform include a probability of occupancy of a grid cube (e.g., the grid cube1305) that is a particular distance from the AV100. The waveform includes a variation of the probability density of occupation plotted against the distance1604of an object608from the AV100. In embodiment, the particle filter extracts a waveform from the DOG1300including a variation of the probabilistic occupancy estimate with the phase of light1508of the LiDAR data504a.

In an embodiment, an intensity of particular LiDAR data504acorresponding to a particular grid cube1305of the multiple grid cubes1305,1310of the DOG1300is represented by a. A first conditional probability that the intensity of the particular LiDAR data504acorresponding to the particular grid cube1305of the multiple grid cubes1305,1310of the DOG1300is greater than a threshold intensity when a portion of the environment190represented by the particular grid cube1305is occupied by a particular object (e.g., the vehicle193) is represented by P(α/occupied). The DOG circuit determines the value of P(α/occupied) from the DOG1300. The DOG circuit further determines a second conditional probability P(α/free) that the intensity of the particular LiDAR data504acorresponding to the particular grid cube1305of the multiple grid cubes1305,1310of the DOG1300is greater than the threshold intensity when the portion of the environment190represented by the particular cube1305is free of the vehicle193. The DOG circuit determines that the portion of the environment190represented by the particular grid cube1305is indeed occupied by the vehicle193based on the first conditional probability P(α|occupied) and the second conditional probability P(α|free). Thus, the DOG circuit determines whether a grid cube is occupied by an object608by comparing two mutually exclusive models. The conditional probabilities P(α|occupied) and P(α|free) are the two mutually exclusive models under comparison.

FIG.17is a flow diagram illustrating a process for operation of the AV100, in accordance with one or more embodiments. In an embodiment, the process ofFIG.17is performed by the DOG circuit, described in more detail with reference toFIG.13. Other entities, for example, the perception module402or the planning module404perform some or all of the steps of the process in other embodiments. Likewise, embodiments may include different and/or additional steps, or perform the steps in different orders. The perception module402and the planning module404are illustrated and described in more detail with reference toFIG.4.

The DOG circuit receives1704LiDAR data504afrom one or more LiDARs502aof the AV100. The LiDAR data504aand LiDAR502aare illustrated and described in more detail with reference toFIG.5. The LiDAR data504arepresents one or more objects608located in the environment190. The environment190is illustrated and described in more detail with reference toFIG.1. The one or more objects608are illustrated and described in more detail with reference toFIG.6.

The DOG circuit generates1708the DOG1300based on a semantic map of the environment190. The DOG1300is illustrated and described in more detail with reference toFIG.13. The DOG1300includes multiple grid cells1305,1310. The grid cells1305,1310are illustrated and described in more detail with reference toFIG.13. Each grid cell1305of the multiple grid cells1305,1310represent a portion of the environment190.

For each grid cell1305of the multiple grid cells1305,1310, the DOG circuit generates1712a probability density function based on the LiDAR data504a. The probability density function represents a probability that the portion of the environment190represented by the grid cell1305is occupied by an object (e.g., the vehicle193) of the one or more objects608. The vehicle193is illustrated and described in more detail with reference toFIG.1.

The DOG circuit determines1716that a time-to-collision (TTC) of the AV100and the vehicle193is less than a threshold time based on the probability density function. The probability density function (sometimes referred to as a particle density function) describes a number of identically distributed and independent particles inside a volume of the state space. Because particles are considered to be identical, an inherent assumption of the technology described herein is that sensor measurements are not used to distinguish between particles. Rather, sensor measurements are defined as a probability of observation γ given a particle is located at x. This measurement can be referred to as a forward sensor model, and denoted as p(γ|x).

Responsive to determining that the TTC is less than the threshold time, the control circuit406operates the AV100to avoid a collision of the AV100and the vehicle193. The control circuit406is illustrated and described in more detail with reference toFIG.4.

FIG.18is a flow diagram illustrating a process for operation of the AV100, in accordance with one or more embodiments. The AV100is illustrated and described in more detail with reference toFIG.1. In an embodiment, the process ofFIG.18is performed by the DOG circuit, described in more detail with reference toFIG.13. Other entities, for example, the perception module402or the planning module404perform some or all of the steps of the process in other embodiments. Likewise, embodiments may include different and/or additional steps, or perform the steps in different orders. The perception module402and the planning module404are illustrated and described in more detail with reference toFIG.4.

The DOG circuit generates1804a dynamic occupancy graph1400representing a drivable area1424along a trajectory198of the AV100. The dynamic occupancy graph1400is illustrated and described in more detail with reference toFIG.14B. The drivable area1424is illustrated and described in more detail with reference toFIG.14A. The trajectory198is illustrated and described in more detail with reference toFIG.1. The dynamic occupancy graph1400includes at least two nodes1404,1408and an edge1412connecting the two nodes1404,1408. The nodes1404,1408are illustrated and described in more detail with reference toFIG.14B. The edge141is illustrated and described in more detail with reference toFIG.14B. The two nodes1404,1408represent two adjacent spatiotemporal locations1416,1420of the drivable area1424. The two adjacent spatiotemporal locations1416,1420are illustrated and described in more detail with reference toFIG.14A.

The DOG circuit generates1808a particle distribution function of multiple particles based on LiDAR data504areceived from one or more LiDARs502aof the AV100. The LiDAR data504aand LiDAR502aare illustrated and described in more detail with reference toFIG.5. The multiple particles represent at least one object608in the drivable area1424. The object608is illustrated and described in more detail with reference toFIG.6. The edge1412of the dynamic occupancy graph1400represents motion of the at least one object608between the two adjacent spatiotemporal locations1416,1420of the drivable area1424.

The DOG circuit generates1812a velocity of the object608relative to the AV100based on the particle distribution function. The modeling is akin to how fluid is modeled in field theory-based fluid dynamics. The term particles, as used herein, do not refer to physical units of matter. Rather, the particles represent a set of interacting variables, forming a virtual representation of objects608, e.g., vehicles193, pedestrians192, or free space in the environment190of the AV100.

The DOG circuit1816determines a time-to-collision (TTC) of the AV100and the at least one object608based on the particle distribution function. In an embodiment, generating the particle distribution function includes adjusting a probability that a portion of the drivable area1424is occupied by the object608to greater than zero. In an embodiment, the DOG circuit updates the particle distribution function based on models of the one or more LiDARs123. For example, the updated particle distribution functions are used in conjunction with forward sensor models associated with the corresponding sensors123to generate predictions on the probability of occupancy of the various nodes1404,1408.

Responsive to determining that the TTC is less than a threshold time, the DOG circuit transmits a collision warning to a control circuit406of the AV100to avoid a collision of the AV100and the at least one object608. The control circuit406is illustrated and described in more detail with reference toFIG.6.

FIG.19is a flow diagram illustrating a process for operation of the AV100, in accordance with one or more embodiments. The AV100is illustrated and described in more detail with reference toFIG.1. In an embodiment, the process ofFIG.18is performed by the DOG circuit, described in more detail with reference toFIG.13. Other entities, for example, the perception module402or the planning module404perform some or all of the steps of the process in other embodiments. Likewise, embodiments may include different and/or additional steps, or perform the steps in different orders. The perception module402and the planning module404are illustrated and described in more detail with reference toFIG.4.

The DOG circuit receives1904sensor data from one or more sensors121,122,123of the AV100. The one or more sensors121,122,123are illustrated and described in more detail with reference toFIG.1. The sensor data has an associated latency from the time of capture (that can be encoded into the data) as it is transmitted from the sensors121,122,123to the DOG circuit (optionally through the perception module402).

Responsive to determining that the latency is less than a threshold latency, the DOG circuit executes1908a cyclic redundancy check on the sensor data. For example, the DOG circuit checks the quality of the sensor data signals, such as timing (e.g., latency) of the path data or a protocol of the path data. The path data refers to sensor data describing the physical path the AV100is traversing. If the DOG circuit determines that the sensor data is of poor quality, the DOG circuit can send a “failed sensor data” signal to an arbiter module of a safety system or to the AV stack (AV navigation system).

Responsive to determining that the sensor data passes the cyclic redundancy check, the DOG circuit determining1912a discrete, binary occupancy probability for each grid cell1305of a DOG1300using an inverse sensor model of the one or more sensors121,122,123based on the sensor data. The grid cell1305and DOG1300are illustrated and described in more detail with reference toFIG.13. The occupancy probability denotes whether a portion of an environment190in which the AV100is operating is occupied by an object608. The environment190is illustrated and described in more detail with reference toFIG.1. The object608is illustrated and described in more detail with reference toFIG.6.

The DOG circuit determines1916a particle density function based on the occupancy probability using a kinetic function. For example, the DOG circuit determines the cube occupancy cumulative distribution function. Evolution of the particle density function over time can be modeled using kinetic equations such as Boltzmann equations for the probability density function.

Responsive to determining that the particle density function indicates that a time to collision (TTC) between the AV100and the object608is less than a threshold TTC, the DOG circuit transmits a deceleration request to a control circuit406of the AV100.

FIG.20is a flow diagram illustrating a process for operation of the AV100, in accordance with one or more embodiments. The AV100is illustrated and described in more detail with reference toFIG.1. In an embodiment, the process ofFIG.18is performed by the DOG circuit, described in more detail with reference toFIG.13. Other entities, for example, the perception module402or the planning module404perform some or all of the steps of the process in other embodiments. Likewise, embodiments may include different and/or additional steps, or perform the steps in different orders. The perception module402and the planning module404are illustrated and described in more detail with reference toFIG.4.

The DOG circuit generates2004a DOG1300based on first LIDAR data504areceived from a LIDAR502aof the AV100. The DOG1300is illustrated and described in more detail with reference toFIG.13. The LIDAR data504aand LIDAR502aare illustrated and described in more detail with reference toFIG.5.

A particle filter executed by one or more processors of the DOG circuit extracts2008a waveform1500from the DOG1300. The waveform1500is illustrated and described in more detail with reference toFIG.15. The waveform1500includes a variation of an intensity1504of the LiDAR data504awith a phase of light1508of the LiDAR502a. The intensity1504of the LiDAR data504aand the phase of light1508are illustrated and described in more detail with reference toFIG.15.

The DOG circuit matches2012the waveform1500against a library of waveforms extracted from historical LiDAR data reflected from one or more objects608to identify that the first LiDAR data504ais reflected from a particular object (e.g., the pedestrian192) of the one or more objects608. The one or more objects608are illustrated and described in more detail with reference toFIG.6. The pedestrian192is illustrated and described in more detail with reference toFIG.1.

The DOG circuit updates2016the waveform1500based on second LiDAR data (an updated version of the first LiDAR data504a) received from the LiDAR502aof the AV100after the first LiDAR data504ais received.

The DOG circuit determines2020a range rate of the AV100and the pedestrian192based on the updated waveform1500. The range rate of the AV100and the pedestrian192indicates how fast the AV100is approaching the pedestrian192.

A control circuit406of the AV100operates2024the AV100to avoid a collision with the pedestrian192based on the range rate of the AV100and the pedestrian192. The control circuit406is illustrated and described in more detail with reference toFIG.4.

In the foregoing description, embodiments of the invention have been described with reference to numerous specific details that may vary from implementation to implementation. The description and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense. The sole and exclusive indicator of the scope of the invention, and what is intended by the applicants to be the scope of the invention, is the literal and equivalent scope of the set of claims that issue from this application, in the specific form in which such claims issue, including any subsequent correction. Any definitions expressly set forth herein for terms contained in such claims shall govern the meaning of such terms as used in the claims. In addition, when we use the term “further including,” in the foregoing description or following claims, what follows this phrase can be an additional step or entity, or a sub-step/sub-entity of a previously-recited step or entity.