Observability and Detectability of Stochastic Labeled Graphs

• 成果类型: Article
• 署名作者: Zhu, Shiyong; Cao, Jinde; Lin, Lin; Rutkowski, Leszek; Lu, Jianquan; Lu, Guoping
• 署名单位: City University of Hong Kong; Southeast University - China; Southeast University - China; Purple Mountain Laboratories; Yonsei University; University of Hong Kong; Polish Academy of Sciences; Systems Research Institute of the Polish Academy of Sciences; AGH University of Krakow; University of Social Sciences; Southeast University - China; Nantong University; Nantong University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2023.3278797
• 发表日期: 2023
• 页码: 7299-7311
• 关键词: Colored graphs; Detectability; discrete-time and discrete-state dynamic systems; minimal sensors placement problem; NP-hardness; observability

摘要

In this article, observable stochastic graphs and detetectable stochastic graphs are, respectively, defined with the detailed implementation for the observability and detectability of stochastic discrete-time and discrete-state dynamic systems. More specifically, they are generally two classes of vertex-colored and edge-labeled graphs rendering a walking agent therein to determine his initial and current positions, respectively, in probability one by measuring the color sequence of his traversed vertices. In the part of analysis, we follow the aforementioned two definitions and establish the corresponding polynomial-time verifying algorithms. Notably, the implicit formulas are also established to calculate the observability and detectability probability for any pairwise vertex pair. In the synthesis part, the minimal number of colors dyeing the vertices to make the considered graph stochastically observable and detectable is investigated, respectively. Our results indicate that the minimal coloring problem is NP-hard for observability in the stochastic situations but is solvable in polynomial time for detectability in the deterministic cases. The observability and detectability of stochastic finite-valued systems, assembling with the finite-cardinal state spaces, are validated as a compelling application of these two types of directed graphs, whereas the minimal sensors placement problems subject to observability and detectability problems are accordingly interpreted by the minimum set cover algorithm.