Integrated Decision Making and Trajectory Planning for Autonomous Driving Under Multimodal Uncertainties: A Bayesian Game Approach

In the past years, efforts have been made to tackle the decision-making and trajectory-planning problems for autonomous driving. State-machine-based methods [18, 19, 20], which utilize hand-crafted rules to generate decisions and trajectories based on the current state of the autonomous vehicle, are popular at the early stage due to their simplicity and interpretability. However, the innumerable nature of traffic scenarios prevents the wide application of these methods, as the difficulty in maintaining such a state machine increases dramatically with increasing scenario complexities. The research focus soon shifts to a more generic formulation of the problem. In light of this, various methods are proposed by actively employing the concept of searching [21, 22, 23], optimization [24, 25, 26], sampling [27, 28], and POMDP [29], etc. Recently, a branch of multi-policy planning methods, including MPDM [30], EUDM [31], EPSILON [32], and MARC [33], are gaining attention due to their ability in efficient behavior planning. These methods rely on dedicated forward simulators to evaluate the performance of each policy and perform the best one selectively. Nonetheless, the aforementioned approaches generally suffer from difficulties in modeling the interactions, particularly in the effect of the trajectory of the autonomous vehicle on the behaviors of the other vehicles. Meanwhile, a series of recent works address the decision-making and trajectory planning problem using a unified neural network trained through end-to-end imitation learning  [34, 35, 36]. However, the lack of interpretability brings safety concerns, which prevents the wide application of these methods in real-world situations.

To tackle the problem mentioned in the previous subsection, game-based methods are extensively researched. In this area, many of the existing methods calculate a single equilibrium and assume that all participants will follow the computed equilibrium [37, 4, 13, 38, 9]. These methods generally assume no uncertainty in agents’ behaviors. In [37, 4], efficient game-solving strategies are proposed to resolve differential games and reach typical Nash equilibriums. In [13], the interaction between traffic agents is formulated as a Stackelberg game, and a solving scheme based on dynamic programming is proposed to solve the game in real time. In [9], a general decision-making framework is introduced, which shows that typical traffic scenarios can be modeled as a potential game. In potential games, a pure-strategy Nash equilibrium is proven to exist and reachable, and therefore effective decision-making strategies can be derived. In [38], an efficient game-theoretic trajectory planning algorithm is introduced based on Monte Carlo Tree Search, together with an online estimation algorithm to identify the driving preferences of road participants. Although different types of games and various solving schemes are intensively studied in these researches, the uncertainties in human driving behaviors are not effectively revealed in the attained equilibria. Meanwhile, a few studies try to actively model different kinds of uncertainties involved in a game process. In [39], uncertainties in the observation model are actively addressed by formulating the interaction between agents as a stochastic dynamic game in belief space. However, the proposed method only considers observation uncertainties with Gaussian noise. In [40], the maximum entropy model is utilized to model the uncertainties in the equilibrium strategies for all agents. Nevertheless, the objectives and intentions of all agents are assumed to be known and fixed, which is unrealistic in complicated urban traffic scenarios.

To address the uncertainties residing in objectives and obtain the optimal strategy against the resulting multi-modal behaviors of rival agents, some of the researches study the game of incomplete information and the corresponding Bayesian equilibrium, where the equilibrium strategy is optimal over the distribution of rivals’ possible objectives and their equilibrium strategies. Representative works include [15, 17, 41, 42, 16, 43]. Nonetheless, these methods adopt overly simplified game settings of tiny scale and use hand-crafted solvers for obtaining the corresponding Bayesian equilibrium, which confines the application of these methods to simple scenarios like lane-switching. Besides, the decision-making and trajectory-planning processes are usually separated, and this discrepancy can lead to suboptimal decisions. A recent research [44] takes a game-theoretic perspective on contingency planning, and the resulting contingency game enables interaction with other agents by generating strategic motion plans conditioned on multiple possible intents for other actors. However, it is a motion planning framework lacking in the capacity to perform high-level decision-making. Also, the dedicated and unsymmetrical game settings make it hard to generalize to different types of games with multiple players, multiple policies, and multiple stages.

