RU2842879C2 - Method and server for updating map view - Google Patents

Abstract

FIELD: physics.

SUBSTANCE: invention relates to methods and a server for updating a map representation of a geographic region. Method provides for time stamp on previous trajectory of unmanned vehicle, when unmanned vehicle was in specified place of geographical region, formation by server using an algorithm for localizing a plurality of possible locations of the unmanned vehicle using a set of point clouds associated with a given location located in the considered part of the map presentation and the map presentation; determination by the server using the convergence metric of the parameter for assessing the localization quality provided by the localization algorithm when the unmanned vehicle is in the considered part of the map presentation, wherein the parameter characterizes the convergence of the probable locations of the unmanned vehicle from the plurality of probable locations of the unmanned vehicle; recognition by the server of the considered part of the map representation as an obsolete part of the map representation based on the parameter if the value of the parameter exceeds a predetermined threshold value; and the server updating the legacy part of the map representation using the actual point cloud data collected by the lidar system.

EFFECT: higher accuracy of vehicle localization.

19 cl, 10 dwg

Description

Field of technology to which the invention relates

[001] The present technology relates to lidar systems in general and, in particular, to methods and servers for updating a map representation.

State of the art

[002] In known solutions, computer navigation systems are proposed and implemented to assist in navigation and/or in driving vehicles. These include a whole range of systems - from simple solutions based on determining the location on a map and using a computer system to assist the driver in navigating along a route from the point of departure to the point of destination, to more complex solutions, such as computerized and/or autonomous driving systems.

[003] Some of these systems are implemented in the form of the well-known cruise control system. In systems of this type, a computer system installed in the vehicle maintains the vehicle speed set by the user. Some cruise control systems implement an intelligent distance control system, in which the user can set the distance to the vehicle moving in front (for example, select a value expressed in the number of vehicles), and the computer system regulates the speed of the vehicle, at least in part, when it approaches the vehicle moving in front by a set distance. Some of the cruise control systems are additionally equipped with a collision avoidance system, which, upon detection of a vehicle (or other obstacles) in front of the moving vehicle, slows down or stops it.

[004] Some of the most advanced systems provide fully autonomous vehicle operation without direct operator (i.e. driver) involvement in the control. Such autonomous vehicles contain systems capable of accelerating, decelerating, stopping, changing lanes, and parking the vehicle independently.

[005] One of the main technical problems in implementing the above systems is to ensure the ability to detect objects around the vehicle. In particular, in such systems there may be a need to detect another vehicle in front of the vehicle with the installed system that poses a danger to the vehicle and may require the system to take preventive measures, such as braking or otherwise changing speed, stopping or changing lanes. In addition, in such systems there may be a need to detect pedestrians or animals crossing the road in front of the vehicle or otherwise moving in the vehicle's surrounding space.

[006] Detecting objects using lidar typically involves emitting light beams into an area of interest and detecting reflected light beams, particularly from objects in the area, to form a representation of the area of interest containing any objects. Lasers, which emit pulses of light in a narrow range of wavelengths, are often used as the radiation (light) source. The position of and distance to an object can be determined, among other things, by calculating the time of flight of the emitted and detected light beams. By calculating such positions as "data points", a multi-dimensional digital representation of the surrounding space can be formed.

[007] This three-dimensional representation is created in part by the reflected rays received by the lidar, which forms data points representing objects in the surrounding space. These points form clouds that characterize the surrounding space and form a three-dimensional map. Each point in such a point cloud is associated with coordinates in the coordinate space. In addition, each point may be associated with some additional information, such as the distance from the self-driving vehicle to the object. Other information may also be associated with the points in the point cloud.

[008] Point clouds obtained by a self-driving car (SDC) can be used not only to detect objects in the surrounding space, but also to determine the current location of the self-driving car. This process is called localization. One method of localization is based on combining the existing point cloud obtained by lidar and a map. Such localization may be unsatisfactory, especially if the map is not up-to-date.

[009] Patent publication US2019204092 discloses a vehicle that performs localization to determine its current location while driving using various localization methods.

Disclosure of invention

[010] Thus, there is a need for systems and methods that can eliminate, reduce or overcome the shortcomings of known technical solutions.

[011] Laser detection and ranging systems, i.e., LIDAR (Light Detection and Ranging) systems, are widely used in unmanned vehicles to detect objects and navigate in the surrounding space. They accumulate points corresponding to light rays reflected from objects in the surrounding space and form a point cloud from them, which serves as a three-dimensional representation of a map of the surrounding space.

[012] During navigation, point clouds obtained by the lidar system, along with a map representation of the geographic region in which the self-driving car operates, can be used to determine the current location of the self-driving car. Accordingly, such map representations can be used in self-driving cars to safely navigate to destinations without human intervention or with limited human intervention.

[013] In some embodiments, the map representation may be a high definition (HD) map. In general, the term "high definition map" refers to a map representation whose data is characterized by a very low error, typically 5-10 cm. For example, high resolution maps may contain spatial geometric information about roads along which an unmanned vehicle may travel. Thus, the created high resolution maps include information necessary to ensure safe navigation of an unmanned vehicle without human intervention. In other embodiments, it is assumed that the map representation may be constructed based on lidar data obtained in a geographic region, which were combined into a single array representing this geographic region. The high resolution map may be represented as a point cloud, a voxel array and/or an object-oriented structure.

[014] As mentioned above, in order to navigate, a self-driving car needs to perform localization, that is, determine its current location with high accuracy. A number of localization methods can be used to determine the current location of a self-driving car.

[015] In some embodiments, the localization method may be based on odometry, which is the process of estimating the relative movement of a vehicle using data sequentially obtained by the vehicle's sensors. Odometry may be used in the localization algorithm to determine the position of the vehicle for the purpose of performing a local search by the localization algorithm. In addition, odometry may be used in the localization algorithm to estimate the speed and acceleration of the vehicle by extrapolating the position of the vehicle between the times of taking readings from the sensors intended for localization. For example, in the event of a failure of any localization data sources, the unmanned vehicle may resort to odometry to estimate its movement relative to a known previous position from signals from an inertial measurement unit (IMU) or from vehicle control signals. Another localization method is lidar localization. Localization data sources based on lidar localization include various localization options based on terrestrial or non-terrestrial objects, in which the features of terrestrial and non-terrestrial objects are processed and compared separately, lidar localization in which all points are processed and compared instead of points with high signal intensity, lidar localization in which color matching is performed, lidar localization in which artificial terrain (hard surfaces, such as building surfaces) and natural terrain (vegetation) are distinguished, etc. Another localization method is feature-based localization in which features are extracted using sensor data such as camera images, and the lidar scans these features and compares them with features on a high-resolution map to determine the location of the vehicle. Another localization method uses visual odometry to determine the location of the vehicle. In various versions of visual odometry, the vehicle location is determined by comparing various features identified in camera images with features on a map, such as surface relief, image features, contours, etc. Another localization method uses lidar odometry to determine the vehicle location. In various versions of lidar odometry, the iterative closest point (ICP) algorithm with pairwise comparison or the iterative closest point algorithm with multiple scans is used. Various versions of the above methods are implemented by replacing certain parameters, such as iteration limits, search radius, weighting factors, etc. Other localization methods include GNSS-based localization and inertial measurement unit-based odometry. Various versions of these methods use a variety of integration methods and correction techniques.

[016] The effectiveness of the localization method may depend on various factors, such as the current environment in which the autonomous vehicle is located, including the geometric characteristics of the structures around the autonomous vehicle, identifiable photometric features, etc. It should be noted that the effectiveness of localization methods that use map representations decreases when the map representation becomes irrelevant.

[017] In some embodiments of the present technology, methods and devices are developed for determining portions of a map representation that need to be updated. In other embodiments, methods and devices are developed in which one or more metrics can be used to determine the convergence of probable locations in a given portion of a map representation. In additional embodiments, methods and devices are developed that allow evaluating the reliability of the results of the localization algorithm during the actions of the unmanned vehicle so that the results of the localization algorithm are excluded from the array of data coming from various sources of localization data for controlling the unmanned vehicle, in cases where the localization algorithm is recognized as ineffective (e.g., generating divergent probable locations) in the considered portion of the map representation.

[018] It may be stated that in some embodiments, a first map representation and a second map representation are used. The second map representation may be constructed from point clouds for the first trajectory. For the second trajectory, localization may be unsatisfactory when using the first map representation and satisfactory when using the second map representation. In some embodiments, the first trajectory may be used in the process of preliminary detection of outdated portions of the map. In other embodiments, when it is determined that a particular portion of the map is outdated, the second trajectory may be used to confirm the need for updating, and the first trajectory - in the actual updating.

[019] According to a first broad aspect of the present technology, a method for updating a map representation of a geographic region is implemented. The map representation was created based on point cloud data collected by a lidar system of an unmanned vehicle operating in this geographic region. The method is implemented on a server. The method provides for a time stamp on the previous trajectory of the unmanned vehicle, when the unmanned vehicle was in a given place of the geographic region, the server, using a localization algorithm, forming a plurality of probable locations using a set of point clouds and a map representation. The set of point clouds is associated with a given place. The given place is in the considered part of the map representation. The method provides for a time stamp on the previous trajectory of the unmanned vehicle, when the unmanned vehicle was in a given place of the geographic region, the server, using a convergence metric, determining a parameter for assessing the quality of localization provided by the localization algorithm when the unmanned vehicle is in the considered part of the map representation. This parameter characterizes the convergence of probable locations from a plurality of probable locations. The method provides for the time stamp on the previous trajectory of the unmanned vehicle, when the unmanned vehicle was in a given location of the geographic region, recognition by the server of the considered part of the map representation as an outdated part of the map representation based on this parameter. Such recognition occurs when the value of the parameter exceeds a specified threshold radius. The method provides for updating by the server of the outdated part of the map representation using point cloud data collected by the lidar system.

[020] In some embodiments, the parameter characterizes the convergence of the first probable location and the second probable location within a specified threshold.

[021] In some embodiments of the method, the first probable location is a first probable position of the unmanned vehicle, wherein the specified threshold value is a specified radius, and the portion of the map representation under consideration is recognized as an outdated portion of the map representation if the first probable position and the second probable position do not fall within a circle of the specified radius.

[022] In some embodiments of the method, the first probable location further includes a first probable orientation of the unmanned vehicle, wherein the specified threshold value is further a specified angle, and the considered portion of the map representation is recognized as an outdated portion of the map representation if the first probable position and the second probable position do not fall within a circle of a specified radius and/or if the first probable orientation and the second probable orientation do not fall within a sector of a specified angle.

[023] According to a second broad aspect of the present technology, a method for updating a representation of a map of a geographic region is implemented. The representation of the map was created based on point cloud data collected by a lidar system of an unmanned vehicle operating in this geographic region. The method is implemented on a server. The method involves determining, by the server, a previous trajectory of the unmanned vehicle in the geographic region. The previous trajectory is associated with a plurality of point clouds from the log data of the unmanned vehicle. The plurality of point clouds were obtained by the lidar system during the movement of the unmanned vehicle along this trajectory in the geographic region. The method involves, for a time stamp on the previous trajectory of the unmanned vehicle, when the unmanned vehicle was at a given location in the geographic region, determining by the server a first point cloud from a plurality of point clouds that were obtained by the lidar system at a time corresponding to this time stamp. The method provides for a timestamp on the previous trajectory of the unmanned vehicle, when the unmanned vehicle was in a given location of the geographic region located in the considered part of the map representation, the formation by the server using a localization algorithm of the first probable location based on the first point cloud and the map representation. The method provides for a timestamp on the previous trajectory of the unmanned vehicle, when the unmanned vehicle was in a given location of the geographic region, the determination by the server of a second point cloud associated with the given location. The method provides for a timestamp on the previous trajectory of the unmanned vehicle, when the unmanned vehicle was in a given location of the geographic region, the formation by the server using a localization algorithm of a second probable location based on the second point cloud and the map representation. The method provides for a timestamp on the previous trajectory of the unmanned vehicle, when the unmanned vehicle was in a given location of the geographic region, the determination by the server using a convergence metric of a parameter for assessing the quality of localization provided by the localization algorithm in the considered part of the map representation. This parameter characterizes the convergence of the first probable location and the second probable location. The method provides for the time stamp on the previous trajectory of the unmanned vehicle, when the unmanned vehicle was in a given location of the geographic region, recognition by the server of the considered part of the map representation as an outdated part of the map representation based on this parameter. The method provides for updating by the server the outdated part of the map representation using the point cloud data collected by the lidar system.

