Patent Description:
Automatic driving vehicles are expected to drive in dynamic traffic conditions in which the road occupation constantly changes due to the continuous movement of vehicles, people and other parties or objects on the road. In such conditions, automatic driving vehicles require ways to estimate and evaluate possible future hazards to maximize safety; with the general objective to reduce the risks for the vehicle, the passengers and other parties on the road or around the vehicle. But automatic driving vehicles require also ways to maximize the utility of the passengers, wherein maximizing utility may include maximize the likelihood that the passengers arrive at destination.

Addressing the problem of automatic driving in traffic conditions requires the fusion of at least two skills. The first skill is the perception of the obstacles on the road with their dynamic aspect, the second skill is navigation to a destination. With respect to the perception skill, initial approaches to address the perception problem were based on detecting and tracking objects using bounding boxes; but the bounding box approach fails to detect large objects, such as buildings for which no bounding box can be constructed and it fails to support information fusion from multiple sensors. In more recent years, alternative approaches based on particle filters in conjunction with dynamic occupancy grids (DOG): dynamic occupancy grid addressed some of the problems of bounding boxes by providing a natural way to fuse information and removing the need to identify bounding boxes around objects on the road. As a result, automatic vehicles may have information about the whereabouts of obstacles on the road.

With respect to the navigation skill, many successful systems and products have addressed this problem, but they all assume that roads are free of traffic. More precisely these products provide a generic direction of motion but they fail to avoid hazards on the road.

Automatic driving vehicles require a way to merge the two skills: the perception skill that detects hazards on the road and the navigation skill to reach the destination by generating trajectories that avoid hazards, minimize risks, maximize safety and still take the passengers to the desired destination.

<NPL>], presents a probabilistic grid-based approach for modeling dynamic environments. In the study, the researchers describe the environment as a spatial grid and use a hidden Markov model to represent the occupancy state and state transition probabilities of each grid cell.

<NPL>], defines the state of multiple grid cells as a random finite set that allows to model an environment as a stochastic, dynamic system with multiple obstacles observed by a stochastic measurement system.

The invention described with this application is set out in the appended set of claims.

The drawings are not necessarily to scale; emphasis is instead generally being placed upon illustrating the principles described herein. In the following description, various embodiments are described with reference to the following drawings, in which:.

The following detailed description refers to the accompanying drawings that show, by way of illustration, specific details and embodiments which are described herein may be practiced. Other aspects may be utilized and structural, logical, and electrical changes may be made without departing from the scope described herein. The various aspects described herein are not necessarily mutually exclusive, as some aspects described herein can be combined with one or more other aspects described herein to form new aspects.

The word "exemplary" is used herein to mean "serving as an example, instance, or illustration". Any embodiment or design described herein as "exemplary" is not necessarily to be construed as preferred or advantageous over other embodiments or designs.

Whereas the description, the examples, and the figures below refer to an Automatic Driving (AD) (e.g. Autonomous Driving) vehicle, it should be understood that examples of Automatic Driving vehicles may include automobiles, buses, mini buses, vans, trucks, mobile homes, vehicle trailers, motorcycles, bicycles, tricycles, moving robots, personal transporters, and drones. It should also be understood that Automatic Driving vehicles may include trains, trams, subways and more generally vehicles that are limited to move on pre-specified tracks; it should also be understood that trajectory of motion determiner disclosed applies to vehicles of any size and type.

In addition, it should be understood that the trajectory of motion determiner disclosed, as well as the examples disclosed, are not restricted to vehicles; rather, the trajectory of motion determiner may be used in a wide range of applications including security cameras that may use the trajectory of motion determiner to monitor access to a given area and or guide other vehicles in that area; traffic lights that may use the trajectory of motion determiner to monitor the traffic waiting at an intersection and/or to guide the traffic around the intersection; smart digital signage for both advertisement and information purposes that may use trajectory of motion determiner to estimate the number of impressions or to derive the most relevant content to display; traffic congestion sensors that may use the trajectory of motion determiner to estimate the traffic in a given area looking for ways to resolve the traffic congestion; speedometers that may use the trajectory of motion determiner to compute the speed of vehicles in a given area or to guide vehicles to a safe position.

<FIG> shows an exemplary vehicle (e.g. an automatic vehicle) <NUM> including a trajectory of motion determiner <NUM> to detect space occupation and determine a trajectory of motion within a predetermined region. In some embodiments, examples of space occupation may include static and dynamic objects, wherein exemplary static objects may include street lights, traffic lights, buildings on the side of the road, and exemplary dynamic objects may include pedestrians as well as other vehicles and traffic. In some embodiments, the trajectory of motion may include a plurality of velocity, acceleration, and steering angle values indicating how to drive vehicle <NUM> across the predetermined area.

The automatic driving vehicle <NUM> may also include an automotive controller <NUM> as well as various automotive components such as a steering module <NUM>, a motor <NUM>, and wheels <NUM> which may also include a braking system and a turning system neither of which are displayed.

In some embodiments, the trajectory of motion determiner <NUM> may be a stand-alone device that may not be connected with other components. In such cases, the trajectory of motion determiner <NUM> may signal to the driver of potential dangers and the way around those dangers.

In some embodiments, the trajectory of motion determiner <NUM> may be connected to automotive controller <NUM> through the exemplary connection <NUM>. The motion determiner <NUM> may transmit to the automotive controller <NUM> through connector <NUM> a trajectory of motion including a plurality of velocity, acceleration, and steering angles and/or occupancy information.