Another branch of methods closely related to this research is no-regret learning, which aims at providing general solutions to various extensive-form games (games with multiple stages). Despite their effectiveness in modeling sequential decision-making processes, solving for large extensive games has been a long-standing challenge. In [45], a counter-factual regret minimization (CFR) algorithm is introduced to iteratively solve this form of games, which is extended by MCCFR [46] with a Monte Carlo sampling process to avoid the difficulties traversing the entire game tree in each iteration. A follow-up work is proposed in [47], which further extends the MCCFR method to enable dynamic construction of the game tree. The convergence of these methods to a corresponding Nash equilibrium is only guaranteed on two-player zero-sum games. To extend these methods to multi-player general-sum games, CFR-S is introduced in [48], which performs sampling at each iteration and illustrates that the frequency distribution of the sampled strategies converges to a Coarse Correlated Equilibrium (CCE). For games of incomplete information with Bayes settings, the condition of convergence to a Bayes-CCE is provided in [49] without detailed solution schemes.

In this section, a parallel solver utilizing classic Monte Carlo counter-factual regret minimization (MCCFR) is introduced to resolve the game and enable a real-time solution for the open-loop Bayes-CCE in general traffic settings. In particular, the structure of a typical extensive-form game of incomplete information in traffic settings is shown as the game tree in Fig. 1. Each of the nodes on the game tree corresponds to a particular game state, and these game states are partitioned into information sets, such that players cannot distinguish between two states in the same information set. Therefore, the behavior strategy of each player is made with respect to information sets, $\sigma_{i}(t_{i})=[\sigma_{i}(t_{i},I)]_{I\in\mathcal{I}_{i}}$, where $\mathcal{I}_{i}$ is the information partition of player $i$, or the set of information sets under which it is the turn of player $i$ to move. $\sigma_{i}(t_{i},I)$ is a distribution over possible actions $A_{i}(t_{i},I)$ for player $i$ of type $t_{i}$ under Information set $I$. At the beginning stage of the game, an extra chance player (also known as the nature) will take chance moves that will randomly select a type for each player subject to the common probability distribution $p$. After the types of all players are determined, players will take moves in turns to proceed through the game tree until a leaf node is reached and the utilities of all players are thus determined.

Before we formally propose the solving scheme, we give a brief introduction to two relevant algorithms as preliminaries.

CFR [45] and MCCFR [46]: The vanilla CFR only considers a two-player zero-sum game without types of players. Therefore, $\sigma_{i}(t_{i},I)$, $u_{i}(t_{i};a)$, and $A_{i}(t_{i},I)$ can be rewritten as $\sigma_{i}(I)$, $u_{i}(a)$, and $A_{i}(I)$, respectively. Given the overall strategy as $\sigma$, the counterfactual value $v_{i}(\sigma,I)$ for information set $I$ is defined as

where $Z_{I}$ is the set of all the paths on the game tree from root to leaf that pass through I, and $z$ is one of the paths in $Z_{I}$ containing all historical actions of all players. $z[I]$ is the prefix of $z$ from root to $I$. $\pi^{\sigma}_{-i}(z[I])$ is the cumulative product of the probabilities of moves taken by other agents along $z[I]$, and $\pi^{\sigma}(z[I],z)$ is the cumulative product of the probabilities of moves taken by all agents from $z[I]$ to $z$. In general, the counterfactual value $v_{i}(\sigma,I)$ describes the expected utility of Information set $I$ given strategy profile $\sigma$ with the extra assumption that agent $i$ plays to reach $I$.