[024] In some embodiments of the method, determining the second point cloud includes generating by the server, based on the first point cloud, a simulated point cloud that is a degraded version of the first point cloud.

[025] In some embodiments of the method, the degraded version of the first point cloud is the first point cloud without some subset of the points.

[026] In some embodiments of the method, generating the simulated point cloud includes the server applying a filter that reflects the effect of environmental conditions on the first point cloud.

[027] In some embodiments of the method, the environmental conditions are rain, snow, and/or dirt that interfere with the operation of the lidar system.

[028] In some embodiments of the method, determining the second point cloud includes determining by the server the second point cloud based on log data of a second unmanned vehicle operating in the geographic region and equipped with a second lidar system, wherein the second point cloud was obtained by the second lidar system when the second unmanned vehicle was in a given location.

[029] In some embodiments of the method, the server is configured to execute a Machine Learning Algorithm (MLA). The method further comprises the server generating a training set containing initial data for training, which includes a map representation, a first probable location and a first point cloud, and a training label based on the parameter. The method further comprises the server training a machine learning algorithm for generating a second parameter using the training set. The second parameter indicates the ability of the localization algorithm to generate converging probable locations for the unmanned vehicle in the considered part of the map representation.

[030] In some embodiments of the method, the probable locations are considered to converge if the localization algorithm generates probable locations that converge within a specified threshold.

[031] In some embodiments of the method, the server is configured to execute a machine learning algorithm. The method further comprises generating by the server a training set containing initial data for training, which includes a map representation, a second probable location, a second point cloud, and a training label based on the parameter. The method further comprises training by the server a machine learning algorithm for generating a second parameter using the training set. The second parameter indicates the ability of the localization algorithm to generate converging probable locations for the unmanned vehicle in the considered part of the map representation.

[032] In some embodiments, the method further comprises, for a timestamp on a previous trajectory of the unmanned vehicle, when the unmanned vehicle was at a given location of the geographic region, determining by the server, using a second convergence metric, a second parameter for assessing the quality of localization provided by the localization algorithm in the considered portion of the map representation. The second parameter serves as an indication of the tendency of the localization algorithm to generate divergent probable locations for the unmanned vehicle in the considered portion of the map representation. The method further comprises, for a timestamp on a previous trajectory of the unmanned vehicle, when the unmanned vehicle was at a given location of the geographic region, recognizing by the server the considered portion of the map representation as an outdated portion of the map representation using the parameter and/or the second parameter.

[033] According to a third aspect of the present technology, a method for controlling the actions of an unmanned vehicle is implemented. The unmanned vehicle is connected to a laser detection and ranging system (lidar system) and an electronic device containing a processor. The processor is configured to collect data from a plurality of localization data sources to determine the location of the unmanned vehicle on a map representation of a geographic region. The method is implemented by the processor. The method provides for, at the moments of the actions of the unmanned vehicle corresponding to the time marks when the unmanned vehicle is in the current location of the geographic region, the formation by the processor, using a localization algorithm, of a probable location of the unmanned vehicle based on a point cloud obtained by the lidar system, a map representation and an initial approximation of the current location of the unmanned vehicle on the map representation. The method involves, at the moments of the unmanned vehicle actions corresponding to the time marks, when the unmanned vehicle is in the current location of the geographic region, the formation by the processor using the machine learning algorithm of a parameter indicating the ability of the localization algorithm to form converging probable locations of the unmanned vehicle in the considered part of the map representation, including the current location, under various conditions. The method involves, at the moments of the unmanned vehicle actions corresponding to the time marks, when the unmanned vehicle is in the current location of the geographic region, the processor determining, based on the parameter, whether the localization algorithm is an unreliable source of localization data in the considered part of the map representation. The method involves, at the moments of the unmanned vehicle actions corresponding to the time marks, when the unmanned vehicle is in the current location of the geographic region, the determination by the server of the location of the unmanned vehicle based on data from a plurality of sources, using data collected from a reduced plurality of localization data sources, which is a plurality of localization data sources excluding the localization algorithm. The method provides for, at the moments of the actions of the unmanned vehicle corresponding to the time marks, when the unmanned vehicle is in the current location of the geographic region, control by the processor of the actions of the unmanned vehicle, in which the current location of the unmanned vehicle is a location determined on the basis of data from a plurality of sources.

[034] According to a fourth aspect of the present technology, a server is implemented for updating a map representation of a geographic region. The map representation was created based on point cloud data collected by a lidar system of an unmanned vehicle operating in this geographic region. The server is capable of determining a previous trajectory of the unmanned vehicle in the geographic region associated with a plurality of point clouds from the log data of the unmanned vehicle, which was obtained by the lidar system during the movement of the unmanned vehicle along this trajectory in the geographic region. The server is capable, for a time stamp on the previous trajectory of the unmanned vehicle, when the unmanned vehicle was at a given location of the geographic region, of determining a first point cloud from a plurality of point clouds that were obtained by the lidar system at a moment corresponding to this time stamp. The server is capable, for a time stamp on the previous trajectory of the unmanned vehicle, when the unmanned vehicle was at a given location of the geographic region located in the considered part of the map representation, of generating, using a localization algorithm, a first probable location using the first point cloud and the map representation. The server is capable of determining a second point cloud associated with the specified location for a timestamp on the previous trajectory of the unmanned vehicle, when the unmanned vehicle was in a given location of the geographic region. The server is capable of forming a second probable location based on the second point cloud and the map representation for a timestamp on the previous trajectory of the unmanned vehicle, when the unmanned vehicle was in a given location of the geographic region, using a localization algorithm. The server is capable of determining, for a timestamp on the previous trajectory of the unmanned vehicle, when the unmanned vehicle was in a given location of the geographic region, using a convergence metric, a parameter for assessing the quality of localization provided by the localization algorithm in the considered part of the map representation, which characterizes the convergence of the first probable location and the second probable location. The server is capable of recognizing the considered part of the map representation as an outdated part of the map representation based on this parameter for a timestamp on the previous trajectory of the unmanned vehicle, when the unmanned vehicle was in a given location of the geographic region. The server is able to update the outdated portion of the map view using point cloud data collected by the lidar system.

[035] In some embodiments of the server, its ability to determine a second point cloud includes the ability to generate, using the first point cloud, a simulated point cloud that is a degraded version of the first point cloud.

[036] In some embodiments of the server, the degraded version of the first point cloud is the first point cloud without some subset of the points.

[037] In some embodiments of the server, the ability to generate a simulated point cloud includes the ability to apply a filter reflecting the effect of environmental conditions on the first point cloud.

[038] In some embodiments of the server, the environmental conditions are rain, snow, and/or dirt that interfere with the operation of the lidar system.

[039] As used herein, the term "light source" broadly refers to any device capable of emitting radiation, in particular transmitting a signal in the form of a beam, such as, but not limited to, a light beam of one or more wavelengths in the electromagnetic spectrum. In one embodiment, the light source may be a laser source. Thus, the light source may comprise a laser, such as a solid-state laser, a laser diode, a high-power laser, or an alternative light source, such as a light source based on light emitting diodes. Some (non-limiting) examples of a laser source are a Fabry-Perot laser diode, a quantum well laser, a Distributed Bragg Reflector (DBR) laser, a Distributed FeedBack (DFB) laser, a fiber laser, or a Vertical-Cavity Surface-Emitting Laser (VCSEL). In addition, the laser source may emit light beams in various formats, such as light pulses, continuous oscillations, quasi-continuous oscillations, etc. In some non-limiting examples, the laser source may comprise a laser diode capable of emitting light with a wavelength in the range of about 650-1150 nm. Alternatively, the light source may comprise a laser diode capable of emitting light beams with a wavelength in the range of about 800-1000 nm, about 850-950 nm, about 1300-1600 nm, or any other suitable range. Unless otherwise specified, the term "about" with respect to a numerical value is defined as a deviation that does not exceed 10% of the specified value.

[040] In the context of the present description, the term "output beam" may refer to a beam of radiation, such as a beam of light, generated by a radiation source and directed toward a region of interest. The output beam may be characterized by one or more parameters such as radiation duration, beam angular divergence, wavelength, instantaneous power, photon density at different distances from the light source, average power, beam power density, beam width, radiation pulse repetition frequency, emitted pulse sequence, pulse duty cycle, wavelength, phase, etc. The output beam may be unpolarized or randomly polarized, may have no defined or constant polarization (e.g., polarization may change over time), or may have a defined polarization (e.g., linear, elliptical, or circular polarization).

[041] As used herein, an "input beam" is a beam of radiation or light that enters the system, typically after being reflected from one or more objects in the region of interest. An "input beam" may also be referred to as a radiation beam or a light beam. The term "reflected" means that at least a portion of the output beam is incident on and reflected from one or more objects in the region of interest. The input beam may be characterized by one or more parameters such as time of flight (i.e., the time from the moment of emission to the moment of detection), instantaneous power (e.g., power signature), average power of the return pulse, distribution of photons in the signal over the period of the return pulse, etc. In some applications, some of the radiation or light in the input beam may not be the reflected output beam, but radiation from other sources. For example, at least some portion of the input beam may represent glitches, light noise from the surrounding environment (including diffuse sunlight) or from other light sources external to the system.

[042] In the context of the present description, the term "surrounding space" or "environment" of a vehicle refers to the area or volume around that vehicle, including that portion of its current environment that is accessible for scanning using one or more sensors mounted on that vehicle, such as to create a three-dimensional map of the surrounding space or to detect objects in it.

[043] In the context of the present description, the term "region of interest" in a broad sense may include a portion of the observed surrounding space of the lidar system in which one or more objects can be detected. It should be noted that the region of interest of the lidar system may be affected by various conditions, such as, among other things, the orientation of the lidar system (e.g., the direction of the optical axis of the lidar system), the position of the lidar system in the surrounding space (e.g., the distance above the ground, as well as the terrain and obstacles in the immediate vicinity of the system), the operating parameters of the lidar system (e.g., the radiant power, computing settings, specified operating angles), etc. The region of interest of the lidar system can be defined, for example, by a plane or solid angle. In one example, the region of interest can also be defined by a range (e.g., up to approximately 200 m).

[044] As used herein, a "server" is a computer program executed by appropriate hardware and capable of receiving requests (e.g., from electronic devices) over a network and of executing or causing these requests to be executed. Such hardware may be implemented as a single physical computer or a single physical computer system, which is not essential to the present technology. As used herein, the term "server" does not imply that any particular task or all tasks (e.g., received commands or requests) are received, executed or started on the same server (i.e., by the same software and/or hardware), but rather that any number of software or hardware may participate in receiving, transmitting, executing or causing the execution of any tasks or requests or the results of any tasks or requests, and all of these software and hardware may represent a single server or multiple servers, and the term "at least one server" includes both of these cases.

[045] In the context of the present description, an "electronic device" is any computer hardware capable of running software suitable for the task. In the context of the present description, the term "electronic device" implies that the device can function as a server for other electronic devices, although this is not a requirement for the present technology. Thus, non-limiting examples of electronic devices include an autonomous driving unit, personal computers (desktop computers, laptops, netbooks, etc.), smartphones and tablets, as well as network equipment such as routers, switches and gateways. It should be understood that in this context, the fact that equipment functions as an electronic device does not mean that it cannot function as a server for other electronic devices.

[046] In the context of this description, the term "information" includes information of any kind or type capable of being stored in a database. Thus, information includes, among other things, visual works (e.g., maps), audiovisual works (e.g., images, films, sound recordings, presentations, etc.), data (e.g., location data, weather data, traffic data, numerical data, etc.), text (e.g., reviews, comments, questions, messages, etc.), documents, spreadsheets, etc.

[047] As used herein, the term "database" means any structured collection of data, regardless of its specific structure, software for managing the database, and computer hardware for storing such data, using it, or otherwise enabling its use. A database may reside on the same hardware as the process that enables the storage or use of the information stored in the database, or on separate hardware such as a dedicated server or group of servers.

[048] In the context of the present description, the numerals "first," "second," "third," etc., serve merely to indicate a distinction between the nouns to which they refer, and do not describe any specific relationships between those nouns. Furthermore, as occurs in other contexts in the present description, references to a "first" element and a "second" element do not exclude the possibility that these two elements may in fact be the same element.

[049] Each embodiment of the present technology relates to at least one of the above-mentioned objectives and/or to one of the above-mentioned aspects, but not necessarily to all of them. It should be understood that some aspects of the present technology associated with an attempt to achieve the above-mentioned objective may not correspond to this objective and/or may correspond to other objectives not explicitly mentioned herein.