The automotive controller <NUM> may control the automotive components such as the steering module <NUM>, the motor <NUM>, and the wheels <NUM>, the braking system, not displayed in <FIG>, and other systems that are included in the vehicle, to drive the vehicle in a way that is consistent with the trajectory and the motion parameters determined by the motion determiner.

The automotive controller <NUM> may be configured to fully or partially control vehicle <NUM>. Full control may indicate that the automotive controller <NUM> may be configured to control the behavior of all other automotive components. Partial control may indicate that the automotive controller <NUM> may be configured to control only some automotive components, but not others which may be under the control of a human driver. In some exemplary embodiments of partial control, the automotive controller <NUM> may be configured to control only the vehicle speed, but not the steering. In some embodiments of vehicle <NUM>, partial control may indicate that the automotive controller <NUM> may be configured to control all automotive components, but only in some situations, for example, control the vehicle on the highway but not on other roads where a human driver should take control. In other embodiments, partial control may indicate any combination of the embodiments above.

In some embodiments, the trajectory of motion determiner <NUM>, and the automotive controller <NUM> may be distinct components. In some embodiments of vehicle <NUM>, the trajectory of motion determiner <NUM>, and the automotive controller <NUM> may be integrated into a single device. In some embodiments the perception device <NUM>, and the automotive controller <NUM> may be partially integrated. In some embodiments, some or all of the components of the trajectory of motion determiner <NUM> may be integrated within the automotive controller <NUM>.

<FIG> also shows an exemplary connection scheme across the different components. The connectors <NUM> may couple the automotive controller <NUM> with the steering module <NUM>, the motor <NUM>, and the wheels <NUM>, and the like. The connectors <NUM> may be configured in such a way that the automotive controller <NUM> may indicate to the steering module <NUM>, the motor <NUM>, and the wheels <NUM> how to drive the vehicle, and the steering module <NUM>, the motor <NUM>, and the wheels <NUM> may indicate odometric information, positioning information and vehicle status information back to the steering module <NUM>.

The connectors <NUM> couple the steering module <NUM> to a turning system (not shown) of the wheels <NUM> to control the driving direction of the vehicle. The connectors <NUM> may be configured in such a way that the steering module <NUM> may indicate to the actuating components, such as the turning system (not shown) of the wheels <NUM> how to drive the vehicle, and the actuating components, such as turning system (not shown) of the wheels <NUM> may indicate odometric information, positioning information and vehicle status information back to the steering module <NUM>.

The connectors <NUM>, <NUM> and <NUM> may be implemented as a wired connection or a wireless connection. Any kind of communication protocol including vehicle bus networks such as Controller Area Network (CAN), Local Interconnected Network (LIN) bus, FlexRay, Media Oriented System Transport (MOST), and Automotive Ethernet, as well as cryptographic and non-cryptographic variations, may be used for a communication between two respective components. Furthermore, the interaction between the components may be implemented as cyclic broadcast or multicast communication or a remote function call or an API call across software modules or in any other way that allows transfer of information between components.

In the exemplary embodiment displayed in <FIG>, vehicle <NUM> may be an automobile, and possibly an automatic driving automobile, but in other embodiments, vehicle <NUM> may be an automatic driving vehicle <NUM>, e.g. an autonomous driving vehicle, an autonomous drone, an autonomous plane or any other flying object, an autonomous bike, trike, or the like. The autonomous vehicle <NUM> may also be any kind of robot or moving hardware agent. Furthermore, it may be to be noted that the vehicle <NUM> does not necessarily need to be a fully autonomous vehicle, but can also be a partially autonomous vehicle or a vehicle in which implements the trajectory of motion determiner as part of the driver assistance systems.

In some embodiments, the vehicle <NUM> may be replaced with any device requiring a trajectory of motion determiner in a given area, such as surveillance drones which may monitor a specific location.

<FIG> shows a trajectory of motion determiner <NUM> that may determine a trajectory of motion across the predetermined region. The trajectory of motion determiner <NUM> may be functionally equivalent to the trajectory of motion determiner <NUM>.

In some embodiments, the trajectory of motion determiner <NUM> may include at least one sensor <NUM>, wherein the at least one sensor <NUM> may include Lidar sensors, Radar sensors, visual sensors, such as monocameras, or any other type of sensor.

In some embodiments, the sensors reach may determine the predetermined region wherein the predetermined region may be limited to the region within which at last one of the sensors may provide information. In other embodiments, the determination of the predetermined region may be established on the bases of other considerations.

The trajectory of motion determiner <NUM> may also include an occupancy hypothesis determiner <NUM> that may be configured to determine an occupancy hypothesis of the predetermined region. In some embodiments, the occupancy hypothesis determiner <NUM>, may identify sub-regions of the predetermined region that may be occupied by static objects, such as buildings, that may persist to be occupied, and sub-regions of the predetermined region that may be occupied by dynamic objects such as vehicles. , that may move away removing their occupation of the sub-region.

The occupancy hypothesis determiner <NUM> may also identify non-occupied sub-regions, in other words sub-regions that may be free of obstacles and that may be utilized by vehicle <NUM> to travel across the predetermined region.

