Overcoming controllability problems in distributed testing from an input output transition system

This paper concerns the testing of a system with physically distributed interfaces, called ports, at which it interacts with its environment. We place a tester at each port and the tester at port p observes events at p only. This can lead to controllability problems, where the observations made by the tester at a port p are not sufficient for it to be able to know when to send an input. It is known that there are test objectives, such as executing a particular transition, that cannot be achieved if we restrict attention to test cases that have no controllability problems. This has led to interest in schemes where the testers at the individual ports send coordination messages to one another through an external communications network in order to overcome controllability problems. However, such approaches have largely been studied in the context of testing from a deterministic finite state machine. This paper investigates the use of coordination messages to overcome controllability problems when testing from an input output transition system and gives an algorithm for introducing sufficient messages. It also proves that the problem of minimising the number of coordination messages used is NP-hard.     

Using status messages in the distributed test architecture

If the system under test has multiple interfaces/ports and these are physically distributed then in testing we place a tester at each port. If these testers cannot directly communicate with one another and there is no global clock then we are testing in the distributed test architecture. If the distributed test architecture is used then there may be input sequences that cannot be applied in testing without introducing controllability problems. Additionally, observability problems can allow fault masking. In this paper we consider the situation in which the testers can apply a status message: an input that causes the system under test to identify its current state. We show how such a status message can be used in order to overcome controllability and observability problems.     

Constructing checking sequences for distributed testing

The objective of testing is to determine whether an implementation under test conforms to its specification. In distributed test architectures involving multiple remote testers, this objective can be complicated by the fact that testers may encounter coordination problems relating to controllability (synchronization) and observability during the application of tests. Based on a finite state machine (FSM) specification of the externally observable behaviour of a distributed system and a distinguishing sequence, this paper proposes a method for constructing a checking sequence where there is no potential controllability or observability problems, and where the use of external coordination message exchanges among testers is minimized. The proposed method does not assume a reliable reset feature in the implementations of the given FSM to be tested by the resulting checking sequence. phone: 613-562-5800(Extn)6684 Received May 2004 Revised March 2005 Accepted April 2005 by J. Derrick, M. Harman and R. M. Herons     

Checking sequences for distributed test architectures

Controllability and observability problems may manifest themselves during the application of a checking sequence in a test architecture where there are multiple remote testers. These problems often require the use of external coordination message exchanges among testers during testing. However, the use of coordination messages requires the existence of an external network that can increase the cost of testing and can be difficult to implement. In addition, the use of coordination messages introduces delays and this can cause problems where there are timing constraints. Thus, sometimes it is desired to construct a checking sequence from the specification of the system under test that will be free from controllability and observability problems without requiring the use of external coordination message exchanges. This paper gives conditions under which it is possible to produce such a checking sequence, using multiple distinguishing sequences, and an algorithm that achieves this.     

On the controllability and observability of discrete-time linear time-delay systems

This article studies the controllability and observability of discrete-time linear time-delay systems, so that the two properties can play a more fundamental role in system analysis before controller and observer design is engaged. Complete definitions of controllability and observability, which imply the stabilisability and detectability, respectively, and determine the feasibility of eigenvalue assignment, are proposed for systems with delays in both state variables and input/output signals. Necessary and sufficient criteria are developed to check the controllability and observability efficiently. The proofs are based on the equivalent expanded system, but the criteria only involve the delays and matrices of the same dimension as the original system. Finally, the duality between the suggested controllability and observability is presented.     

Overcoming controllability problems with fewest channels between testers

When testing a system that has multiple physically distributed ports/interfaces it is normal to place a tester at each port. Each tester observes only the events at its port and it is known that this can lead to additional controllability problems. While such controllability problems can be overcome by the exchange of external coordination messages between the testers, this requires the deployment of an external network and may thus increase the costs of testing. The problem studied in this paper is finding a minimum number of coordination channels to overcome controllability problems in distributed testing. Three instances of this problem are considered. The first problem is to find a minimum number of channels between testers in order to overcome the controllability problems in a given test sequence to be applied in testing. The second problem is finding a minimal set of channels that allow us to overcome controllability problems in any test sequence that may be selected from the specification of the system under test. The last problem is to find a test sequence that achieves a particular test objective and in doing so allows fewest channels to be used.     