[050] Additional and/or alternative features, aspects and advantages of embodiments of the present technology are contained in the following description, in the attached drawings and in the claims.

Brief description of the drawings

[051] These and other features, aspects and advantages of the present technology are contained in the following description, in the appended claims and in the following drawings.

[052] Fig. 1 is a schematic representation of an example of a computer system suitable for implementing certain non-limiting embodiments of the present technology.

[053] Fig. 2 is a schematic representation of a networked computing environment suitable for use with certain non-limiting embodiments of the present technology.

[054] Fig. 3 is a schematic representation of an example of a lidar system implemented in accordance with certain non-limiting embodiments of the present technology.

[055] Fig. 4 shows data stored in a data storage device that is accessed by a server and an electronic device from the networked computer environment shown in Fig. 2.

[056] Fig. 5 shows a plurality of computer procedures performed by a server and an electronic device.

[057] Fig. 6 illustrates how a plurality of point clouds associated with a previous trajectory of a vehicle are determined from the networked computer environment shown in Fig. 2 and a simulated point cloud is generated in accordance with some non-limiting embodiments of the present technology.

[058] Fig. 7 shows a localization algorithm used to generate probable vehicle locations.

[059] Fig. 8 shows the first metric applied to the probable locations generated by the localization algorithm.

[060] Fig. 9 shows a training iteration and a usage iteration for a second metric in accordance with some non-limiting embodiments of the present technology.

[061] Fig. 10 is a block diagram of a method implemented in accordance with some non-limiting embodiments of the present technology.

Implementation of the invention

[062] The examples and conventional language provided herein are intended to provide a better understanding of the principles of the present technology and are not intended to limit its scope to such specifically provided examples and conditions. It should be understood that those skilled in the art are capable of developing various methods and devices that are not explicitly described or shown, but implement the principles of the present technology within its spirit and scope.

[063] Furthermore, to facilitate better understanding, the following description may contain simplified embodiments of the present technology. Those skilled in the art will understand that various embodiments of the present technology may be significantly more complex.

[064] In some cases, supposedly useful examples of modifications of the present technology are given. They are intended only to facilitate understanding and also do not define the scope or boundaries of the present technology. The list of modifications provided is not exhaustive and a person skilled in the art can develop other modifications within the scope of the present technology. In addition, if in some cases modifications are not described, this does not mean that they are impossible and/or that the description contains the only possible embodiment of a particular element of the present technology.

[065] The description of the principles, aspects and embodiments of the present technology, as well as specific examples thereof, are intended to cover their structural and functional equivalents, regardless of whether they are currently known or will be developed in the future. For example, those skilled in the art should understand that all block diagrams provided herein correspond to conceptual representations of illustrative circuit diagrams implementing the principles of the present technology. It should also be understood that all block diagrams, process diagrams, state transition diagrams, pseudocodes, etc. correspond to various processes that can be represented on a machine-readable physical storage medium and can be executed by a computer or processor, regardless of whether such a computer or processor is explicitly shown or not.

[066] The functions of the various elements shown in the drawings, including all functional blocks designated as a "processor", may be implemented using dedicated hardware as well as hardware capable of running associated software. If a processor is used, these functions may be performed by a single dedicated processor, a single shared processor, or multiple separate processors, some of which may be shared. Furthermore, the explicit use of the term "processor" or "controller" shall not be construed as referring exclusively to hardware capable of running software, and may include, but are not limited to, a digital signal processor (DSP), a network processor, an application-specific integrated circuit (ASIC), a field programmable gate array (FPGA), ROM for storing software, RAM, and non-volatile memory. Other general-purpose and/or custom hardware may also be included.

[067] Software modules or simply modules, the implementation of which is supposed to be based on software, may be represented here as any combination of flow chart elements or other elements indicating the execution of process steps and/or containing a text description. Such modules may be implemented using hardware, shown explicitly or implied.

[068] Taking into account the above principles, some non-limiting examples are discussed below to illustrate various embodiments of aspects of the present technology.

Computer system

[069] Fig. 1 is a diagram of a computer system 100 suitable for use in some embodiments of the present technology. The computer system 100 includes various hardware elements, including one or more single-core or multi-core processors, collectively represented by a processor 110, a solid-state drive 120, and a memory 130, which may be random access memory or any other type of memory.

[070] Communication between elements of the computer system 100 may be accomplished via one or more internal and/or external buses (not shown), such as a PCI bus, a USB bus, an IEEE 1394 FireWire bus, a SCSI bus, a Serial-ATA bus, etc., to which various hardware elements are electronically connected. According to embodiments of the present technology, the solid-state drive 120 stores software instructions suitable for loading into the memory 130 and executing by the processor 110 to determine the presence of an object. For example, the software instructions may be part of a vehicle control application executed by the processor 110. It should be noted that the computer system 100 may contain additional and/or optional elements (not shown), such as network data communication modules, location determination modules, etc.

Networked computing environment

[071] Fig. 2 illustrates a networked computing environment 200 suitable for use with certain non-limiting embodiments of the present technology. The networked computing environment 200 includes an electronic device 210 coupled to a vehicle 220 and/or to a user (not shown) who is coupled to the vehicle 220 (in particular, to an operator of the vehicle 220). The networked computing environment 200 also includes a server 235 coupled to the electronic device 210 via a communications network 240 (e.g., via the Internet, etc., as described in more detail below).

[072] In some non-limiting embodiments of the present technology, the networked computer environment 200 may comprise a global positioning system (GPS) satellite (not shown) that transmits a GPS signal to the electronic device 210 and/or receives a GPS signal from it. It should be understood that the present technology is not limited to the use of the GPS system and may be implemented based on any other location determination technology. It should be noted that a GPS satellite may be completely absent.

[073] The vehicle 220 to which the electronic device 210 is associated may be any recreational or other vehicle, such as a personal or commercial automobile, a truck, a motorcycle, etc. Although the vehicle 220 is depicted as a land vehicle, this is not necessarily the case for every non-limiting embodiment of the present technology. For example, in some non-limiting embodiments of the present technology, the vehicle 220 may be a watercraft, such as a boat, or an aircraft, such as an unmanned aerial vehicle.

[074] The vehicle 220 may be controlled by a user or may be an unmanned vehicle. In some non-limiting embodiments of the present technology, it is contemplated that the vehicle 220 may be implemented as an unmanned automobile. It should be noted that there are no restrictions on the specific parameters of the vehicle 220, which include, for example, the manufacturer of the vehicle, the model of the vehicle, the year of manufacture of the vehicle, the mass of the vehicle, the dimensions of the vehicle, the distribution of the mass of the vehicle, the surface area of the vehicle, the height of the vehicle, the type of transmission (e.g., with two-wheel drive or four-wheel drive), the type of tires, the braking system, the fuel system, the mileage, the identification number of the vehicle and the working volume of the engine.

[075] According to the present technology, there are no particular limitations on the implementation of the electronic device 210. For example, the electronic device 210 can be implemented as an engine control unit of the vehicle, a central processor of the vehicle, a navigation device of the vehicle (e.g., TomTom™, Garmin™), a tablet, a personal computer built into the vehicle 220, etc. It should be noted that the electronic device 210 may or may not be permanently connected to the vehicle 220. Additionally or alternatively, the electronic device 210 can be implemented as a wireless communication device, such as a mobile phone (e.g., a smartphone or a radiotelephone). In some embodiments, the electronic device 210 comprises a display 270.

[076] The electronic device 210 may comprise some or all of the elements of the computer system 100 shown in Fig. 1, depending on the particular embodiment. In some embodiments, the electronic device 210 is an on-board computer device and comprises a processor 110, a solid-state drive 120, and a memory 130. In other words, the electronic device 210 comprises hardware and/or software and/or firmware, or a combination thereof, for performing data processing, as described in more detail below.

[077] In some non-limiting embodiments of the present technology, the communication network 240 is the Internet. In other non-limiting embodiments of the present technology, the communication network 240 may be implemented as any suitable local area network (LAN), wide area network (WAN), private communication network, etc. It should be understood that the embodiments of the communication network 240 are given for illustrative purposes only. A communication link (not separately indicated) is provided between the electronic device 210 and the communication network 240, the implementation of which depends, among other things, on the implementation of the electronic device 210. For example, in those non-limiting embodiments of the present technology, where the electronic device 210 is implemented as a wireless communication device, such as a smartphone or a navigation device, the communication link may be implemented as a wireless communication link, but is not limited to this. Examples of wireless communication links can be, among other things, a 3G communication network channel, a 4G communication network channel, etc. The communication network 240 may also use a wireless connection to the server 235.

[078] In some embodiments of the present technology, the server 235 is implemented as a computer server and may include some or all of the elements of the computer system 100 shown in Fig. 1. In one non-limiting example, the server 235 is implemented as a Dell™ PowerEdge™ server running a Microsoft™ Windows Server™ operating system, but it may also be implemented on any other suitable types of hardware, software, and/or firmware, or a combination thereof. In the presented non-limiting embodiments of the present technology, the server 235 is a single server. In other non-limiting embodiments of the present technology, the functions of the server 235 may be distributed among multiple servers (not shown).

[079] In some non-limiting embodiments of the present technology, the processor 110 of the electronic device 210 may be connected to the server 235 to receive one or more updates. Such updates may include, among other things, software updates, map updates, route updates, weather data updates, and the like. In some non-limiting embodiments of the present technology, the processor 110 is also capable of sending certain operational data to the server 235, such as information about the routes taken, traffic data, operational data, and the like. Some or all of such data transmitted between the vehicle 220 and the server 235 may be encrypted and/or anonymized.

[080] It should be noted that the electronic device 210 can use a variety of sensors and systems to collect information about the surrounding space 250 of the vehicle 220. As shown in Fig. 2, the vehicle 220 can be equipped with a plurality of sensor systems 280. It should be noted that different sensor systems from the plurality of sensor systems 280 can be used to collect different types of data about the surrounding space 250 of the vehicle 220.

[081] In one example, the plurality of sensor systems 280 may comprise various optical systems, including one or more camera-type sensor systems mounted on the vehicle 220 and coupled to the processor 110 of the electronic device 210. In general, the one or more camera-type sensor systems may collect image data about different portions of the surrounding space 250 of the vehicle 220. In some cases, the image data provided by the one or more camera-type sensor systems may be used by the electronic device 210 to perform object detection procedures. For example, the electronic device 210 may transmit the image data provided by the one or more camera-type sensor systems to an Object Detection Neural Network (ODNN) trained to determine the location and classify potential objects in the surrounding space 250 of the vehicle 220.

[082] In another example, the plurality of sensor systems 280 may comprise one or more radar sensor systems mounted on the vehicle 220 and coupled to the processor 110. In general, the one or more radar sensor systems may use radio waves to collect data about different portions of the surrounding space 250 of the vehicle 220. For example, the one or more radar sensor systems may collect radar data about potential objects in the surrounding space 250 of the vehicle 220, and such data may relate to the distance from the radar sensor system to the objects, the orientation of the objects, the vector and/or scalar velocity of the objects, and the like.

[083] It should be noted that the plurality of sensor systems 280 may include sensor systems of other types in addition to those described above in a non-exhaustive manner, within the scope of the present technology.

Lidar system

[084] According to non-limiting embodiments of the present technology, as shown in Fig. 2, the vehicle 220 is equipped with at least one laser detection and ranging system (lidar system), such as a lidar system 300, for collecting information about the surrounding space 250 of the vehicle 220. Although described herein in the context of installation on the vehicle 220, it is also contemplated that the lidar system 300 may operate independently or in connection with another system.

[085] Depending on the embodiment, the vehicle 220 may include more or fewer lidar systems 300 than shown in the drawings. Depending on the particular embodiment, the selection of particular systems from the plurality of sensor systems 280 may depend on the particular embodiment of the lidar system 300. The lidar system 300 may be installed on the vehicle 220 initially or as a retrofit in different locations and/or in different configurations.

[086] For example, depending on the design of the vehicle 220 and the lidar system 300, the lidar system 300 can be installed in the upper part of the windshield of the vehicle 220 on its inner side. In this case, as shown in Fig. 2, installing the lidar system 300 in other places, including the rear window, side windows, front hood, roof, front grille, front bumper and side of the vehicle 220, does not go beyond the scope of the present technology. In some cases, the lidar system 300 can be mounted in a special housing installed on top of the vehicle 220.