The occupancy hypothesis determiner <NUM> may make its determination on the bases of information from sensors, such as the at least one sensor <NUM> received through the at least one connector <NUM>. In some embodiments. , the occupancy hypothesis determiner <NUM> may also perform sensor fusion; therefore, the occupancy hypothesis may be the result of the merging different types of information coming from different sensors.

The trajectory of motion determiner <NUM> may also include a utility value determiner <NUM> configured to determine a utility value of all sub-regions in the predetermined region. Specifically, the utility value determiner <NUM> may divide the predetermined region into sub-regions on the bases of some utility criteria wherein each some region of the predetermined region may be associated with one utility value.

In some embodiments, the utility value determiner <NUM> may divide the predetermined region into sub-regions on the bases of the route to its intended destination, wherein the sub-regions that are in the direction of the intended destination may receive a higher utility value than sub-regions that are in other directions.

In order to assign a utility to the sub-regions, the utility value determiner <NUM> may require as input an indication of the direction to the intended destination. Such indication of the direction of the intended destination, may be provided by a navigation system <NUM> through connector <NUM>. The navigator system may be any navigation system with the functionalities of determining a route from a starting point to a destination and the additional functionality to provide local directions to indicate the way to reach the destination.

The trajectory of motion determiner <NUM> may also include a profile of motion indicator <NUM> configured to indicate the profile of motion of vehicle <NUM>, wherein the profile of motion may indicate the values of motion parameters related the movements of vehicle <NUM> in a predetermined time interval.

In some embodiments, the motion parameters may include a velocity profile, an acceleration profile and a steering angle profile.

An exemplary profile of motion may indicate that in a predetermined time interval of <NUM> minutes, vehicle <NUM> turned in the left direction with a turning angle that progressively ranged from <NUM> to <NUM> grades, a velocity that progressively decreased from <NUM> to <NUM>/h with a constant negative acceleration.

The profile of motion indicator <NUM> may receive data about the vehicle's motion parameters from one or more odometry sensors <NUM> through connector <NUM>. In some embodiments, the odometry sensors may include an Inertial Measurement Unit (IMU) on the vehicle; in some embodiments, the odometry sensors may include sensors measuring the velocity of the wheels, and/or sensor measuring the acceleration produced by the engine and/or sensors measuring the steering angle of the wheels; in some embodiments, the odometry sensors may include other odometry estimates such as estimates with respect to landmarks positions or other types of estimates.

The trajectory of motion selector <NUM> may receive through connector <NUM> an occupancy hypothesis that may indicate the sub-regions of the predetermined region that are occupied by either static objects such as buildings, and dynamic objects such as vehicles. The occupancy hypothesis may also include indications of unoccupied sub-regions on which the vehicle may be able to drive.

In addition, the trajectory of motion selector <NUM> may receive through connector <NUM> an indication of the utility of the sub-regions of the predetermined region. By combining the unoccupied sub-regions and the utility values of the sub-regions of the predetermined region, the trajectory of motion selector <NUM> may determine the non-occupied sub-regions with higher utility, these sub-regions are the preferred sub-regions to be crossed by a trajectory of motion. More generally the combination of the unoccupied sub-regions and the utility values of the sub-regions of the predetermined region may result in a scoring of the unoccupied sub-regions indicating alternative options for a trajectory and scoring the alternatives with respect to the utility measure.

Finally, the trajectory of motion selector <NUM> may receive through connector <NUM> an indication of the profile of motion of the vehicle <NUM>. By combining unoccupied regions scored with the utility function and the motion profile of vehicle <NUM>, the trajectory of motion selector <NUM> may select a trajectory with high utility while controlling steering angles, velocities and accelerations along the trajectory.

The output of the trajectory of motion selector <NUM> may include a trajectory of motion and a plurality of position values, velocity values, acceleration values and steering angle values indicating how to drive along the trajectory. These outputs may be transmitted through connector <NUM> to other components. In some embodiments, connector <NUM> may be functionally equivalent to connector <NUM>, in such embodiments, the trajectory of motion and the velocity values, acceleration values and steering angle values may result in indications to the automotive controller <NUM> that nay use them to control the behavior of vehicle <NUM>.

In some embodiments of the trajectory of motion determiner <NUM>, the utility value determiner <NUM> or the profile of motion indicator <NUM> may be missing providing alternative versions of the trajectory of motion determiner <NUM>.

In some embodiments, the trajectory of motion determiner <NUM> may include only the occupancy hypothesis determiner <NUM> and the profile of motion indicator <NUM>. In such embodiments, the direction of motion may have to be determined outside the trajectory of motion determiner <NUM>. In some of such embodiments, the driver may be responsible for steering the vehicle, or at least indicating the direction of motion to the vehicle <NUM>.

In some embodiments, the trajectory of motion determiner <NUM> may include only the occupancy hypothesis determiner <NUM> and the utility value determiner <NUM>. In such embodiments, the profile of motion may have to be determined outside the trajectory of motion determiner <NUM>. In some of such embodiments, the driver may be responsible for determining the velocity and acceleration of the vehicle, while the trajectory of motion determiner <NUM> may be responsible for the direction of motion of the vehicle <NUM>.

