Patent ID: 12190155

DETAILED DESCRIPTION

The examples and conditional language recited herein are principally intended to aid the reader in understanding the principles of the present technology and not to limit its scope to such specifically recited examples and conditions. It will be appreciated that those skilled in the art may devise various arrangements which, although not explicitly described or shown herein, nonetheless embody the principles of the present technology and are included within its spirit and scope.

Furthermore, as an aid to understanding, the following description may describe relatively simplified implementations of the present technology. As persons skilled in the art would understand, various implementations of the present technology may be of a greater complexity.

In some cases, what are believed to be helpful examples of modifications to the present technology may also be set forth. This is done merely as an aid to understanding, and, again, not to define the scope or set forth the bounds of the present technology. These modifications are not an exhaustive list, and a person skilled in the art may make other modifications while nonetheless remaining within the scope of the present technology. Further, where no examples of modifications have been set forth, it should not be interpreted that no modifications are possible and/or that what is described is the sole manner of implementing that element of the present technology.

Moreover, all statements herein reciting principles, aspects, and implementations of the technology, as well as specific examples thereof, are intended to encompass both structural and functional equivalents thereof, whether they are currently known or developed in the future. Thus, for example, it will be appreciated by those skilled in the art that any block diagrams herein represent conceptual views of illustrative circuitry embodying the principles of the present technology. Similarly, it will be appreciated that any flowcharts, flow diagrams, state transition diagrams, pseudo-code, and the like represent various processes which may be substantially represented in computer-readable media and so executed by a computer or processor, whether or not such computer or processor is explicitly shown.

The functions of the various elements shown in the figures, including any functional block labeled as a “processor”, may be provided through the use of dedicated hardware as well as hardware capable of executing software in association with appropriate software. When provided by a processor, the functions may be provided by a single dedicated processor, by a single shared processor, or by a plurality of individual processors, some of which may be shared. Moreover, explicit use of the term “processor” or “controller” should not be construed to refer exclusively to hardware capable of executing software, and may implicitly include, without limitation, digital signal processor (DSP) hardware, network processor, application specific integrated circuit (ASIC), field programmable gate array (FPGA), read-only memory (ROM) for storing software, random access memory (RAM), and non-volatile storage. Other hardware, conventional and/or custom, may also be included.

Software modules, or simply modules which are implied to be software, may be represented herein as any combination of flowchart elements or other elements indicating performance of process steps and/or textual description. Such modules may be executed by hardware that is expressly or implicitly shown.

With these fundamentals in place, we will now consider some non-limiting examples to illustrate various implementations of aspects of the present technology.

Computer System

Referring initially toFIG.1, there is depicted a schematic diagram of a computer system100suitable for use with some implementations of the present technology. The computer system100includes various hardware components including one or more single or multi-core processors collectively represented by a processor110, a solid-state drive120, and a memory130, which may be a random-access memory or any other type of memory.

Communication between the various components of the computer system100may be enabled by one or more internal and/or external buses (not shown) (e.g. a PCI bus, universal serial bus, IEEE 1394 “Firewire” bus, SCSI bus, Serial-ATA bus, etc.), to which the various hardware components are electronically coupled. According to embodiments of the present technology, the solid-state drive120stores program instructions suitable for being loaded into the memory130and executed by the processor110for determining a presence of an object. For example, the program instructions may be part of a vehicle control application executable by the processor110. It is noted that the computer system100may have additional and/or optional components (not depicted), such as network communication modules, localization modules, and the like.

Networked Computing Environment

With reference toFIG.2, there is depicted a networked computing environment200suitable for use with some non-limiting embodiments of the present technology. The networked computing environment200includes an electronic device210associated with a vehicle220and/or associated with a user (not depicted) who is associated with the vehicle220(such as an operator of the vehicle220). The environment200also includes a server235in communication with the electronic device210via a communication network240(e.g. the Internet or the like, as will be described in greater detail herein below).

In at least some non-limiting embodiments of the present technology, the electronic device210is communicatively coupled to control systems of the vehicle220. The electronic device210could be arranged and configured to control different operations systems of the vehicle220, including but not limited to: an ECU (engine control unit), steering systems, braking systems, and signaling and illumination systems (i.e. headlights, brake lights, and/or turn signals). In such an embodiment, the vehicle220could be a self-driving vehicle220.

In some non-limiting embodiments of the present technology, the networked computing environment200could include a GPS satellite (not depicted) transmitting and/or receiving a GPS signal to/from the electronic device210. It will be understood that the present technology is not limited to GPS and may employ a positioning technology other than GPS. It should be noted that the GPS satellite can be omitted altogether.

The vehicle220, to which the electronic device210is associated, could be any transportation vehicle, for leisure or otherwise, such as a private or commercial car, truck, motorbike or the like. Although the vehicle220is depicted as being a land vehicle, this may not be the case in each and every non-limiting embodiment of the present technology. For example, in certain non-limiting embodiments of the present technology, the vehicle220may be a watercraft, such as a boat, or an aircraft, such as a flying drone.

The vehicle220may be user operated or a driver-less vehicle. In some non-limiting embodiments of the present technology, it is contemplated that the vehicle220could be implemented as a Self-Driving Car (SDC). It should be noted that specific parameters of the vehicle220are not limiting, these specific parameters including for example: vehicle manufacturer, vehicle model, vehicle year of manufacture, vehicle weight, vehicle dimensions, vehicle weight distribution, vehicle surface area, vehicle height, drive train type (e.g. 2× or 4×), tire type, brake system, fuel system, mileage, vehicle identification number, and engine size.

