Patent Description:
The present disclosure generally relates to the control of autonomous vehicles, and in particular to improving an ability to correlate location information in a map with location data obtained by a vehicle while in motion.

Control of autonomous vehicles may rely on comparisons between maps of a local area and information acquired by on-board vehicle sensors. These sensors may rely, in various aspects, on one or more of optical, radio, and laser based technologies. The comparisons between the maps and the data obtained by the vehicle sensors may enable the vehicle to identify its position along a roadway, in real time, and make adjustments to its position and/or speed based on the identified position. International patent application <CIT> describes a mapping system for ego-motion estimation in an autonomous vehicle that generates a map in real-time based on the cumulative sensor data from an inertial measurement unit, a camera unit and from a laser scanning unit.

The invention is a method, computing system and apparatus as defined in the appended claims.

Some embodiments are illustrated by way of example, and not limitation, in the figures of the accompanying drawings.

Maps of an autonomous system can be used to perceive the environment, detect objects, localize and control of autonomous vehicles. One type of map is a map that provides coordinates of certain map features, such as roads, addresses, points of interests, traffic information, and the like. Such maps, sometimes referred to as coverage maps, can be used to generate routing information from point A to point B. However, the maps of an autonomous system for the function listed above may require higher fidelity representation of the world. For example, a map for autonomous vehicles ("AV Map") may include a <NUM>-D point cloud of the environment. As will be described below, such AV maps can be generated by driving a mapping vehicle equipped with a sensor within an area being mapped. The mapping vehicle may drive a section of road a number of times to generate a dense set of map data for the section of road. In this way, the map data represents the world from the perspective of the sensor on the mapping vehicle. The map data can include geolocation metadata so that the autonomous vehicle can determine the sensor data that is expected at a given location.

Maps may be generated from data collected in a variety of environments. For example, some maps are generated based on data collected from vehicles having roof mounted sensors, e.g., a LIDAR (Light Detection and Ranging), RADAR (Radio Detection and Ranging), or Visual sensors (e.g., a camera sensor). Other maps are generated from data collected by vehicles with sensors mounted on an extension platform. The extension platform may position the sensor substantially above the vehicle's roof line. Furthermore, while the data collected for maps may vary, vehicles using the maps for autonomous position determination may also have sensors that vary in their positions. For example, a small compact car may have an LIDAR sensor located at a first distance from the ground while a large semi-tractor may have an LIDAR sensor positioned at a larger second distance. Thus, a sensor mounted to the top of a compact car and to the top of a truck may generate different point clouds because of the different perspectives.

Additionally, the angle of a sensor used to collect map data may also vary from map to map. For example, some vehicles may be positioned in a slightly nose up attitude, resulting in the sensor being slightly inclined with respect to the horizontal. Other map generating vehicles may have a nose down stance, resulting in the sensor line of sight falling slightly below the horizontal.

The disclosed methods, devices, and systems provide for improvements in autonomous vehicles in a variety of environments, such as those described above. In some aspects disclosed, an autonomous vehicle generates an overlap score. The overlap score provides an indication of how well position information derived from three-dimensional LIDAR point cloud captured by the autonomous vehicle matches position information (e.g. point cloud data) included in a particular map at a particular location and, in some embodiments, orientation. The autonomous vehicle generates multiple overlap scores from a single set of captured position information by calculating the overlap score at different candidate positions within the particular map. Each overlap score provides an indication of how likely the corresponding candidate position corresponds to the vehicle's true position within the map data. A candidate location corresponding to map data having the best overlap score may be considered the best approximation of the vehicle's position in some aspects.

As discussed above, in some embodiments, an autonomous vehicle's sensor that is collecting the position information is configured differently (e.g., different heights from the ground) than a sensor that captured the map data. This difference may result in a reduced overlap score when data derived from the two sensors is compared because, for example, the perspective of the vehicle's sensor is different from the perspective of the sensor that was used to generate the map. At a given location, different perspectives can cause certain objects or map features to be occluded or not occluded. In some cases, the reduction in overlap score, even for the overlap score at a location within the map that corresponds to the vehicle's true location, may result in the autonomous vehicle failing to recognize its current position from the map data. This may cause the vehicle to provide a warning, to exit from autonomous driving, or to rely on less accurate means of estimating its position.

To improve the determination of overlap between vehicle's captured sensor data ("vehicle data") and map data, the disclosed methods, devices, and systems may detect differences between the vehicle data and map data that can be explained by differences in positions of the respective sensors used to collect the data. For example, in some aspects, if a point in the vehicle data does not have a match in the map data, a ray may be traced from the vehicle's sensor position through the non-matching point in the vehicle data. If the traced ray intersects a point in the map data, the non-matching point may be included in the overlap score determination. Otherwise it may not be included. For example, in some aspects, an overlap score is a ratio of a number of points in the vehicle data that match points in the map data, to a total number of points in the vehicle data. If the non-matching point is not included in the overlap score, the total number of points does not include the non-matching point.