Distributed testing without encountering controllability and observability problems

The objective of testing is to determine whether a system under test conforms to its specification. In distributed test architectures that utilize remote testers, this objective can be complicated by the fact that testers may encounter problems relating to controllability and observability during the application of a test sequence. Existing solutions to these problems involve first constructing a test sequence from the specification of an implementation under test, and then inserting coordination messages or appending selected test subsequences that prevent the occurrences of controllability and observability problems during the application of the resulting test sequence. This paper proposes a method that utilizes a set of transformation rules to construct an auxiliary directed graph from a given specification, and constructs a rural Chinese postman tour in this graph to yield a minimum-length test sequence where there is no potential controllability or observability problems, and where the use of coordination messages is minimized.     

On the input and output reducibility of multivariable linear systems

By introducing into a constant linear system (F, G, H) with input vectoruand output vectoryan open-loop controlu = Pvand observerz = Qy, a new constant linear system (F, GP, QH) results which has input vectorupsilonand output vectorz. The problem investigated is one of constructing (F, GP, QH) so thatupsilonandzhave minimal dimension, subject to the condition that the controllability and observability properties of (F, G, H) are preserved. It is shown that when the scalar fieldF(over which the system is defined) is infinite, the minimal dimensions ofupsilonandzare essentially independent of the specific values of the input and output matricesGandH. It is also shown that this is not the case whenFis finite. Furthermore, an algorithm is presented for the construction of the minimal input (minimal output) (F, GP, QH), which is directly represented in a useful canonical form.     

网络调度中的能控性与能观性研究

为了研究网络调度对能控性与能观性的影响,对输入、输出通道都存在通信约束的网络控制系统的调度进行建模;利用通信序列表示通道的调度情况,最终将模型转化为离散切换系统;在静态调度下,利用循环不变子空间理论及其相关的性质,给出了网络控制系统能控性、能观性成立的充要条件,并给出了原有控制系统与经网络静态调度后的系统之间能控性、能观性的关系;最后用仿真实例说明了所提结论的正确性。     

The robustness of controllability and observability of linear time-varying systems

Fixed point methods from nonlinear analysis are used to establish conditions under which the uniform complete controllability, of linear time-varying systems is preserved under nonlinear perturbations in the state dynamics and the zero-input uniform complete observability of linear time-varying systems is preserved under nonlinear perturbation in the state dynamics and output read-out map. Robustness of partial controllability., observability, and a specific kind of nonzero input observability are also proven.     

On multivariable linear systems

A general result in linear system theory concerning the controllability and observability of multi-input multi-output systems is presented. Specifically, it is shown that any controllable observable linear system can be made controllable from any input and observable from any output using output feedback.     

Controllability and observability of 2D thermal flow in bulk storage facilities using sensitivity fields

To control and observe spatially distributed thermal flow systems, the controllable field and observable field around the actuator and sensor are of interest, respectively. For spatially distributed systems, the classical systems theoretical concepts of controllability and observability are, in general, difficult to apply. In this study, sensitivity fields were used to analyse the behaviour from input to state and from initial state to output. For the analysis of controllability and observability, a large-scale, bulk storage facility with coupled thermal flow of air and agro-products was used. Analysis of this system using the classical systems theory results in controllability and observability results that are dependent on the step size of the spatially discretised system. Due to matrix multiplications, inaccurate results are calculated if the step size is too small. Our findings indicate that input-state and initial-state output sensitivity fields provide sufficient information about the controllability and observability of large coupled spatially distributed systems, using finite-dimensional state space representation with small discretisation steps.     

Output regulation for linear singular systems using dual-observer based compensators

In this article, the output regulation problem is solved for singular systems by using dual observer-based compensators. This has the advantage that output regulation can be achieved under weak conditions. Namely, different from previous approaches, an implementable compensator can be directly determined in form of a classical state space model without a transformation into Weierstrass–Kronecker canonical form. Furthermore, the impulse controllability and observability of the singular system is not required and the output to be controlled needs not be measurable. The results of the article are demonstrated by means of a simple mechanical system.     