According to the present technology, the implementation of the electronic device210is not particularly limited. For example, the electronic device210could be implemented as a vehicle engine control unit, a vehicle CPU, a vehicle navigation device (e.g. TomTom™, Garmin™), a tablet, a personal computer built into the vehicle220, and the like. Thus, it should be noted that the electronic device210may or may not be permanently associated with the vehicle220. Additionally or alternatively, the electronic device210could be implemented in a wireless communication device such as a mobile telephone (e.g. a smart-phone or a radio-phone). In certain embodiments, the electronic device210has a display270.

The electronic device210could include some or all of the components of the computer system100depicted inFIG.1, depending on the particular embodiment. In certain embodiments, the electronic device210is an on-board computer device and includes the processor110, the solid-state drive120and the memory130. In other words, the electronic device210includes hardware and/or software and/or firmware, or a combination thereof, for processing data as will be described in greater detail below.

In some non-limiting embodiments of the present technology, the communication network240is the Internet. In alternative non-limiting embodiments of the present technology, the communication network240can be implemented as any suitable local area network (LAN), wide area network (WAN), a private communication network or the like. It should be expressly understood that implementations for the communication network240are for illustration purposes only. A communication link (not separately numbered) is provided between the electronic device210and the communication network240, the implementation of which will depend, inter alia, on how the electronic device210is implemented. Merely as an example and not as a limitation, in those non-limiting embodiments of the present technology where the electronic device210is implemented as a wireless communication device such as a smartphone or a navigation device, the communication link can be implemented as a wireless communication link. Examples of wireless communication links may include, but are not limited to, a 3G communication network link, a 4G communication network link, and the like. The communication network240may also use a wireless connection with the server235.

In some embodiments of the present technology, the server235is implemented as a computer server and could include some or all of the components of the computer system100ofFIG.1. In one non-limiting example, the server235is implemented as a Dell™ PowerEdge™ Server running the Microsoft™ Windows Server™ operating system, but can also be implemented in any other suitable hardware, software, and/or firmware, or a combination thereof. In the depicted non-limiting embodiments of the present technology, the server235is a single server. In alternative non-limiting embodiments of the present technology, the functionality of the server235may be distributed and may be implemented via multiple servers (not shown).

In some non-limiting embodiments of the present technology, the processor110of the electronic device210could be in communication with the server235to receive one or more updates. Such updates could include, but are not limited to, software updates, map updates, routes updates, weather updates, and the like. In some non-limiting embodiments of the present technology, the processor110can also be configured to transmit to the server235certain operational data, such as routes travelled, traffic data, performance data, and the like. Some or all such data transmitted between the vehicle220and the server235may be encrypted and/or anonymized.

It should be noted that a variety of sensors and systems may be used by the electronic device210for gathering information about surroundings250of the vehicle220. As seen inFIG.2, the vehicle220may be equipped with a plurality of sensor systems280. It should be noted that different sensor systems from the plurality of sensor systems280may be used for gathering different types of data regarding the surroundings250of the vehicle220.

In one example, the plurality of sensor systems280may include various optical systems including, inter alia, one or more camera-type sensor systems that are mounted to the vehicle220and communicatively coupled to the processor110of the electronic device210. Broadly speaking, the one or more camera-type sensor systems may be configured to gather image data about various portions of the surroundings250of the vehicle220. In some cases, the image data provided by the one or more camera-type sensor systems could be used by the electronic device210for performing object detection procedures. For example, the electronic device210could be configured to feed the image data provided by the one or more camera-type sensor systems to an Object Detection Neural Network (ODNN) that has been trained to localize and classify potential objects in the surroundings250of the vehicle220.

In another example, the plurality of sensor systems280could include one or more radar-type sensor systems that are mounted to the vehicle220and communicatively coupled to the processor110. Broadly speaking, the one or more radar-type sensor systems may be configured to make use of radio waves to gather data about various portions of the surroundings250of the vehicle220. For example, the one or more radar-type sensor systems may be configured to gather radar data about potential objects in the surroundings250of the vehicle220, such data potentially being representative of a distance of objects from the radar-type sensor system, orientation of objects, velocity and/or speed of objects, and the like.

In a further example, the plurality of sensor systems280could include one or more Light Detection and Ranging (LIDAR) systems that are mounted to the vehicle220and communicatively coupled to the processor110. Broadly speaking, a LIDAR system is configured to capture data about the surroundings250of the vehicle220used, for example, for building a multi-dimensional map of objects in the surroundings250of the vehicle220. The LIDAR system could be mounted, or retrofitted, to the vehicle220in a variety of locations and/or in a variety of configurations for gathering information about surroundings250of the vehicle220.

For example, depending on the implementation of the vehicle220and the LIDAR system, the LIDAR system could be mounted on an interior, upper portion of a windshield of the vehicle220. Nevertheless, other locations for mounting the lidar system are within the scope of the present disclosure, including on a back window, side windows, front hood, rooftop, front grill, front bumper or the side of the vehicle220.

In the context of the present technology, the electronic device210is configured to detect one or more objects in the surroundings250of the vehicle220based on data acquired from one or more camera systems and from one or more LIDAR systems. For example, the electronic device210configured to detect a given object in the surroundings250of the vehicle220may be configured to identify LIDAR data and camera data associated with the given object, generate an “embedding” representative of features associated with the given object, and detect the object by generating a bounding box for the object.

With reference toFIG.3, there is an illustrative example300of the vehicle220in the surroundings250. Let it be assumed that the vehicle220is travelling on a road segment350. The electronic device210may receive from the sensor system280information about the surroundings250of the vehicle220, and more particularly, about the road segment350and one or more “actors” (also sometimes referred to as “agents”) on the road segment350, such as neighboring objects in surroundings of the vehicle220.