In some embodiments, the trajectory of motion determiner <NUM> may be a single component including all sensors and IMU sensors; in other embodiments, the trajectory of motion determiner <NUM> may be distributed across the vehicle <NUM>, wherein each component may be placed in the most appropriate place to perform its tasks. In some embodiments, the connectors <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> may be implemented as a wired connection or a wireless connection. Any kind of communication protocol including vehicle bus networks such as Controller Area Network (CAN), Local Interconnected Network (LIN) bus, FlexRay, Media Oriented System Transport (MOST), and Automotive Ethernet, as well as cryptographic and non-cryptographic variations, may be used for a communication between two respective components. Furthermore, the interaction between the components may be implemented as cyclic broadcast or multicast communication or a remote function call or an API call across software modules or in any other way that allows transfer of information between components.

<FIG> shows an exemplary urban scene <NUM> that may indicate the road in front of vehicle <NUM>. The urban scene <NUM> may include a first wall <NUM>, a second wall <NUM>, a tree <NUM> in front of the second wall <NUM>, a first sidewalk <NUM>, a second sidewalk <NUM>, an object <NUM> on the first sidewalk and a vehicle <NUM>. In addition, in the urban scene <NUM> signs <NUM> and <NUM>, may indicate additional objects, such as exemplary walls while the signs <NUM> and <NUM> may indicate two additional sidewalks; finally, the urban scene <NUM> may represent an intersection delimited by walls indicated by <NUM>, <NUM>, <NUM>, and <NUM>.

The urban scene <NUM>, <FIG> may also show a sample of a plurality of sensor readings represented by the dots <NUM>, <NUM>, <NUM>, <NUM>, <NUM>. The sensor readings may have been detected by one or more sensors functionally equivalent to the at least one sensor <NUM>. The sensor readings may relate to some of the objects in the urban scene <NUM>. Each sensor reading may indicate the presence of an object in the predetermined region. As a way of example, sensor reading <NUM> may indicate the presence of the first wall <NUM>, sensor reading <NUM> may indicate the presence of the second wall <NUM>, sensor reading <NUM> may indicate the presence of the object <NUM>, sensor reading <NUM> may indicate the presence of the tree <NUM> and sensor reading <NUM> may indicate the presence of the vehicle <NUM>.

Each sensor reading may also provide additional information about the objects detected such as velocity estimates or object type estimates. As a way of example, sensor reading <NUM> may indicate the distance from vehicle <NUM>, the velocity of vehicle <NUM>, in some cases the type of the object detected, such as for example that vehicle <NUM> is a car.

The sensor readings may be transmitted from one or more sensors, for example the at least one sensor <NUM>, to an occupancy hypothesis determiner that may be configured to determine an occupancy hypothesis of the predetermined region wherein such determination may depend on the sensor readings received from the sensors.

In some embodiments, the occupancy hypothesis may be a dynamic occupancy grid (DOG) wherein the dynamic occupancy grid may provide a way to model the space in the predetermined region wherein sensor readings are transformed in particles that are placed in the DOG and then abstracted to recognize free space, static obstacles, and dynamic, i.e. moving, objects. In some embodiments, the dynamic occupancy grid may be interpreted as a map of the predetermined region representing both the static features such as walls, and temporary barriers, and dynamic features such as moving vehicles.

<FIG> shows an exemplary dynamic occupancy grid <NUM> including a plurality of grid cells <NUM>. Each grid cell <NUM> may be framed by respective grid cell frame lines <NUM>. In some embodiments, the grid cells may be square or rectangular, in other embodiments grid cells may assume other shapes.

In some embodiments, the dynamic occupancy grid may provide a representation of the predetermined region, wherein the predetermined region may comprise the area of all the cells that are part of the grid. In some embodiments, the predetermined region may be contiguous: in such embodiments, cells may be placed next to each other, as in the case of grid <NUM>, in other embodiments the dynamic occupancy grid may be fragmented to capture special requirements. In some embodiments, each grid cell may represent a sub-region of the predetermined region, in other embodiments, clusters of cells may represent sub-regions of the predetermined region.

The size of the grid cells may vary: exemplary values for the grid cells size may range from a size of a few square centimeters, to a size of a few squared meters. In some embodiments, smaller grid cells may tend to result in higher representation resolution. In some exemplary embodiments, the dynamic occupancy grid may have cells of different sizes wherein the grid cells may be smaller in some areas of the grid, which may represent sub-regions of the predetermined region for which a higher representation resolution is required, and bigger in other areas for which a lower representation resolution may be required.

In some exemplary embodiments vehicle <NUM> may be placed in the center of the dynamic occupancy grid, and therefore at the center of the predetermined area. The cells closer to vehicle <NUM> may be smaller than the cells in relation to the cells at the edge of the dynamic occupancy grid since less resolution is required closer to the vehicle to better control its movements. In other exemplary embodiments, the cells closer to the front and the sides of the vehicle may be smaller than the cells behind the vehicle.

The predetermined region of a dynamic occupancy grid may be a region around the vehicle <NUM>. In some embodiments, the vehicle <NUM> may be positioned in the center of the occupancy grid and the predetermined region may be a region equally distributed around the vehicle. In other embodiments, vehicle <NUM> may be positioned at the side of the dynamic occupancy grid, or equivalently at the side of the predetermined region, to accommodate the requirement that more information may be required on one side of the vehicle. In some embodiments, vehicle <NUM> may be outside the dynamic occupancy grid. In some embodiments, the dynamic occupancy grid may move with vehicle <NUM>.

