An Algorithm to Compute the Inverse Image of a Point With Respect to a Nondeterministic Max-Plus Linear System

• 成果类型: Article
• 署名作者: Candido, Renato Markele Ferreira; Hardouin, Laurent; Lhommeau, Mehdi; Mendes, Rafael Santos
• 署名单位: Universidade Estadual de Campinas; Universite d'Angers
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2020.2998726
• 发表日期: 2021
• 页码: 1618-1629
• 关键词: Multiprotocol label switching; Complexity theory; Mathematical model; computational modeling; Task analysis; reachability analysis; Linear systems; Inverse image; interval analysis; max-plus linear (MPL) systems; nondeterministic systems

摘要

Max-plus linear (MPL) systems are often described by a transition function, which models the state evolution of the system, and a measurement function, which binds the measures with the system states. Methods for computing the inverse image of a point w.r.t. the measurement function are particularly interesting in applications where it is desirable to obtain information about the system states based on the output observations. The inverse image of a set w.r.t. a nondeterministic MPL system, called uncertain MPL (uMPL) system, can be computed by using the difference-bound matrices (DBM) approach. In this article, we aim to use an interval analysis to propose a method to compute the inverse image of a point w.r.t. an uMPL system. The algorithm proposed has a lower worst-case complexity compared with the DBM approach as previously proposed in the literature.