The electronic device210is configured to generate a “graph-structure” for operating the vehicle220on the road segment at a given moment in time. For instance, at a given moment in time, the electronic device210may be configured to generate a graph-structure having nodes and edges connecting respective pairs of nodes thereof. Nodes are representative of respective potential positions of the vehicle220on the road segment350and edges are representative of transitions between respective pairs of potential positions. In this instance, the electronic device210may determine a given sequence of edges in such a graph-structure which (i) is associated with an acceptable total cost of edges in the sequence, and (ii) is representative of a potential path that the SDC should follow on the road segment350. It should be noted that the electronic device210may make use of this information for generating trajectory data for the vehicle220to actually follow that path on the road segment350.

To better illustrate this, reference will now be made toFIG.4depicting a non-limiting example of a graph-structure420that the electronic device210may be configured to generate for the road segment350at a given moment in time. The graph-structure420has a plurality of nodes (not numbered) and a plurality of edges (not numbered) connecting respective nodes of the plurality of nodes. For example, an edge450of the graph-structure420connects a first node451and a second node452. A given node is associated with a respective potential position of the vehicle220on the road segment350. A given edge is representative of a transition of the vehicle220between potential positions of the respective pair of nodes. For example, the edge450is representative of the transition of the vehicle220between its potential positions of the first node451and the second node452.

It should be noted that the electronic device210may be configured to store information in association with a respective node and a respective edge of the graph-structure420. For example, the electronic device210may be configured to store positional data in association with a given node. In another example, the electronic device210may be configured to store, in association with a given edge, the positional data of a respective pair of nodes.

Furthermore, it is contemplated that additional data may be stored in association with a respective node of the graph-structure420. It can be said that additional data may be stored in association with a respective node of the graph-structure420and which is indicative of at least some information about a potential state of the vehicle220on the road segment350.

In the context of the present technology, when generating the graph-structure420, the electronic device210is configured to generate attributes for respective edges of the graph-structure420and store these attributes in association with the respective edges in cache memory. In at least some embodiments of the present technology, the electronic device210may be configured to assign a unique identifier (UID) to a respective node of the graph-structure420. As such, the electronic device210may be configured to store information about a given edge (including its attributes) in association with a respective pair of UIDs in the cache memory. Therefore, when information about a given edge is to be retrieved for further processing, the electronic device210may use a pair of UIDs of a respective pair of nodes as a “key” for accessing the information about the given edge in the cache memory. It can be said that the electronic device210may be configured to store an “entry” for a given edge with a respective pair of UIDs as a key for that entry in the cache memory.

The electronic device210may make use of the graph-structure420for operating the vehicle220on the road segment350. To that end, the electronic device210may generate a “path” for the vehicle220on the road segment and which is representative of a respective sequence of edges in the graph-structure420. Broadly speaking, the electronic device210may be configured to generate one or more potential paths that the vehicle220may follow on the road segment350. These paths may also be ranked amongst each other based on a total cost associated with a respective sequence of edges.

For example, edge cost criteria may be applied onto attributes of the respective edges in a given sequence for determining a “total cost” for the sequence of edges. The electronic device210may rank the paths based on how costly a respective sequence of edges is. The electronic device210may also use the attributes of the respective sequence of edges for generating a trajectory for the vehicle220for following a given path. This means that the electronic device210may be configured to generate trajectory data for operating the vehicle220on the road segment350based on the edge data associated with the sequence of the edges. The electronic device210may also cause operation of the vehicle220in accordance with the so-determined trajectory on the road segment350. It should be noted that the electronic device210may be configured to periodically generate graph-structures at respective moments in time during operation of the vehicle220similarly to how the electronic device210generate the graph-structure420.

It should be noted that generation of the graph-structure420is a computationally expensive operation, which can take a considerable amount of time. This is due to the fact that the electronic device210needs to compute a plurality of attributes for respective edges of the graph-structure420. In at least some embodiments of the present technology, developers of the present technology have devised methods and electronic devices for increasing the efficiency of the graph-structure generation process.

It should be noted that a given edge may be associated with at least two types of attributes, namely “static attributes” and “dynamic attributes”. How static attributes and dynamic attributes are generated will be discussed in greater details herein further below. However, it should be noted that developers of the present technology have realized that the electronic device210may be configured to parallelize the generation processes of static and dynamic attributes. In other words, it is contemplated that the electronic device210may be configured to execute a first processing pipeline for generating dynamic attributes for edges of the graph-structure420, and a second (parallel) processing pipeline for generating static attributes for edges of the graph-structure420.

In the context of the present technology, a first given processing pipeline may be referred to as a “main processing pipeline” or a “dynamic processing pipeline” that is used by the electronic device210for (i) generating dynamic attributes for respective edges of a given graph-structure, and (ii) retrieving from cache memory static attributes for respective edges of the given graph-structure. A second given processing pipeline may be referred to as a “support processing pipeline” or a “static processing pipeline” that is used by the electronic device for (i) generating static attributes for potential positions on the road segment350, and (ii) caching the static attributes of respective potential positions on the road segment350in the cache memory.

Developers of the present technology have realized that executing the two processing pipelines in parallel (e.g., computing dynamic attributes and static attributes in a parallel manner) may reduce the amount of time necessary for generating a graph-structure and, in turn, may reduce the total amount of time necessary for generating trajectory data for operating the vehicle220on the road segment350. Increasing computational speed of the graph-structure generation process during operation of the vehicle220is beneficial for the operation of the vehicle220.

How the electronic device210is configured to implement the support processing pipeline and the main processing pipeline in at least some embodiments of the present technology will be discussed in turn with reference toFIG.5.

Static Pipeline

