检索结果-内蒙古大学图书馆

SMT-based and fixed-point approaches for state estimation in max-plus linear systems

DISCRETE EVENT DYNAMIC systems-THEORY AND APPLICATIONS 2025年 1-17页

作者： Espindola-Winck, Guilherme Hardouin, Laurent Lhommeau, Mehdi Univ Lille CNRS Cent Lille UMR 9189CRIStAL F-59000 Lille France Univ Angers LARIS SFR MATHST F-49000 Angers France

This work builds on the seminal paper (Winck et al. IFAC-PapersOnLine 58(1):36-41 2024) and evaluates an existing method against a new approach for state estimation in max-plus linear systems with bounded uncertainties. Traditional stochastic filtering is inapplicable to this system class, even though the posterior probability density function (PDF) can be computed. Previous research has shown a limited scalability of the disjunctive approach using difference-bound matrices. To address this, we investigate an alternative method recently explored in Mufid et al. (IFAC-PapersOnLine 53(4):459-465 2020, IEEE Trans Autom Control 67(6):2700-2714 2022), employing Satisfiability Modulo Theory (SMT) techniques, despite their NP-hard nature. The main novelty of this work is the proposal of a concise method based on fixed-point iteration in max-plus algebra, which is known to be a pseudo-polynomial time algorithm. To compare both approaches, a representative autonomous system is used in the paper to illustrate the basic computations. The efficiency of both approaches is compared through numerical experiments.

关键词： max-plus linear systems State-estimation Satisfiability modulo theories Fixed point algorithm

来源：评论

学校读者我要写书评

暂无评论

Modeling and analysis of switching max-plus linear systems with discrete-event feedback

引用

DISCRETE EVENT DYNAMIC systems-THEORY AND APPLICATIONS 2023年第3期33卷 341-372页

作者： Mohamadkhani, Alireza Geilen, Marc Voeten, Jeroen Basten, Twan Eindhoven Univ Technol Dept Elect Engn Eindhoven Netherlands ESI TNO Eindhoven Netherlands

Switching max-plus linear system (SMPLS) models are an apt formalism for performance analysis of discrete-event systems. SMPLS analysis is more scalable than analysis through other formalisms such as timed automata, because SMPLS abstract pieces of determinate concurrent system behavior into atomic modes with fixed timing. We consider discrete-event systems that are decomposed into a plant and a Supervisory Controller (SC) that controls the plant. The SC needs to react to events, concerning e.g. the successful completion or failure of an action, to determine the future behavior of the system, for example, to initiate a retrial of the action. To specify and analyze such system behavior and the impact of feedback on timing properties, we introduce an extension to SMPLS with discrete-event feedback. In this extension, we model the plant behavior with system modes and capture the timing of discrete-event feedback emission from plant to SC in the mode matrices. Furthermore, we use I/O automata to capture how the SC responds to discrete-event feedback with corresponding mode sequences of the SMPLS. We define the semantics of SMPLS with events using new state-space equations that are akin to classical SMPLS with dynamic state-vector sizes. To analyze the extended models, we formulate a transformation from SMPLS with events to classical SMPLS with equivalent semantics and properties such that performance properties can be analyzed using existing techniques. Our approach enables the specification of discrete-event feedback from the plant to the SC and its performance analysis. We demonstrate our approach by specifying and analyzing the makespan of a flexible manufacturing system.

关键词： max-plus linear systems Modeling and analysis Discrete event systems Flexible manufacturing systems

来源：评论

学校读者我要写书评

暂无评论

Optimistic optimization for model predictive control of max-plus linear systems

引用

AUTOMATICA 2016年 74卷 16-22页

作者： Xu, Jia van den Boom, Ton De Schutter, Bart Delft Univ Technol Delft Ctr Syst & Control Delft Netherlands

Model predictive control for max-plus linear discrete-event systems usually leads to a nonsmooth nonconvex optimization problem with real valued variables, which may be hard to solve efficiently. An alternative approach is to transform the given problem into a mixed integer linear programming problem. However, the computational complexity of current mixed integer linear programming algorithms increases in the worst case exponentially as a function of the prediction horizon. The focus of this paper is on making optimistic optimization suited to solve the given problem. Optimistic optimization is a class of algorithms that can find an approximation of the global optimum for general nonlinear optimization. A key advantage of optimistic optimization is that one can specify the computational budget in advance and guarantee bounds on the suboptimality with respect to the global optimum. We prove that optimistic optimization can be applied for the given problem by developing a dedicated semi-metric and by proving it satisfies the necessary requirements for optimistic optimization. Moreover, we show that the complexity of optimistic optimization is exponential in the control horizon instead of the prediction horizon. Hence, using optimistic optimization is more efficient when the control horizon is small and the prediction horizon is large. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： max-plus linear systems Model predictive control Optimistic optimization

