Computation of an over-approximation of the backward reachable set using subsystem level set functions

Dušan M. Stipanović, Inseok Hwang, Claire J. Tomlin

Research output: Contribution to journalArticlepeer-review


In this paper, we present a method to decompose the problem of computing the backward reachable set for a dynamic system in a space of a given dimension, into a set of computational problems involving level set functions, each defined in a lower dimensional (subsystem) space. This allows the potential for great reduction in computation time. The overall system is considered as an interconnection of either disjoint or overlapping subsystems. The projection of the backward reachable set into the subsystem spaces is over-approximated by a level set of the corresponding subsystem level set function. It is shown how this method can be applied to two-player differential games. Finally, results of the computation of polytopic over-approximations of the unsafe set for the two aircraft conflict resolution problem are presented.

Original languageEnglish (US)
Pages (from-to)399-411
Number of pages13
JournalDynamics of Continuous, Discrete and Impulsive Systems Series A: Mathematical Analysis
Issue number2-3
StatePublished - Apr 1 2004
Externally publishedYes


  • Interconnected systems
  • Over-approximations
  • Reachable sets

ASJC Scopus subject areas

  • Analysis
  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Computation of an over-approximation of the backward reachable set using subsystem level set functions'. Together they form a unique fingerprint.

Cite this