There is depicted inFIG.5a representation of a support processing pipeline510executed by the electronic device210in real-time during operation of the vehicle220. As part of the support processing pipeline510, the electronic device210is configured to perform a first static attribute caching (SAC) operation511at a first moment in time (not numbered) and a second SAC operation512at a second moment in time (not numbered). During the first SAC operation511, the electronic device210is configured to cache first static data513in a cache550. During the second SAC operation512, the electronic device210is configured to cache second static data514in the cache550.

It should be noted that the electronic device210may generate the first static data513by computing static attributes for a plurality of potential positions of the vehicle220on the road segment350. Broadly speaking, a given static attribute is indicative of information about a static object on the road segment350relative to a respective potential position. For example, a given static attribute may be, but is not limited to:a distance between the respective potential position and a position of a road cone on the road segment350;a distance between the respective potential position and a position of a stop sign on the road segment350;a distance between the respective potential position and a position of a lane on the road segment350; anda distance between the respective potential position and a position of a lane center of a lane on the road segment350.

It is contemplated that the electronic device210may be configured to compute static attributes for a large number of potential positions on the road segment350. For example, the electronic device210may be configured to generate static attributes for potential positions of respective nodes of a given graph-structure and for other potential positions that are intermediate to the respective potential positions of nodes of the given graph-structure.

In at least some embodiments of the present technology, due to the fact that the electronic device210may identify a large number of potential positions on the road segment350, the electronic device210may be configured to apply a “priority” logic for determining an order of potential positions for which the static attributes are to be generated. For example, the electronic device210may be configured to prioritize generation of static attributes for potential positions that are located closest to lane centers of lanes. In one embodiment, the electronic device210may be configured to generate static attributes for a pre-selected number of top priority potential positions. In an other embodiment, the electronic device210may be configured to generate static attributes for potential positions having been ordered based on their priority and until a pre-selected time limit is reached.

Once the electronic device210generates static attributes for a plurality of potential positions on the road segment350, the electronic device210may store the first static data513in the cache550in association with the respective potential positions.

The electronic device210may also be configured to perform generation of static attributes for respective potential positions in a periodical manner. For example, once the electronic device210performs the first SAC operation511, the electronic device210may begin a new cycle of static attributes generation. In some embodiments, it can be said that the electronic device210may be configured to re-compute and/or update static attributes for at least some potential positions and/or compute static attributes for other potential positions. This generation process occurs during a time interval515and ends with the second SAC operation512during which the second static data514is stored in the cache550.

It can be said that the electronic device210may be configured to store static data in the cache550in “batches”—that is, during a respective static generation cycle, the electronic device210may be configured to generate respective static data and store (and/or update) the static data in the cache550. The size of a given batch, such as the size of the second static data514, for example, may depend on a length of the time interval515. How the length of the time interval515is determined will be discussed in greater details herein further below.

Dynamic Pipeline

Also depicted inFIG.4, is a representation of a main processing pipeline520executed by the electronic device210in real-time during operation of the vehicle220. As part of the main processing pipeline520, the electronic device210is configured to perform a first graph-structure generation (GSG) operation521at a first moment in time (not numbered), a second GSG operation522at a second moment in time (not numbered), and a third GSG operation523at a third moment in time (not numbered).

During the first GSG operation521, the electronic device210is configured to generate dynamic attributes for respective edges of a first graph-structure and retrieve static attributes for respective edges of the first graph-structure. The electronic device210may be configured to use the so-generated first graph-structure for operating the vehicle220during a time interval525, and/or until the second GSG operation522at the second moment in time. During the second GSG operation522, the electronic device210is configured to generate dynamic attributes for respective edges of a second graph-structure and retrieve static attributes for respective edges of the second graph-structure. It is contemplated that the first graph-structure and the second graph-structure may share at least some edges, or in other words, at least some edges of the second graph-structure may correspond to edges of the first graph-structure, without departing from the scope of the present technology. The electronic device210may be configured to use the so-generated second graph-structure for operating the vehicle220until the third GSG operation523at the third moment in time. During the third GSG operation523, the electronic device210is configured to generate dynamic attributes for respective edges of a third graph-structure and retrieve (latest/updated) static attributes for respective edges of the third graph-structure. It is contemplated that the second graph-structure and the third graph-structure may share at least some edges, or in other words, at least some edges of the third graph-structure may correspond to edges of the second graph-structure, without departing from the scope of the present technology. The electronic device210may be configured to use the so-generated third graph-structure for operating the vehicle220until a next GSG operation.

Returning to the description of the first GSG operation521, the electronic device210may generate dynamic attributes for respective edges of the first graph-structure. Broadly speaking, a given dynamic attribute is indicative of information about a moving object on the road segment350relative to a respective one of a respective set of intermediate potential positions associated with a given edge. As mentioned above, a given edge connects a pair of respective nodes associated with a respective pair of potential positions of the vehicle220on the road segment350. However, it can also be said that a given edge is also associated with a set of intermediate potential positions on the road segment350between the respective pair of potential positions, and in which intermediate potential positions the vehicle220will be located if the vehicle220attempts a transition between the respective pair of potential positions (associated with the respective pair of nodes).

For example, a given dynamic attribute may be, but is not limited to:a distance between a respective intermediate potential position and a position of an other moving vehicle on the road segment350;a distance between a respective intermediate potential position and a position of a moving pedestrian on the road segment350; anda distance between a respective intermediate potential position and a position of a moving cyclist on the road segment350.

In addition to generating dynamic attributes for respective edges of the first graph-structure, the electronic device210is further configured during the first GSG operation521to retrieve static attributes for respective edges of the first graph-structure from the cache550. To that end, the electronic device210may be configured to send a request526to the cache550for retrieving relevant static data.