[087] In some non-limiting embodiments of the invention, such as that shown in FIG. 2, one of the plurality of lidar systems 300 is mounted on the roof of the vehicle 220 and is capable of rotation. For example, the lidar system 300 mounted on the vehicle 220 and capable of rotation may include at least some elements capable of rotating 360 degrees about the axis of rotation of the lidar system 300. The lidar system 300 mounted with the ability to rotate can collect data about a large portion of the surrounding space 250 of the vehicle 220.

[088] In other non-limiting embodiments of the present technology, such as shown in Fig. 2, the lidar system 300 is mounted on the side or on the front grille and is not capable of rotation. In particular, the lidar system 300 mounted on the vehicle 220 without the ability to rotate may include at least some elements that are not capable of rotating 360 degrees, but are capable of collecting data about specified portions of the surrounding space 250 of the vehicle 220.

[089] Regardless of the specific installation location and/or specific embodiment, the lidar system 300 is capable of collecting data about the surrounding space 250 of the vehicle 220, for example, to construct a multidimensional map of objects in the surrounding space 250 of the vehicle 220. Below is a description of the design of the lidar systems 300 from the point of view of collecting data about the surrounding space 250 of the vehicle 220.

[090] It should be noted that in the description given herein, the lidar system 300 is implemented as a "time-of-flight" lidar system and therefore contains the corresponding elements inherent in such an implementation, but other embodiments of the lidar system 300 are also allowed without deviating from the essence and scope of the present technology. For example, in some non-limiting embodiments of the present technology, the lidar system 300 can also be implemented as a lidar system with a continuous frequency-modulated signal (FMCW, Frequency-Modulated Continuous Wave) according to one or more embodiments and based on the corresponding elements, as set forth in patent application RU2020117983 "Methods and systems for detecting lidars"), filed on June 1, 2020, the content of which is fully incorporated herein by reference.

[091] Fig. 3 is a diagram of one specific embodiment of a lidar system 300 implemented in accordance with certain non-limiting embodiments of the present technology.

[092] In general, the lidar system 300 includes a plurality of internal elements, including (1) a light source 302 (also referred to as a “laser source” or “radiation source”), (2) a light-splitting element 304, (3) a scanning unit 308 (also referred to as a “scanner” or “scanning node”), (4) a detection unit 306 (also referred to as a “detection system,” “receiver node,” or “detector”), and (5) a controller 310. It is contemplated that, in addition to the elements listed above in a non-exhaustive manner, the lidar system 300 may include a plurality of sensors (e.g., a temperature sensor, a humidity sensor, etc.), which are not shown in Fig. 3 for simplicity.

[093] In some non-limiting embodiments of the present technology, one or more internal components of the lidar system 300 are housed in a common housing 330, as shown in Fig. 3. In some embodiments of the present technology, the controller 310 may be located outside the common housing 330 and communicate with the components therein. As described below, the housing 330 has a window 380 on the side of the surrounding space of the vehicle 220, through which light beams exit and enter the housing 330.

[094] In general, the lidar system 300 operates as follows: the light source 302 of the lidar system 300 emits light pulses, forming an output beam 314, the scanning unit 308 scans the output beam 314 into the surrounding space 250 of the vehicle 220 through the window 380 to collect data on previously unknown objects (such as the object 320) located therein and to determine their location, for example, in order to create a multidimensional map of the surrounding space 250, the objects (including the object 320) on which are represented as one or more data points. The light source 302 and the scanning unit 308 are described in more detail below.

[095] In some non-limiting examples, object 320 may represent, in whole or in part, a person, a vehicle, a motorcycle, a truck, a train, a bicycle, a wheelchair, a baby carriage, a pedestrian, an animal, a road sign, a traffic light, a lane marking, a pavement marking, a parking space, a pylon, a guardrail, a road barrier, a pothole, a railroad crossing, an obstruction on or near a road, a curb, a stopped vehicle on or near a road, a utility pole, a house, a building, a trash can, a mailbox, a tree, as well as any other suitable object, or any suitable combination, in whole or in part, of two or more objects.

[096] Assume that the object 320 is located at some distance 318 from the lidar system 300. When the output beam 314 reaches the object 320, at least a portion of the light of the output beam 314 is typically reflected from the object 320, and some of the reflected light rays may return to the lidar system 300 as an input beam 316. By "reflected" is meant that at least a portion of the light of the output beam 314 is reflected from the object 320. The light of the output beam 314 may be partially absorbed or scattered by the object 320.

[097] Accordingly, the input beam 316 is captured and registered by the lidar system 300 using the detection unit 306. In this case, the detection unit 306 is capable of generating one or more representative data signals. For example, the detection unit 306 can generate an output electrical signal (not shown) representing the input beam 316. In addition, the detection unit 306 can transmit the electrical signal thus generated to the controller 310 for further processing. Finally, by measuring the time between the moment of emission of the output beam 314 and the moment of reception of the input beam 316, the controller 310 calculates the distance 318 to the object 320.

[098] As described in more detail below, the light-splitting element 304 directs the output beam 314 from the light source 302 to the scanning unit 308 and the input beam 316 from the scanning unit to the detection unit 306.

[099] Uses and embodiments of these elements of the lidar system 300 in accordance with some non-limiting embodiments of the present technology are described below.

Light source

[0100] The light source 302 is connected to the controller 310 and is capable of emitting light with a given operating wavelength. For this purpose, in some non-limiting embodiments of the present technology, the light source 302 may comprise at least one laser for operating at a given operating wavelength. The operating wavelength of the light source 302 may be in the infrared, visible or ultraviolet part of the electromagnetic spectrum. For example, the light source 302 may comprise at least one laser with an operating wavelength in the range of approximately 650-1150 nm. In another embodiment, the light source 302 may comprise a laser diode capable of emitting light with a wavelength in the range of approximately 800-1000 nm, approximately 850-950 nm or approximately 1300-1600 nm. In some other embodiments of the invention, the light source 302 may comprise a light-emitting diode.

[0101] Typically, the light source 302 of the lidar system 300 is a vision-safe laser. In other words, the lidar system 300 can be classified as a vision-safe laser system or a vision-safe laser product. In general, a vision-safe laser, laser system or laser product can be considered a system with such a combination of characteristics, namely, the emission wavelength, average power, peak power, peak intensity, pulse energy, beam size, beam divergence, emission duration, or with such a scanning output beam, in which the probability of visual impairment of a person due to exposure to light emitted by this system is small or equal to zero.

[0102] According to some non-limiting embodiments of the present technology, the operating wavelength of the light source 302 may be in a region of the electromagnetic spectrum corresponding to light emitted by the Sun. Therefore, in some cases, sunlight may act as background noise that can mask the light signal detected by the lidar system 300. This solar background noise may lead to false detections and/or otherwise distort the results of measurements performed by the lidar system 300. Although it may be desirable in some cases to increase the signal-to-noise ratio (SNR) of the lidar system 300 by increasing the power level of the output beam 314, in at least some circumstances this is undesirable. For example, in some embodiments of the invention, it may be undesirable to increase the power of the output beam 314 to a level exceeding the eye-safe threshold.

[0103] The light source 302 comprises a pulsed laser capable of generating or emitting light pulses of a certain duration. For example, in some non-limiting embodiments of the present technology, the light source 302 can emit pulses with a duration (i.e., with a pulse width) in the range of 10 ps to 100 ns. In other non-limiting embodiments of the present technology, the light source 302 can emit pulses with a repetition rate in the range of approximately 100 kHz to 5 MHz or with a pulse repetition period (i.e., with a time interval between adjacent pulses) in the range of approximately 200 ns to 10 μs. In general, the light source 302 can generate an output beam 314 with any suitable average optical power, and the output beam 314 can be optical pulses with any pulse energy or peak optical power suitable for a given application.

[0104] In some non-limiting embodiments of the present technology, the light source 302 may comprise one or more laser diodes, including, but not limited to, a Fabry-Perot laser diode, a quantum well laser, a distributed Bragg Reflector (DBR) laser, a distributed feedback (DFB) laser, or a vertical-cavity surface-emitting laser (VCSEL). As an example, the laser diode in the light source 302 may be an aluminum gallium arsenide (AlGaAs), indium gallium arsenide (InGaAs), or indium gallium arsenide phosphide (InGaAsP) laser diode, or any other suitable laser diode. It is also contemplated that the light source 302 may comprise one or more current-modulated laser diodes for generating optical pulses.

[0105] In some non-limiting embodiments of the invention, the light source 302 is typically capable of emitting an output beam 314 that is a collimated optical beam, but it is contemplated that such a beam may have any divergence suitable for a given application. In general, the divergence of the output beam 314 is an angular measure of the increase in the transverse size of the beam (e.g., the radius or diameter of the beam) as the output beam 314 moves away from the light source 302 or the lidar system 300. In some non-limiting embodiments of the present technology, the output beam 314 may have a substantially circular cross-section.

[0106] It is also contemplated that the output beam 314 emitted by the light source 302 may be unpolarized or randomly polarized, may have no specific or constant polarization (e.g., its polarization may change over time), or may have a specific polarization (e.g., the output beam 314 may have linear, elliptical, or circular polarization).

[0107] In at least some non-limiting embodiments of the present technology, the output beam 314 and the input beam 316 may be substantially coaxial. In other words, the input beam 316 and the output beam 314 may at least partially overlap or have a common propagation direction so that they travel along substantially the same optical path (but in opposite directions). However, in other non-limiting embodiments of the present technology, the output beam 314 and the input beam 316 may be non-coaxial or, in other words, may not overlap or have a common propagation axis within the lidar system 300 without departing from the spirit and scope of the present technology.

[0108] It should be noted that in at least some non-limiting embodiments of the present technology, the light source 302 may rotate, for example, by an angle of 360 degrees or less, about the rotation axis (not shown) of the lidar system 300, if the lidar system 300 is configured to rotate. However, in other embodiments, the light source 302 may be stationary, even if the lidar system 300 is implemented to rotate, without departing from the spirit and scope of the present technology.

Light-splitting element

[0109] As shown in Fig. 3, a light-splitting element 304 is further provided, located in the housing 330. For example, as mentioned earlier, the light-splitting element 304 is capable of directing the output beam 314 from the light source 302 to the scanning unit 308. The light-splitting element 304 is also capable of directing the input beam 316 reflected from the object 320 to the detection unit 306 for further processing by the controller 310.

[0110] In other non-limiting embodiments of the present technology, the beam-splitting element 304 may split the output beam 314 into at least two components of lower intensity, including a scanning beam (not separately shown) for scanning the surrounding space 250 of the lidar system 300 and a reference beam (not separately shown), which is then directed to the detection unit 306.

[0111] In other words, it can be stated that in such embodiments, the light-splitting element 304 is capable of distributing the intensity (optical power) of the output beam 314 between the scanning beam and the reference beam. In some non-limiting embodiments of the present technology, the light-splitting element 304 can distribute the intensity of the output beam 314 between the scanning beam and the reference beam equally. In other non-limiting embodiments of the present technology, the light-splitting element 304 can distribute the intensity of the output beam 314 with any given splitting ratio. For example, the light-splitting element 304 can use up to 80% of the intensity of the output beam 314 to form the scanning beam, and the remaining portion, up to 20% of the intensity of the output beam 314, to form the reference beam. In some non-limiting embodiments of the present technology, the beam splitting element 304 may vary the splitting ratio to form the scanning beam (e.g., in the range of 1% to 95% of the intensity of the output beam 314).

[0112] It should also be noted that some portion (for example, up to 10%) of the intensity of the output beam 314 may be absorbed by the material of the light-splitting element 304, depending on the design of the latter.

[0113] Depending on the implementation of the lidar system 300, the light-splitting element 304 may be represented in various forms, including, among others, as a glass prism-based light-splitting element, a half-silvered mirror-based light-splitting element, a dichroic mirror prism-based light-splitting element, a fiber-optic light-splitting element, and the like.

[0114] Thus, in accordance with non-limiting embodiments of the present technology, an open list of adjustable parameters associated with the light-splitting element 304, depending on the specific area of its application, may include, for example, an operating range of wavelengths, which can vary from a finite number of wavelengths to a wider light spectrum (e.g., from 1200 to 1600 nm), an input angle of incidence, the presence or absence of polarization, etc.

[0115] In a specific non-limiting example, the light-splitting element 304 may be implemented as a fiber optic light-splitting element available from OZ Optics Ltd., 219 Westbrook Rd Ottawa, Ontario K0A 1L0, Canada. It should be understood that the light-splitting element 304 may be implemented on any other suitable equipment.

