This paper deals with the online fault diagnosis problem of discrete event systems under malicious external attacks. We consider a scenario where an attacker can intercept certain sensor measurements and alter them ar...
详细信息
This paper deals with the online fault diagnosis problem of discrete event systems under malicious external attacks. We consider a scenario where an attacker can intercept certain sensor measurements and alter them arbitrarily, potentially causing a diagnoser to malfunction. In the framework of labeled Petri nets, a novel integer linear programming problem is formulated by introducing binary variables to estimate the possible transition sequences of an observation that may have been tampered with by an attacker. The proposed approach makes two main contributions. The first one is that, by specifying two different objective functions to the integer linear programming problem, we can obtain the diagnosis results in the presence of attacks, which classic diagnosers may fail to achieve;the second is computational efficiency. In the absence of attacks, the proposed approach is experimentally verified to have lower computational overhead compared with the existing results that are based on integer linear programming and those using basis markings. Finally, the proposed approach is illustrated through a manufacturing system for assembling brake valves.
This study focuses on exhaustive global optimization algorithms over a simplicial feasible set with simplicial partition sets. Bounds on the objective function value and its partial derivative are based on interval au...
详细信息
This study focuses on exhaustive global optimization algorithms over a simplicial feasible set with simplicial partition sets. Bounds on the objective function value and its partial derivative are based on interval automatic differentiation over the interval hull of a simplex. A monotonicity test may be used to decide to either reject a simplicial partition set or to reduce its simplicial dimension to a relative border (at the boundary of the feasible set) facet (or face) by removing one (or more) vertices. A monotonicity test is more complicated for a simplicial sub-set than for a box, because its orientation does not coincide with the components of the gradient. However, one can focus on directional derivatives (DD). In a previous study, we focused on either basic directions, such as centroid to vertex or vertex to vertex directions, or finding the best directional derivative by solving an LP or MIP. The research question of this paper refers to using local search (LS) based sampling of directions from vertex to facet. Results show that most of the monotonic DD found by LP are also found by LS, but with much less computational cost. Notice that finding a monotone direction does not require to find the direction in which a derivative bound is the steepest.
We derive a linear programming bound on the maximum cardinality of error-correcting codes in the sum-rank metric. Based on computational experiments on relatively small instances, we observe that the obtained bounds o...
详细信息
We derive a linear programming bound on the maximum cardinality of error-correcting codes in the sum-rank metric. Based on computational experiments on relatively small instances, we observe that the obtained bounds outperform all previously known bounds.
This study proposes LiP-LLM: integrating linear programming and dependency graph with large language models (LLMs) for multi-robot task planning. For multi-robots to efficiently perform tasks, it is necessary to manag...
详细信息
This study proposes LiP-LLM: integrating linear programming and dependency graph with large language models (LLMs) for multi-robot task planning. For multi-robots to efficiently perform tasks, it is necessary to manage the precedence dependencies between tasks. Although multi-robot decentralized and centralized task planners using LLMs have been proposed, none of these studies focus on precedence dependencies from the perspective of task efficiency or leverage traditional optimization methods. It addresses key challenges in managing dependencies between skills and optimizing task allocation. LiP-LLM consists of three steps: skill list generation and dependency graph generation by LLMs, as well as task allocation using linear programming. The LLMs are utilized to generate a comprehensive list of skills and to construct a dependency graph that maps the relationships and sequential constraints among these skills. To ensure the feasibility and efficiency of skill execution, the skill list is generated by calculated likelihood, and linear programming is used to optimally allocate tasks to each robot. Experimental evaluations in simulated environments demonstrate that this method outperforms existing task planners, achieving higher success rates and efficiency in executing complex, multi-robot tasks. The results indicate the potential of combining LLMs with optimization techniques to enhance the capabilities of multi-robot systems in executing coordinated tasks accurately and efficiently. In an environment with two robots, a maximum success rate difference of 0.82 is observed in the language instruction group with a change in the object name.
An infinite set is orbit-finite if, up to permutations of atoms, it has only finitely many elements. We study a generalisation of linear programming where constraints are expressed by an orbit-finite system of linear ...
详细信息
An infinite set is orbit-finite if, up to permutations of atoms, it has only finitely many elements. We study a generalisation of linear programming where constraints are expressed by an orbit-finite system of linear inequalities. As our principal contribution we provide a decision procedure for checking if such a system has a real solution, and for computing the minimal/maximal value of a linear objective function over the solution set. We also show undecidability of these problems in case when only integer solutions are considered. Therefore orbit-finite linear programming is decidable, while orbit-finite integer linear programming is not.
Women remain significantly underrepresented in the fields of science, technology, engineering and mathematics (STEM), but positive mentoring relationships can help mitigate the challenges they face when studying and w...
详细信息
Women remain significantly underrepresented in the fields of science, technology, engineering and mathematics (STEM), but positive mentoring relationships can help mitigate the challenges they face when studying and working in these areas. To support female university students in STEM, the Auckland University of Technology (AUT) established the Women in Tech mentorship programme in 2019. Initially, the matching of mentees and mentors was achieved manually, but as the programme's popularity grew, this process became increasingly time consuming. This study addresses the challenges associated with assigning mentees to mentors by automating the matching process based on mentee and mentor attributes. A rule-based heuristic is proposed and compared with a linear programming (LP) approach. Numerical experiments were conducted to evaluate the performance of these algorithms across various scenarios. The rule-based heuristic provides a simple and easily understandable way to allocate mentees and mentors that performs nearly as well as an optimal matching provided by the LP approach. Applying these algorithms to real data from the AUT Women in Tech mentorship programme, it was found that they outperformed manual matching in several performance metrics.
In this paper, we use a linear programming (LP) optimization approach to evaluate the equivocation when coding over a wiretap channel model where the main channel is noiseless and the eavesdropper's channel is a b...
详细信息
In this paper, we use a linear programming (LP) optimization approach to evaluate the equivocation when coding over a wiretap channel model where the main channel is noiseless and the eavesdropper's channel is a binary symmetric channel (BSC). Using this technique, we present a numerically-derived upper bound for the achievable secrecy rate in the finite blocklength regime that is tighter than traditional infinite blocklength bounds. We also propose a secrecy coding technique that outperforms random binning codes. When there is one overhead bit, this coding technique is optimum and achieves the newly derived bound. For cases with additional bits of overhead, our coding scheme can achieve equivocation rates close to the new bound. Furthermore, we explore the patterns of the generator matrix and the parity-check matrix for linear codes and we present binning techniques for both linear and nonlinear codes using two different approaches: recursive and non-recursive. To our knowledge, this is the first optimization solution for secrecy coding obtained through linear programming. Our new bounds and codes mark a significant breakthrough towards understanding fundamental limits of performance (and how to achieve them in some instances) for the binary symmetric wiretap channel with real finite blocklength coding constructions. Our techniques are especially useful for codes of small to medium blocklength, such as those that may be required by applications with small payloads, such as the Internet of Things.
We propose an adaptation of the Feasible Direction Interior Points Algorithm (FDIPA) of J. Herskovits, for solving large-scale linear programs. At each step, the solution of two linear systems with the same coefficien...
详细信息
We propose an adaptation of the Feasible Direction Interior Points Algorithm (FDIPA) of J. Herskovits, for solving large-scale linear programs. At each step, the solution of two linear systems with the same coefficient matrix is determined. This step involves a significant computational effort. Reducing the solution time of linear systems is, therefore, a way to improve the performance of the method. The linear systems to be solved are associated with definite positive symmetric matrices. Therefore, we use Split Preconditioned Conjugate Gradient (SPCG) method to solve them, together with an Incomplete Cholesky preconditioner using Matlab's ICHOL function. We also propose to use the first iteration of the conjugate gradient, and to presolve before applying the algorithm, in order to reduce the computational cost. Following, we then provide mathematica proof that show that the iterations approach Karush-Kuhn-Tucker points of the problem under reasonable assumptions. Finally, numerical evidence show that the method not only works in theory but is also competitive with more advanced methods.
While quantum weight enumerators establish some of the best upper bounds on the minimum distance of quantum error-correcting codes, these bounds are not optimized to quantify the performance of quantum codes under the...
详细信息
While quantum weight enumerators establish some of the best upper bounds on the minimum distance of quantum error-correcting codes, these bounds are not optimized to quantify the performance of quantum codes under the effect of arbitrary quantum channels that describe bespoke noise models. Herein, for any Kraus decomposition of any given quantum channel, we introduce corresponding quantum weight enumerators that naturally generalize the Shor-Laflamme quantum weight enumerators. We establish an indirect linear relationship between these generalized quantum weight enumerators by introducing an auxiliary exact weight enumerator that completely quantifies the quantum code's projector, and is independent of the underlying noise process. By additionally working within the framework of approximate quantum error correction, we establish a general framework for constructing a linear program that is infeasible whenever approximate quantum error correcting codes with corresponding parameters do not exist. Our linear programming framework allows us to establish the non-existence of certain quantum codes that approximately correct amplitude damping errors, and obtain non-trivial upper bounds on the maximum dimension of a broad family of permutation-invariant quantum codes.
This paper presents the practical consensus of T-S fuzzy positive multi-agent systems with interval type-1 and type-2 fuzzy sets using observer-based control protocols. A fuzzy positive observer is first constructed f...
详细信息
This paper presents the practical consensus of T-S fuzzy positive multi-agent systems with interval type-1 and type-2 fuzzy sets using observer-based control protocols. A fuzzy positive observer is first constructed for the systems. An observer-based fuzzy control protocol is designed, where an additional constant term is introduced. Some linear programming conditions are established to achieve the positivity of the original system and its observer. Then, the practical consensus of the original system is transformed into the stability of a dynamic system, where a set of new variables is defined by combining the constant term and the states of the agents. In the first step, the positivity of the new variables is guaranteed. In the second step, the stability of the dynamic system consisting new variables is addressed by using a fuzzy copositive Lyapunov function. The gain matrices of observer and control protocols are formulated based on a matrix decomposition approach. All positive and consensus conditions are described via linear programming. Finally, two examples are provided to verify the validity of the obtained results.
暂无评论