The request526may take many forms. In one embodiment, the request526may be indicative of information regarding pairs of respective UIDs associated with respective edges from the first graph-structure. In an other embodiment, the request526may also be indicative of information regarding respective sets of intermediate potential positions associated with respective edges from the graph-structure. Irrespective of specific information included in the request526, the request526comprises information that allows identifying and retrieving static attributes stored in the cache550and which are associated with sets of intermediate potential positions of respective edges of the first graph-structure. As such, the electronic device210may acquire third static data516comprising static attributes associated with sets of potential positions of respective edges of the first graph-structure.

It can be said that the third static data516is a subset of the first static data513stored by the electronic device210during execution of the support processing pipeline510.

By the same token, during the second GSG operation522, the electronic device210may generate dynamic attributes for respective edges of the second graph-structure, and retrieve static attributes for respective edges of the second graph-structure from the cache550. To that end, the electronic device210may be configured to send a request527to the cache550for retrieving relevant static data. The request527comprises information that allows identifying and retrieving static attributes stored in the cache550and which are associated with potential positions of respective edges of the second graph-structure. As such, the electronic device210may acquire fourth static data517comprising static attributes associated with sets of potential positions of respective edges of the second graph-structure.

It can be said that the fourth static data517is a subset of the first static data513stored by the electronic device210during execution of the support processing pipeline510. In some embodiments of the present technology, if the first graph-structure and the second graph-structure share at least one edge, it is contemplated that the third static data516and the fourth static data517may both include static attributes for the at least one shared edge.

It should be noted that static attributes of a given edge are a less likely to change in time if compared to dynamic attributes of the given edge. For example, a distance between a potential position on the road segment350and a static object is likely to stay the same, whereas a distance between that potential position and a moving object is likely to change. For that reason, it is beneficial to perform GSG operations more frequently than the SAC operations in order to have accurate attributes associated with edges of graph-structures.

Similarly to what has been described above for the first and second GSG operations521and522, during the third GSG operation523, the electronic device210may generate dynamic attributes for respective edges of the third graph-structure, and retrieve static attributes for respective edges of the third graph-structure from the cache550. To that end, the electronic device210may be configured to send a request528to the cache550for retrieving relevant static data. The request528comprises information that allows identifying and retrieving static attributes stored in the cache550and which are associated with potential positions of respective edges of the third graph-structure. As such, the electronic device210may acquire fifth static data518comprising static attributes associated with sets of potential positions of respective edges of the third graph-structure.

It can be said that the fifth static data518is a subset of the second static data514stored by the electronic device210during execution of the support processing pipeline510, since the second SAC operation512has occurred prior to the third GSG operation523.

Developers of the present technology have realized that so-excluding computation of static attributes from the main processing pipeline520, and in a sense “offloading” this computation to the parallel support processing pipeline510, allows reducing the amount of time required by the electronic device210for performing the GSG operations521,522, and523if compared to a given GSG operation during which both dynamic and static attributes have to be computed in a same processing pipeline. Indeed, as opposed to a GSG operation during which both dynamic and static attributes are computed in a same processing pipeline, some embodiments of the present technology allow parallel computation and caching of the static attributes so that they can be retrieved from the cache during the GSG operations521,522, and523, leaving computation of only dynamic attributes in the main processing pipeline520.

It should also be noted that in the non-limiting example illustrated onFIG.5, GSG operations and SAC operations do not occur at the same moments in time. Thus, it can be said that in some embodiments of the present technology, generation of static attributes for the plurality of potential positions (SAC operations) by the electronic device210can be executed asynchronously from generation of dynamic attributes (GSG operations) by the electronic device210. In fact, as previously alluded, the periodicity of GSG operations may be different from the periodicity of the SAC operations, meaning that GSG operations can occur at a different frequency than the SAC operations.

In at least some embodiments of the present technology, it is contemplated that the frequency of SAC operations may be pre-selected by an operator of the electronic device210based on a frequency of GSG operations.

In a first example, let it be assumed that the time interval515is selected to be considerably shorter to the time interval525, meaning that the SAC operations will be performed at a considerably higher frequency than GSG operations. Such selection of the time interval515based on the time interval525may be undesirable as a large number of batches will need to be cached. It should be noted that performing writing calls on the cache requires considerable resources, and therefore, having a large number of batches increases that amount of resources necessary for their caching.

In a second example, let it be assumed that the time interval515is selected to be considerably longer than the time interval525, meaning that SAC operations will be performed at a considerably lesser frequency than GSG operations. Such selection of the time interval515based on the time interval525may be undesirable as very large batches will need to be cached at each SAC operation. It should be noted that the longer the time interval525, the more time the electronic device210has for generating static data, and the more static data will need to be cached at the second SAC operation512. However, the larger the batch, the more time is required for its caching in the cache550, and so there is a risk that static data contained therein may already be outdated by the time the caching of a large batch is completed.

Therefore, developers of the present technology have realized that the operator of the electronic device210may select a length of the time interval515based on the length of the time interval525for mitigating a trade-off caused by the size of batches generated by the support processing pipeline510. In at least some embodiments of the present technology, the operator of the electronic device210may pre-select the length of the time interval515based on the length of the time interval525such that the time interval515is not shorter than the time interval525, and such that the resulting batches generated by the support processing pipeline510are not too large, nor too numerous.

In one example, the time interval515associated with the SAC operations may be 400 milliseconds. In an other example, the time interval515associated with the SAC operations may be 450 milliseconds. In further examples, the time interval515may be between 400 and 450 milliseconds. In yet other examples, the time interval515may be about 420 milliseconds.

In one example, the time interval525associated with the GSG operations may be 300 milliseconds. In an other example, the time interval525associated with the GSG operations may be 350 milliseconds. In further examples, the time interval525may be between 300 and 350 milliseconds. In yet other examples, the time interval525may be about 320 milliseconds.