Some aspects may determine points within the map data that are occluded. For example, these points may not have been visible to a sensor used to collect the map data. If a non-matching point in the vehicle data falls within an occluded portion of the map data, the non-matching point may not be included in the overlap score determination. Otherwise, the non-matching point may be included in the overlap score determination. Use of the above techniques may improve an overlap score's representation of how well the vehicle data matches the map data.

<FIG> is an overview diagram of an autonomous driving truck. The vehicle <NUM> includes a sensor <NUM>, a controller or vehicle computing system <NUM>, and a map database <NUM>. The sensor <NUM> captures point cloud data representing a scene <NUM>. In the illustrated embodiment, the sensor <NUM> is positioned on the roof of the truck, resulting in a distance of D<NUM> between the ground and the sensor <NUM>. The sensor <NUM> may be a LIDAR sensor. In some other aspects, the sensor <NUM> may be a visual sensor or an infrared sensor. The sensor <NUM> may be comprised of multiple physical sensors or multiple physical sensor devices. The sensor <NUM> may provide three-dimensional data. For example, data in an X, Y, and Z dimension may be obtained from the sensor <NUM>.

The controller or vehicle computing system <NUM> compares data collected by the sensor <NUM> to map data included in the map database <NUM>. As discussed above, the controller or vehicle computing system <NUM> computes an overlap score between the data collected by the sensor <NUM> and the map data in the map database <NUM> to determine a position of the vehicle <NUM>.

<FIG> shows an example embodiment of a map data collection vehicle. The map data collection vehicle <NUM> includes a sensor <NUM>, a controller <NUM>, and the map database <NUM>. The sensor <NUM> operationally captures point cloud data representing a scene <NUM> in front of the vehicle <NUM>. The point cloud data captured by the sensor <NUM> may include three-dimensional data, such as data across each of X, Y, and Z dimension. The controller <NUM> stores map data derived from point cloud data collected by the sensor <NUM> in the map database <NUM>. The map data may reflect a perspective of the sensor <NUM>, which is located at a distance D<NUM> from the ground. Note that distance D<NUM> is a different distance from that of distance D<NUM>, discussed above with respect to <FIG> and the vehicle <NUM>.

With reference to the figures, example embodiments of the present disclosure will be discussed in further detail. <FIG> is a block diagram of an example system <NUM> to control the navigation of a vehicle <NUM> according to example embodiments of the present disclosure. The autonomous vehicle <NUM> is capable of sensing its environment and navigating with little to no human input. The autonomous vehicle <NUM> can be a ground-based autonomous vehicle (e.g., car, truck, bus, etc.), an air-based autonomous vehicle (e.g., airplane, drone, helicopter, or other aircraft), or other types of vehicles (e.g., watercraft). The autonomous vehicle <NUM> can be configured to operate in one or more modes, for example, a fully autonomous operational mode and/or a semi-autonomous operational mode. A fully autonomous (e.g., self-driving) operational mode can be one in which the autonomous vehicle can provide driving and navigational operation with minimal and/or no interaction from a human driver present in the vehicle. A semi-autonomous (e.g., driver-assisted) operational mode can be one in which the autonomous vehicle operates with some interaction from a human driver present in the vehicle.

As discussed above, the autonomous vehicle <NUM> can include one or more sensors <NUM>, a controller or vehicle computing system <NUM>, and one or more vehicle controls <NUM>. The vehicle controls <NUM> may include one or more of the vehicle computing system <NUM> can assist in controlling the autonomous vehicle <NUM>. In particular, the vehicle computing system <NUM> can receive sensor data from the one or more sensors <NUM>, attempt to comprehend the surrounding environment by performing various processing techniques on data collected by the sensors <NUM>, and generate an appropriate motion path through such surrounding environment. The vehicle computing system <NUM> can control the one or more vehicle controls <NUM> to operate the autonomous vehicle <NUM> according to the motion path.

The vehicle computing system <NUM> can include one or more processors <NUM> and at least one memory <NUM>. The one or more processors <NUM> can be any suitable processing device (e.g., a processor core, a microprocessor, an ASIC, a FPGA, a controller, a microcontroller, etc.) and can be one processor or a plurality of processors that are operatively connected. The memory <NUM> can include one or more non-transitory computer-readable storage mediums, such as RAM, ROM, EEPROM, EPROM, flash memory devices, magnetic disks, etc., and combinations thereof. The memory <NUM> can store data <NUM> and instructions <NUM> which are executed by the processor <NUM> to cause vehicle computing system <NUM> to perform operations. In some implementations, the one or more processors <NUM> and at least one memory <NUM> may be comprised in one or more computing devices, such as computing device(s) <NUM>, within the vehicle computing system <NUM>.

