Facilitating vehicle driving and self-driving

• US 9,645,577 B1
• Filed: 03/23/2016
• Issued: 05/09/2017
• Est. Priority Date: 03/23/2016
• Status: Active Grant

• Current Assignee: Motional AD, LLC (Aptiv PLC)
• Original Assignee: nuTonomy, Inc. (BorgWarner Incorporated)
• Inventors: Frazzoli, Emilio, Iagnemma, Karl
• Primary Examiner(s): Ortiz, Angela
• Assistant Examiner(s): EVANS, GARRETT F
• Application Number:
  US15/078,143
• Time in Patent Office: 412 Days
• Field of Search: None
• CPC Class Codes: B60W 2050/0013 Optimal controllers
• CPC Class Codes: B60W 2050/146 Display means
• CPC Class Codes: B60W 2420/40 Photo, light or radio wave sensitive means, e.g. infrared sensors
• CPC Class Codes: B60W 2420/403 Image sensing, e.g. optical camera
• CPC Class Codes: B60W 2420/408 Radar; Laser, e.g. lidar
• CPC Class Codes: B60W 2420/54 Audio sensitive means, e.g. ultrasound
• CPC Class Codes: B60W 2510/18 Braking system
• CPC Class Codes: B60W 2510/20 Steering systems
• CPC Class Codes: B60W 2540/18 Steering angle
• CPC Class Codes: B60W 2552/00 Input parameters relating to infrastructure
• CPC Class Codes: B60W 2552/50 Barriers
• CPC Class Codes: B60W 2552/53 Road markings, e.g. lane marker or crosswalk
• CPC Class Codes: B60W 2554/00 Input parameters relating to objects
• CPC Class Codes: B60W 2554/20 Static objects
• CPC Class Codes: B60W 2554/4026 Cycles
• CPC Class Codes: B60W 2554/4029 Pedestrians
• CPC Class Codes: B60W 2554/4041 Position
• CPC Class Codes: B60W 2554/406 Traffic density
• CPC Class Codes: B60W 2554/60 Traversable objects, e.g. speed bumps or curbs
• CPC Class Codes: B60W 2554/802 Longitudinal distance
• CPC Class Codes: B60W 2554/804 : Relative longitudinal speed
• CPC Class Codes: B60W 2555/20 : Ambient conditions, e.g. wind or rain
• CPC Class Codes: B60W 2555/60 : Traffic rules, e.g. speed limits or right of way
• CPC Class Codes: B60W 2556/65 : Data transmitted between vehicles
• CPC Class Codes: B60W 2710/18 : Braking system
• CPC Class Codes: B60W 2710/20 : Steering systems
• CPC Class Codes: B60W 2756/10 : Involving external transmission of data to or from the vehicle
• CPC Class Codes: B60W 30/00 : Purposes of road vehicle drive control systems not related to the control of a particular sub-unit, e.g. of systems using conjoint control of vehicle sub-units
• CPC Class Codes: B60W 30/09 : Taking automatic action to avoid collision, e.g. braking and steering
• CPC Class Codes: B60W 30/0956 : the prediction being responsive to traffic or environmental parameters
• CPC Class Codes: B60W 30/18163 : Lane change; Overtaking manoeuvres
• CPC Class Codes: B60W 60/0011 : involving control alternatives for a single driving scenario, e.g. planning several paths to avoid obstacles
• CPC Class Codes: B60W 60/0015 : specially adapted for safety
• CPC Class Codes: B60W 60/0016 : of the vehicle or its occupants
• CPC Class Codes: B60W 60/00276 : for two or more other traffic participants
• CPC Class Codes: G05D 1/0212 : with means for defining a desired trajectory involving a plurality of land vehicles G05D1/0287
• CPC Class Codes: G05D 1/0214 : in accordance with safety or protection criteria, e.g. avoiding hazardous areas monitoring the location of vehicles within a certain area, e.g. forbidden or allowed areas, in traffic control systems for road vehicles G08G1/13
• CPC Class Codes: G05D 1/0231 : using optical position detecting means position-fixing by using electromagnetic waves other than radio waves, e.g. optical position detecting means G01S5/16
• CPC Class Codes: G05D 1/0251 : extracting 3D information from a plurality of images taken from different locations, e.g. stereo vision stereoscopic image analysis H04N13/00; depth recovery from images G06T7/593
• CPC Class Codes: G05D 1/0257 : using a radar radar systems designed for anti-collision purposes between land vehicles or between land vehicle and fixed obstacles G01S13/931
• CPC Class Codes: G05D 1/0268 : using internal positioning means
• CPC Class Codes: G05D 1/0278 : using satellite positioning signals, e.g. GPS
• CPC Class Codes: G05D 1/0285 : using signals transmitted via a public communication network, e.g. GSM network
• CPC Class Codes: G09B 19/167 : Control of land vehicles