In further embodiments of the present technology, it is contemplated that the electronic device210may be configured to further cache dynamic attributes generated during a given GSG operation and then retrieve at least some of them during a subsequent GSG operation for reducing the amount of time required for generating a respective graph-structure.

To better illustrate this, reference will now be made toFIG.6depicting a representation600of how some dynamic attributes may be cached in the cache550, in addition to static attributes. In addition to what has been described with reference toFIG.5above, in the embodiment illustrated inFIG.6, the electronic device210may be configured to further store first dynamic data610generated during the first GSG operation521in the cache550. For example, the first dynamic data610may include dynamic attributes generated for respective edges of the first graph-structure that is generated during the first GSG operation521. During the second GSG operation522, the electronic device210is configured to generate the second graph-structure. In this embodiment, if the second graph-structure shares at least one edge with the first graph-structure generated during the first GSG operation521, the electronic device210may be configured to send a request640to the cache550for retrieving the relevant static attributes (similarly to what has been described above), and also the dynamic attributes associated with the at least one edge that is shared by the first and the second graph-structures. As such, the electronic device210may acquire fourth static data517comprising static attributes associated with sets of potential positions of respective edges of the second graph-structure (similarly to what has been described above), and also second dynamic data620comprising dynamic attributes associated with the shared edges between the first and the second graph-structure.

Developers of the present technology have realized that caching dynamic attributes generated during a current GSG operation, in addition to static attributes, may further reduce the amount of time required for performing a subsequent GSG operation if a subsequent graph-structure is sharing edges with a current graph-structure.

For example, if a value of a dynamic attribute has been computed during the first GSG operation521for an edge that is relatively far from a current position of the vehicle220on the road segment350, the accuracy of the value may be less important for the immediate operation of the vehicle220. Hence, instead of re-computing the value of this dynamic attribute of a far edge during the second GSG operation522, the electronic device210may re-use the value of the dynamic attribute computed during the first GSG operation521.

In this embodiment illustrated inFIG.6, the electronic device210may be configured to cache the first dynamic data610for a pre-determined time limit corresponding to a time interval630. Temporarily caching dynamic attributes for edges may reduce the risk of using values of dynamic attributes that could no longer be accurate enough. Indeed, as dynamic attributes tend to change in time, values of dynamic attributes may no longer be eligible for re-use after the pre-determined time limit has passed.

With reference toFIG.7, there is depicted a method700that is performed by the electronic device210in at least some embodiments of the present technology. It is contemplated that the method700may be performed by the electronic device210in real-time during operation of the vehicle220. It is also contemplated that steps of the method700may be performed in parallel as will now be discussed in greater details.

STEP710: Executing in Real-Time a First Processing Pipeline, Comprising Generating Static Attributes for a Plurality of Potential Positions of the SDC on the Road Segment, and Caching the Static Attributes in Association with the Respective Ones of the Plurality of Potential Positions

The method700has a step710during which the electronic device210executes, in real-time, a first processing pipeline. In at least some embodiments, it can be said that the first processing pipeline is the support/static processing pipeline described above.

As part of the first processing pipeline, the electronic device210is configured to generate static attributes for a plurality of potential positions of the vehicle220on the road segment350. Broadly speaking, a given static attribute is indicative of information about a static object on the road segment350relative to a respective potential position associated with a given edge. As part of the first processing pipeline, the electronic device210is configured to cache, in a cache memory (the cache550), the static attributes in association with the respective ones of the plurality of potential positions. The cache550may be implanted as hardware component, a software component, and/or a combination of both for storing data so that future requests for that data can be serviced faster. For example, data stored in the cache550might be the result of an earlier computation or a copy of data stored elsewhere.

In some embodiments of the present technology, it is contemplated that the electronic device210may be configured to apply a prioritization logic for determining an order of potential positions for which the static attributes are to be generated in the first processing pipeline. For example, the plurality of potential positions for which static attributes are generated may include a pre-selected number of potential positions (top ranked based on the prioritization logic). The caching the static attributes may be triggered once the static attributes are generated for the pre-selected number of potential positions. In another example, the plurality of potential positions for which static attributes are generated may include top ranked potential positions from an order list of potential positions for which the electronic device210has enough time to generate static attributes before a pre-determined time limit expires.

In some embodiments, a given static attribute of a respective edge may be one of: a distance between a given one of respective set of intermediate potential positions and a position of a road cone on the road segment, a distance between the given one of the respective set of intermediate potential positions and a position of a stop sign on the road segment, a distance between the given one of the respective set of intermediate potential positions and a position of a lane on the road segment, and a distance between a given one of the respective set of intermediate potential positions and a position of a lane center of the lane on the road segment.

STEP720: Executing in Real-Time a Second Processing Pipeline in Parallel with the First Processing Pipeline, Comprising Generating a Graph-Structure for Operating the SDC on the Road Segment

The method has a step720during which the electronic device210is configured to execute, in real-time, a second processing pipeline in parallel with the first processing pipeline of the step710. In at least some embodiments, it can be said that the second processing pipeline is a main/dynamic processing pipeline described above.

It can also be said that steps710and720of the method700can be executed by the electronic device210in parallel. In at least some embodiments, the electronic device210may be configured to dedicate first processing resources for executing the step710and second processing resources for executing the step720. It is contemplated that the first processing resources may be distinct from the second processing resources.

As part of the second processing pipeline, the electronic device is configured to generate graph-structure for operating the vehicle220on the road segment350. The graph-structure has nodes and edges, and where a given node is associated with a respective potential position of the vehicle220on the road segment350, and where a given edge is representative of a transition of the vehicle220between potential positions of the respective pair of nodes. The given edge is associated with a respective set of intermediate potential positions between the potential positions of the respective pair of nodes.