来源：评论

学校读者我要写书评

暂无评论

Model Predictive Control for Stochastic max-plus linear systems With Chance Constraints

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2019年第1期64卷 337-342页

作者： Xu, Jia van den Boom, Ton De Schutter, Bart Delft Univ Technol Delft Ctr Syst & Control NL-2628 CD Delft Netherlands

The topic of this paper is model predictive control (MPC) for max-plus linear systems with stochastic uncertainties the distribution of which is supposed to be known. We consider linear constraints on the inputs and the outputs. Due to the uncertainties, these linear constraints are formulated as probabilistic or chance constraints, i.e., the constraints are required to be satisfied with a predefined probability level. The proposed chance constraints can be equivalently rewritten into a maxaffine (i.e., the maximum of affine terms) form if the linear constraints are monotonically nondecreasing as a function of the outputs. Based on the resulting max-affine form, two methods are developed for solving the chance-constrained MPC problem for stochastic max-plus linear systems. Method 1 uses Boole's inequality to convert the multivariate chance constraint into univariate chance constraints for which the probability can be computed more efficiently. Method 2 employs Chebyshev's inequality and transforms the chance constraint into linear constraints on the inputs. The simulation results for a production system example show that the two proposed methods are faster than the Monte Carlo simulation method and yield lower closed-loop costs than the nominal MPC method.

关键词： Constrained control discrete-event systems max-plus linear systems nonlinear predictive control stochastic optimal control

来源：评论

学校读者我要写书评

暂无评论

Locally and globally optimal solutions of global optimisation for max-plus linear systems

引用

IET CONTROL THEORY AND APPLICATIONS 2022年第2期16卷 219-228页

作者： Wang, Cailu Tao, Yuegang Beijing Inst Technol Sch Automat Beijing Peoples R China Hebei Univ Technol Sch Artificial Intelligence Tianjin 300130 Peoples R China

This paper considers the locally and globally optimal solutions of the global optimisation problem whose objective function is a max-plus vector-valued function and constraint function is a real affine function. The formulas about global optimisation in the existing work are further explained and simplified. The necessary and sufficient conditions for the existence and uniqueness of locally optimal solutions of a single objective are established, which are then used to deduce these of globally optimal solutions. Furthermore, the general formulas of locally and globally optimal solutions are presented, respectively. The local optimisation is then applied to solve the load distribution problem of distributed systems with no globally optimal solution, and the optimal allocation scheme is proposed to complete the overall task at the earliest time. The proposed method is constructive, and the obtained results are illustrated by the numerical examples.

关键词： affine function load distribution sufficient conditions linear systems vectors locally optimal solution globally optimal solution optimisation max-plus vector-valued function objective function local optimisation optimal allocation constraint function max-plus linear systems distributed systems necessary conditions global optimisation

来源：评论

学校读者我要写书评

暂无评论

A Compositional Model for Multi-Rate max-plus linear systems 15th

A Compositional Model for Multi-Rate Max-Plus Linear Systems

引用

15th IFAC Workshop on Discrete Event systems (WODES)

作者： Elahi, H. Geilen, M. Basten, T. Eindhoven Univ Technol Eindhoven Netherlands TNO ESI Eindhoven Netherlands

The timing of discrete-event systems with synchronization is naturally modeled with canonical multi-rate max-plus linear equations. The main objectives of these models are to analyze and control the systems. As a system becomes more complex, determining its canonical model becomes more complicated. Moreover, these systems may change over time which demands the model to be recalculated. Motivated by the compositional structure of many systems, we propose operations to determine the canonical model for composed multi-rate maxplus linear systems. The operations allow efficient (re-)calculation of the canonical models from constituent canonical models. These models can be utilized to analyze and/or control complex systems using existing methods. Copyright (C) 2020 The Authors.

关键词： Discrete-event systems max-plus linear systems Compositional models

来源：评论

学校读者我要写书评

暂无评论

Symbolic Reachability Analysis of High Dimensional max-plus linear systems 15th