Abstract

Among other things, an operation related to control of a vehicle is facilitated by actions that include the following. A finite set of candidate trajectories of the vehicle is generated that begin at a location of the vehicle as of a given time. The candidate trajectories are based on a state of the vehicle and on possible behaviors of the vehicle and of the environment as of the location of the vehicle and the given time. A putative optimal trajectory is selected from among the candidate trajectories based on costs associated with the candidate trajectories. The costs include costs associated with violations of rules of operation of the vehicle. The selected putative optimal trajectory is used to facilitate the operation related to control of the vehicle.

Claims

1. A method comprising

autonomously driving a vehicle within an environment to a destination by actions that include:

generating a finite set of candidate trajectories of the vehicle that begin at a location of the vehicle as of a given time, the candidate trajectories each being based on a sequence of world states at successive times and on transitions between successive states of the sequence, each of the world states comprising a state of the vehicle and a state of the environment as of the location of the vehicle and the corresponding time, the state of the environment comprising states of at least one of another vehicle, a cyclist, a pedestrian, or another obstacle,

selecting a putative optimal trajectory from among the candidate trajectories based on costs associated with the candidate trajectories, including costs associated with violations of rules of operation of the vehicle, the costs associated with a given trajectory being evaluated based on costs associated with sequences of two or more of the transitions between successive states of the trajectory, and

based on the selected putative optimal trajectory, commanding actuators of the vehicle to engage in control actions to drive the vehicle autonomously within the environment toward the destination.

2. The method of claim 1 in which the facilitating of the operation related to control of the vehicle comprises applying a feedback control policy associated with the putative optimal trajectory to control elements of the vehicle the application of the feedback control policy being based on the states of the vehicle and of the environment.

3. The method of claim 1 comprising applying one or more constraints to the finite set of candidate trajectories, the constraints being applied based on the sequence of world states at the successive times.

4. The method of claim 3 in which applying one or more constraints comprises attributing labels to each of the candidate trajectories of the finite set, each of the labels comprising a logical predicate that represent a property of the vehicle based on the candidate trajectory.

5. The method of claim 1 in which the putative optimal trajectory is associated with both speed and direction of the vehicle and selecting the putative optimal trajectory comprises determining a minimum-cost path through a directed graph of which the candidate trajectories comprise edges, the cost of the minimum-cost path comprising a penalty associated with violation of a constraint.

6. The method of claim 1 in which generating a finite set of candidate trajectories of the vehicle comprises applying a model that represents the vehicle'"'"'s expected response to a given control policy as of the location of the vehicle and the given time, the model representing responses of elements of the environment to the given control policy and the vehicle'"'"'s expected response as of the location of elements of the environment vehicle.

7. The method of claim 1 in which the costs associated with a given trajectory are based on costs associated with interactions between the states of the vehicle and the states of the environment and the costs are expressed as cost rules in a formal language that enables expression of the cost rules that are interpreted over sequences of two or more world states of a trajectory over time.

13. The method of claim 1 in which the facilitating an operation related to control of a vehicle comprises autonomously driving the vehicle.

26. The method of claim 1 in which the costs associated with a given trajectory are based on costs associated with interactions between the states of the vehicle and the states of the environment.

27. The method of claim 1 in which the selected putative optimal trajectory is associated with both speed and direction of the vehicle.

29. The method of claim 1 in which the state of the environment comprises the states of other vehicles, pedestrians, and obstacles as of the corresponding time.

30. The method of claim 2 in which the application of the feedback control policy is based on the states of the vehicle and of the environment.

8. A method comprising

evaluating driving performance for a vehicle being driven within an environment to a destination, by actions that include:

generating a finite set of candidate trajectories of the vehicle that begin at a location of the vehicle as of a given time, the candidate trajectories each being based on a sequence of world states at successive times and on transitions between successive states of the sequence, each of the world states comprising a state of the vehicle and a state of the environment as of the location of the vehicle and the corresponding time, the environment comprising at least one of another vehicle, pedestrians, cyclists, or other obstacle,

selecting a putative optimal trajectory from among the candidate trajectories based on costs associated with the candidate trajectories, including costs associated with violations of rules of operation of the vehicle, the candidate trajectories taking account of locations of elements of the environment,

monitoring an actual trajectory of the vehicle for a given time period, and

comparing the actual trajectory of the vehicle with the putative optimal trajectory as an indication of the driving performance.

9. The method of claim 8 in which the driving performance comprises a human driver'"'"'s performance.