As part of the second processing pipeline, during the generation of the graph-structure, the electronic device210is configured to generate dynamic attributes for a given edge of the graph-structure. Broadly speaking, a given dynamic attribute is indicative of information about a moving object on the road segment350relative to a respective one of a respective set of intermediate potential positions (and/or potential positions of respective pair of nodes).

In some embodiments, the given dynamic attribute of a respective edge may be one of: a distance between a given one of a respective set of intermediate potential positions and a position of an other vehicle on the road segment, a distance between the given one of the respective set of intermediate potential positions and a position of a pedestrian on the road segment, and a distance between the given one of the respective set of intermediate potential positions and a position of a cyclist on the road segment. It is contemplated that generation of static attributes may be performed by the electronic device210asynchronously from the generation of dynamic attributes.

As part of the second processing pipeline, during the generation of the graph-structure, the electronic device210is configured to acquire from the cache memory static attributes for the given edge of the graph-structure. The static attributes for the given edge include the static attributes cached in association with the respective set of intermediate potential positions and/or potential positions of a respective pair of nodes. The given edge in the graph-structure is thus associated with the static attributes generated by the first processing pipeline and with the dynamic attributes generated by the second processing pipeline.

In further embodiments of the present technology, the graph-structure may be a first graph-structure amongst a plurality of graph-structures to be generated in a periodical manner during operation of the vehicle220. The electronic device210may be configured to use the first graph-structure for operation the vehicle220during a first time interval on the road segment350. In these embodiments, as part of the second processing pipeline, the electronic device210may be configured to generate a second graph-structure for operating the vehicle220on the road segment350during a second time interval. The second graph-structure may share the given edge with the first graph-structure. The generation of the second graph-structure comprises the electronic device210configured to generate updated dynamic attributes for the given edge. A given updated dynamic attribute may be indicative of updated information about the moving object on the road segment relative to the respective one of the respective set of intermediate potential positions (and/or potential positions of the respective pair of nodes). The generation of the second graph-structure comprises the electronic device210configured to acquiring from the cache memory the static attributes for the given edge, such that the given edge in the second graph-structure is associated with the static attributes generated by the first processing pipeline and with the updated dynamic attributes generated by the second processing pipeline.

In some embodiments, generation of the static attributes for the plurality of potential positions of the vehicle220on the road segment350may be performed at a first moment in time. In these embodiments, execution of the first processing pipeline may further comprise the electronic device210configured to generate updated static attributes for the plurality of potential positions at a second moment in time, and where the first moment in time and the second moment in time defining a third time interval. It should be noted that a length of the third time interval may be pre-selected based on a length of at least one of the first time interval and the second time interval for reducing processing resources of the electronic device required for executing the first processing pipeline, as explained above.

In other embodiments, the method700may further comprise the electronic device210causing operation of the vehicle220on the road segment350based on the graph-structure. For example, the electronic device210may be configured to determine a cost of the given edge in the graph-structure based on the respective static and dynamic attributes. One or more cost criteria as known in the art may be used by the electronic device210for determining the cost. The electronic device210is also configured to determine a sequence of edges in the graph-structure representative of a potential path for the vehicle220on the road segment350. The sequence of edges includes the given edge and is associated with an acceptable total cost of edges in the sequence. The electronic device210is also configured to generate a given trajectory for the vehicle220on the road segment350based on the sequence of edges. For example, the electronic device210may be configured to generate inter alia a speed profile for the vehicle220for following the sequence of edges on the road segment350. The electronic device210is also configured to cause operation of the vehicle220for travelling on the road segment in accordance with the given trajectory.

With reference toFIG.8, there is depicted a method800that is performed by the electronic device210in at least some embodiments of the present technology. It is contemplated that the method800may be performed by the electronic device210in real-time during operation of the vehicle220. It is also contemplated that steps of the method800may be performed in parallel as will now be discussed in greater details.

STEP810: Executing in Real-Time a First Processing Pipeline, Comprising Generating Static Attributes for a Plurality of Potential Positions of the SDC on the Road Segment for a First Interval of Time, and Caching the Static Attributes in Association with the Respective Ones of the Plurality of Potential Positions

The method800has a step810during which the electronic device210executes, in real-time, a first processing pipeline. In at least some embodiments, it can be said that the first processing pipeline is the support/static processing pipeline described above.

As part of the first processing pipeline, the electronic device210is configured to generate static attributes for a plurality of potential positions of the vehicle220on the road segment350. Broadly speaking, a given static attribute is indicative of information about a static object on the road segment350relative to a respective potential position associated with a given edge. As part of the first processing pipeline, the electronic device210is configured to cache, in a cache memory (the cache550), the static attributes in association with the respective ones of the plurality of potential positions. The cache550may be implanted as hardware component, a software component, and/or a combination of both for storing data so that future requests for that data can be serviced faster. For example, data stored in the cache550might be the result of an earlier computation or a copy of data stored elsewhere. It should be noted that generation of the static attributes for the plurality of potential positions of the vehicle220on the road segment350may be performed for a first time interval.

In some embodiments of the present technology, it is contemplated that the electronic device210may be configured to apply a prioritization logic for determining an order of potential positions for which the static attributes are to be generated in the first processing pipeline. For example, the plurality of potential positions for which static attributes are generated may include a pre-selected number of potential positions (top ranked based on the prioritization logic). The caching the static attributes may be triggered once the static attributes are generated for the pre-selected number of potential positions. In another example, the plurality of potential positions for which static attributes are generated may include top ranked potential positions from an order list of potential positions for which the electronic device210has enough time to generate static attributes before a pre-determined time limit expires.