Grid cells may be associated with particles, wherein each particle may represent one or more sensor readings, such as the exemplary sensor readings <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, that may have detected objects present in the area represented by the grid cell. Through the placement of particles, a dynamic occupancy grid may provide information about the location of objects within the predetermined region. A dynamic occupancy grid may be thought as a dynamic map of the predetermined region, alternatively a dynamic occupancy grid may be thought as providing an occupancy hypothesis of the predetermined region.

Signs <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> may represent particles that may be positioned in the occupancy grid <NUM>. As a way of example, the particle <NUM> may have been generated from the information associated with sensor reading <NUM> and it may represent part of the first wall <NUM> in the dynamic occupancy grid; particle <NUM> may have been generated from the information associated to the sensor reading <NUM> and it may represent part of the second wall <NUM>; the particle <NUM> may have been generated from the information associated to the pixel <NUM> and it may represent part of the vehicle <NUM>.

In some embodiments, the particles indicated by <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> may represent sensors readings detected by different sensors, nevertheless they all provide evidence of obstacles that may occupy the predetermined region. By transforming all sensors readings in particles dynamic occupancy grids may provide a sensor fusion function.

In some embodiments, objects such as the first wall, the second wall and the vehicle, may be represented by a plurality of particles. In some embodiments, such plurality of particles may comprise a large number of particles. In some embodiments, the number of particles generated may depend on the quality of the sensor, wherein high-resolution sensors may generate a larger number of particles; the number of particles may also depend on resource considerations wherein a larger number of particles may require a larger amount of resources; finally, the number of particles may depend on the resolution required, wherein a larger number of particles may lead to a higher resolution.

Particles may also be associated with a velocity which may be represented by a direction of motion and by a speed value. Particles associated with a non-zero velocity may be indicated as dynamic particles, while particles associate with zero velocity may be indicated as static particles. As a way of example, particle <NUM>, representing part of the vehicle <NUM>, may be a dynamic particle with non-zero velocity in the direction indicated by arrow <NUM>; while particles <NUM> and <NUM>, both of which represent parts of walls may be static particles with zero velocity.

In addition to particles, dynamic occupancy grids may also associate to each cell a single occupancy hypothesis wherein each single occupancy hypothesis may provide an indication of the level of occupation of the associated cell. Each single occupancy hypothesis may provide additional information such as the cell velocity, or the type of occupation. In some embodiments, a single occupancy hypothesis may also provide a measure of the likelihood, or of the belief, that the cell is occupied, and a measure of the velocity associated with the occupation of the cell.

The shape <NUM> may represent an exemplary single occupancy hypothesis associated to cell <NUM>, wherein a single occupancy hypothesis may provide an indication of the level of occupation of a cell, of the cell velocity, and of the type of occupation. The exemplary cell <NUM> may include particles that, like particle <NUM>, may refer to wall <NUM>, therefore most or all particles in the cell may have <NUM> or near <NUM> velocities. As a consequence, the single occupancy hypothesis <NUM> may indicate that the corresponding cell may have <NUM> velocity, in other words that the cell is static. Similarly, shape <NUM> may represent an exemplary single occupancy hypothesis for cell <NUM>. Cell <NUM> may include particles that, like particle <NUM>, may refer to vehicle <NUM>, therefore most or all particles cell <NUM> may be dynamic reflecting the velocity of vehicle <NUM>. The arrow <NUM> may indicate the direction of motion associated with the non-zero velocity of the single occupancy hypothesis <NUM>.

In some embodiments, a single occupancy hypothesis, such as single occupancy hypothesis <NUM> and <NUM>, may be determined using the belief mass function, wherein the belief mass of occupation of a cell may be defined as the proportion of particles in the cell with respect to all particles in the dynamic occupancy grid. The belief mass of the velocity may be computed from the distribution of velocities associated with the particles in the cell.

In some embodiments, the belief mass function may indicate occupation information specifying whether the occupation of the corresponding cell is static or dynamic, or free space or whether the occupation information is unknown, possibly because other objects prevent sensors for reading the occupation in those cells. Using the Dempster-Shafer theory of evidence the belief mass function may be reduced to a <NUM>Θ frame of discernment, wherein <MAT> wherein.

Given the frame of discernment as described in (<NUM>), in some embodiments, the belief mass function used to determine the single occupancy hypothesis may be determined in accordance with the following formula: <MAT> wherein.

Formula (<NUM>) may provide a way to determine the belief mass of occupation of cells on the bases of the position value assigned to the particles, while keeping into account technical differences between the sensors.

A formula analogous to formula (<NUM>) may indicate how to determine the mass belief for other cases as well as for other information such as velocity associated with a cell.

In some embodiments, the degree of belief that the grid cell Ci is occupied may be computed by the belief function that may be analogous to the following formula (<NUM>) <MAT> wherein:.

In formula (<NUM>), the Gaussian function acts as a discount factor wherein the measurements ztj that are further from xi provide a reduced contribution to the occupancy of grid cell i; furthermore the use of the maxj function selects the sensor j measurement that contributes the most to a grid cell, removing the contribution of all the others. Finally, it should be observed that formula (<NUM>) returns values that are included between <NUM> and <NUM>. In other words, the contribution of a sensor information value to the degree of belief of occupancy of the grid cell i substantially decreases with an increase of a distance of the location of the object detected by the sensor from xi.

In some embodiments, the value σ in formula (<NUM>) may be related to the standard deviation of the values of x with respect to z. In such cases, msi({S, D}) may have mathematical properties of the probabilistic normal distribution.