In some implementations, vehicle computing system <NUM> can further be connected to, or include, a positioning system <NUM>. Positioning system <NUM> can determine a current geographic location of the autonomous vehicle <NUM>. The positioning system <NUM> can be any device or circuitry for analyzing the position of the autonomous vehicle <NUM>. For example, the positioning system <NUM> can determine actual or relative position by using a satellite navigation positioning system (e.g. a GPS system, a Galileo positioning system, the Global Navigation satellite system (GLONASS), the BeiDou Satellite Navigation and Positioning system), an inertial navigation system, a dead reckoning system, based on IP address, by using triangulation and/or proximity to cellular towers or WiFi hotspots, and/or other suitable techniques for determining position. The position of the autonomous vehicle <NUM> can be used by various systems of the vehicle computing system <NUM>.

As illustrated in <FIG>, in some embodiments, the vehicle computing system <NUM> can include a perception system <NUM>, a prediction system <NUM>, and a motion planning system <NUM> that cooperate to perceive the surrounding environment of the autonomous vehicle <NUM> and determine a motion plan to control the motion of the autonomous vehicle <NUM> accordingly. In some implementations, the vehicle computing system <NUM> can also include a feature extractor/concatenator <NUM> and a speed limit context awareness machine-learned model <NUM> that can be provide data to assist in determining the motion plan to control the motion of the autonomous vehicle <NUM>.

In particular, in some implementations, the perception system <NUM> can receive sensor data from the one or more sensors <NUM> that are coupled to or otherwise included within the autonomous vehicle <NUM>. As examples, the one or more sensors <NUM> can include a Light Detection and Ranging (LIDAR) system, a Radio Detection and Ranging (RADAR) system, one or more cameras (e.g., visible spectrum cameras, infrared cameras, etc.), and/or other sensors. The sensor data can include information that describes the location of objects within the surrounding environment of the autonomous vehicle <NUM>.

As one example, for LIDAR systems, the sensor data can include the location (e.g., in three-dimensional space relative to the LIDAR system) of a number of points that correspond to objects that have reflected a ranging laser. For example, LIDAR system can measure distances by measuring the Time of Flight (TOF) that it takes a short laser pulse to travel from the sensor to an object and back, calculating the distance from the known speed of light.

As another example, for RADAR systems, the sensor data can include the location (e.g., in three-dimensional space relative to RADAR system) of a number of points that correspond to objects that have reflected a ranging radio wave. For example, radio waves (pulsed or continuous) transmitted by the RADAR system can reflect off an object and return to a receiver of the RADAR system, giving information about the object's location and speed. Thus, RADAR system can provide useful information about the current speed of an object.

As yet another example, for one or more cameras, various processing techniques (e.g., range imaging techniques such as, for example, structure from motion, structured light, stereo triangulation, and/or other techniques) can be performed to identify the location (e.g., in three-dimensional space relative to the one or more cameras) of a number of points that correspond to objects that are depicted in imagery captured by the one or more cameras. Other sensor systems can identify the location of points that correspond to objects as well.

Thus, the one or more sensors <NUM> can be used to collect sensor data that includes information that describes the location (e.g., in three-dimensional space relative to the autonomous vehicle <NUM>) of points that correspond to objects within the surrounding environment of the autonomous vehicle <NUM>.

In addition to the sensor data, the perception system <NUM> can retrieve or otherwise obtain map data <NUM> that provides detailed information about the surrounding environment of the autonomous vehicle <NUM>. The map data <NUM> can provide information regarding: the identity and location of different travel ways (e.g., roadways), road segments, buildings, or other items or objects (e.g., lampposts, crosswalks, curbing, etc.); the location and directions of traffic lanes (e.g., the location and direction of a parking lane, a turning lane, a bicycle lane, or other lanes within a particular roadway or other travel way); traffic control data (e.g., the location and instructions of signage, traffic lights, or other traffic control devices); and/or any other map data that provides information that assists the vehicle computing system <NUM> in comprehending and perceiving its surrounding environment and its relationship thereto.

The perception system <NUM> can identify one or more objects that are proximate to the autonomous vehicle <NUM> based on sensor data received from the one or more sensors <NUM> and/or the map data <NUM>. In particular, in some implementations, the perception system <NUM> can determine, for each object, state data that describes a current state of such object. As examples, the state data for each object can describe an estimate of the object's: current location (also referred to as position); current speed; current heading (also referred to together as velocity); current acceleration; current orientation; size/footprint (e.g., as represented by a bounding shape such as a bounding polygon or polyhedron); class (e.g., vehicle versus pedestrian versus bicycle versus other); yaw rate; and/or other state information.