Internal paths of ray propagation

[0116] As schematically shown in Fig. 3, the lidar system 300 has a plurality of internal beam paths 312 along which the output beam 314 (generated by the light source 302) and the input beam 316 (received from the surrounding space 250) propagate. In particular, the light propagates along the internal beam paths 312 as follows: the light from the light source 302 passes through the beam splitting element 304 to the scanning unit 308, and the scanning unit 308, in turn, directs the output beam 314 outward into the surrounding space 250.

[0117] The input beam 316 similarly passes through a plurality of internal beam paths 312 to the detection unit 306. In particular, the input beam 316 is directed by the scanning unit 308 into the lidar system 300 through the beam splitting element 304 to the detection unit 306. In some embodiments, the lidar system 300 may be provided with beam paths for the input beam 316 to pass from the surrounding space 250 directly to the detection unit 306 (bypassing the scanning unit 308).

[0118] It should be noted that in various non-limiting embodiments of the present technology, the plurality of internal beam paths 312 may comprise a variety of optical elements. For example, the lidar system 300 may comprise one or more optical elements capable of changing the parameters and shape, filtering and modifying, and changing or setting the direction of the output beam 314 and/or the input beam 316. For example, the lidar system 300 may comprise lenses, mirrors, filters (e.g., bandpass or rejection), optical fibers, circulators, beam splitters, polarizers, polarizing beam splitters, wave (e.g., half-wave or quarter-wave) plates, diffraction elements, microelectromechanical elements, collimating elements, or holographic elements in an amount of one or more units.

[0119] It is contemplated that in at least some non-limiting embodiments of the present technology, at least some common optical elements may be shared among some or other of the plurality of internal beam paths 312, although this is not required for all embodiments of the present technology.

Scanning block

[0120] In general, the scanning unit 308 directs the output beam 314 in one or more directions into the surrounding space 250. The scanning unit 308 is connected to the controller 310. Accordingly, the controller 310 is capable of controlling the scanning unit 308, directing the output beam 314 in a desired direction and/or in accordance with a predetermined scanning pattern. In general, in the context of the present description, a “scanning pattern” means a pattern or trajectory along which the scanning unit 308 directs the output beam 314 during operation.

[0121] In some non-limiting embodiments of the present technology, the controller 310 is capable of scanning the space with the output beam 314 using the scanning unit 308 in several ranges of horizontal and/or vertical angles, wherein the total range of angles in which the scanning unit 308 scans the space with the output beam 314 is referred to herein in some cases as a field of view. It is contemplated that the arrangement of elements, orientation and/or angular ranges may depend on a particular implementation of the lidar system 300. The field of view typically includes several regions of interest, which are defined as portions of the field of view that may contain, for example, objects of interest. In some embodiments, the scanning unit 308 may survey a selected region of interest 325. The region of interest 325 of the lidar system 300 may be an area, a volume, a region, an angular range, and/or a portion(s) of the surrounding space 250 where the lidar system 300 is capable of performing scanning and/or data collection.

[0122] It should be noted that the region of interest 325 of the lidar system 300 may overlap, encompass, or contain, at least partially, the location of the object 320 in the surrounding space 250 of the vehicle 220.

[0123] According to some non-limiting embodiments of the present technology, the scanning unit 308 can scan the space with the output beam 314 horizontally and/or vertically, and the region of interest 325 of the lidar system 300, accordingly, can be oriented in the horizontal and/or vertical direction. For example, the region of interest 325 can be limited by an angle of 45° in the horizontal direction and an angle of 45° in the vertical direction. In some embodiments, the scanning axes can have different orientations.

[0124] The scanning unit 308 includes a first reflective element 350 and a second reflective element 360. The first reflective element 350 is capable of redirecting the output beam 314 from the light-splitting element to the second reflective element 350 when the output beam is scanned along the first axis. The second reflective element 360 is capable of redirecting the output beam 314 from the first reflective element 350 into the surrounding space 250 (through the window 380 of the housing 330) when the output beam is scanned along the second axis. The second axis can be perpendicular and/or orthogonal to the first axis. Thus, the redirection and scanning of the output beam 314 together with the first reflective element 350 and the second reflective element 360 make it possible to scan the surrounding space 250 of the vehicle 220 along at least two perpendicular (orthogonal) axes.

[0125] It can be stated that the scanning unit is capable of scanning the surrounding space along two axes. For example, the first reflective element 350 can sweep the output beam 314 along the first axis, and the second reflective element 360 along the second axis. In one embodiment, the first axis can be a vertical axis, and the second axis can be a horizontal axis. In another embodiment, the first axis can be a horizontal axis, and the second axis can be a vertical axis.

[0126] In some non-limiting embodiments of the present technology, the scanning unit may further comprise several more optical and/or mechanical elements to provide scanning with the output beam. For example, the scanning unit may comprise mirrors, prisms, lenses, microelectromechanical elements, piezoelectric elements, optical fibers, splitters, diffraction elements, collimator elements, etc. in an amount of one or more units. It should be noted that the scanning unit may also comprise one or more additional actuators (not separately shown) that drive at least some other optical elements, for example, for their rotation, tilt, rotation, or movement at an angle relative to one or more axes.

[0127] Thus, as shown in Fig. 3, the lidar system 300 can use a given scanning pattern to generate a point cloud that substantially covers the region of interest 325 of the lidar system 300. This point cloud of the lidar system 300 can also be used to visualize a multidimensional map of objects in the surrounding space 250 of the vehicle 220.

Detection Block

[0128] According to some non-limiting embodiments of the present technology, the detection unit 306 is coupled to the controller 310 and can be implemented in a variety of ways. According to the present technology, the detection unit 306 comprises a photodetector, but may comprise a photodetector, an optical receiver, an optical sensor, a detector, an optical detector, optical fibers, and the like, without being limited thereto. As noted above, in some non-limiting embodiments of the present technology, the detection unit 306 can receive or detect at least a portion of the input beam 316 and generate an electrical signal corresponding to the input beam 316. For example, if the input beam 316 includes an optical pulse, the detection unit 306 can generate an electrical current or voltage pulse corresponding to the optical pulse detected by the detection unit 306.

[0129] It is contemplated that in various non-limiting embodiments of the present technology, the detection unit 306 may be implemented using one or more avalanche photodiodes (APD), one or more single-photon avalanche diodes (SPAD), one or more PN photodiodes (i.e., a photodiode structure formed by a p-type semiconductor and an n-type semiconductor), one or more PIN photodiodes (i.e., a photodiode structure with an undoped region of intrinsic semiconductor located between the p-type and n-type regions), and the like.

[0130] In some non-limiting embodiments, the detection unit 306 may also comprise electronic circuits that perform amplification, sampling, signal filtering, waveform conversion, analog-to-digital conversion, time-to-digital conversion, pulse detection, threshold detection, leading edge detection, trailing edge detection, and the like. For example, the detection unit 306 may comprise electronic elements that are capable of converting a received photocurrent (in particular, a current generated by the APD diode under the influence of a received optical signal) into a voltage signal. The detection unit 306 may also comprise additional circuits for generating an analog or digital output signal corresponding to one or more characteristics (e.g., a leading edge, a trailing edge, an amplitude, a duration, and the like) of the received optical pulse.

[0131] The developers of the present technology took into account that the photodetector operates when an operating voltage (e.g., a reverse bias voltage) is applied to it. The value of the operating voltage may vary, among other things, depending on the embodiment of the present technology. The developers of the present technology also took into account that the operating parameters of the photodetector (such as the operating voltage) may deteriorate and/or change during active use of the lidar system, in particular, depending on humidity, temperature, movement, illumination, etc. Therefore, in order to ensure the required quality of the data generated by the lidar system, it is advisable to constantly calibrate and/or adjust one or more operating parameters of the photodetector.

[0132] In the context of the present technology, the voltage value established by the photodetector during the calibration process in response to receiving a special return light beam is compared with a base voltage value. In particular, during the calibration process, the scanning unit 308 is capable of redirecting the incoming light beam to the inner surface of the housing 330, preventing it from exiting the housing 330. In this case, the return light beam is reflected to the photodetector of the detection unit 306 from the inner surface of the housing 330, and does not enter there from the surrounding space.

[0133] As indicated above, the voltage value set in response to capturing a special return light beam is compared with a base voltage value. In general, the base voltage value characterizes the voltage value that is set by the photodetector in a calibrated state (i.e., in a normal or base operating state) in response to capturing a special return light beam. Thus, the calibration of the photodetector is performed based on the difference between these two voltage values.

[0134] The ability of the scanning unit provided in some embodiments of the present technology to generate a special return light beam for calibrating the detection unit is described in more detail below with reference to Figs. 6 and 7.

Controller

[0135] Depending on the implementation, the controller 310 may comprise one or more processors, an application-specific integrated circuit (ASIC), a field-programmable gate array (FPGA), and/or other suitable circuits. The controller 310 may also comprise physical machine-readable memory for storing instructions executed by the controller 310, as well as data that the controller 310 may generate based on signals received from other internal elements of the lidar system 300 and/or signals output to other internal elements of the lidar system 300. The memory may comprise volatile (e.g., RAM) and/or non-volatile (e.g., flash memory, hard disk) elements. The controller 310 may generate data during operation and store it in the memory. For example, such data generated by the controller 310 may be associated with data points in a point cloud of the lidar system 300.

[0136] It is contemplated that in at least some non-limiting embodiments of the present technology, the controller 310 may be implemented similarly to the electronic device 210 and/or the computer system 100 without departing from the spirit and scope of the present technology. In addition to collecting data from the detection unit 306, the controller 310 may also output control signals for the light source 302 and the scanning unit 308 and, possibly, receive diagnostic data from them.

[0137] As indicated above, the controller 310 is coupled to the light source 302, the scanning unit 308, and the detection unit 306. In some non-limiting embodiments of the present technology, the controller 310 can receive electrical trigger pulses from the light source 302, where each electrical trigger pulse corresponds to the emission of an optical pulse by the light source 302. The controller 310 can further provide the light source 302 with commands, a control signal, and/or a trigger signal indicating when the light source 302 should generate optical pulses, for example, for the output beam 314.

[0138] As an example, the controller 310 may output an electrical trigger signal comprising electrical pulses so that the light source 302 emits an optical pulse represented by the output beam 314 in response to each pulse of the electrical trigger signal. It is also contemplated that the controller 310 may cause the light source 302 to change one or more characteristics of the output beam 314 generated by the light source 302, such as, among other things, the frequency, period, duration, pulse energy, peak power, average power and wavelength of the optical pulses.

[0139] According to the present technology, the controller 310 is configured to determine a "time of flight" value of an optical pulse for calculating a distance between the lidar system 300 and one or more objects in the field of view, as described below. The time of flight is determined based on time information associated with (1) a first time when an optical pulse (e.g., output beam 314) was emitted by the light source 302, and (2) a second time when a portion of this optical pulse (e.g., from the input beam 316) was detected or received by the detection unit 306. In some non-limiting embodiments of the present technology, the first time may correspond to the time when the controller 310 transmits an electrical pulse associated with the optical pulse, and the second time may correspond to the time when the controller 310 receives from the detection unit 306 an electrical signal generated in response to receiving the portion of the optical pulse of the input beam 316.

[0140] In other non-limiting embodiments of the present technology, in which the light-splitting element 304 is capable of splitting the output beam 314 into a scanning beam (not shown) and a reference beam (not shown), the first moment in time may be the moment of receiving from the detection unit 306 a first electrical signal generated in response to receiving a portion of the reference beam. Accordingly, in these embodiments, the second moment in time may be determined as the moment of receiving by the controller 310 from the detection unit 306 a second electrical signal generated in response to receiving another portion of the optical pulse of the input beam 316.

[0141] According to the present technology, the controller 310 is capable of determining, based on the first and second moments of time, the time of flight value and/or the amount of phase modulation of the emitted pulse of the output beam 314. The time of flight value T in a sense represents the time of travel of the emitted pulse “there and back”, i.e. from the lidar system 300 to the object 320 and back to the lidar system 300. Thus, the controller 310 is generally capable of determining the distance 318 according to the following formula:

(1)

where D is the distance 318, T is the time of flight, and c is the speed of light (approximately 3.0×10 ⁸ m/s).