<FIG> shows an embodiment of an occupancy hypothesis determiner <NUM> that may be functionally equivalent to the occupancy hypothesis determiner <NUM>.

In <FIG>, signs <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> represent processes; while signs <NUM>, <NUM><NUM><NUM> and <NUM> represent data. The interpretation of the connectors changes consequently. Connectors connecting processes may represent data flow and/or control flow; connectors connecting processes and data may indicate input/output relations; connectors connecting data may indicate data transformations which in some embodiments may simply be data identity or data assignment.

In <FIG>, the sign <NUM> may represent at least one sensor that may be functionally equivalent to the at least one sensor <NUM>. Connector <NUM> may represent the input of the occupancy hypothesis determiner <NUM>. Connector <NUM> may be functionally equivalent to connector <NUM>.

In <NUM>, the occupancy hypothesis determiner <NUM> may compute a sensors-based dynamic occupancy grid which may be functionally equivalent to the exemplary occupancy grid <NUM>. In some embodiments, the determination of the sensors-based dynamic occupancy grid may also involve the determination of the belief masses corresponding to each cell of the sensors-based dynamic occupancy grid, wherein the determination of the belief masses may be performed in accordance with formula (<NUM>).

In some embodiments, sensors may produce faulty readings which may result in erroneous particles to be added to the dynamic occupancy grid. Faulty particles may need to be removed from the dynamic occupancy grid to improve its accuracy.

The occupancy hypothesis determiner <NUM> may improve the dynamic occupancy grid through two filter processes. The first filter <NUM> may be a particle filter, the second filter <NUM> may be based on the Dempster Shafer theory of evidence.

The particle filter <NUM> may be defined as a process wherein a first dynamic occupancy grid <NUM> may be transmitted through connector <NUM> to a mapping process <NUM> to generate a second updated, dynamic occupancy grid <NUM> transmitted through connector <NUM>. Specifically, the generation of the second updated dynamic occupancy grid <NUM> involves the injection in the first dynamic occupancy grid <NUM> of additional particles that may be coming from the sensors-based dynamic occupancy grid <NUM> transmitted to the particle filter through connector <NUM> and a projection and a re-sampling process to filter out particles that may result from sensor errors. The connector <NUM> may indicate that the second dynamic occupancy grid may become the first dynamic occupancy grid of the next iteration of the process. In some embodiments, connector <NUM> may be implemented as a variable assignment.

The result of the particle filtering, indicated by connector <NUM>, may be an evidence-based dynamic occupancy grid <NUM>, wherein the evidence particle map <NUM> may be a dynamic occupancy grid wherein each cell of dynamic occupancy grid is associated with a mass belief of the type of occupation of the cell in the dynamic occupancy grid.

In some embodiments, the evidence-based dynamic occupancy grid <NUM> may be functionally equivalent to the second updated dynamic occupancy grid <NUM>.

In some embodiments, the evidence-based dynamic occupancy grid <NUM> may differ from the second updated dynamic occupancy grid <NUM> in that the values of each cell of the dynamic occupancy grid may indicate the belief masses associated with the cell determined in accord with formula (<NUM>).

The evidence-based dynamic occupancy grid <NUM> may contain incorrect belief estimates that may be due to incorrect sensor readings. In some embodiments, the estimates in the evidence-based dynamic occupancy grid <NUM> may be further improved by the Dempster Shafer filter <NUM> based on a Dempster Shafer map process <NUM>.

The Dempster Shafer map process <NUM> may transform a first evidence-based dynamic occupancy grid <NUM> received through connector <NUM>, to output a second evidence-based dynamic occupancy grid <NUM> as indicated by connector <NUM> through the inclusion of information from the evidence-based dynamic occupancy grid <NUM> received through connector <NUM>. The second evidence-based dynamic occupancy grid <NUM> may be the output of filter <NUM> and of the occupancy hypothesis determiner <NUM>.

The connector <NUM> may indicate that the second evidence-based dynamic occupancy grid <NUM> may become the first evidence-based dynamic occupancy grid <NUM> of the next iteration of the process. In some embodiments, connector <NUM> may be implemented as a variable assignment.

In some embodiments, the Dempster Shafer map process <NUM> may be defined according to the Dempster-Shafer theory of evidence, wherein the frame of discernment may be defined according to formulae (<NUM>).

The Dempster Shafer map process <NUM> may be based on the following formulae (<NUM>). <MAT> wherein.

Formulae (<NUM>) assumes that from time t - <NUM> to t all dynamic objects, such as vehicles, represented in the first evidence-based dynamic occupancy grid by the mass belief mt-<NUM> (D) may have moved away and the corresponding space have been freed. Therefore, there is no more evidence of any dynamic object.

Formulae (<NUM>) below may specify the belief masses of the second evidence-based dynamic occupancy grid wherein the evidence for dynamic objects comes from the evidence-based dynamic occupancy grid <NUM> while the other belief masses are updated accordingly. <MAT> wherein.

The output connector <NUM>, which may be functionally equivalent to connector <NUM> in <FIG>, may indicate that at each time instance t the second evidence-based dynamic occupancy grid may be transmitted to other components as the estimate of the occupation in the predetermined area. In some embodiments, the second evidence-based dynamic occupancy grid may indicate the occupancy around vehicle <NUM>.

<FIG> shows an exemplary utility value determination <NUM> associated with exemplary navigation indications <NUM>, <NUM>, <NUM>, indicating alternative directions to cross an exemplary intersection.

