Approximate Solutions to a Class of Reachability Games
In this paper, we present a method for finding approximate Nash equilibria in a broad class of reachability games. These games are often used to formulate both collision avoidance and goal satisfaction. Our method is computationally efficient, running in real-time for scenarios involving multiple players and more than ten state dimensions. The proposed approach forms a family of increasingly exact approximations to the original game. Our results characterize the quality of these approximations and show operation in a receding horizon, minimally-invasive control context. Additionally, as a special case, our method reduces to local gradient-based optimization in the single-player (optimal control) setting, for which a wide variety of efficient algorithms exist.
Code (0)
등록된 구현이 없습니다.
Tasks
Collision AvoidanceSimilar Papers 제목 키워드 기반
Bidding Games on Markov Decision Processes with Quantitative Reachability Objectives
Graph games are fundamental in strategic reasoning of multi-agent systems and their environments. We study a new family of graph games which combine stochastic environmental uncertainties and auction-based interactions a…
Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptions
We address payoff-based decentralized learning in infinite-horizon zero-sum Markov games. In this setting, each player makes decisions based solely on received rewards, without observing the opponent's strategy or action…
Automated Approach for Solving Infinite-state Polynomial Reachability Games
Reachability games are two-player games played on a graph, where the objective of $\texttt{REACH}$ player is to reach the target set whereas the objective of $\texttt{SAFE}$ player is to stay away from the target set. Re…
Reachability Poorman Discrete-Bidding Games
We consider {\em bidding games}, a class of two-player zero-sum {\em graph games}. The game proceeds as follows. Both players have bounded budgets. A token is placed on a vertex of a graph, in each turn the players simul…
Approximate Hamilton-Jacobi Reachability Analysis for a Class of Two-Timescale Systems, with Application to Biological Models
Hamilton-Jacobi reachability (HJR) is an exciting framework used for control of safety-critical systems with nonlinear and possibly uncertain dynamics. However, HJR suffers from the curse of dimensionality, with computat…