[0142] As mentioned earlier, the lidar system 300 can be used to determine a distance 318 to one or more other potential objects located in the surrounding space 250. By scanning the output beam 314 of the region of interest 325 of the lidar system 300 in accordance with a predetermined scanning pattern, the controller 310 is able to display distances (similar to the distance 318) to corresponding data points in the region of interest 325 of the lidar system 300. In this case, the controller 310, as a rule, is able to represent these successively obtained data points (e.g., point clouds) in the form of a multi-dimensional map. In some embodiments, data associated with a certain time of flight and/or distances to objects can be displayed in various information formats.

[0143] For example, such a multidimensional map may be used by the electronic device 210 to detect objects or otherwise identify them, or to determine the shape of or distance to potential objects in the region of interest 325 of the lidar system 300. It is contemplated that the lidar system 300 is capable of repeatedly or iteratively obtaining and/or generating point clouds at any rate suitable for a given application.

[0144] It should be noted that the multidimensional maps can be recorded and stored as part of the log data associated with the vehicle 220. In this way, the point cloud data obtained by the lidar systems on the vehicles in the fleet of vehicles can be stored for subsequent use. In addition, the multidimensional maps obtained by one or another lidar system provide for determining the location of the unmanned vehicle during its operation. The description below explains how the location of the vehicle 220 can be determined using the point cloud data obtained by the lidar system during operation.

Data storage

[0145] Fig. 4 shows a data storage device 400. The data storage device 400 may be connected to the server 235 and to the electronic device 210 of the vehicle 220. The data storage device 400 may be used by the server 235 and/or the electronic device 210 to store data collected during operation of the vehicle 220. The data storage device 400 may be used by the server 235 and/or the electronic device 210 to identify at least a portion of the stored data to be updated. The data storage device 400 may be used by the server 235 and/or the electronic device 210 to retrieve data to be used during operation of the vehicle 220.

[0146] In some embodiments of the present technology, the data storage device 400 may receive data collected by sensors on a plurality of vehicles 404, for example, including hundreds or thousands of vehicles implemented similarly to the vehicle 220. The vehicles collect data from sensors obtained during movement along various routes and transmit them to the data storage device 400. In this regard, it can be stated that the data storage device 400 may store log data 406 for a plurality of vehicles 404 (a fleet of vehicles).

[0147] In other embodiments of the present technology, the server 235 may use the log data 406 to create and/or update a map representation 402 of a geographic region in which the plurality of vehicles 404 operate and/or have operated. It is contemplated that the server 235 may generate the map representation 402 of the geographic region based on the aggregate information received from the plurality of vehicles 404 and store the map representation 402 in the data storage device 400.

[0148] The server 235 is capable of transmitting data characterizing the map representation 402 to the electronic devices associated with the respective vehicles of the plurality of vehicles 404. For example, if the vehicle 220 is to travel along a certain route, the electronic device 210 can provide the server 235 with information describing the route to be traveled. In response to this, the server 235 transmits the map representation 402 (or portions thereof) to ensure travel along the route. It is contemplated that, without departing from the spirit and scope of the present technology, the map representation 402 can be periodically transmitted for local storage in the electronic device 210 for the purpose of its use.

[0149] In one embodiment, the server 235 transmits portions of the map representation 402 to the vehicles in a compressed format so that the transmitted data takes up less bandwidth of the communication channel. The server 235 can receive information from various vehicles describing data that is locally stored on the electronic device 210. If the server 235 detects that any portion of the map representation 402 is missing from the local memory of the vehicle 220, the server 235 can transmit this portion of the map representation 402. If the server 235 detects that the vehicle 220 has already received this particular portion of the map representation, but the corresponding data has been updated by the server 235 since the last time the data was received by the vehicle 220, the server 235 can transmit an update for this portion of the map representation 402 to the electronic device 210.

[0150] It should be noted that the server 235 may generate the map representation 402 based on the log data 406. The server 235 updates the previously generated map data by receiving more current information from vehicles that have recently traveled along routes for which the map data has changed. In one embodiment, the server 235 may use map matching techniques based on iterative closest point algorithms (and their variants), which ensure that the closest points on different cloud maps from the log data 406 are associated, which allows them to be combined and expand the map representation of the geographic region for which the cloud data from the log data 406 was collected.

Computer procedures

[0151] Fig. 5 shows a plurality of computer procedures 500 that can be performed by at least one server 235 and electronic device 210.

[0152] The plurality of computer procedures 500 includes a map update algorithm 502. When a considered portion of the map representation 402 is recognized as outdated, the server 235 can receive the most current point cloud data associated with the considered portion of the map representation 402 and use one or more map matching methods, for example, based on iterative closest point algorithms, to establish a relationship between the closest points in these most current point clouds in order to combine them and replace the considered portion of the map representation 402. In some embodiments, when the value of at least one of the two metrics indicates that the portion of the map representation 402 is subject to update, the server 235 can execute the map update algorithm 502 to receive the corresponding most current point clouds and run one or more map matching methods. In further embodiments, if it appears that the most current point clouds were generated earlier than a specified time, the map update algorithm 502 may defer the update until more current point clouds are received in the considered portion of the map view 402.

[0153] The plurality of computer routines 500 include a sensor data fusion routine 502. In general, sensor data fusion is a method of combining data obtained from various sources to form consistent information. The resulting information may be more accurate than the information from the individual sources. This data processing method may be particularly effective when combining different types of information. For example, computer vision may be implemented using a camera, and additional information about obstacles and distances may be collected using other sensors, such as a lidar sensor and/or a radar sensor. One or more sensor data fusion methods may be used to summarize information about the surrounding space of the vehicle 220 obtained from multiple sources. In some embodiments, initial sensor data fusion and/or final sensor data fusion may be used. In initial sensor data fusion methods, three-dimensional point clouds are combined with two-dimensional images. Initial sensor fusion does not merge detection results, but rather raw data such as pixels and point clouds. It can be argued that initial sensor fusion performs a projection from 3D to 2D before object detection. Final sensor fusion occurs after object detection and tracking.

[0154] The plurality of computer procedures 500 includes a localization algorithm 750. As described below, the localization algorithm 750 is capable of generating a probable location of the vehicle 220 based on the map representation 402, a given point cloud obtained by the vehicle 220, and an initial estimate of the current location of the vehicle 220. In one embodiment, the localization algorithm 750 can apply one or another iterative closest point algorithm to the point cloud data and to the map representation 402. In general, during the operation of the iterative closest point algorithm, one point cloud (vertex cloud) - the control or target - is kept unchanged, and the other - the original - is transformed in such a way as to ensure its best match to the control. The algorithm iteratively makes the necessary changes to the transformation (a combination of translation and rotation) to minimize the error metric, which is typically the distance from the original point cloud to the reference point cloud, such as the sum of the squared differences between the coordinates of the pairs being matched. The iterative closest point algorithm is one of the 3D model matching algorithms that are widely used to "initialize" the rigorous transformation.

[0155] The plurality of computer routines 500 include other localization algorithms 506. In some embodiments, the localization data source may determine a probable location of the vehicle based on odometry, which is the process of estimating the relative movement of the vehicle using data sequentially obtained by sensors of the vehicle. Odometry may be used in the localization algorithm to initialize the position of the vehicle for the purpose of performing a search for local objects by the localization algorithm. In addition, odometry may be used in the localization algorithm to estimate the speed and acceleration of the car by extrapolating the position of the vehicle in periods between the moments of taking sensor readings that can be used in localization.

[0156] In additional embodiments, the sources of localization data for determining the location of the vehicle may include visual odometry. In various embodiments of visual odometry, the location of the vehicle is determined by comparing various features highlighted in camera images with features on a map, in particular, with surface relief, characteristic features of images, contours, etc.

[0157] In other embodiments, one or more lidar localization methods may be used as sources of localization data. It is contemplated that the source of localization data may be feature-based localization, in which features are extracted using sensor data, such as camera images, and the lidar scans these features and compares them with features on one or more representations of a map of a region to determine the location of the vehicle.

[0158] In at least some embodiments of the present technology, the source of localization data for determining the location of the vehicle may be lidar odometry methods. In various embodiments of lidar odometry, an iterative closest point algorithm with pairwise comparison or an iterative closest point algorithm with multiple scans is used. Various embodiments of all of the above methods are implemented by replacing certain parameters, such as the maximum number of iterations, the search radius, weighting factors, etc.

[0159] The localization data sources described above in a non-exhaustive manner may further include other localization data sources that utilize GNSS-based localization and inertial measurement unit-based odometry. Various integration methods and correction methods are used in various embodiments of these methods.

[0160] The plurality of computer routines 500 include a modeling algorithm 650. As described in more detail below, the modeling algorithm 650 is capable of generating simulated point clouds using point clouds extracted from the log data 406. The modeling algorithm 650 is designed to generate a degraded version of the original point cloud. The degradation caused by the modeling algorithm 650 is designed to reflect the influence of various conditions in which the vehicle may operate. In one example, the degradation may reflect the influence of the road environment, such as the presence of large vehicles nearby that interfere with the lidar sensor. In another example, the degradation may reflect the influence of environmental conditions, such as rain, mud and/or snow, that interfere with the operation of the lidar system.

[0161] The plurality of computer procedures 500 include calculating a first metric 508 and a second metric 950. In general, the server 235 and/or the electronic device 210 may use the first metric 508 and/or the second metric 950 to determine whether a portion of the map representation is out of date. Additionally or alternatively, the server 235 and/or the electronic device 210 may use the first metric 508 and/or the second metric 950 to determine whether the results of the localization algorithm 750 are somewhat "trustworthy" in this portion of the map representation 402. As described in more detail below, the server 235 may train a machine learning algorithm based on the results obtained using the first metric 508 and use such trained machine learning algorithm as the second metric 950.

[0162] In general, this machine learning algorithm is initially created (or trained) using training data and training objectives. In a training iteration, the machine learning algorithm is fed with initial training data and the algorithm generates a corresponding prediction. The server 106 may then, in a sense, "tune" the machine learning algorithm as a result of comparing the prediction with the training objective with respect to the initial training data. For example, such tuning may be performed by the server 106 using one or more machine learning methods, such as, among others, the back propagation method. Accordingly, after a large number of training iterations, the machine learning algorithm is "tuned" such that its predictions, generated based on the input data, are close to the training objectives. In some embodiments, the trained machine learning algorithm may serve as a metric used to determine which portion of the map view 402 to update. In some embodiments, the trained machine learning algorithm may serve as a metric used to determine whether the current results of the localization algorithm 750 are reliable enough to be used during operation of the vehicle 220.

[0163] Below is a more detailed description of how the server 235 is able to use the first metric 508 to determine the portion of the map view 402 to be updated.

Previous trajectories and data degradation

[0164] The server 235 is capable of using the log data 604 of the vehicle 602 (the unmanned vehicle in the fleet) to form, in the process of modeling, a trajectory 606 of the unmanned vehicle 602 on the map representation 402. It should be noted that the vehicle 602 operated in a geographic region that is covered by the map representation 402. Thus, the server 235 is capable of determining the previous trajectory of the vehicle 602 and using it as the trajectory 606. Accordingly, the trajectory 606 can be called the previous trajectory 606. The server 235 is capable of extracting from the log data 604 a plurality of point clouds 610, which are point clouds obtained by the lidar system of the vehicle 602 on the previous trajectory 606.

[0165] It should be noted that the point clouds of the plurality of point clouds 610 are associated with additional log data 604. For example, the point cloud 612 is associated with additional data 622, the point cloud 614 is associated with additional data 624, and the point cloud 616 is associated with additional data 626. The additional data may include time stamps representing the moments in time at which the corresponding point cloud was obtained, GPS data approximately characterizing the location of the vehicle 602 at the time of obtaining the corresponding point cloud, kinematic data or odometry data (scalar and vector velocity, acceleration, etc.) of the vehicle 602 at the time of obtaining the corresponding point cloud, and the like.

[0166] The server 235 is capable of selecting one or more (for example, a sequence) point clouds from the plurality of point clouds 610 and generating one or more simulation point clouds based on them. For example, the server 235 is capable of generating a simulation point cloud 654 based on a given point cloud associated with a previous trajectory 606. To do this, the server 235 is capable of performing a modeling procedure 650 with respect to the point cloud 614 to generate the simulation point cloud 654.

[0167] It should be noted that the simulated point cloud 654 may be a degraded version of the point cloud 614. In some embodiments, the degrading procedure 650 may provide for removing at least a set of points from the point cloud 614. Removing a set of points may simulate a road environment in which a large object obscures part of the surrounding space from the lidar system.