Symbolic Reachability Analysis of High Dimensional Max-Plus ...

引用

15th IFAC Workshop on Discrete Event systems (WODES)

作者： Mufid, Muhammad Syifa'ul Adzkiya, Dieky Abate, Alessandro Univ Oxford Dept Comp Sci Oxford England ITS Surabaya Dept Math Surabaya Indonesia

This work discusses the reachability analysis (RA) of max-plus linear (MPL) systems, a class of continuous-space, discrete-event models defined over the max-plus algebra. Given the initial and target sets, we develop algorithms to verify whether there exist trajectories of the MPL system that, starting from the initial set, eventually reach the target set. We show that RA can be solved symbolically by encoding the MPL system, as well as initial and target sets into difference logic, and then checking the satisfaction of the resulting logical formula via an off-the-shelf satisfiability modulo theories (SMT) solver. The performance and scalability of the developed SMT-based algorithms are shown to clearly outperform state-of-the-art RA algorithms for MPL systems, newly allowing to investigate RA of high-dimensional MPL systems: the verification of models with more than 100 continuous variables shows the applicability of these techniques to MPL systems of industrial relevance. Copyright (C) 2020 The Authors.

关键词： max-plus linear systems reachability analysis piecewise-affine systems difference-bound matrices difference logic satisfiability modulo theories

来源：评论

学校读者我要写书评

暂无评论

Structural Controllability of Switching max-plus linear systems 21st

Structural Controllability of Switching Max-Plus Linear Syst...

引用

21st IFAC World Congress on Automatic Control - Meeting Societal Challenges

作者： Gupta, Abhimanyu van den Boom, Ton van der Woude, Jacob De Schutter, Bart Delft Univ Technol Delft Ctr Syst & Control Delft Netherlands Delft Univ Technol DIAM EWI Van Mourik Broekmanweg 6 NL-2628 XE Delft Netherlands

We introduce a framework for studying controllability properties of discrete-event systems modelled as switching max-plus linear systems. In this framework, we generalise the notion of structural controllability to include the switching phenomenon. Such models provide an additional discrete input to change the synchronisation and/or ordering constraints of the system. In this paper, we solve the problem of assigning the throughput of the system by suitable controller configurations. In particular, we formulate structural conditions for the existence of controllers achieving stable stationary behaviour. We also classify the achievable throughput under different controller configurations. Copyright (C) 2020 The Authors.

关键词： Discrete event systems max-plus linear systems switching structural properties controllability

来源：评论

学校读者我要写书评

暂无评论

Comparing Disjunctive and Concise Approaches for Set-Guaranteed Estimation in max-plus linear systems 17

Comparing Disjunctive and Concise Approaches for Set-Guarant...

引用

17th IFAC Workshop on discrete Event systems (WODES)

作者： Espindola-Winck, Guilherme Hardouin, Laurent Lhommeau, Mehdi Univ Lille CNRS Cent Lille UMR CRIStAL 9189 F-59000 Lille France Univ Angers LARIS SFR MATHSTIC F-49000 Angers France

This study compares an existing method with a novel approach for state estimation of max-plus linear systems with bounded uncertainties. Traditional stochastic filtering does not apply to this system class, despite computable posterior probability density function (PDF) support. Existing literature suggests a limited scalability disjunctive approach using difference-bound matrices. To overcome this, we study an alternative method recently investigated in Mufid et al. (2022) using Satisfiability Modulo Theory (SMT) techniques, which are known to be NP-hard. We propose a concise method that utilizes a pseudo-polynomial time algorithm using max-plus algebra. We evaluate its efficiency against SMT techniques through numerical experiments involving sparse matrix multiplications for enhanced computational speed.

关键词： max-plus linear systems State-Estimation Satisfiability Modulo Theories Fixed point algorithm

来源：评论

学校读者我要写书评

暂无评论

Comparing Disjunctive and Concise Approaches for Set-Guaranteed Estimation in max-plus linear systems

引用

IFAC-PapersOnLine 2024年第1期58卷 36-41页

作者： Guilherme Espindola-Winck Laurent Hardouin Mehdi Lhommeau Univ. Lille CNRS Centrale Lille UMR 9189 CRIStAL F-59000 Lille France Univ. Angers LARIS SFR MATHSTIC F-49000 Angers France

关键词： max-plus linear systems State-Estimation Satisfiability Modulo Theories Fixed point algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：