Laboratório de Análise e Controle de Sistemas a Eventos Discretos


Security verification and reconfiguration of DES

This area of research has currently three ramifications. The first one is related to the application to manufacturing systems.

Manufacturing systems may be subject to external attacks and failures, so it is important to deal with the detection of the attack and recoverability of the system after these situations.

One of the problems that may occur after an attack is the desynchronization of the control structure, called supervisor, with the physical plant. Such desynchronization may be seen as plant and supervisor being in uncorresponding states. The possibility of leading the system to a known state, recovering control, is of extreme importance to the safety of industrial processes. The main idea of this research is to use concepts of synchronizing automata to find synchronizing word, that regardless the state of each one of the subsystems (plant and supervisor), brings the system and supervisor back to a known state.

The second ramification is related to the detection of the attacks in computational systems and the third ramification is related to the design of fault tolerant control for autonomous vehicles under attacks in the communication.

Related works:


UltraDES is an object oriented library composed of data structures and algorithms for the modeling, analysis and control of discrete event systems (DES). The library was developed in C# language and is based on the .NET Framework.

UltraDES can be used in any programming language and platform that supports .NET Standard 2.0, even in mobile environments, like in Android and IOS apps.

The library has several algorithms implemented, most of then used in the Supervisory Control Theory, but also some algorithms and data structures for graphs and petri nets.

Related works:

Task scheduling in Manufacturing Systems using the Supervisory Control of Discrete Event Systems

We develop an approach for the problem of optimal task scheduling in flexible manufacturing systems as a combination of metaheuristic optimization techniques with the supervisory control theory of discrete-event systems.

One of the great problems in optimization is to model the restrictions of the system. The closed loop behavior of the system under the Supervisory Control Theory is used as the search universe for the optimization problem. The optimization algorithm performs the search for the optimal schedules, while the supervisory control has the role of codifying all the problem constraints, allowing an efficient feasibility correction procedure, and avoiding schedules that are sensitive to uncertainties in the execution times associated with the plant operation.

Typically, we deal with makespan, that is the duration of the production of a batch of products. There are a few different directions taken using the same idea.

SCT to model the search universe for classical optimization algorithms

With the search space delimited by the Supervisory Control Solution, we have worked with different evolutionary computation algorithms, such as VNS with a 2-opt local search, Clonal Selection Algorithm, Ant Colony, Tabu Search, among known algorithms from the literature.

Related works:

Maximization of the Parallelism

In this ramification, we also use as the search space to a planning problem, the closed loop behavior of a system under the Supervisory Control Theory. Aiming to minimize makespan, we propose another metric that allows to turn the problem into a path finding problem. This metric relates to the number of devices working in parallel, by adding the information of the number of active tasks in each state of an automaton. States where the machine is idle have 0 active tasks and the states where the machine is working have a nonzero number of active tasks. Algorithms were developed in order to find sequences with high parallelism, that is a suboptimal solution to the problem of minimizing makespan. Three heuristics were developed under the same paradigm.

Logical Parallelism Maximization
Heuristic Makespan Minimization
Paralelism Maximization with Time Restrictions

Related works:


This approach starts from the closed-loop behavior and searches for a production route that minimizes makespan. It uses a divide-and-conquer strategy that allows to decompose the domain into a concatenation of smaller languages, then optimize each of them separately, and finally, concatenate all the partial solutions to get the optimal production route. The decomposition depends on the existence of states with a specific characteristic, the idle states. When they are The proposed method is implemented in an exact algorithm and its performance is tested on a set of benchmark examples.

Related works:


Formal Verification

In this ramification, we study the use of model checking to solve the problem of optimal task scheduling in a flexible manufacturing system. The system is modelled as a discrete event system, and first the least restrictive safe behaviour is synthesised according to supervisory control theory. Timing constraints are added to the model in the form of extended finite-state machines, and time-optimal schedules are computed using the discrete event systems and model checking tool Supremica. Preliminary work was done with the tool Uppaal.

Related works:


Our group is committed to developing solutions that seek immediate application to real problems. Sometimes we do so by applying the concepts in prototypes of industry that we have built in our lab. Sometimes we take industrial case studies from the literature or from industry.

We have developed an algorithm to automatically translate a Blocking Flexible
Job Shop Scheduling Problem modeling into automata using the Supervisory Control Theory. The algorithm is able to interpret the problem data from textual intances and then generating automata that represents the behavior and constraints of the problem.

Another study was done on the parameters that influence the cluster tool performance.
Four different layouts are considered, two of the radial type, with 1 and 2 handler robots,
and two of the linear type, with single input-output and separated input-output. The comparison was based on the makespan and the Relative Accumulated Parallelism of the machines.

Related works:

Abstractions to overcome complexity issues in DES

The closed-loop behavior of a system under the Supervisory Control Theory (SCT) guarantees nonblockingness and safety requirements while implementing the minimally restrictive behavior. Such feature causes the SCT to suffer with the “curse of dimensionality” when systems become bigger and more complex.

The use of abstraction for task scheduling

The closed-loop behavior of a system under the Supervisory Control Theory (SCT) guarantees nonblockingness and safety requirements and, thus, it can be used as the search universe for a planning problem. Abstractions obtained through natural projection with the observer property applied to the closed-loop behavior are used instead, as the search universe for a planning problem. We develop conditions that such abstractions may have. This process leads to a reduction of the search space.

Heuristics to do the search over the abstractions are also developed.

Related works:

The use of abstractions for the nonconflict test

This work proposed an efficient test that uses abstractions to detect conflict in composed systems controlled by local supervisors. This test, called nonconflict test, is not applied over the languages generated by the supervisors, but over abstractions of the supervisors with some specific characteristics, related to the observe property and the sets of events kept by the projection.

Related works:

Verification of the observer property

The observer property is an important condition to be satisfied by abstractions of Discrete Event System (DES) models. We developed a test to find out if an abstraction of a DES obtained through natural projection has the observer property. The procedure, called OP-Verifier, can be applied to (potentially nondeterministic) automata, with quadratic complexity in the number of states.

Also, we developed an algorithm to extends the set of events kept by the projection in order to attain the observer property.

Related works:


We develop prototypes of systems that can be modeled as discrete event systems, aiming to use them in Discrete-Event Systems undergraduate and graduate classes as long as case studies for the research developments.

Flexible Manufacturing System

The Flexible Manufacturing System (FMS) (Queiroz et al., 2005) produces two types of products from raw blocks and raw pegs: a block with a conical pin on top (Product A) and a block with a cylindrical painted pin (Product B). The FMS consists of eight devices. The lathe, the mill, the painting device and the assembling machine perform tasks over the pieces. The pieces are taken from buffers and, after the end of each operation, they are deposited in buffers. The three conveyors and the robot move the pieces from buffers to machines and from machines to buffers. There are 8 buffers that act as intermediate deposits for the pieces, Bi, i = 1,…, 8, each one with capacity for one piece. The arrows, in the diagram below, indicate the events that represent the flow of unfinished parts through the FMS.

Flexible Manufacturing System diagram
Flexible Manufacturing System plant working

Related works:

Other prototypes


Other projects

Solution for the Hanoi Tower problem