The exemplary utility value determination <NUM> may indicate that the exemplary intersection is divided into <NUM> sub-regions: a first sub-region <NUM>, which may also be the sub-region from where vehicle <NUM> is coming from; a second sub-region <NUM> which may also be the sub-region indicated by the navigation system as the best direction of motion, as indicated by the arrow <NUM>; a third sub-region <NUM> which may also be the sub-region indicated by the navigation system as an alternative direction of motion as indicated by the dotted arrow <NUM>; and a fourth sub-region <NUM> which may also be the sub-region indicated by the navigation system as a wrong direction of motion as indicated by the cross sign <NUM>.

In some embodiments, navigation systems may not indicate wrong directions but rather indicate that there are no alternative directions of motion crossing the specific sub-region. Such indication may be interpreted by a utility value determiner equivalently to the cross sign indication <NUM>.

The utility value determination <NUM> may have been determined by a utility value determiner, functionally equivalent to the utility value determiner <NUM>, wherein the utility value determiner may assign the higher utility value to region <NUM> since crossing region <NUM> may lead directly towards the destination, as indicated the arrow <NUM> The utility value determiner may assign a lower utility value to region <NUM> since crossing region <NUM> may still lead to the destination, as indicated by the dotted arrow <NUM>, but it may involve a detour; as such it may not be the preferred route. The utility value determiner may assign the lowest utility value, and possibly a negative utility value, to region <NUM> since crossing region <NUM> may not lead to the destination but rather in the opposite direction.

<FIG> shows a diagram <NUM> illustrating an exemplary direction of motion and an exemplary motion profile <NUM>. In diagram <NUM>, the signs <NUM>, <NUM>, <NUM>, and <NUM> show the boundaries of statically or dynamically occupied space, such as the boundaries of exemplary buildings, the space between the signs <NUM>, <NUM>, <NUM>, and <NUM>, indicated as <NUM>, <NUM>, <NUM>, <NUM>, may be unoccupied space on which may indicate an exemplary intersection. The line <NUM> may indicate the trajectory traveled by the exemplary vehicle <NUM> while crossing the intersection. The lines <NUM>, <NUM>, <NUM> indicated by the labels A, B and C respectively, may indicate points along the trajectory <NUM>.

Diagram <NUM> shows an exemplary motion profile including an exemplary velocity profile illustrated in diagram <NUM> indicating velocity values, an exemplary an acceleration profile illustrated in diagram <NUM> indicating the acceleration values, and an exemplary a steering angle profile illustrated in diagram <NUM> indicating the steering angle values.

The velocity profile in <NUM> is illustrated by the curve <NUM> representing the velocity with respect to time, wherein the velocity values are represented by the axis <NUM> labeled "v" and the time is represented by the axis <NUM> labeled as "t". The point <NUM> labeled as "A" may correspond to point <NUM> in diagram <NUM>; the point <NUM> labeled as "B" may correspond to point <NUM> in diagram <NUM>; the point <NUM> labeled as "C" may correspond to point <NUM> in diagram <NUM>. The velocity profile in <NUM> shows that the velocity decreased as the vehicle entered a curve in point A <NUM>, reached a minimum value as the vehicle reached point B <NUM> and increased again until the vehicle reached point C <NUM> and then stabilized on a constant velocity.

The acceleration profile in <NUM> is illustrated by the curve <NUM> representing the acceleration with respect to time, wherein the acceleration values are represented by the axis <NUM> labeled "a" and the time is represented by the axis <NUM> labeled as "t". The point <NUM> labeled as "A" may correspond to point <NUM> in diagram <NUM>; the point <NUM> labeled as "B" may correspond to point <NUM> in diagram <NUM>; the point <NUM> labeled as "C" may correspond to point <NUM> in diagram <NUM>. The acceleration profile in <NUM> shows that the acceleration decreased to negative values as the vehicle entered a curve in point A <NUM> indicating that the vehicle is breaking, reached a minimum value and then increased reaching the <NUM> value as the vehicle reached point B <NUM> indicating that the vehicle is no longer breaking, and then increased reaching a maximum value and the decreased again until the vehicle reached point C, <NUM>, and then stabilized around a value of <NUM> acceleration indicating constant velocity.

The steering angle profile in <NUM> is illustrated by the curve <NUM> representing the steering angle with respect to time, wherein the steering angle values are represented by the axis <NUM> labeled "sa" and the time is represented by the axis <NUM> labeled as "t". The point <NUM> labeled as "A" may correspond to point <NUM> in diagram <NUM>; the point <NUM> labeled as "B" may correspond to point <NUM> in diagram <NUM>; the point <NUM> labeled as "C" may correspond to point <NUM> in diagram <NUM>. The steering angle profile in <NUM> shows that the steering angle increased as the vehicle entered a curve in point A <NUM>, reached a maximum steering angle value in point B <NUM>, and then decreased the steering angle reaching a minimum value of <NUM> when the vehicle reached point C <NUM> wherein <NUM> indicates that the vehicle drives in a straight line.

In the embodiment described above, the velocity, acceleration and steering angle profiles were represented using charts in Cartesian coordinates, in other embodiments other representations may be used. In some embodiments, the representation of the motion parameter profiles may be based on a representation of the direction of motion and the motion parameters may be represented as color variations overlapped on the trace sign.