An analysis technique to increase testability of object‐oriented components

Object‐oriented component engineering is increasingly used for system development, partly because it emphasizes portability and reusability. Each time a component is used, it must be retested in the new environment. Unfortunately, the data abstraction that components usually use results in low testability. First, internal variables cannot be directly set. Second, even though a test input may trigger a fault, the failure does not propagate to the output. This paper presents a technique to increase object‐oriented component testability, thereby making it easier to detect faults. Components are often sealed so that source code is not available. The program analysis is performed at the Java component bytecode level. A component's bytecode is analysed to create a control and data flow graph, which is then used to increase component testability by increasing both controllability and observability. We have implemented this technique and applied it to several components. Experimental results reveal that fault detection can be increased by using our increasing testability process. Copyright © 2008 John Wiley & Sons, Ltd.     

A temporal approach for testing distributed systems

This paper deals with testing distributed software systems. In the past, two important problems have been determined for executing tests using a distributed test architecture: controllability and observability problems. A coordinated test method has subsequently been proposed to solve these two problems. In the present article: 1) we show that controllability and observability are indeed resolved if and only if the test system respects timing constraints, even when the system under test is non-real-time; 2) we determine these timing constraints; 3) we determine other timing constraints which optimize the duration of test execution; 4) we show that the communication medium used by the test system does not necessarily have to be FIFO; and 5) we show that the centralized test method can be considered just as a particular case of the proposed coordinated test method.     

Observability for two-dimensional systems

Sufficient conditions that a two-dimensional system with output is locally observable are presented. Known results depend on time derivatives of the output and the inverse function theorem. In some cases, no information is provided by these theories, and one must study observability by other methods. We dualize the observability problem to the controllability problem, and apply the deep results of Hermes on local controllability to prove a theorem concerning local observability.Research supported by NASA Ames Research Center under Grant NAG2-189 and the Joint Services Electronics Program under ONR Contract N0014-76-C1136.Research supported by NASA Ames Research Center under Grant NAG2-203 and the Joint Services Electronics Program under ONR Contract N0014-76-C1136.     

A novel matrix approach to observability analysis of finite automata

In this paper, the observability of finite automata (acronym is FA) that contain both deterministic finite automata and non-deterministic finite automata is investigated under the framework of the semi-tensor product of matrices. For both initial state and current state cases, two different observability definitions with or without input information are considered, respectively. First, we show that how the observability problem of initial state of FA can be transformed to the construction problem of an initial state-outputs matrix that presents the relationship between initial state and outputs. Second, a current state-outputs matrix to verify the observability problem of current state is given. When two matrices are obtained, four theorems to verify the observability of initial state and current state are presented, respectively. In particular, compared with the existing approach, the proposed approach not only provides a unified verification for the two types of observability of both initial state and current state but also reduces the computational complexity considerably. An illustrative example is presented to show the theoretical results.     

Robust controllability and observability degrees of polynomially uncertain systems

This paper deals with the class of polynomially uncertain continuous-time linear time-invariant (LTI) systems whose uncertainties belong to a semi-algebraic set. The objective is to determine the minimum of the smallest singular value of the controllability or observability Gramian over the uncertainty region. This provides a quantitative measure for the robust controllability or observability degree of the system. To this end, it is shown that the problem can be recast as a sum-of-squares (SOS) problem. In the special case when the uncertainty region is polytopic, the corresponding SOS formulation can be simplified significantly. One can apply the proposed method to any large-scale interconnected system in order to identify those inputs and outputs that are more effective in controlling the system, in a robust manner. This enables the designer to simplify the control structure by ignoring those inputs and outputs whose contribution to the overall control operation is relatively weak. A numerical example is presented to demonstrate the efficacy of the results.     

Vulnerability of dynamic systems†

The purpose of this paper is to formulate and partially resolve the problem of vulnerability of dynamic systems in the context of the theory of directed graphs. A system is considered vulnerable if its structural properties such as input (output) reachability or structural controllability (observability) is destroyed by a perturbation characterized as removal of a line, or set of lines, from the corresponding graph. Graph-theoretic procedures are developed to identify the minimal sets of lines which are essential for preserving the structural properties of the system.