A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games

被引:731
作者
Mitchell, IM [1 ]
Bayen, AM
Tomlin, CJ
机构
[1] Univ British Columbia, Dept Comp Sci, Vancouver, BC V6T 1Z4, Canada
[2] Univ Calif Berkeley, Dept Civil & Environm Engn, Berkeley, CA 94720 USA
[3] Stanford Univ, Dept Aeronaut & Astronaut, Stanford, CA 94305 USA
关键词
differential games; Hamilton-Jacobi equations; reachability; verification;
D O I
10.1109/TAC.2005.851439
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We describe and implement an algorithm for computing the set of reachable states of a continuous dynamic game. The algorithm is based on a proof that the reachable set is the zero sublevel set of the viscosity solution of a particular time-dependent Hamilton-Jacobi-Isaacs partial differential equation. While alternative techniques for computing the reachable set have been proposed, the differential game formulation allows treatment of nonlinear systems with inputs and uncertain parameters. Because the time-dependent equation's solution is continuous and defined throughout the state space, methods from the level set literature can be used to generate more accurate approximations than are possible for formulations with potentially discontinuous solutions. A numerical implementation of our formulation is described and has been released on the web. Its correctness is verified through a two vehicle, three dimensional collision avoidance example for which an analytic solution is available.
引用
收藏
页码:947 / 957
页数:11
相关论文
共 47 条
[1]  
[Anonymous], 1993, LIB C CAT IN PUBL DA
[2]  
[Anonymous], 1997, Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations
[3]  
Asarin E, 2003, LECT NOTES COMPUT SC, V2623, P20
[4]  
ASH RB, 1972, REAL ANAL PROBABILIR, V11
[5]  
AUBIN J, 1991, VIABILITY THEORY S C
[6]  
Bardi M., 1995, LECT NOTES MATH, V1660, P44
[7]  
Bardi M., 1999, ANN INT SOC DYNAMIC, V4, p[xvi, 380]
[8]  
BAYEN A, 2003, AIAA C GUID NAV CONT
[9]  
Bemporad A, 2000, LECT NOTES COMPUT SC, V1790, P45
[10]  
Boyce W. E., 1986, Elementary Differential Equations and Boundary Value Problems, V4th