10. The method of claim 9 comprising evaluating the driver'"'"'s performance based on one or more performance metrics.

11. The method of claim 9 comprising displaying information related to the driver'"'"'s performance on an in-vehicle display.

12. The method of claim 9 comprising transmitting information related to the driver'"'"'s performance wirelessly to a receiver remote from the vehicle.

14. A method comprising

autonomously driving a vehicle within an environment to a destination by actions that include:

generating a finite set of candidate trajectories of the vehicle as of a given time, the finite set of candidate trajectories belonging to a trajectory space of all possible trajectories of the vehicle,

assessing costs of each of the candidate trajectories, the costs comprising one or more of the following;

length, turning angle, or other geometry related costs;

acceleration, jerk, control effort, or other dynamic costs; and

rule or constraint violations or other logical costs, the costs comprising a total order, and the putative optimal trajectory is selected as one with minimum cost according to the total order,

selecting a putative optimal trajectory from among the candidate trajectories of the finite set based on costs associated with the candidate trajectories, the selected putative optimal trajectory is associated with both speed and direction of the vehicle,

the space of all possible trajectories of the vehicle being sufficiently covered by the generated finite set of candidate trajectories so that the putative optimal trajectory comprises an arbitrarily close approximation to an actual optimal trajectory, and

based on the selected putative optimal trajectory commanding actuators of the vehicle to engage in control actions to drive the vehicle within the environment toward the destination.

15. The method of claim 14 comprising applying one or more constraints to the finite set of candidate trajectories.

16. The method of claim 14 comprising representing the candidate trajectories as edges of a directed graph.

17. The method of claim 14 in which the environment comprises a vehicle.

18. The method of claim 14 in which generating a finite set of candidate trajectories of the vehicle comprises applying a model that represents the vehicle'"'"'s and the environment'"'"'s expected response to a given control policy as of the location of the vehicle and a given time.

19. The method of claim 18 in which the control policy comprises a feedback function that determines commands to control the vehicle.

28. The method of claim 14 in which the selected putative optimal trajectory is associated with both speed and direction of the vehicle.

20. A method comprising

evaluating driving performance for a vehicle being driven within an environment to a destination, by actions that include:

generating a finite set of candidate trajectories of the vehicle as of a given time, the finite set of candidate trajectories belonging to a trajectory space of all possible trajectories of the vehicle,

assessing costs of each of the candidate trajectories,

selecting a putative optimal trajectory from among the candidate trajectories of the finite set based on costs associated with the candidate trajectories,

the space of all possible trajectories of the vehicle being sufficiently covered by the generated finite set of candidate trajectories so that the putative optimal-trajectory comprises an arbitrarily close approximation to an optimal trajectory,

monitoring an actual trajectory of the vehicle for a given time period, and

comparing the actual trajectory of the vehicle with the putative optimal trajectory as an indication of the driving performance.

21. The method of claim 20 in which evaluating driving performance comprises monitoring a human driver'"'"'s performance.

22. The method of claim 20 comprising reporting a result of the monitoring of the driver'"'"'s performance.

23. The method of claim 20 comprising evaluating the driver'"'"'s performance based on one or more performance metrics.

24. The method of claim 20 comprising assessing the likelihood of an accident occurring.

25. An apparatus comprising

an autonomous vehicle comprising

controllable devices configured to cause the vehicle to traverse at least part of an optimal trajectory in a manner consistent with control policies and with cost rules that apply to sequences of transitions between successive world states along a world trajectory,

a controller to provide commands to the controllable devices in accordance with the world trajectory,

sources of information about world states at successive times, and

a computational element to

iteratively update (a) a set of world states, each of the world states representing a combination of a state of the vehicle, a state of an environment of the vehicle, and a state of at least one other object in the environment based at least in part on the information about world states, and (b) a set of world trajectories, each of the world trajectories representing a sequence of temporal transitions each transition being between one of the world states and another of the world states,

each of the iterations of the updating comprising

for each of one or more of the world states and for a corresponding vehicle control policy, simulating a candidate trajectory from the world state to a subsequent world state,

if the simulated candidate trajectory does not violate a constraint, adding the trajectory to the set of world trajectories to form an updated set of world trajectories,

if necessary, adding a new world state to the set of world states corresponding to the transition represented by the simulated candidate trajectory to form an updated set of world states, and

determining a minimum-cost path through the updated set of world states and the updated set of world trajectories, the determining including applying cost rules to a sequence of two or more successive transitions of each of the world trajectories, and

deliver to the controller information representing a next transition from the current world state to a next world state along the minimum-cost path, for autonomous control of the vehicle.