TY - GEN
T1 - Safe sequential path planning of multi-vehicle systems via double-obstacle Hamilton-Jacobi-Isaacs variational inequality
AU - Chen, Mo
AU - Fisac, Jaime F.
AU - Sastry, Shankar
AU - Tomlin, Claire J.
N1 - Publisher Copyright:
© 2015 EUCA.
PY - 2015/11/16
Y1 - 2015/11/16
N2 - We consider the problem of planning trajectories for a group of N vehicles, each aiming to reach its own target set while avoiding danger zones of other vehicles. The analysis of problems like this is extremely important practically, especially given the growing interest in utilizing unmanned aircraft systems for civil purposes. The direct solution of this problem by solving a single-obstacle Hamilton-Jacobi-Isaacs (HJI) variational inequality (VI) is numerically intractable due to the exponential scaling of computation complexity with problem dimensionality. Furthermore, the single-obstacle HJI VI cannot directly handle situations in which vehicles do not have a common scheduled arrival time. Instead, we perform sequential path planning by considering vehicles in order of priority, modeling higher-priority vehicles as time-varying obstacles for lower-priority vehicles. To do this, we solve a double-obstacle HJI VI which allows us to obtain the reach-avoid set, defined as the set of states from which a vehicle can reach its target while staying within a time-varying state constraint set. From the solution of the double-obstacle HJI VI, we can also extract the latest start time and the optimal control for each vehicle. This is a first application of the double-obstacle HJI VI which can handle systems with time-varying dynamics, target sets, and state constraint sets, and results in computation complexity that scales linearly, as opposed to exponentially, with the number of vehicles in consideration.
AB - We consider the problem of planning trajectories for a group of N vehicles, each aiming to reach its own target set while avoiding danger zones of other vehicles. The analysis of problems like this is extremely important practically, especially given the growing interest in utilizing unmanned aircraft systems for civil purposes. The direct solution of this problem by solving a single-obstacle Hamilton-Jacobi-Isaacs (HJI) variational inequality (VI) is numerically intractable due to the exponential scaling of computation complexity with problem dimensionality. Furthermore, the single-obstacle HJI VI cannot directly handle situations in which vehicles do not have a common scheduled arrival time. Instead, we perform sequential path planning by considering vehicles in order of priority, modeling higher-priority vehicles as time-varying obstacles for lower-priority vehicles. To do this, we solve a double-obstacle HJI VI which allows us to obtain the reach-avoid set, defined as the set of states from which a vehicle can reach its target while staying within a time-varying state constraint set. From the solution of the double-obstacle HJI VI, we can also extract the latest start time and the optimal control for each vehicle. This is a first application of the double-obstacle HJI VI which can handle systems with time-varying dynamics, target sets, and state constraint sets, and results in computation complexity that scales linearly, as opposed to exponentially, with the number of vehicles in consideration.
UR - http://www.scopus.com/inward/record.url?scp=84963830530&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84963830530&partnerID=8YFLogxK
U2 - 10.1109/ECC.2015.7331044
DO - 10.1109/ECC.2015.7331044
M3 - Conference contribution
AN - SCOPUS:84963830530
T3 - 2015 European Control Conference, ECC 2015
SP - 3304
EP - 3309
BT - 2015 European Control Conference, ECC 2015
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - European Control Conference, ECC 2015
Y2 - 15 July 2015 through 17 July 2015
ER -