Facilitating Vehicle Driving and Self-Driving

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.

1 . A method comprising
 effecting an operation related to control of a vehicle 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 being 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,   selecting a putative optimal trajectory from among the candidate trajectories based on costs associated with the candidate trajectories and expressed as cost rules in a formal language, and   using the selected putative optimal trajectory to effect the operation related to control of the vehicle.   
     
     
         2 . The method of  claim 1  comprising assigning priorities to respective cost rules. 
     
     
         3 . The method of  claim 2  in which the priorities comprise preferences for violations of cost rules. 
     
     
         4 . The method of  claim 3  comprising assigning weights to respective cost rules. 
     
     
         5 . The method of  claim 1  in which the formal language comprises at least one of Linear Temporal Logic (LTL), Computation Tree Logic (CTL*), or μ-calculus. 
     
     
         6 . The method of  claim 1  comprising converting the cost rules into an equivalent finite-state automaton. 
     
     
         7 . The method of  claim 6  in which selecting the putative optimal trajectory comprises assessing costs of respective candidate trajectories. 
     
     
         8 . The method of  claim 7  in which the assessing of a cost of a candidate trajectory comprises updating a state of a finite state automaton based on a sequence of labels expressed in the formal language and associated with a portion of the trajectory. 
     
     
         9 . The method of  claim 8  in which the cost is proportional to a number of labels that would need to be removed for the finite state automaton to accept that portion of the trajectory. 
     
     
         10 . The method of  claim 1  in which the effecting 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. 
     
     
         11 . The method of  claim 1  in which selecting the putative optimal trajectory comprises determining a minimum-cost path through a directed graph of which the candidate trajectories comprise edges. 
     
     
         12 . 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. 
     
     
         13 . The method of  claim 1  comprising monitoring an actual trajectory of the vehicle for a given time period. 
     
     
         14 . The method of  claim 13  comprising comparing, for the given time period, the actual trajectory of the vehicle with the putative optimal trajectory. 
     
     
         15 . The method of  claim 1  in which the effecting of an operation related to control of a vehicle comprises monitoring a driver's performance. 
     
     
         16 . The method of  claim 15  comprising evaluating the driver's performance based on one or more performance metrics. 
     
     
         17 . The method of  claim 15  comprising displaying information related to the driver's performance on an in-vehicle display. 
     
     
         18 . The method of  claim 15  comprising transmitting information related to the driver's performance wirelessly to a receiver remote from the vehicle. 
     
     
         19 . The method of  claim 1  in which the effecting an operation related to control of a vehicle comprises autonomously driving the vehicle. 
     
     
         20 . 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. 
     
     
         21 . The method of  claim 1  in which the selected putative optimal trajectory is associated with both speed and direction of the vehicle. 
     
     
         22 . 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. 
     
     
         23 . 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 cost rules,   a controller to provide commands to the controllable devices in accordance with the optimal trajectory, and   a computational element configured to effect, through the controllable devices, an operation related to control of the vehicle, 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 being 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, 
 selecting a putative optimal trajectory from among the candidate trajectories based on costs associated with the candidate trajectories and expressed as cost rules in a formal language, and 
 using the selected putative optimal trajectory to effect the operation related to control of the vehicle. 
   
     
     
         24 . The apparatus of  claim 23  in which the actions include assigning priorities to respective cost rules. 
     
     
         25 . The apparatus of  claim 24  in which the priorities comprise preferences for violations of cost rules. 
     
     
         26 . The apparatus of  claim 25  in which the actions include assigning weights to respective cost rules. 
     
     
         27 . The apparatus of  claim 23  in which the formal language comprises at least one of Linear Temporal Logic (LTL), Computation Tree Logic (CTL*), or pt-calculus. 
     
     
         28 . The apparatus of  claim 23  in which the actions include converting the cost rules into an equivalent finite-state automaton. 
     
     
         29 . The apparatus of  claim 28  in which selecting the putative optimal trajectory comprises assessing costs of respective candidate trajectories. 
     
     
         30 . The apparatus of  claim 29  in which the assessing of a cost of a candidate trajectory comprises updating a state of a finite state automaton based on a sequence of labels expressed in the formal language and associated with a portion of the trajectory. 
     
     
         31 . The apparatus of  claim 30  in which the cost is proportional to a number of labels that would need to be removed for the finite state automaton to accept that portion of the trajectory. 
     
     
         32 . The apparatus of  claim 23  in which the effecting 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. 
     
     
         33 . The apparatus of  claim 23  in which selecting the putative optimal trajectory comprises determining a minimum-cost path through a directed graph of which the candidate trajectories comprise edges. 
     
     
         34 . The apparatus of  claim 23  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. 
     
     
         35 . The apparatus of  claim 23  in which the actions include monitoring an actual trajectory of the vehicle for a given time period. 
     
     
         36 . The apparatus of  claim 35  in which the actions include comparing, for the given time period, the actual trajectory of the vehicle with the putative optimal trajectory. 
     
     
         37 . The apparatus of  claim 23  in which the effecting of an operation related to control of a vehicle comprises monitoring a driver's performance. 
     
     
         38 . The apparatus of  claim 37  comprising evaluating the driver's performance based on one or more performance metrics. 
     
     
         39 . The apparatus of  claim 37  comprising displaying information related to the driver's performance on an in-vehicle display. 
     
     
         40 . The apparatus of  claim 37  comprising transmitting information related to the driver's performance wirelessly to a receiver remote from the vehicle. 
     
     
         41 . The apparatus of  claim 23  in which the effecting an operation related to control of a vehicle comprises autonomously driving the vehicle. 
     
     
         42 . The apparatus of  claim 23  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. 
     
     
         43 . The apparatus of  claim 23  in which the selected putative optimal trajectory is associated with both speed and direction of the vehicle. 
     
     
         44 . The apparatus of  claim 23  in which the state of the environment comprises the states of other vehicles, pedestrians, and obstacles as of the corresponding time.