Counterfactual regret minimization for the safety verification of autonomous driving

Abstract

Rare safety-critical events remain a major challenge in autonomous vehicle testing. This paper proposes to use game theory to build a novel testing environment for autonomous vehicles. In this environment, a virtual agent based on counterfactual minimization (CFR) is used to accelerate testing and validate the safety performance of autonomous vehicles. The virtual agent updates the adversarial policies to be enforced by continuously accumulating regret values, thus increasing the probability of security-critical events occurring during the testing process. Finally, recognized metrics such as Time-to-Collision (TTC) and Minimum Safe Distance Factor (MSDF) are introduced to assess the quality of the scenario. Experimental results show that the virtual agent based on counterfactual minimization explicitly generates more safety-critical scenarios and accelerates the evaluation process by multiple orders of magnitude ($10^{3}$ times faster).

Appendix A

Counterfactual Regret Minimization(CFR)

Counterfactual minimization is solved using a regret matching algorithm. We need to consider the probability of reaching each information set given a player’s strategy; if the game is processed sequentially through a series of information sets, then the game’s state information and the probabilities of the sequence of players’ actions are passed forward, and the utility information is passed backward through the information sets. For each information set accessed recursively in the training iterations, the mixed strategy is computed according to the regret matching equation, which is given below in a series of notations and definitions:

$$\begin{aligned} v_i \left( \sigma ,h\right) =\sum _{h\in z ,\ \ z \in \mathcal {Z}}{\pi _{-i}^\sigma \left( h\right) }\pi ^\sigma (h, z )u_i( z ) \end{aligned}$$

(A1)

The counterfactual regret value for not taking action a in history is defined as:

$$\begin{aligned} r\left( h,a\right) =v_i\left( \sigma _{I\rightarrow a},h\right) -v_i\left( \sigma ,h\right) \end{aligned}$$

(A2)

The counterfactual regret value for not taking action a in information set I is:

$$\begin{aligned} r\left( I,a\right) =\sum _{h\in I}{r(h,a)} \end{aligned}$$

(A3)

Let $r_i^t\left( I,a\right)$ be the regret value when player i adopts the strategy $\sigma ^t$ in the information set I and does not adopt the action a. Define the cumulative counterfactual regret value as:

$$\begin{aligned} R_i^T\left( I,a\right) =\sum _{t=1}^{T}{r_i^t\left( I,a\right) } \end{aligned}$$

(A4)

When a player uses the strategy $\sigma$, the difference between the value of action a and the expected value is always chosen to be the regret value of an action, which is then weighted by the probability that the other players will adopt the action to reach that node. Define the non-negative counterfactual regret value as $R_i^{T,+}(I,a)=max(R_i^T(I,a),\ 0)$, then the update formula for the new strategy is as follows:

$$\begin{aligned} \sigma _i^{T+1}\left( I,a\right) = {\left\{ \begin{array}{ll} \frac{R_i^{T,+}(I,a)}{\sum _{a\in A(I)}{R_i^{T,+}(I,a)}}, & \text {if } \sum _{a\in A(I)}{R_i^{T,+}(I,a)}>0 \\ \frac{1}{|A(I)|}, & \text {otherwise}. \end{array}\right. } \end{aligned}$$

(A5)

For each information set, the equation is used to compute the probability of an action proportional to the value of positive cumulative regret.For each action, the CFR generates the next state in the game and calculates the utility value of each action by recursion. Regret values are computed from the return values, and finally the probability of occurrence at the current node is computed and returned.