<FIG> shows an exemplary trajectory of motion selector <NUM> that may be functionally equivalent to <NUM>. The trajectory of motion selector <NUM> may receive as inputs, as shown by the arrows <NUM>, a dynamic occupancy grid <NUM>, that may be functionally equivalent to the dynamic occupancy grid <NUM>; a utility value determination <NUM> that may be functionally equivalent to the utility value determination <NUM> indicating a utility assignment to all sub-regions in the predetermined region received from a utility value determiner that may be functionally equivalent to <NUM>; a plurality of motion parameters profiles <NUM> that may be functionally equivalent to the motion parameters profiles <NUM>, and an indication of the previous direction of motion that may be functionally equivalent to the direction of motion <NUM>.

The output of the trajectory of motion selector <NUM> is indicated by the arrows <NUM> and it may include a trajectory of motion <NUM> and a plurality of velocity values, acceleration values and steering angle values <NUM> indicating the trajectory and constraints on how to drive along the trajectory <NUM>.

The trajectory of motion <NUM> generated by the trajectory of motion selector <NUM> may tend to maximize the utility of the trajectory wherein the utility of the trajectory may depend on the utility associated with the sub-regions that are crossed by the trajectory. In some exemplary embodiments, the utility of a trajectory may be defined as the sum of the utilities of the sub-regions crossed by the trajectory.

In some embodiments, the trajectory of motion selector <NUM> may be a neural network which may encode in the input layer <NUM> the inputs of the trajectory of motion selector <NUM>, wherein in some embodiments the inputs may be encoded as images.

In the embodiments, in which the trajectory of motion selector <NUM> is a neural network, the outputs of the trajectory of motion selector may be encoded in the output layer of the neural network, wherein in some embodiments the outputs may be encoded as images in the output layer.

In some embodiments, the trajectory of motion selector <NUM> may be a fully convolutional neural network <NUM> which in addition to the input layer <NUM> and the output layer <NUM> may include sets of convolution layers <NUM>, <NUM>, <NUM>, <NUM>, pooling layers <NUM> and <NUM> max unpooling layers <NUM> and <NUM>, and at least one softmax layer <NUM>.

In some embodiments, the trajectory of motion selector <NUM> may also contain recurrent layers, not shown, which may be configured as Long Short-Term Memory layers.

<FIG> shows a method to determine a trajectory of motion of a vehicle in a predetermined region, wherein the predetermined region comprises a plurality of sub-regions.

In <NUM>, an occupancy hypothesis of the predetermined region is determined, wherein the occupancy hypothesis indicates occupied sub-regions of the plurality of sub-regions and non-occupied sub-regions of the plurality of sub-regions.

In <NUM>, a utility value of each sub-region of the non-occupied sub-regions is determined.

In <NUM>, a utility value of the trajectory of motion is determined, wherein the trajectory of motion crosses at least one sub-region of the non-occupied sub-regions, wherein the utility value of the trajectory of motion is determined according to a function of the utility values of the least one sub-region of the non-occupied sub-regions crossed by the trajectory of motion; wherein the utility value of each sub-region of the non-occupied sub-regions is further determined according to an intended direction of motion of the vehicle.

In <NUM>, a trajectory of motion to maximize the utility value of the trajectory of motion is selected.

<FIG>, shows a non-transient computer readable medium <NUM> storing a computer program in a data and instructions storage <NUM> which, when executed by a processor <NUM>, implements a method <NUM> to determine a trajectory of motion in a predetermined region.

The non-transient computer-readable medium <NUM> may include a plurality of processors <NUM> and/or one or a plurality of controllers, now shown. Each processor or controller may thus be or include an analog circuit, digital circuit, mixed-signal circuit, logic circuit, processor, microprocessor, Central Processing Unit (CPU), Graphics Processing Unit (GPU), Digital Signal Processor (DSP), Field Programmable Gate Array (FPGA), integrated circuit, Application Specific Integrated Circuit (ASIC), etc., or any combination thereof. Any other kind of implementation of the respective functions, which will be described below in further detail, may also be understood as a processor, controller, or logic circuit. It may be understood that any two (or more) of the processors, controllers, or logic circuits detailed herein may be realized as a single entity with equivalent functionality or the like, and conversely that any single processor, controller, or logic circuit detailed herein may be realized as two (or more) separate entities with equivalent functionality or the like.

Claim 1:
A method of determining a trajectory of motion of a vehicle (<NUM>) in a predetermined region, wherein the predetermined region comprises a plurality of sub-regions, the method being executed by one or more processors (<NUM>), the method comprising
determining (<NUM>) an occupancy hypothesis of the predetermined region, wherein the occupancy hypothesis indicates occupied sub-regions of the plurality of sub-regions and non-occupied sub-regions of the plurality of sub-regions;
determining (<NUM>) a utility value for each sub-region of the predetermined region;
determining (<NUM>) the trajectory of motion which crosses at least one sub-region of the non-occupied sub-regions, based on a function of the utility values of the least one sub-region of the non-occupied sub-regions crossed by the trajectory of motion and by maximizing a utility of motion of the vehicle (<NUM>), wherein the utility of motion of the vehicle (<NUM>) is indicated by a function of the utility values of the sub-regions crossed by the trajectory of motion; wherein the utility value of each sub-region of the non-occupied sub-regions is further determined according to an intended direction of motion of the vehicle (<NUM>).