Backward monte Carlo tree search model for monitoring and analyzing safety of belief reasoning for autonomous vehicles
A vehicle traversing a vehicle transportation network may use a scenario-specific operational control evaluation model instance. The vehicle may receive operational environment data that includes data associated with an object external to the vehicle. The vehicle may determine, based at least in part on the data associated with the object, a final belief associated with an undesired outcome. The vehicle may construct a backward Monte Carlo tree search model based on the final belief and may determine, based on the backward Monte Carlo tree search model, a set of initial beliefs corresponding to a likelihood of leading to the final belief within a timestep threshold. A policy may be trained using the set of initial beliefs. Based on the trained policy, a set of candidate vehicle control actions may be determined, and a vehicle control action may be selected from the set of candidate vehicle control actions.
1 . A method for use with a vehicle in traversing a vehicle transportation network, the method comprising:
receiving, by an autonomous vehicle operational management controller (AVOMC) implemented on the vehicle, while the vehicle is traversing the vehicle transportation network, operational environment data, wherein the operational environment data includes data associated with an object external to the vehicle;
determining, by the AVOMC and based at least in part on the data associated with the object, a final belief associated with an undesired outcome;
constructing, by the AVOMC, a backward Monte Carlo tree search model based on the final belief;
determining, by the AVOMC and based on the backward Monte Carlo tree search model, a set of initial beliefs corresponding to a likelihood of leading to the final belief within a timestep threshold;
generating, by the AVOMC, a trained policy by training, using the set of initial beliefs, a policy that maps a respective belief for the object within a distinct vehicle operation scenario to a respective candidate vehicle control action;
determining, by the AVOMC and based on the trained policy, a set of candidate vehicle control actions; and
controlling, by the AVOMC, the vehicle to traverse the vehicle transportation network based on selecting a vehicle control action from the set of candidate vehicle control actions.
2 . The method of claim 1 , wherein determining the set of initial beliefs comprises sampling the set of initial beliefs from a subspace of a belief space.
3 . The method of claim 2 , wherein the subspace corresponds to a face of a computed convex polygon.
4 . The method of claim 1 , wherein an initial belief of the set of initial beliefs corresponds to a path from the initial belief to the final belief within the timestep threshold via a sequence of actions and observations.
5 . The method of claim 1 , wherein the object is an additional vehicle.
6 . The method of claim 5 , wherein the set of candidate vehicle control actions comprises a set of alternative actions associated with an intersection approached by the vehicle and the additional vehicle.
7 . The method of claim 5 , wherein the set of initial beliefs is represented as a partially observable Markov decision process.
8 . The method of claim 1 , wherein determining the set of initial beliefs comprises:
establishing a first node corresponding to the final belief, wherein the first node is associated with a first time;
sampling, based on the first node, a set of possible observations associated with a second time occurring one timestep prior to the first time;
sampling, based on the first node, a set of possible actions associated with a third time occurring one timestep prior to the second time, wherein the set of possible actions correspond to a likelihood of leading to the set of possible observations; and
sampling, based on the set of possible actions, the set of initial beliefs.
9 . The method of claim 8 , wherein sampling the set of initial beliefs comprises sampling the set of initial beliefs from a convex polytope, the method further comprising constraining the convex polytope based on a reachability probability threshold.
10 . The method of claim 1 , wherein constructing the backward Monte Carlo tree search model comprises constructing the backward Monte Carlo tree search model based on a maximum depth value.
11 . The method of claim 1 , determining the set of initial beliefs comprises approximating a terminal Bayesian probability of an initial belief of the set of initial beliefs.
12 . The method of claim 1 , determining the set of initial beliefs comprises partitioning a belief space based on an association between a set of actions and a corresponding set of observations.
13 . An apparatus for use with a vehicle traversing a vehicle transportation network, the apparatus comprising:
a processor configured to:
receive, by an autonomous vehicle operational management controller (AVOMC) implemented on the vehicle, while the vehicle is traversing the vehicle transportation network, operational environment data, wherein the operational environment data includes data associated with an object external to the vehicle;
determine, by the AVOMC and based at least in part on the data associated with the object, a final belief associated with an undesired outcome;
determine, by the AVOMC and based on a backward Monte Carlo tree search model constructed based on the final belief, a set of initial beliefs corresponding to a likelihood of leading to the final belief within a timestep threshold;
generate, by the AVOMC, a trained policy by training, using the set of initial beliefs, a policy that maps a respective belief for the object within a distinct vehicle operation scenario to a respective candidate vehicle control action;
determine, by the AVOMC and based on the trained policy, a set of candidate vehicle control actions; and
control, by the AVOMC, the vehicle to traverse the vehicle transportation network based on selecting a vehicle control action from the set of candidate vehicle control actions.
14 . The apparatus of claim 13 , wherein the set of initial beliefs is sampled from a subspace of a belief space, and wherein the subspace corresponds to a face of a computed convex polygon.
15 . The apparatus of claim 13 , wherein an initial belief of the set of initial beliefs corresponds to a path from the initial belief to the final belief within the timestep threshold via a sequence of actions and observations.
16 . The apparatus of claim 13 , wherein the object is an additional vehicle.
17 . The apparatus of claim 16 , wherein the set of candidate vehicle control actions comprises a set of alternative actions associated with an intersection approached by the vehicle and the additional vehicle.
18 . The apparatus of claim 13 , wherein the processor, to determine the set of initial beliefs, is configured to:
establish a first node corresponding to the final belief, wherein the first node is associated with a first time;
sample, based on the first node, a set of possible observations associated with a second time occurring one timestep prior to the first time;
sample, based on the first node, a set of possible actions associated with a third time occurring one timestep prior to the second time, wherein the set of possible actions correspond to a likelihood of leading to the set of possible observations; and
sample, based on the set of possible actions, the set of initial beliefs.
19 . An autonomous vehicle, comprising:
a processor configured to execute instructions stored on a non-transitory computer readable medium to:
receive, by an autonomous vehicle operational management controller (AVOMC) implemented on the vehicle, while the vehicle is traversing a vehicle transportation network, operational environment data, wherein the operational environment data includes data associated with an object external to the vehicle;
determine, by the AVOMC and based at least in part on the data associated with the object, a final belief associated with an undesired outcome;
determine, by the AVOMC and based on a backward Monte Carlo tree search model constructed based on the final belief, a set of initial beliefs corresponding to a likelihood of leading to the final belief within a timestep threshold;
determine, by the AVOMC and based on a trained policy, a set of candidate vehicle control actions, wherein the trained policy comprises a policy, trained using the set of initial beliefs, that maps a respective belief for the object within a distinct vehicle operation scenario to a respective candidate vehicle control action; and
control, by the AVOMC, the vehicle to traverse the vehicle transportation network based on selecting a vehicle control action from the set of candidate vehicle control actions.
20 . The autonomous vehicle of claim 19 , wherein an initial belief of the set of initial beliefs corresponds to a path from the initial belief to the final belief within the timestep threshold via a sequence of actions and observations.