The immediate counterfactual regrets of each action $a\in A_{i}(I)$ is $r(\sigma,I,a)=v_{i}(\sigma_{(I\rightarrow a)},I)-v_{i}(\sigma,I)$, with $\sigma_{(I\rightarrow a)}$ define as the strategy profile identical to $\sigma$ except that $\sigma_{(a\rightarrow I)}(a|I)=1$, namely that action $a$ is selected with probability $1$. In the entire no-regret learning process, rounds of playing are conducted. In each round, the regret-matching strategy is conducted to improve the strategy. Particularly in round $k+1$, the strategy $\sigma^{k+1}$ is determined by $\sigma^{k+1}_{i}(a|I)=R^{k,+}_{i}(I,a)/\sum_{a^{\prime}\in A_{i}(I)}R^{k,+}_{i}(I,a^{\prime})$, where $R^{k,+}_{i}(I,a)=\max\{\sum_{\tau=1}^{k}r(\sigma^{\tau},I,a),0\}$. It is proven that when $k\rightarrow\infty$, the average strategy $\overline{\sigma}^{k}$ defined as $\overline{\sigma}^{k}_{i}(a|I)=\sum_{\tau=1}^{k}\pi^{\sigma^{\tau}}_{i}(I)\sigma^{\tau}(a|I)/\sum_{\tau=1}^{k}\pi^{\sigma^{\tau}}_{i}(I)$ converges to a Nash equilibrium for a two-player zero-sum game.

A drawback of the vanilla CFR method is that in each round of playing, traversing the entire game tree is required, which is time-consuming and even intractable when the size of the game is large. To cope with this problem, the method MCCFR is proposed, such that in each round of playing, only part of the game tree is explored. Particularly in outcome-sampling MCCFR, only one leaf node of the game tree is sampled according to some pre-defined distribution, $z\sim q(z)$, and all other leaves are dropped (equivalently, their utilities are zeroed out). The following sampled counterfactual value is introduced:

It is shown that $\mathbb{E}_{z\sim p(z)}\tilde{v}_{i}(\sigma,I;z)=v_{i}(\sigma,I)$. Replacing $v_{i}(\sigma,I)$ by $\tilde{v}_{i}(\sigma,I;z)$ yields the outcome-sampling MCCFR. It is obvious that in each round of playing, the only information sets that require updating are those passed through by the sampled path $z$.

The previous restatement of CFR and MCCFR describes a solution to obtain the (mixed-strategy) Nash equilibrium in a two-player zero-sum extensive-form game. We integrate MCCFR, the no-regret learning method in game of incomplete information [49], and CFR-S [48] to introduce MCCFR-S for game of incomplete information, a parallelizable solving scheme that is proven to converge to a Bayes-CCE for a multi-player general-sum game of incomplete information settings. Details are shown in Algorithm 1. We give a brief explanation of each procedure used in this algorithm.

Bayes-CCE$(G,M,p)$: this is the main procedure of Algorithm 1. $G$ is the game described in Fig.1. $M$ is the number of iterations and $p$ is the common distribution over intentions of vehicles. $re$, $\sigma$, and $\phi$ are the array of cumulative counterfactual regrets, the array of behavioral strategies, and the frequency of plan $s$, respectively. $va$ is the array of the cumulative sampled counterfactual values. All those arrays are zero-initialized. In each iteraction, a type vector $t$ representing vehicles’ intentions are sampled from distribution $p$, and then the outcome-sampling MCCFR is performed once to update the regret array $re$ and the strategy array $\sigma$. A sampling process is then performed based on updated $\sigma$ strategy such that a plan $s$ is sampled from $\sigma$ and the frequency $\phi$ is updated.