[0168] In other embodiments, the modeling procedure 650 may be used not to model the effect of the road situation on the point cloud 614, but to model the effect of one or more environmental conditions, such as rain, snow, and/or dirt, that interfere with the operation of the lidar system. To this end, in some embodiments, the server 235, when performing the modeling procedure 650, is capable of applying a filter to the point cloud 614 that introduces noise into the point cloud 614. For example, the noise function may be determined based on log data representing point clouds obtained in a specific road situation and/or in specific environmental conditions.

Localization algorithm

[0169] Fig. 7 shows two examples of the implementation of the localization algorithm 750 by the server 235. In the first example, the server 235 is capable of transmitting to the localization algorithm 750 a point cloud 614 and an initial approximation 710 of the location of the vehicle 220 for a timestamp associated with the point cloud 614. It should be noted that the localization algorithm 750 also has access to the map representation 402. Due to this, the localization algorithm 750 is capable of generating a probable location 780. It should also be noted that the probable location 780 is associated with a timestamp of the point cloud 614 and the considered portion of the map representation 402 representing the current surrounding space of the vehicle 220 at the time of receiving the point cloud 614. It is assumed that the probable location generated by the localization algorithm 750 can include a probable position of the vehicle 220 and a probable orientation of the vehicle 220.

[0170] In some embodiments, the localization algorithm 750 may initiate the determination of a probable location 780 by pre-selecting a position of the point cloud 614 relative to the map representation 402 based on the initial approximation 710, and may also iteratively move the point cloud 614 and, accordingly, iteratively adjust the location returned by the localization algorithm 750.

[0171] In a second example, the server 235 is capable of transmitting to the localization algorithm 750 a simulated point cloud 654 and an initial approximation 710. As a result, the localization algorithm 750 is capable of generating a probable location 790. It should be noted that the probable location 790 is associated with a timestamp of the point cloud 614 and the considered portion of the map representation 402 representing the current surrounding space of the vehicle 220 at the time of receiving the point cloud 614.

[0172] In some embodiments, the server 235 is capable of using, in addition to or instead of the simulated point cloud, another point cloud from the log data of another unmanned vehicle in the fleet. For example, the server 235 is capable of retrieving one or more point clouds associated with the location at which the point cloud 614 was obtained by the lidar system. Thus, the server 235 can use another point cloud obtained by another lidar system on another unmanned vehicle in the fleet.

[0173] In some embodiments of the present technology, the server 235 is capable of generating a plurality of probable locations associated with a time stamp of the point cloud 614 on the previous trajectory 606. One of such probable locations may be partially generated based on the point cloud 614, another may be partially based on the simulated point cloud 654, another may be partially based on another simulated point cloud (reflecting the influence of any conditions not manifested in the simulated point cloud 654), and yet another may be partially based on a point cloud obtained by another lidar system on another vehicle at the time when it was at this location.

[0174] In further embodiments, a plurality of probable locations may be generated in a similar manner for a number of timestamps on the previous trajectory 606. For example, a first plurality of probable locations may be generated for a first timestamp, a second plurality of probable locations for a second timestamp, a third plurality of probable locations for a third timestamp, and so on.

[0175] The server 235 is capable of applying the first metric 508 to a plurality of probable locations associated with the timestamp and the location on the map view 402. In the context of the present technology, the first metric 508 can determine a convergence parameter based on the plurality of probable locations and correlate it with a location on the map view.

[0176] As described in detail below, depending on the convergence parameter, the server 235 may decide that the considered portion of the map representation 402 containing the location needs to be updated. It is also contemplated that the server 235 may determine convergence parameters for a sequence of timestamps (for example, a sequence of locations in the considered portion of the map representation). The convergence parameters for a sequence of timestamps on the previous trajectory 606 may be used in combination to determine whether the considered portion of the map representation 402 containing the sequence of locations needs to be updated.

Convergence metric

[0177] Fig. 8 shows two examples of using the first metric 508 to determine a convergence parameter for a set of probable locations.

[0178] In the first example, it is assumed that the set of probable locations comprises four probable locations, the first of which includes the first probable position 801 and the first probable orientation 841, the second - the second probable position 802 and the second probable orientation 842, the third - the third probable position 803 and the third probable orientation 843, and the fourth - the fourth probable position 804 and the fourth probable orientation 844.

[0179] The server 235 may apply the first metric 508 to determine the size of the smallest circle that encompasses the probable positions 801, 802, 803 and 804. In addition, the server 235 may compare the radius of such smallest circle with the given radius 810. In this case, it can be stated that the server 235, applying the first metric 508, is able to determine whether the probable positions 801, 802, 803 and 804 are covered by the circle 815 of the given radius 810.

[0180] It can also be argued that the circle 815 is a circle of a given radius centered at a given location. In some embodiments, the given location may be the true location of the vehicle on a previous trajectory associated with the specified time stamp. In other embodiments, the given position may differ from the true position. It can be argued that the purpose of applying the first metric 508 is to determine whether the probable positions generated by the localization algorithm 750 "converge" within the circle of the given radius 810. It can also be argued that the ability of the localization algorithm 750 to generate probable positions close to the true position is of less importance than the ability of the localization algorithm to generate consistent probable positions when using simulated or degraded point clouds.

[0181] The server 235 may apply the first metric 508 to determine the size of the smallest angular sector that covers the probable orientations 841, 842, 843 and 844. In addition, the server 235 may compare the angle of such smallest sector with the given angle 850. In this case, it can be stated that the server 235, applying the first metric 508, is able to determine whether the probable orientations 841, 842, 843 and 844 are covered by the sector 855 with the given angle 850.

[0182] It may be argued that the purpose of applying the first metric 508 is to determine whether the probable orientations generated by the localization algorithm 750 “converge” within a given angle 850. It may also be argued that the ability of the localization algorithm 750 to generate probable orientations that are close to the true orientation is of less importance than the ability of the localization algorithm 750 to generate consistent probable orientations when using simulated or degraded point clouds.

[0183] In the context of this first example, it can be argued that the convergence parameter defined by the first metric 508 indicates the ability of the localization algorithm 750 to generate convergent location options in the considered part of the map representation.

[0184] In the second example, it is assumed that the set of probable locations comprises four probable locations, the first of which includes the fifth probable position 821 and the fifth probable orientation 861, the second the sixth probable position 832 and the sixth probable orientation 862, the third the seventh probable position 833 and the seventh probable orientation 863, and the fourth the eighth probable position 834 and the eighth probable orientation 864.

[0185] The server 235 may apply the first metric 508 to determine the size of the smallest circle that encompasses the probable positions 831, 832, 833 and 834. In addition, the server 235 may compare the radius of such smallest circle with the given radius 810. In this case, it can be stated that the server 235, applying the first metric 508, is able to determine whether the probable positions 831, 832, 833 and 834 are covered by the circle 815 of the given radius 810.

[0186] It can be argued that the purpose of applying the first metric 508 is to determine whether the probable positions generated by the localization algorithm 750 “converge” within a circle with a given radius 810. In the context of the second example, it can be argued that the probable positions 831, 832, 833 and 834 do not converge within a circle with a given radius 810, but converge within a circle with a given radius 820, that is, they are covered by a circle 825 (of a larger size).

[0187] The server 235 may apply the first metric 508 to determine the size of the smallest sector that covers the probable orientations 861, 862, 863 and 864. In addition, the server 235 may compare the angle of such smallest sector with the given angle 850. In this case, it can be stated that the server 235, applying the first metric 508, is able to determine whether the probable orientations 861, 862, 863 and 864 are covered by the sector 855 with the given angle 850.

[0188] It can also be argued that the purpose of applying the first metric 508 is to determine whether the probable orientations generated by the localization algorithm 750 “converge” within the given angle 850. In the context of the second example, it can be argued that the probable orientations 861, 862, 863 and 864 do not converge within the given angle 850.

[0189] In the context of the second example, it can also be argued that the convergence parameter specified by the first metric 508 serves as an indication that the localization algorithm 750 generates location options in the considered part of the map representation that diverge and/or do not converge within one or more specified values (one or more radii and/or one or more angles).

[0190] In some embodiments of the present technology, the server 235, based on the parameter specified by the first metric 508, can determine whether the considered portion of the map representation 402 needs to be updated. In other words, it can be stated that if the probable locations generated for the timestamp in the considered portion of the map representation 402 do not converge within a specified value, the effect of the outdated portion of the map representation 402 affects the results of the localization algorithm 750. Thus, the result of applying the first metric 508 can serve as an indication of the need to update the corresponding portion of the map representation 402.

[0191] The server 235 is capable of updating the considered portion of the map representation. As indicated above, the server 235 is capable of receiving the most current point cloud data associated with the considered portion of the map representation 402 and using one or more map matching methods, for example, based on iterative closest point algorithms, to establish a relationship between the closest possible points in these most current point clouds for the purpose of merging them and replacing the considered portion of the map representation 402. In additional embodiments, if it turns out that the most current point clouds were generated earlier than a specified point in time, the map update algorithm 502 can postpone the update until more current point clouds are received in the considered portion of the map representation 402.

The second metric

[0192] As indicated above, the server 235 is capable of determining, during the training process, a second metric 950 based on the results of applying the first metric 508. In Fig. 9, an iteration 991 of training the machine learning algorithm and an iteration 992 of using the machine learning algorithm are shown. After the machine learning algorithm is trained, this algorithm can be used as the second metric 950. As described below, the iteration 992 of using the machine learning algorithm can be performed "offline" on the server 235 to determine the portions of the map view 402 to be updated and, in the same or other embodiments, "in real time" in the electronic device 210 during the operations of the vehicle 220 to decide whether the localization algorithm 750 is a reliable source of localization data in the current portion of the map view 402.

[0193] During training, the server 235 is capable of generating a training set that contains initial training data 901 and a training label 902. The initial training data 901 includes a map representation 402 (or at least a portion thereof that is of interest), a probable location 780, and a point cloud 614. The server 235 is capable of generating the training label 902 based on a parameter specified by the first metric 506.

[0194] For example, the training label 902 may have a value of 0, indicating that the probable locations for the timestamp do not converge within the given radius 810, or a value of 1, indicating that the probable locations for the timestamp do converge within the given radius 810. It may be argued that in some embodiments, the training label 902 serves as a feature that characterizes the initial data for training in relation to the machine learning algorithm 950 as either a positive example or a negative example. It should be noted that the training label 902 does not necessarily have to be in a binary format. The training label 902 may indicate a true class among several classes. For example, different classes may be associated with given convergence radii. In the example shown, the server 235 can assign a true class from a plurality of classes to the initial data 901 for training, which correspond to the radii of convergence of probable locations in this training example. In additional embodiments, without departing from the spirit and scope of the present technology, the training label 902 can take the form of a value from a continuous spectrum of values (for example, regression). It is assumed that the result of applying the first metric 508 can be used to form a training label for the purpose of determining the second metric 950 in the training process.

[0195] The server 235 uses the training set to train the machine learning algorithm 950 to obtain a predictive parameter 920 indicating whether the localization algorithm 750 generates divergent probable locations for the self-driving car 602 in the considered portion of the map representation 402.

[0196] For example, a predictive parameter 920 serves as an indication that the probable locations are diverging if the localization algorithm generates probable locations that do not converge within a given threshold.

[0197] In additional embodiments, the initial data for training in this training set may include a simulated point cloud instead of point cloud 614 and a corresponding probable location generated based on the simulated point cloud instead of probable location 780.

[0198] It is contemplated that the first metric 508 and/or the second metric 950 may be used on the server 235 in an "offline mode" to find and update portions of the map view 402 that are subject to updating. It is contemplated that the first metric 508 and/or the second metric 950 may be used on the server 235 in a "real-time mode" to determine whether the results of the localization algorithm 750 may be used to control the actions of the vehicle 220 in that portion of the map view where the vehicle 220 is currently located.

[0199] In some embodiments, the server 235 may use the first metric 506 in a similar manner as described above with reference to Fig. 8 to determine a parameter for the probable locations generated for the considered portion of the map view 402. Additionally or alternatively, the second metric 950 (after training) may also be used to determine a second parameter for the probable location generated for the considered portion of the map view 402. The server 235 may use a combination of the parameters specified by the first metric 506 and the second metric 950 to determine whether the considered portion of the map view 402 needs to be updated.