In some embodiments, a given static attribute of a respective edge may be one of: a distance between a given one of respective set of intermediate potential positions and a position of a road cone on the road segment, a distance between the given one of the respective set of intermediate potential positions and a position of a stop sign on the road segment, a distance between the given one of the respective set of intermediate potential positions and a position of a lane on the road segment, and a distance between a given one of the respective set of intermediate potential positions and a position of a lane center of the lane on the road segment.

STEP820: Executing in Real-Time a Second Processing Pipeline in Parallel with the First Processing Pipeline, Comprising Generating a Graph-Structure for Operating the SDC on the Road Segment for a Second Time Interval, a Length of the First Time Interval Being Pre-Selected Based on a Length of the Second Time Interval for Reducing Processing Resources of the Electronic Device for Executing the First Processing Pipeline

The method has a step820during which the electronic device210is configured to execute, in real-time, a second processing pipeline in parallel with the first processing pipeline of the step810. In at least some embodiments, it can be said that the second processing pipeline is a main/dynamic processing pipeline described above.

It can also be said that steps810and820of the method800can be executed by the electronic device210in parallel. In at least some embodiments, the electronic device210may be configured to dedicate first processing resources for executing the step810and second processing resources for executing the step820. It is contemplated that the first processing resources may be distinct from the second processing resources.

As part of the second processing pipeline, the electronic device is configured to generate graph-structure for operating the vehicle220on the road segment350. The graph-structure has nodes and edges, and where a given node is associated with a respective potential position of the vehicle220on the road segment350, and where a given edge is representative of a transition of the vehicle220between potential positions of the respective pair of nodes. The given edge is associated with a respective set of intermediate potential positions between the potential positions of the respective pair of nodes.

As part of the second processing pipeline, during the generation of the graph-structure, the electronic device210is configured to generate dynamic attributes for a given edge of the graph-structure. Broadly speaking, a given dynamic attribute is indicative of information about a moving object on the road segment350relative to a respective one of a respective set of intermediate potential positions (and/or potential positions of respective pair of nodes).

The graph-structure may be generated for operating the vehicle during a second time interval. It can be said that the second time interval determines the frequency of computation of dynamic attributes whereas the first time interval from the step810determined the frequency of computation of static attributes. It should be noted that length of the first time interval can be pre-selected based on a length of the second time interval (for example, by an operator of the electronic device210) for reducing processing resources of the electronic device for executing the first processing pipeline.

In some embodiments, the given dynamic attribute of a respective edge may be one of: a distance between a given one of a respective set of intermediate potential positions and a position of an other vehicle on the road segment, a distance between the given one of the respective set of intermediate potential positions and a position of a pedestrian on the road segment, and a distance between the given one of the respective set of intermediate potential positions and a position of a cyclist on the road segment. It is contemplated that generation of static attributes may be performed by the electronic device210asynchronously from the generation of dynamic attributes.

As part of the second processing pipeline, during the generation of the graph-structure, the electronic device210is configured to acquire from the cache memory static attributes for the given edge of the graph-structure. The static attributes for the given edge include the static attributes cached in association with the respective set of intermediate potential positions and/or potential positions of a respective pair of nodes. The given edge in the graph-structure is thus associated with the static attributes generated by the first processing pipeline and with the dynamic attributes generated by the second processing pipeline.

In further embodiments of the present technology, the graph-structure may be a first graph-structure amongst a plurality of graph-structures to be generated in a periodical manner during operation of the vehicle220. The electronic device210may be configured to use the first graph-structure for operation the vehicle220during a first time interval on the road segment350. In these embodiments, as part of the second processing pipeline, the electronic device210may be configured to generate a second graph-structure for operating the vehicle220on the road segment350during a second time interval. The second graph-structure may share the given edge with the first graph-structure. The generation of the second graph-structure comprises the electronic device210configured to generate updated dynamic attributes for the given edge. A given updated dynamic attribute may be indicative of updated information about the moving object on the road segment relative to the respective one of the respective set of intermediate potential positions (and/or potential positions of the respective pair of nodes). The generation of the second graph-structure comprises the electronic device210configured to acquiring from the cache memory the static attributes for the given edge, such that the given edge in the second graph-structure is associated with the static attributes generated by the first processing pipeline and with the updated dynamic attributes generated by the second processing pipeline.

In other embodiments, the method700may further comprise the electronic device210causing operation of the vehicle220on the road segment350based on the graph-structure. For example, the electronic device210may be configured to determine a cost of the given edge in the graph-structure based on the respective static and dynamic attributes. One or more cost criteria as known in the art may be used by the electronic device210for determining the cost. The electronic device210is also configured to determine a sequence of edges in the graph-structure representative of a potential path for the vehicle220on the road segment350. The sequence of edges includes the given edge and is associated with an acceptable total cost of edges in the sequence. The electronic device210is also configured to generate a given trajectory for the vehicle220on the road segment350based on the sequence of edges. For example, the electronic device210may be configured to generate inter alia a speed profile for the vehicle220for following the sequence of edges on the road segment350. The electronic device210is also configured to cause operation of the vehicle220for travelling on the road segment in accordance with the given trajectory.

Modifications and improvements to the above-described implementations of the present technology may become apparent to those skilled in the art. The foregoing description is intended to be exemplary rather than limiting. The scope of the present technology is therefore intended to be limited solely by the scope of the appended claims.

While the above-described implementations have been described and shown with reference to particular steps performed in a particular order, it will be understood that some of these steps may be combined, sub-divided, or re-ordered without departing from the teachings of the present technology. Accordingly, the order and grouping of the steps is not a limitation of the present technology.