In some implementations, the perception system <NUM> may determine state data for each object over a number of iterations. In particular, the perception system <NUM> can update the state data for each object at each iteration. Thus, the perception system <NUM> can detect and track objects (e.g., vehicles, pedestrians, bicycles, and the like) that are proximate to the autonomous vehicle <NUM> over time.

The prediction system <NUM> may receive the state data from the perception system <NUM> and predict one or more future locations for each object based on such state data. For example, the prediction system <NUM> can predict where each object will be located within the next <NUM> seconds, <NUM> seconds, <NUM> seconds, etc. As one example, an object can be predicted to adhere to its current trajectory according to its current speed. As another example, other, more sophisticated prediction techniques or modeling can be used.

The motion planning system <NUM> may determine a motion plan for the autonomous vehicle <NUM> based at least in part on the predicted one or more future locations for the object provided by the prediction system <NUM> and/or the state data for the object provided by the perception system <NUM>. Stated differently, given information about the current locations of objects and/or predicted future locations of proximate objects, the motion planning system <NUM> can determine a motion plan for the autonomous vehicle <NUM> that best navigates the autonomous vehicle <NUM> relative to the objects at such locations.

As one example, in some implementations, the motion planning system <NUM> can determine a cost function for each of one or more candidate motion plans for the autonomous vehicle <NUM> based at least in part on the current locations and/or predicted future locations of the objects. For example, the cost function can describe a cost (e.g., over time) of adhering to a particular candidate motion plan. For example, the cost described by a cost function can increase when the autonomous vehicle <NUM> approaches a possible impact with another object and/or deviates from a preferred pathway (e.g., a preapproved pathway).

Thus, given information about the current locations and/or predicted future locations of objects, the motion planning system <NUM> can determine a cost of adhering to a particular candidate pathway. The motion planning system <NUM> can select or determine a motion plan for the autonomous vehicle <NUM> based at least in part on the cost function(s). For example, the candidate motion plan that minimizes the cost function can be selected or otherwise determined. The motion planning system <NUM> can provide the selected motion plan to a vehicle controller <NUM> that controls one or more vehicle controls <NUM> (e.g., actuators or other devices that control gas flow, acceleration, steering, braking, etc.) to execute the selected motion plan.

<FIG> is an example of an expanded view of the autonomous vehicle <NUM>. As discussed above, the autonomous vehicle <NUM> may include the sensor <NUM>, the vehicle controller or vehicle computing system <NUM>, a motor controller <NUM>, a steering controller <NUM>, a braking controller <NUM>, and the map database <NUM>. The controller <NUM> is operably connected to each of the sensor <NUM>, motor controller <NUM>, steering controller <NUM> and braking controller <NUM>, via any known interconnect technology. In <FIG>, this is illustrated as a bus. The vehicle controller <NUM> may be configured to capture multiple point cloud data sets from the sensor <NUM> and compare the point cloud data sets to map data in the map database <NUM>. Based on the comparison, the controller <NUM> may determine a position of the vehicle <NUM>. The vehicle controller <NUM> may control the position and/or speed of the vehicle <NUM> by issuing commands to one or more of the motor controller <NUM>, steering controller <NUM>, and/or braking controller <NUM>. For example, if the controller <NUM> determines a speed of the truck should be increased, the controller <NUM> may transmit a command to the motor controller <NUM> indicating an increased level of fuel is to be provided to the motor. In embodiments utilizing electric motors, the vehicle controller <NUM> may transmit a command to the motor controller <NUM> indicating an increased current or voltage is to be provided to the motor. If the vehicle controller <NUM> determines a position of the vehicle <NUM> should be adjusted to the left or right, the controller <NUM> may send a command indicating same to the steering controller <NUM>.

<FIG> is an expanded view of an example controller or vehicle computing system <NUM>. The example controller or vehicle computing system <NUM> of <FIG> includes one or more hardware processors <NUM>, a hardware memory or memories <NUM>, and one or more interfaces <NUM>. The hardware processor(s) <NUM>, memories <NUM>, and interfaces <NUM> may be operably connected via any known interconnect technology, such as a bus <NUM>. In some aspects, instructions stored in the memory/memories <NUM> may configure the one or more hardware processors <NUM> to perform one or more of the functions discussed below to provide for autonomous control of a vehicle, such as the vehicle <NUM>. The interface(s) <NUM> may provide for electronic communication between the controller <NUM> and one or more of the motor controller <NUM>, steering controller <NUM>, braking controller <NUM>, sensor <NUM>, and/or map database <NUM>.

