On the complexity of bounded time and precision reachability for piecewise affine systems

被引：1
|
作者：
Bazille, Hugo [3 ,4 ]
Bournez, Olivier [1 ]
Gomaa, Walid [2 ,5 ]
Pouly, Amaury [1 ]
机构：
[1] Ecole Polytech, LIX, F-91128 Palaiseau, France
[2] Egypt Japan Univ Sci & Technol, CSE, Alexandria, Egypt
[3] ENS Cachan Bretagne, Rennes, France
[4] Univ Rennes 1, Rennes, France
[5] Alexandria Univ, Fac Engn, Alexandria, Egypt
来源：
THEORETICAL COMPUTER SCIENCE | 2018年 / 735卷
关键词：
Complexity; Reachability; Piecewise affine; DYNAMICAL-SYSTEMS;
D O I：
10.1016/j.tcs.2016.09.021
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Reachability for piecewise affine systems is known to be undecidable, starting from dimension 2. In this paper we investigate the exact complexity of several decidable variants of reachability and control questions for piecewise affine systems. We show in particular that the region-to-region bounded time versions leads to NP-complete or co-NP-complete problems, starting from dimension 2. We also prove that a bounded precision version leads to PSPACE-complete problems. (C) 2016 Elsevier B.V. All rights
引用
收藏
页码：132 / 146
页数：15
相关论文
共 50 条
  • [31] Stability analysis of piecewise affine systems with multi-model predictive control
    Petsagkourakis, Panagiotis
    Heath, William Paul
    Theodoropoulos, Constantinos
    AUTOMATICA, 2020, 111
  • [32] On the Reachability of Discrete-Time Switched Linear Systems
    Liu, Chao
    Yang, Zheng
    Sun, Dihua
    Liu, Xiaoyang
    Liu, Wanping
    JOURNAL OF DYNAMICAL AND CONTROL SYSTEMS, 2017, 23 (04) : 815 - 823
  • [33] Reconfigurable control of piecewise affine systems with actuator and sensor faults: Stability and tracking
    Richter, J. H.
    Heemels, W. P. M. H.
    van de Wouw, N.
    Lunze, J.
    AUTOMATICA, 2011, 47 (04) : 678 - 691
  • [34] Model predictive control of piecewise affine systems with constrained input and terminal ellipsoid
    Liu, Zhilin
    Pei, Run
    Zhang, Jun
    Mu, Xiangyong
    WCICA 2006: SIXTH WORLD CONGRESS ON INTELLIGENT CONTROL AND AUTOMATION, VOLS 1-12, CONFERENCE PROCEEDINGS, 2006, : 1338 - +
  • [35] On the Reachability of Discrete-Time Switched Linear Systems
    Chao Liu
    Zheng Yang
    Dihua Sun
    Xiaoyang Liu
    Wanping Liu
    Journal of Dynamical and Control Systems, 2017, 23 : 815 - 823
  • [36] Reachability Properties of Continuous-Time Positive Systems
    Valcher, Maria Elena
    IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2009, 54 (07) : 1586 - 1590
  • [37] Reachability and controllability of discrete-time descriptor systems
    Karampetakis, Nicholas P.
    Gregoriadou, Anastasia
    INTERNATIONAL JOURNAL OF CONTROL, 2014, 87 (02) : 235 - 248
  • [38] Time scale reachability and controllability of time-varying linear systems
    Ben Nasser, Bacem
    Djemai, Mohamed
    Defoort, Michael
    Laleg-Kirati, Taous-Meriem
    ASIAN JOURNAL OF CONTROL, 2022, 24 (05) : 2074 - 2088
  • [39] Bilinearization, Reachability, and Optimal Control of Control-Affine Nonlinear Systems: A Koopman Spectral Approach
    Goswami, Debdipta
    Paley, Derek A.
    IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2022, 67 (06) : 2715 - 2728
  • [40] Reachability Properties of Single-Input Continuous-Time Positive Switched Systems
    Valcher, Maria Elena
    Santesso, Paolo
    IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2010, 55 (05) : 1117 - 1130
12345