MCCFR$(G,re,\sigma,t,va,z,pr,l)$: this is a recursive implementation of MCCFR [46], where $G,re,\sigma,t$ are defined as above. $z$ is the history of play or the past actions of all players concatenated together. For a particular $z$, $pr$ is the vector containing probabilities of all players play to reach $z$ according to current strategy $\sigma$, namely $\{\pi^{\sigma}_{i}(z)\}_{i\in\mathcal{N}}$. $l$ is the probability of sampling $z$, namely $q(z)$. The algorithm contains a forward pass and a backward pass. In the forward pass we randomly proceed through the game tree from the root to one of the leaf by sampling action from the $\epsilon$-modulated strategy at each node (line 17 and 18) and calculate the $pr$ and $l$ for current $z$ (line 19 and 20). Once a leaf is reached, we obtain the utility for all players (line 11 to 14). In the backward pass, we revisit all the information sets we visited in the forward pass in reverse order. For an information set $I$, we obtain the probability playing from $I$ to the sampled leaf according to current strategy (line 23), and updates the cumulative counterfactual regret for $I$ (line 24 to 31). A standard regret matching is performed to update the behavioral strategy associated with $I$ (line 32).

RM$(re,i,t_{i},I)$: this is the standard regret matching algorithm for updating behavioral strategy associated with information set $I$ called by the MCCFR procedure.

Sample$(\sigma,\phi)$: this is the sampling procedure. given updated strategy $\sigma$, a plan $s_{i}$ is sampled for each $i\in\mathcal{N}$. The concatenated plan $s\in\Sigma$ is then obtained and record. $\phi$ measures the time when $s$ is sampled, such that $\phi/M$ is an empirical distribution over the space of plan $\Sigma$.

Algorithm 1 is easily parallelizable and implemented with multiple processes, as each process samples the type vector $t$, proceeds along the game tree, and samples the overall plan $s$, independently. The only coupled part is the line 32, as each process needs to gather the $re$ computed by all other processes to perform the regret matching and update the strategy. For Algorithm 1, we have the following theorem.

Sampling an entire plan $s_{i}$ requires traversing the entire game tree and sampling action for each information set $I\in\mathcal{I}_{i}$, which is computationally heavy for extensive-form games with multiple stages, as the number of information sets grows exponentially with respect to the number of stages. In the proposed framework, the receding horizon control is adopted, as each agent only performs the action computed in the first stage (details will be discussed in Section IV-D). Therefore, we only need to record the actions taken by players at the first stage, resulting in a partial plan. The resulting distribution can be viewed as a marginal distribution of the origin Bayes-CCE.

In a typical game of incomplete information, the type of each player is usually drawn by nature, a chance player, from the prior distribution. In the settings of autonomous driving, however, the types are self-determined by players, and therefore we can select the best type to perform. In the proposed framework, we view the selection of the best type $t^{*}_{i}$ from the type list $T_{i}$ as equivalent to the decision-making process. Formally given the computed Bayes-CCE $\psi$, we denote the expected utility of a type $t^{\prime}_{i}$ as

Then the best type $t^{*}_{i}$ and equivalently the best decision, is determined by $t^{*}_{i}=\operatorname*{argmax}_{t^{\prime}_{i}\in T_{i}}V(t^{\prime}_{i}).$ However, as we mentioned in Section IV-A, we only keep a partial record of the Bayes-CCE $\psi$ for computation efficiency, and therefore it is not feasible to directly calculate $V(t^{\prime}_{i})$. Instead, we introduce an estimator of this expectation and use this estimator as a criterion of decision-making. We denote the root information set corresponding to $t_{i}$ as $I_{0,t_{i}}$, and the estimator is given as $\hat{V}(t^{\prime}_{i})=va[i,t^{\prime}_{i},I_{0,t^{\prime}_{i}}]/|\mathcal{M}_{t^{\prime}_{i}}|$. Immediately, we have the following theorem.

Theorem 2 indicates that $\hat{V}(t^{\prime}_{i})$ is an unbiased and consistent estimator of $V(t^{\prime}_{i})$. Moreover, it can be seen from Algorithm 1 that calculating $\hat{V}(t^{\prime}_{i})$, which corresponds to line 33 of the algorithm, adds only minimal computation load to the algorithm as no extra sampling is required. Therefore, we propose the decision-making strategy as

such that by selecting its type as $t^{*}_{i}$, the player $i$ makes the decision that maximizes its overall expected utility corresponding to the given Bayes-CCE $\psi$.

