Memory efficient symbolic solution of quantitative reach-avoid problems.

Elisei Macoveiciuc and Gunther Reissig.
Memory efficient symbolic solution of quantitative reach-avoid problems.
Proc. American Control Conference (ACC), Philadelphia, U.S.A., 10-12 July 2019, pp. 1671-1677.

Full text. (Definitive publication; restricted access.)

Abstract:
Abstraction-based controller synthesis is an emerging approach to automatically synthesize correct-by-design controllers for a wide class of continuous-state control problems. Its application is currently limited, however, since the number of transitions of non-deterministic discrete abstractions for a state-input pair is exponential in dimension of the state space. In this paper, we present a novel synthesis algorithm for quantitative reach-avoid problems that does not require pre-computation of abstraction or any part of it. Our approach outperforms existing on-the-fly works by the fact that, regardless of the state space dimension, it provably stores at most one transition for any abstract state-input pair at any point in time. Hence, memory-wise, one of ``bottlenecks'' of abstraction-based control is removed. To achieve reasonable time complexity, we place assumptions only on the geometry of the problem data. We illustrate performance of our method on several examples.

BibTeX entry:

@InProceedings{MacoveiciucReissig18aC,
  author = {Elisei Macoveiciuc and Gunther Reissig},
  title  = {Memory efficient symbolic solution of quantitative reach-avoid problems},
booktitle= {Proc. American Control Conference (ACC), Philadelphia, U.S.A., 10-12 July 2019},
  PAGES  = {1671-1677},
   YEAR  = 2019,
   doi   = {10.23919/ACC.2019.8814850}
}

Impressum und Haftungsausschluß