Safe sequential path planning of multi-vehicle systems via double-obstacle Hamilton-Jacobi-Isaacs variational inequality

Mo Chen, Jaime F. Fisac, Shankar Sastry, Claire J. Tomlin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

52 Scopus citations


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.

Original languageEnglish (US)
Title of host publication2015 European Control Conference, ECC 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9783952426937
StatePublished - Nov 16 2015
Externally publishedYes
EventEuropean Control Conference, ECC 2015 - Linz, Austria
Duration: Jul 15 2015Jul 17 2015

Publication series

Name2015 European Control Conference, ECC 2015


ConferenceEuropean Control Conference, ECC 2015

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering


Dive into the research topics of 'Safe sequential path planning of multi-vehicle systems via double-obstacle Hamilton-Jacobi-Isaacs variational inequality'. Together they form a unique fingerprint.

Cite this