Stochastic Games with Stopping States and their Application to Adversarial Motion Planning Problems

We model a finite horizon decision making process between an ego and a non-ego vehicle, where the non-ego vehicle has a certain probability of moving adversarially over each planning stage. The adversarial intent of the non-ego vehicle is inferred only when a particular set of actions are performed by both vehicles, thereby creating a stopping state. We term such a decision-making process as a multi-stage stochastic zero-sum game (SSG) with stopping states, i.e., once adversarial intent is ascertained, the non-ego vehicle continues to choose its actions adversarially for the remaining stages of the interaction. We analytically characterize the Nash equilibria of this game for the case of two actions per player. We then demonstrate this approach via two autonomous motion planning applications. The first involves maintaining a safe distance from a non-ego vehicle ahead, modeled using fixed stage costs. The second involves safe lane-changing with costs that are stage dependent. In both scenarios, we provide a comparison between the analytic/simulated and experimental results using ground robots.