[0200] In some embodiments, the electronic device 210 may use the first metric 506 in a similar manner as described above with reference to Fig. 8 to determine a parameter for the probable locations generated for the current portion of the map view 402 during the actions of the vehicle 220. Additionally or alternatively, the second metric 950 (after training) may be used to determine a second parameter for the probable location generated for the current portion of the map view 402. The electronic device 210 may use a combination of the parameters defined by the first metric 506 and the second metric 950 to determine whether the current probable location generated by the localization algorithm 750 may be used to control the actions of the vehicle 220 in the current portion of the map view 402.

[0201] Fig. 10 shows a flow chart of a method 1000 for updating a portion of a map view 402 implemented on a server 235. A more detailed description of the steps of the method 1000 is given below.

Step 1002: The server determines the previous trajectory of the self-driving car in the geographic region.

[0202] The implementation of the method 1000 begins with step 1002, in which the server 235 can determine a previous trajectory 606 of the vehicle 220 in the geographic region. The previous trajectory 606 is associated with a plurality of point clouds 610 from the log data of the vehicle 220. The plurality of point clouds were obtained by the lidar system during the movement of the vehicle 220 along the previous trajectory 606 in the geographic region.

[0203] It is assumed that the server 235 is capable of performing the method 1000 for a plurality of previous trajectories in a geographic region. This allows various routes taken by vehicles in the geographic region to be presented for verification or updating.

Step 1004: for a timestamp on the previous trajectory, determining by the server the first point cloud from the plurality of point clouds that were obtained by the lidar system at the moment corresponding to this timestamp.

[0204] The next step in the method 1000 is step 1004, in which the server 235 can, for a time stamp on the previous trajectory of the vehicle 220 corresponding to the moment when the vehicle 220 was at a given location in the geographic region, determine a point cloud 614 from a plurality of point clouds 610 that were obtained by the lidar system at the moment corresponding to this time stamp.

Step 1006: For the timestamp on the previous trajectory, the server uses the localization algorithm to generate a first probable location based on the first point cloud and the map representation.

[0205] The next step in the method 1000 is step 1006, in which the server 235 can, for a time stamp on the previous trajectory of the vehicle 220, corresponding to the moment when the vehicle 220 was in a given place of the geographic region, generate, using the localization algorithm 750, a first probable location 780 based on the point cloud 614 and the map representation 402. The given place is in the considered part of the map representation 402.

Step 1008: For a timestamp on the previous trajectory, determine by the server the second point cloud associated with the given location.

[0206] The next step in the method 1000 is step 1008, in which the server 235 may, for a time stamp on the previous trajectory of the vehicle 220 corresponding to the moment when the vehicle 220 was at a given location in the geographic region, determine a second point cloud associated with the given location.

[0207] In some embodiments, the second point cloud may be a simulated point cloud 654 that is a degraded version of the first point cloud. For example, the degraded version of the point cloud 614 is the point cloud 614 without a certain subset of points. In some embodiments, the server 235 may apply a filter that reflects the effect of environmental conditions on the point cloud 614. For example, the environmental conditions may be rain, snow, and/or dirt that interfere with the operation of the lidar system. In additional embodiments, without departing from the spirit and scope of the present technology, the server 235 may determine the second point cloud from the log data of a second vehicle that was operating in this geographic region.

Step 1010: For the timestamp on the previous trajectory, using the localization algorithm, the server generates a second probable location based on the second point cloud and map representation.

[0208] The next step in the method 1000 is step 1010, in which the server 235 may, for a time stamp on the previous trajectory of the vehicle 220 corresponding to the moment when this self-driving vehicle was in a given place of the geographic region, generate, using the localization algorithm 750, a second probable location 790 based on the second point cloud and the map representation 402.

Step 1012: For a timestamp on the previous trajectory, determine by the server, using the convergence metric, a parameter for assessing the localization quality provided by the localization algorithm in the considered part of the map representation.

[0209] The next step in the method 1000 is step 1012, in which the server 235 can, for a time stamp on the previous trajectory of the vehicle 220, corresponding to the moment when this self-driving vehicle was in a given place of the geographic region, determine, using the first metric 506, a parameter for assessing the quality of the localization provided by the localization algorithm 750 in the considered part of the map representation 402. This parameter characterizes the convergence of the first probable location 780 and the second probable location 790.

Step 1014: For the timestamp on the previous trajectory, the server recognizes the map view part in question as an outdated map view part based on the parameter.

[0210] The next step in the method 1000 is step 1014, in which the server 235 may, for a time stamp on the previous trajectory of the vehicle 220 corresponding to the moment when this self-driving vehicle was at a given location of the geographic region, recognize the considered portion of the map representation 402 as an outdated portion of the map representation 402 based on a parameter. For example, the server 235 may recognize the considered portion of the map as outdated if the parameter indicates that the first and second probable locations do not converge within a given value.

Step 1016: Update the outdated portion of the map view by the server using the first point cloud or the second point cloud.

[0211] The next step in the method 1000 is step 1016, in which the server 235 can update the outdated portion of the map representation 402 using the first point cloud or the second point cloud. In some embodiments, the server 235 can use an iterative closest point algorithm to replace the outdated portion of the map with point cloud data from the first point cloud and/or from the second point cloud.

[0212] Possible changes and improvements to the above-described embodiments of the present technology may be obvious to a person skilled in the art. The preceding description is provided for illustrative purposes only and is not intended to limit the scope of the invention. The scope of protection of the present technology is determined solely by the scope of the appended claims.

Claims (45)

1. A method for updating a representation of a map of a geographic region created based on point cloud data collected by a lidar system of an unmanned vehicle operating in that geographic region, implemented on a server and providing for a timestamp on the previous trajectory of the unmanned vehicle when the unmanned vehicle was at a given location in the geographic region: - the formation by the server, using a localization algorithm, of a set of probable locations of an unmanned vehicle using a set of point clouds associated with a given location located in the considered part of the map representation and the map representation; - determination by the server, using the convergence metric, of a parameter for assessing the quality of localization provided by the localization algorithm when the unmanned vehicle is located in the considered part of the map representation, wherein the parameter characterizes the convergence of the probable locations of the unmanned vehicle from a set of probable locations of the unmanned vehicle; - recognition by the server of the considered part of the map representation as an outdated part of the map representation based on the parameter if the value of the parameter exceeds the specified threshold; and - updating the outdated part of the map representation by the server using the current point cloud data collected by the lidar system. 2. The method according to claim 1, wherein the parameter characterizes the convergence of the first probable location of the unmanned vehicle and the second probable location of the unmanned vehicle within a given threshold value. 3. The method according to claim 2, wherein the first probable location of the unmanned vehicle includes a first probable position of the unmanned vehicle, wherein the specified threshold value is a specified radius, and the portion of the map representation in question is recognized as an outdated portion of the map representation if the first probable position of the unmanned vehicle and the second probable position of the unmanned vehicle do not fall within a circle of the specified radius. 4. The method according to claim 3, wherein the first probable location of the unmanned vehicle includes a first probable orientation of the unmanned vehicle, wherein the specified threshold value is a specified angle, and the considered portion of the map representation is recognized as an outdated portion of the map representation if the first probable position of the unmanned vehicle and the second probable position of the unmanned vehicle do not fall within a circle of a specified radius and the first probable orientation and the second probable orientation do not fall within a sector of a specified angle. 5. A method for updating a representation of a map of a geographic region created based on point cloud data collected by a lidar system of an unmanned vehicle operating in the geographic region, implemented on a server and providing for: - determining by the server a previous trajectory of the unmanned vehicle in a geographic region associated with a plurality of point clouds from the log data of the unmanned vehicle, which was obtained by the lidar system during the movement of the unmanned vehicle along this trajectory in the geographic region; - for a timestamp on the previous trajectory of the unmanned vehicle, when the unmanned vehicle was at a given location of a geographic region located in the considered part of the map representation, determining by the server the first point cloud from a plurality of point clouds that were obtained by the lidar system at the moment corresponding to this timestamp; - formation by the server, using a localization algorithm, of the first probable location of the unmanned vehicle based on the first point cloud and map representation; - determination by the server of a second point cloud associated with a given location; - formation by the server, using a localization algorithm, of a second probable location of the unmanned vehicle based on a second point cloud and a map representation; - determination by the server, using the convergence metric, of the parameter for assessing the quality of localization provided by the localization algorithm in the considered part of the map representation, which characterizes the convergence of the first probable location of the unmanned vehicle and the second probable location of the unmanned vehicle; - recognition by the server of the part of the map representation in question as an obsolete part of the map representation based on the parameter; and - updating the outdated part of the map representation by the server using the current point cloud data collected by the lidar system. 6. The method according to claim 5, wherein determining the second point cloud includes the server generating, based on the first point cloud, a simulation point cloud that is a worse version of the first point cloud. 7. The method of claim 6, wherein the degraded version of the first point cloud is the first point cloud without a certain subset of points. 8. The method according to claim 6, wherein the formation of the simulated point cloud includes the application by the server of a filter reflecting the impact of environmental conditions on the first point cloud. 9. The method of claim 8, wherein the environmental conditions are rain, snow and/or dirt that interfere with the operation of the lidar system. 10. The method according to claim 5, wherein determining the second point cloud includes determining by the server the second point cloud based on the log data of a second unmanned vehicle operating in the geographic region and having a second lidar system, wherein the second point cloud was obtained by the second lidar system when the second unmanned vehicle was in a given location. 11. The method according to paragraph 5, wherein the server is capable of executing a machine learning algorithm and which further comprises: - generating by the server a training set containing initial data for training, which includes a map representation, a first probable location of the unmanned vehicle and a first point cloud, and a training label based on the parameter; and - training the machine learning algorithm to generate, using the training set, a second parameter that indicates the ability of the localization algorithm to generate converging probable locations for the unmanned vehicle in the considered part of the map representation. 12. The method according to claim 11, in which it is considered that the probable locations of the unmanned vehicle converge if the localization algorithm generates probable locations of the unmanned vehicle that converge within a given threshold value. 13. The method according to paragraph 5, wherein the server is capable of executing a machine learning algorithm and which further comprises: - the formation by the server of a training set containing initial data for training, which includes a map, a second probable location of the unmanned vehicle and a second point cloud, and a training label based on the parameter; and - training the machine learning algorithm to generate, using the training set, a second parameter that indicates the ability of the localization algorithm to generate converging probable locations for the unmanned vehicle in the considered part of the map. 14. The method according to paragraph 5, in which for the time mark on the previous trajectory of the unmanned vehicle, when the unmanned vehicle was in a given location of the geographic region, the following is additionally provided: - determining by the server, using a second convergence metric, a second parameter for assessing the quality of localization provided by the localization algorithm in the considered part of the map representation, which indicates the ability of the localization algorithm to generate converging probable locations for the unmanned vehicle in the considered part of the map; and - recognition by the server of the part of the map representation in question as an obsolete part of the map representation using the parameter and/or the second parameter. 15. A server for updating a representation of a map of a geographic region created based on point cloud data collected by a lidar system of an unmanned vehicle operating in that geographic region, capable of: - determine a previous trajectory of the self-driving vehicle in a geographic region associated with a plurality of point clouds from the self-driving vehicle log data that was obtained by the lidar system during the movement of the self-driving vehicle along this trajectory in the geographic region; - for a time stamp on the previous trajectory of the unmanned vehicle, when the unmanned vehicle was at a given location of a geographic region located in the considered part of the map representation, determine the first point cloud from a plurality of point clouds that were obtained by the lidar system at the moment corresponding to this time stamp; - generate, using a localization algorithm, the first probable location of the unmanned vehicle using the first point cloud and map representation; - determine the second point cloud associated with a given location; - generate, using a localization algorithm, a second probable location of the unmanned vehicle based on a second point cloud and a map representation; - using the convergence metric, determine the parameter for assessing the quality of localization provided by the localization algorithm in the considered part of the map representation, which characterizes the convergence of the first probable location of the unmanned vehicle and the second probable location of the unmanned vehicle; - recognize the map view portion in question as an obsolete map view portion based on the parameter; and - update the outdated part of the map view using the current point cloud data collected by the lidar system. 16. The server according to claim 15, the ability of which to determine the second point cloud includes the ability to form, using the first point cloud, a simulation point cloud, which is a worse version of the first point cloud. 17. The server of claim 16, wherein the degraded version of the first point cloud is the first point cloud without a certain subset of points. 18. The server of claim 16, the ability of which to generate the simulated point cloud includes the ability to apply a filter reflecting the impact of environmental conditions on the first point cloud. 19. The server of claim 18, wherein the environmental conditions are rain, snow and/or dirt that interfere with the operation of the lidar system.