Game-theoretic models are increasingly used to describe multi-agent interactions in control and robotics applications. However, theoretical and computational complexity makes these models intractable in many dynamic, incomplete information scenarios. Recent work makes strong assumptions to reduce computational complexity: agents share sensor measurements with one another and maintain a common estimate of state uncertainty. Unfortunately, these assumptions enforce a degree of cooperation in generically noncooperative interactions. This paper takes the perspective of an ego agent seeking both computational tractability and robustness to unanticipated behavior of other agents due to mismatched state estimates from private---rather than shared---sensor measurements. To that end, we formulate the game theoretic planning problem in an augmented belief space with perturbed Bayesian dynamics that allows the ego to predict all agents' potentially divergent state estimates. These perturbations are chosen by a hypothetical adversary, ``nature,'' to reflect how non-ego agents' state estimates---based on measurements the ego agent will not see at runtime---may deviate from the ego's own belief. Ultimately, our approach can be understood in the spirit of classical H-infinity robust control, extended to noncooperative, stochastic dynamic games. We present a solver with polynomial-time iterations and conduct two experiments which show how robust belief space reasoning leads ego agents to proactively limit their future vulnerability to model misspecification of other agents' beliefs and actions, reducing performance degradation by over 48%.
Figures & tables
Fig. 1: Simplified depiction of an interaction between an autonomous car and a pedestrian. The car plans under the assumption that the pedestrian estimates a 10 ft gap to the vehicle and will yield. However, if the pedestrian believes the distance is greater (e.g. 20 ft) and attempts to cross the street, then the car is unable to slow down in time and the two collide.
Fig. 2: Here, we have two activist groups who attempt to influence 3 lawmakers’ opinions by fundraising and campaigning. In the experiment, the two causes are not directly opposed. However, as the activist groups have different informational channels, the groups may incorrectly model the other’s beliefs. Thus, in our experiment, we investigate robustness as a method to mitigate epistemic uncertainty about the information-gathering capabilities of non-robust activists.
Fig. 3: Distribution of cost difference from nominal (non-robust) incurred by the robust activist (2), across 50 Monte Carlo trials. The solid black lines denote the means of each distribution, and the baseline’s performance is the horizontal axis marked with a gray dotted line. Notice that as c decreases and activist 2 becomes more robust, its cost decreases relative to the non-robust baseline.
Fig. 4: Cost incurred by a robust activist for varying degrees of misspecified belief dynamics ( σd1 ) and Activist 2 robustness c . Solid lines and ribbons depict the means and standard deviations respectively. Robustness consistently lowers costs in unexpectedly adversarial environments ( σd1>0 ) but can increase cost in unexpectedly collaborative environments ( σd1<0 ). As c decreases, the slope of the cost-drift curve deviates from the nominal baseline; effectively, selecting c balances a tradeoff between the worst-case cost gain and the best-case cost reduction. The c=0.5 level of robustness reduces the additional incurred cost at σ^d1=0.4 by 48%, as compared to the additional cost incurred by the non-robust baseline at σ^d1=0.4 from σ^d1=0.0 .
Fig. 5: Cost change for Activist 2 under three different magnitudes of misspecified belief dynamics ( σd1 ) across different paired robustness profiles of both activists, (c1,c2) . Across all three drift mismatch grids shown, Activist 2 can reduce costs by being more robust (lower c2 ) regardless of the robustness of Activist 1. However, Activist 2 suffers a higher cost when both activists are robust in comparison to when both are non-robust (baseline NR). This trend can also be observed in Activist 1’s cost despite the lack of belief dynamics mismatch for Activist 1.
Fig. 6: Cost incurred by robust and non-robust defenders for varying inverse control cost multipliers of the attacker λ1 that the defender is not aware of: believed λ^1=1 . Solid lines and ribbons depict the means and standard deviations. The baseline’s performance is depicted with a black dashed line. As the attacker becomes more aggressive, λ1>1 , the more robust the defender, the lower cost it incurs. Even at low values where the attacker is passive, λ1<1 , the cost increase incurred by the robust defender is small.
Department of Aeronautics and Astronautics, MIT. · Department of Computing and Mathematical Sciences, Caltech. · Automatic Control Laboratory, ETH Zurich.