Back to the Future: Efficient, Time-Consistent Solutions in Reach-Avoid Games
We study the class of reach-avoid dynamic games in which multiple agents interact noncooperatively, and each wishes to satisfy a distinct target criterion while avoiding a failure criterion. Reach-avoid games are commonly used to express safety-critical optimal control problems found in mobile robot motion planning. Here, we focus on finding time-consistent solutions, in which future motion plans remain optimal even when a robot diverges from the plan early on due to, e.g., intrinsic dynamic uncertainty or extrinsic environment disturbances. Our main contribution is a computationally-efficient algorithm for multi-agent reach-avoid games which renders time-consistent solutions for all players. We demonstrate our approach in two- and three-player simulated driving scenarios, in which our method provides safe control strategies for all agents.
Code (1)
Tasks
Motion PlanningSimilar Papers 제목 키워드 기반
BURNS: Backward Underapproximate Reachability for Neural-Feedback-Loop Systems
Learning-enabled planning and control algorithms are increasingly popular, but they often lack rigorous guarantees of performance or safety. We introduce an algorithm for computing underapproximate backward reachable set…
Backward Learning for Goal-Conditioned Policies
Can we learn policies in reinforcement learning without rewards? Can we learn a policy just by trying to reach a goal state? We answer these questions positively by proposing a multi-step procedure that first learns a wo…
Imitation Learningreinforcement-learningThe backtracking survey propagation algorithm for solving random K-SAT problems
Discrete combinatorial optimization has a central role in many scientific disciplines, however, for hard problems we lack linear time algorithms that would allow us to solve very large instances. Moreover, it is still un…
Combinatorial OptimizationDistributionally robust goal-reaching optimization in the presence of background risk
In this paper, we examine the effect of background risk on portfolio selection and optimal reinsurance design under the criterion of maximizing the probability of reaching a goal. Following the literature, we adopt depen…
Neural Predictive Monitoring under Partial Observability
We consider the problem of predictive monitoring (PM), i.e., predicting at runtime future violations of a system from the current state. We work under the most realistic settings where only partial and noisy observations…
Active LearningConformal PredictionState Estimation