<FIG> shows example scenes captured by LIDAR sensor(s) of an autonomous vehicle and a map generating vehicle. While a LIDAR sensor may capture point cloud data, for ease of illustration the scenes <NUM>, <NUM>, and <NUM> are shown as two dimensional images. An autonomous vehicle sensor may capture point cloud data for the scene <NUM>. The scene <NUM> may be captured, in some aspects, by the sensor <NUM>. The scene <NUM> shows a relatively straight road <NUM>, a tree <NUM>, and a pedestrian <NUM>. The scene <NUM> shows that the tree <NUM> is a distance D<NUM> from the LIDAR sensor (e.g. <NUM>) capturing the scene <NUM>.

Point cloud data for a scene <NUM> may be captured by a vehicle generating map data. For example, point cloud data for the scene <NUM> may be captured by the sensor <NUM> of the vehicle <NUM>. The scene <NUM> also shows the road <NUM> and the tree <NUM>. The tree <NUM> in the scene <NUM> is a distance D<NUM> from the imaging sensor <NUM>. D4 is less than D<NUM> in the scene <NUM>. Thus, the scene <NUM> may be captured when the vehicle <NUM> is positioned closer to the tree than the vehicle <NUM> was positioned when capturing the scene <NUM>.

Point cloud data for the scene <NUM> may also be captured by a vehicle generating map data. The scene <NUM> shows the road <NUM> and the tree <NUM>. The tree <NUM> in the scene <NUM> is further from the LIDAR sensor capturing the scene <NUM> (e.g. a distance D<NUM>', not shown) than in either the scene <NUM> or <NUM>.

Some aspects may generate a first overlap score <NUM> for point cloud data representing the scenes <NUM> and <NUM>, and a second overlap score <NUM> for point cloud data representing scenes <NUM> and <NUM>. The two overlap scores <NUM> and <NUM> may be compared, with results of the comparison used to select a set of point cloud data for a scene that is closest to the scene <NUM> captured by the autonomous vehicle.

To generate an overlap score, a positional relationship between two scenes may be determined. For example, in some aspects, a "best fit" process may be performed so as to establish a correspondence between point cloud data representing the scene <NUM> and point cloud data representing the scene <NUM>, and similarly to establish a correspondence between point cloud data representing the scene <NUM> and point cloud data representing the scene <NUM>.

<FIG> is a visual representation of a best fit correspondence between point cloud data 502i and 510i representing the scenes <NUM> and <NUM> respectively. As shown in <FIG>, aligning features in each of the point cloud data sets 502i and 510i may result in offsets in one or more dimensions between the point cloud data sets 502i and 510i. For example, point cloud data 502i is shown, in a simplified two dimensional view, offset to the right and below the point cloud data 510i to obtain the best fit. A size of the offsets in a first and second dimension is shown by D<NUM> and D<NUM> respectively. In some aspects, after the correspondence between point cloud data 502i and point cloud data S 10i is established as visually indicated in <FIG> (in two dimensions only for ease of illustration), an overlap score may then be determined based on portions of each set of point cloud data representing a shared three-dimensional space. The shared three-dimensional space is established based on the correspondence. In some aspects, correspondence between two sets of point cloud data establishes coordinate offsets between points in each of the point clouds that represent a common point in three-dimensional space. For example, if the point cloud data 502i is offset to the right relative to point cloud data <NUM>10i by ten (<NUM>) pixels, the correspondence in the horizontal dimension will indicate that data at a position (x, y, z) in point cloud data 502i is to be compared to data at position (x+<NUM>,y,z) in point cloud data 510i.

In some aspects, after the correspondence illustrated in <FIG> is established, the portion of three-dimensional space that is shared by the two sets of point cloud data is illustrated as region <NUM>. An overlap score for region <NUM> of the two point clouds may then be determined in some aspects.

<FIG> show the two sets of point cloud data 502i and 510i respectively. Point cloud data 502i represents the scene <NUM> of <FIG> in three dimensions (only two dimensions shown in <FIG>), while point cloud data S 10i represents scene <NUM> of <FIG> in three dimensions (only two dimensions shown in <FIG>). Regions 610a and 610b are shown within each of point cloud data 502i and <NUM>10i. These regions 610a-b represent the region <NUM> shown in <FIG>, but contained within each of the respective point cloud data 502i and 510i.

Magnified views of portions of regions 610a and 610b are shown as 710a and 710b respectively. Portion 710a includes four points 720a-d while portion 710b includes three points 722a-c. The portions 710a-b are shown in two dimensions for ease of illustration, but the portions shown are intended to represent point cloud data in a three-dimensional space. A location within portion 710b corresponding to point 720d in region 610a is shown as 722d. The two points 720d and 722d may be considered corresponding or "matching" because they have equivalent coordinates in their respective images or point clouds after the images or point clouds are aligned, for example, via a registration process. In some aspects, if the two points have coordinates within a predetermined range of each other, they may also be considered corresponding. The predetermined range may be provided to allow for some error in alignment of point clouds. For example, in some of the disclosed embodiments, the predetermined range may represent a relatively small distance error in the alignment, such as less than any of <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, or <NUM> centimeters. In some embodiments, an overlap score may relate a number of matching points to a total number of points. Thus, in the simplified examples of <FIG>, some embodiments would determine an overlap score of. <NUM> for the two portions 710a and 710b. This approach may be extended to encompass the entirety of regions 610a-b and/or point cloud data 502i and 510i.

<FIG> show example two dimensional representations of point cloud data used to determine an overlap score. The point cloud data <NUM> may be captured from an autonomous vehicle and compared to map data including the point cloud data <NUM>. The point cloud data <NUM> shows a road <NUM>, bridge <NUM>, and building <NUM>. The map point cloud data <NUM> also includes the road <NUM>, bridge <NUM>, and building <NUM>. The map point cloud data <NUM> differs from the vehicle point cloud data <NUM> in that a portion of the building <NUM> is visible above the bridge <NUM> in the vehicle point cloud data <NUM> but not in the map point cloud data <NUM>. In some aspects, this difference may be caused by a difference in height of the two LIDAR sensors that captured the two sets of point cloud data <NUM> and <NUM>. For example, as shown in <FIG> and <FIG>, the sensor <NUM>, mounted on a roof of the vehicle <NUM>, and used to capture point cloud data <NUM>, may be further from the ground (i.e. distance Di) than the sensor <NUM>, mounted on a roof of the car <NUM> (i.e. distance D2) and used to capture map point cloud data <NUM>. An overlap score based on the point cloud data <NUM> and <NUM> may be reduced due to the difference in perspective caused by the different distances D1 and D2, and the resulting building portion <NUM> appearing in point cloud <NUM> but not in point cloud data <NUM>.

Aspects disclosed may determine whether a portion of a three-dimensional space including the building portion <NUM> in point cloud data <NUM> was obscured in point cloud data <NUM>. In some aspects, this determination may be performed in response to determining that the portion <NUM> in point cloud data <NUM> is not present in point cloud data <NUM>. In some aspects, if any portion of three-dimensional space including the building portion <NUM> was obscured in point cloud data <NUM>, that portion may not be included in an overlap score based on the point cloud data <NUM> and point cloud data <NUM>. For example, if an obscured portion of the space occupied by building portion <NUM> included a particular number of data points, those particular number of data points would not be included in the overlap score, in that a total number of points would not include the particular number of points.

<FIG> illustrate tracing of a ray from a laser source to a destination. <FIG> shows the scene <NUM>. Point cloud data representing the scene <NUM> may be captured by an autonomous vehicle, such as the autonomous vehicle <NUM> discussed above with respect to at least <FIG> and <FIG>. <FIG> shows one embodiment of map data <NUM>. The map data <NUM> may include point cloud data captured by a map data collection vehicle, such as the map data collection vehicle <NUM> discussed above with respect to <FIG>. The map data <NUM> may not include the tree <NUM> or the pedestrian <NUM>.

As discussed above, point cloud data representing the scene <NUM> may be compared to point cloud data representing the scene <NUM> when determining a position of an autonomous vehicle in at least some of the disclosed embodiments. The comparison of the two point cloud data sets may identify points representing the tree <NUM> in scene <NUM> that do not have corresponding points in the point cloud representing the scene <NUM>, since the tree <NUM> is not present in the scene <NUM>. These points may be considered non-matching points. In other words, corresponding or "matching" points may be two points in two respective point cloud data sets that have equivalent coordinates after the two point cloud data sets are aligned, for example, via a registration process. In some aspects, some degree of error may be provided for in determining whether two points are corresponding. For example, in some aspects, two points may be considered corresponding if they are within a first predetermined number of units in a first axis (such as an X axis), a second predetermined number of units in a second axis (such as a Y axis), and a third predetermined number of units in a third axis (such as a Z axis).

In some aspects, to determine whether each point representing the tree in scene <NUM> should be included in an overlap score between the two scenes <NUM> and <NUM>, ray tracing data may be generated for the point cloud data representing the scene <NUM>. The ray tracing data may be used to determine if a point exists in the scene <NUM>'s point cloud data at any position along the path of the ray (e.g. ray <NUM> in <FIG>). A source of the ray may be a laser source position of a LIDAR sensor capturing the scene <NUM>. The ray may intersect a location in the scene <NUM> occupied by a non-matching point in the point cloud data for scene <NUM>. The ray may also extend beyond the non-matching point. If the ray intersects a point in the point cloud data representing the scene <NUM>, then the non-matching point in the scene <NUM> may be included in an overlap score. If the ray does not intersect any point in the point cloud data representing the scene <NUM>, in some embodiments, the non-matching point may not be included in the overlap score.

<FIG> is an example of a comparison of point cloud data captured by an autonomous vehicle (e.g. <NUM>) and data included in a map. <FIG> illustrates that with some points, both a normal vector associated with a point and the point itself match. For some additional portion of points, locations of the points match between the two data but the normal vectors are different. This may occur, for example, with foliage, which may be repositioned frequently by wind or even in some aspects by passing vehicles. For some other points, there may not be a point in the map data at a location of a point in the vehicle's point cloud.

<FIG> is a flowchart of an example method of controlling an autonomous vehicle. The process <NUM> discussed below with respect to <FIG> may be performed, in some aspects, by the vehicle controller <NUM>. For example, instructions stored in the memory <NUM> may configure the one or more hardware processors <NUM> to perform one or more of the functions discussed below with respect to <FIG> and process <NUM>.

Process <NUM> determines an overlap score. The overlap score indicates an amount of overlap between position data collected by a first vehicle, for example, from a LiDAR sensor, and map data. The map data may be generated prior to performance of the process <NUM>. The map data may be based on data obtained from a separate sensor mounted on a different second vehicle. As discussed above, differences in height between the first sensor and the second sensor may result in reduced overlap between the vehicle data and the map data. In some aspects, this may have deleterious effects if not properly compensated.

In block <NUM>, a point cloud is captured with a LIDAR sensor. For example, in some aspects, point cloud data representing the scene <NUM> may be captured by the sensor <NUM>. The point cloud data is representative of a surrounding of an autonomous vehicle. For example, as discussed above with respect to <FIG>, the sensor <NUM> may capture the scene 105immediately in front of the vehicle <NUM>.

In block <NUM>, a point is identified in the point cloud data as a non-matching point in response to the point having no corresponding point in a map. The map may also include three-dimensional data or point cloud data. The three-dimensional space represented by each of the point cloud data and the map is compared. In some aspects, at least a portion of points in the captured point cloud data will match a point in the map data. Another portion of points may not have a corresponding matching point in the map. For example, if a point in the point cloud data represents a reflection of LIDAR signals from an object at a location in the point cloud, the corresponding location in the map may be empty, or in other words, may not indicate a reflection of LIDAR data.

Corresponding or "matching" points may be two points in the captured point cloud data and the map data respectively that have equivalent coordinates after the two point cloud data sets are aligned, for example, via a registration process. In some aspects, some degree of error may be provided for in determining whether the two points are corresponding or matching. For example, in some aspects, two points may be considered corresponding if they are within a first predetermined number of units in a first axis (such as an X axis), a second predetermined number of units in a second axis (such as a Y axis), and a third predetermined number of units in a third axis (such as a Z axis). In some aspects, if the two points have coordinates within a predetermined range of each other, they may also be considered corresponding. The predetermined range may be provided to allow for some error in alignment of point clouds. For example, in some of the disclosed embodiments, the predetermined range may represent a relatively small absolute distance error in the alignment, such as less than any of <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, or <NUM> centimeters.

In some aspects, a height parameter for the map may be determined. For example, some aspects may store information relating to distance D<NUM> with the map generated by the vehicle <NUM>. The height parameter may be compared to a height of the one or more Lidar sensors used to capture the point cloud in block <NUM> (e.g. Di). The point-cloud data may be adjusted based on the comparison.

In some aspects, an angle of the one or more LIDAR sensors with respect to a reference plane may be determined, and compared with an angle associated with the map data. The point-cloud data based on the angle in some aspects. After one or more of the adjustments, the determination of whether the point is a matching point or a non-matching point may be made.

In block <NUM>, a determination is made as to whether the non-matching point is used in an overlap score. The determination is based on one or more comparisons of the point cloud data and the map. For example, in some aspects, in some aspects, block <NUM> may determine whether the corresponding position in the map is obscured in the map data. As discussed above, in some aspects, because of differences in perspective between a LIDAR sensor used to capture the map data, and a LIDAR sensor used to capture point cloud data for an autonomous vehicle, some objects visible to the LIDAR sensor(s) of the autonomous vehicle may not be visible to the LIDAR sensor collecting data for the map.

Some aspects may generate ray-tracing data representing a tracing of a ray from a laser source of the one or more Lidar sensors to a location in the map corresponding to the location of the non-matching point. If a point is at the location in the map, the non-matching point may be included in the determination of the overlap score. If there is no point at the location in the map, the non-matching point may not be included in the determination of the overlap score.

Some aspects may determine whether the non-matching point corresponds to a non-occluded point of the map; and include the non-matching point in the determination of the overlap score in response to the non-matching point corresponding to a non-occluded point. For example, as discussed with respect to <FIG>, some objects, such as the building <NUM>, may be represented by the point cloud data representing a scene captured by an autonomous vehicle, but may be obscured in point cloud data of the map. In these cases, non-matching points may not be considered in an overlap score.

In block <NUM>, the overlap score is determined based on the included points and the map. The overlap score relates a number of point that map to the map to a total number of points included in the determination of the overlap score.

In block <NUM>, a position of the vehicle is determined based on the overlap score. For example, as discussed above, an overlap score may be determined for a plurality of map point cloud data sets. A set of point cloud data in the map having the highest overlap score with vehicle point cloud data may be selected as most closely approximating the vehicle position. Offsets from the selected map point cloud data may then be determined to determine a more precise position of the vehicle relative to the selected map point cloud data.

In block <NUM>, the vehicle is controlled based on the determined position. For example, as discussed above, the controller <NUM> may send a command to one or more of the motor controller <NUM>, steering controller <NUM>, and braking controller <NUM> to control the vehicle based on the determined position. For example, if the determined position indicates the vehicle is not centered in a lane of travel, the controller <NUM> may send a command to the steering controller <NUM> to adjust the path of the vehicle to move the vehicle closer to the center of the lane. As another example, if the determined position is within a predetermined threshold distance of a curve in a road, the controller <NUM> may send a command to the braking controller <NUM> and/or motor controller <NUM> to reduce a speed of the vehicle.

In some aspects, process <NUM> includes determining a motion plan for the autonomous vehicle. The motion plan may be based in some aspects on the overlap score. Process <NUM> may include sending a signal to one or more of a steering controller, engine controller, or braking controller based on the motion plan.

As used herein, the term "machine-readable medium," "computer-readable medium," or the like may refer to any component, device, or other tangible medium able to store instructions and data temporarily or permanently. Examples of such media may include, but are not limited to, random-access memory (RAM), read-only memory (ROM), buffer memory, flash memory, optical media, magnetic media, cache memory, other types of storage (e.g., Electrically Erasable Programmable Read-Only Memory (EEPROM)), and/or any suitable combination thereof. The term "machine-readable medium" should be taken to include a single medium or multiple media (e.g., a centralized or distributed database, or associated caches and servers) able to store instructions. The term "machine-readable medium" may also be taken to include any medium, or combination of multiple media, that is capable of storing instructions (e.g., code) for execution by a machine, such that the instructions, when executed by one or more processors of the machine, cause the machine to perform any one or more of the methodologies described herein. Accordingly, a "machine-readable medium" may refer to a single storage apparatus or device, as well as "cloud-based" storage systems or storage networks that include multiple storage apparatus or devices. The term "machine-readable medium" excludes transitory signals per se.

Where a phrase similar to "at least one of A, B, or C," "at least one of A, B, and C," "one or more of A, B, or C," or "one or more of A, B, and C" is used, it is intended that the phrase be interpreted to mean that A alone may be present in an embodiment, B alone may be present in an embodiment, C alone may be present in an embodiment, or any combination of the elements A, B, and C may be present in a single embodiment; for example, A and B, A and C, B and C, or A and B and C may be present.

Claim 1:
A method of controlling an autonomous vehicle (<NUM>), comprising:
obtaining map data (510i; <NUM>) including a three dimensional, <NUM>-D, point cloud representing a perspective of a sensor (<NUM>) on a mapping vehicle (<NUM>);
capturing (<NUM>) point-cloud data (502i; <NUM>) representative of a surrounding environment of the autonomous vehicle (<NUM>) with one or more light detection and ranging, LIDAR, sensors (<NUM>), each point in the point-cloud data representing a reflection from the surrounding environment;
determining (<NUM>) a position of the autonomous vehicle in the area mapped by the mapping vehicle based on an overlap score (<NUM>; <NUM>) and the map data (510i; <NUM>); and
controlling (<NUM>) the autonomous vehicle based on the position;
characterized by
identifying (<NUM>) a first point in the point cloud data as a non-matching point by aligning the captured point cloud data with the map data and determining that there is no point in the map data having equivalent coordinates to the first point;
determining (<NUM>) whether the non-matching point is to be used in a determination of the overlap score (<NUM>; <NUM>) based on one or more comparisons of the point cloud data and the map data, the overlap score being a ratio of a number of points in the point cloud data that match points in the map data, to a total number of points in the point cloud data,
wherein if the non-matching point is not included in the overlap score, the total number of points does not include the non-matching point;
determining (<NUM>) the overlap score based at least partly on the determining that the non-matching point is to be used in the determination of the overlap score, the overlap score being determined by determining a ratio between (i) the number of points in the point cloud data that match points in the map data and (ii) the total number of points in the point cloud data