Once the type $t^{*}_{i}$ is determined, we can select the optimal plan $s^{*}_{i}$ from the Bayes-CCE $\psi$, such that the trajectory is given by $s^{*}_{i}(t^{*}_{i})$. We introduce two different schemes to perform the Bayes-CCE $\psi$ and select the optimal plan.

Accurate implementation of Bayes-CCE $\psi$: since a Bayes-CCE is correlated, the accurate performance of a Bayes-CCE will require either negotiation beforehand (which is unlikely in urban traffic scenarios) or a leader-follower assumption which is often adopted in the Stackelberg game formulation of traffic interactions  [8, 13]. Without loss of generality, we assume that player 1 is the leader, and player $i$ is a direct follower of player $i-1$ for all $i\in\mathcal{N}$ and $i\neq 1$. The joint probability distribution $\psi$ can be decomposed into a series of marginal distributions and conditional distributions, such that the probability of a joint plan $s=\{s_{i}\}_{i\in\mathcal{N}}$ is given by

such that $\psi_{1}$ is the marginal distribution of the plan corresponding to player $1$, and $\psi^{\prime}_{i}$ is the conditional distribution of the plans of player $i$ conditioned on the plan of all the players before $i$. If plans are selected by maximum likelihood, the plans selected are

We consider this scheme to be overly idealistic due to the following reasons:

• •

  Although being widely adopted, the leader-follower assumption is not always valid, especially when more than two vehicles are involved.

• •

  Due to partial observation, vehicle $i$ cannot know for sure the plan $s_{j}$ adopted by vehicle $j$. At best, it can only maintain a belief over $s_{j}$.

Due to these reasons, we introduce the following marginal implementation of the Bayes-CCE.

Marginal implementation of Bayes-CCE $\psi$: to avoid the problem mentioned before, we propose an approximation performance scheme of the Bayes-CCE $\psi$. We define $\psi_{i}$ as the marginal distribution of the plan of player $i$, and then the plan is determined as

The marginal implementation of Bayes-CCE is used in the simulation. Once the optimal plan $s^{*}_{i}$ is determined by one of the schemes introduced before, the planning process is conducted by taking $s^{*}_{i}(t^{*}_{i})$ with the optimal decision $t^{*}_{i}$. As a result, an integrated decision-making and trajectory planning scheme is introduced based on the Bayes-CCE.

Following a Bayes-CCE, the probabilities of actions taken by vehicles depend on their underlying driving intentions. Therefore, the actual actions performed by vehicles provide extra information gains over the belief of driving intentions. In this section, we introduce strategies to update the common belief over the driving intentions of all vehicles based on the observed actions. Corresponding to different implementations of the Bayes-CCE, different updating strategies are introduced.

Update strategy for the accurate implementation: suppose that at time stamp $\lambda$ the common prior on intentions of vehicles is given as $p^{\lambda}$, the Bayes-CCE is given as $\psi^{\lambda}$, and the action performed by all vehicles is $a^{\lambda}=\{a_{i}^{\lambda}\}_{i\in\mathcal{N}}$. The following equation gives the updated common prior $p^{\lambda+1}$

which follows the standard Bayes’ rule of posterior probability. $f$ is the observation model such that $f(a^{\lambda},t;\psi^{\lambda})$ gives the probability that action $a^{\lambda}$ is taken if all players follow the Bayes-CCE $\psi^{\lambda}$ and their underlying types are defined by $t$. To effectively model $f$, we adopt the Mixture-of-Gaussians distributions, and $f$ is defined as

where $\eta(\cdot;s(t))$ is the probability density function of a Gaussian distribution $N(\mu(s(t)),\Sigma)$. $\mu(a^{\lambda})$ and $\mu(s(t))$ are the end states of vehicles when action $a^{\lambda}$ and $s(t)$ are taken, respectively. $\Sigma$ is a predefined covariance matrix.

Update strategy for the marginal implementation: under this implementation, the update rule is similarly given as

where