Decoding Output Sequences for Discrete-Time Linear Hybrid Systems.
Decoding Output Sequences for Discrete-Time Linear Hybrid Systems.
复制标题
解码离散时间线性混合系统的输出序列。
DOI：
10.1145/3501710.3519530
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Sankaranarayanan, Sriram
中科院分区：
文献类型：
--
作者：
Narasimhamurthy, Monal;Sankaranarayanan, Sriram
本文研究了离散时间随机混合系统的“解码”问题，该系统在每个模态下都具有线性动力学。给定系统的输出轨迹，解码问题寻求构建一个模式和状态序列，以产生与原始输出轨迹“尽可能接近”的轨迹。解码问题推广了状态估计问题，适用于具有不确定性的混合系统。解码问题是np完全的，可以简化为求解一个混合整数线性规划（MILP）。在本文中，我们将解码问题分解为两部分：(a)寻找一系列离散的模式和转换；(b)寻找模态/跃迁序列对应的连续状态。特别是，一旦模式/转换序列固定，“填充”连续状态的问题由线性规划问题执行。为了支持分解，我们用一个有限的子集“覆盖”了所有可能的模式/转换序列的集合。我们使用众所周知的概率论点来证明高置信度的掩护选择，并设计随机算法来寻找这样的掩护。我们的方法在一系列基准测试中得到了证明，其中我们观察到相对很小一部分可能的模式/转换序列可以用作掩护。此外，我们还证明了利用集合覆盖的树形结构可以快速求解得到的线性规划。
In this paper, we study the “decoding” problem for discrete-time, stochastic hybrid systems with linear dynamics in each mode. Given an output trace of the system, the decoding problem seeks to construct a sequence of modes and states that yield a trace “as close as possible” to the original output trace. The decoding problem generalizes the state estimation problem, and is applicable to hybrid systems with non-determinism. The decoding problem is NP-complete, and can be reduced to solving a mixed-integer linear program (MILP). In this paper, we decompose the decoding problem into two parts: (a) finding a sequence of discrete modes and transitions; and (b) finding corresponding continuous states for the mode/transition sequence. In particular, once a sequence of modes/transitions is fixed, the problem of “filling in” the continuous states is performed by a linear programming problem. In order to support the decomposition, we “cover” the set of all possible mode/transition sequences by a finite subset. We use well-known probabilistic arguments to justify a choice of cover with high confidence and design randomized algorithms for finding such covers. Our approach is demonstrated on a series of benchmarks, wherein we observe that relatively tiny fraction of the possible mode/transition sequences can be used as a cover. Furthermore, we show that the resulting linear programs can be solved rapidly by exploiting the tree structure of the set cover.
登录
查看更多内容
线性随机系统的预测运行时监控及其在无人机地理围栏执法中的应用
DOI：
10.1007/978-3-030-32079-9_20
发表时间：
2019
期刊：
Lecture notes in computer science
影响因子：
--
作者：
Yoon, Hansol;Chou, Yi;Chen, Xin;Frew, Eric;Sankaranarayanan, Sriram
通讯作者：
Sankaranarayanan, Sriram
DOI：
10.1109/iros45743.2020.9340755
发表时间：
2020-10
期刊：
2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)
影响因子：
--
作者：
Yi‐Shyong Chou;Hansol Yoon;S. Sankaranarayanan
通讯作者：
Yi‐Shyong Chou;Hansol Yoon;S. Sankaranarayanan
定时和混合自动机的成员资格问题
DOI：
--
发表时间：
1998
期刊：
Proceedings 19th IEEE Real-Time Systems Symposium (Cat. No.98CB36279)
影响因子：
--
作者：
R. Alur;R. Kurshan;Mahesh Viswanathan
通讯作者：
Mahesh Viswanathan
使用基于逻辑的贝叶斯意图推理对移动机器人进行预测运行时监控
DOI：
10.1109/icra48506.2021.9561193
发表时间：
2021
期刊：
2021 IEEE International Conference on Robotics and Automation (ICRA
影响因子：
--
作者：
Yoon, Hansol;Sankaranarayanan, Sriram
通讯作者：
Sankaranarayanan, Sriram
Scarab：基于 SAT 的 CP 系统的工具
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
通讯作者：
--