Flexible Manufacturing Systems, Controller Synthesis.

Abstract

In this work the problem of the coordination in industrial multi-robot systems is analyzed, that is to say the coordination of several robots that have to perform different tasks in the same workspace.

A methodology is presented, for off-line coordination of several robots interacting in a 3D environment. In particular, parts of the 3D space in which the robots could collide are found out (mutex zones) and automata models for the robots tasks and for the zones created are built. Then, the tasks for each robot are scheduled in order to minimize the time of execution of all the tasks, preventing collisions and blocking situations. Since the complexity of the problem is very large, automatic procedures are needed. This is done with the help of a software named RobotStudio, provided by ABB Robotics, for three dimensional simulations, and with Supremica, a software program developed at the Department of Signals and Systems at Chalmers University of Technology in Gothenburg, for the analysis of automata and Petri nets.

The main result of the work is the automatic synthesis of a discrete event controller that optimizes the total time of work and guarantees that the multi-robot system is collision free and non-blocking. Future work can regard optimal choice of zones of mutual exclusions and simulations in a parallel environment for the robots.

Keywords: Discrete Event Systems, Robots Simulation, Motion Planning, Scheduling,

Flexible Manufacturing Systems, Controller Synthesis.

Acknowledgements

First of all, I would like to express my gratitude to the people that gave me the big opportunity to make this work. I would like to thank Prof. Bengt Lennartson for his trust in me from the beginning and for having made my life in Gothenburg easier. I would like to thank Prof. Mario Innocenti because he fully supported the idea of this work and for being a constant professional support.

Then, I would like to thank Assistant Prof. Knut Åkesson for his invaluable help and for the supervision of the work.

A particular thanking goes to Hugo Flordal for the time spent with me in silence and not.

The discussions with him have often led to new ideas.

I would also like to thank all the people at the Automation Group of the Department of Signals and Systems at Chalmers University of Technology for having made the life at the Department more pleasant, and, in particular, Associate Prof. Martin Fabian, Arash Vahidi, and Johan Richardsson for the ideas shared in the “discrete group” meetings.

Finally, but first in importance, I would like to thank every single member of my family for the unconditional love and support that they have been giving me during all the time.

Pisa, 12

December 2003

Domenico Spensieri

Table of Contents

1 Introduction... 5

1.1 Thesis outline...8

2 Problem formulation ... 9

2.1 Solving approach...9

2.1.1 Tools ... 11

2.2 Software architecture ... 11

3 Automata Theory ... 13

3.1 Automata and languages ... 13

3.1.1 Automata relations ... 17

3.1.2 Example of synchronous composition ... 18

3.2 Introduction to Supervisory Control Theory ... 19

3.2.1 Plants and specifications ... 20

3.2.2 The controller... 21

3.2.3 Uncontrollable states... 23

4 Multi-robot system analysis ... 25

4.1 Paths, mutex zones and intersections ... 26

4.1.1 Assumptions to save simulation time ... 28

4.2 Automatic introduction of via points ... 30

4.3 Implementation... 33

4.3.1 “SpanGenerator” ... 33

4.3.2 “MechanismListener”... 35

4.3.3 Problems encountered with RobotStudio. ... 36

5 Discrete event system model ... 38

5.1 The common format... 39

5.2 Model ... 41

5.2.1 From common format to automata... 44

5.2.2 Time modeling ... 45

5.2.3 Example of modeling a robot job... 46

5.3 Implementation... 49

5.3.1 From mutex zones to automata ... 49

5.3.2 From robots to automata ... 50

6 The supervisor ... 53

6.1 Deadlock reduction with via points ... 55

6.2 Controllable Supervisor ... 58

6.3 Supervisor synthesis ... 58

6.4 Computing the makespan ... 59

7 Simulation... 63

7.1 Synthesis resume ... 63

7.2 Experimental result... 64

8 Conclusions ... 69

8.1 Future work ... 70

Bibliography ... 71

Appendix A ... 73

Appendix B ... 76

Appendix C... 79

1 Introduction 5

1 Introduction

The study of multi-agent systems arises in the coordination of the city traffic, in air traffic management as well as in scheduling processes for CPUs and manufacturing systems, and in many other activities. The approach used here is to model these systems with Discrete Event Systems (DES), and the attention is given to industrial multi-robot systems. DESs are a mathematical abstraction of systems with discrete state space and driven by events, see [4] for details. Industrial multi-robot systems are present in manufacturing industries and have gained higher importance in last years.

The global market world of nowadays, indeed, always requests more competitiveness to the companies to let them survive. The customers’ requests on the market are more and more fulfilled using a just-in-time philosophy and this way of thinking needs a flexible vision of the plants and of the fabrication processes together with a flexible control system. The capital and material costs are often extremely high and even small changes in operating conditions have a large impact on the company space in the market.

Thus, the design phase of a manufacturing system becomes a very important feature, since

interruptions in the production flow cause fatal problems, and changes in the production

lines are the cause of large delays, with catastrophic consequences in terms of time and

money. The main difficulties concerning the design are primarily due to the complexity of

plants and to the specific needs of different companies. In fact, these two characteristics

often lead to specific solutions for each specific problem. Big efforts are needed to organize the problems under a global common vision. These efforts usually do not justify the big amounts of money required. In fact industrial demands for a fast project-implement-run cycle often limit the generality of the systems even if its components can easily support flexibility of use. This happens because the control system is usually entirely tied to the specific plant in order to obtain an optimal production, so that small changes in the plant require a complete re-design of the control system.

On this background, the possibility for the control system to support modifications of the plants layout and of the machines tasks, and the introduction of new product models represents what we call flexibility. The design phase of a flexible manufacturing system early leads to the fundamental problem of the automatic modeling of plants. The automatic procedure leads to the avoidance of manual work and its connected errors. Manual works, indeed, are the most common way to analyze plants and to synthesize controllers for the production.

Object-oriented modeling can be a method to deal with flexible design. In the last ten years, indeed, object-oriented modeling has shown to be a valuable tool for structuring complex systems and to ease their implementation and modification by providing independent communicating modules. Capturing information to model the plant sometimes needs very accurate simulation tools or, more often, a deep study of the structure of the plant.

The automatic modeling of the plant and of the plant’s tasks, on the other hand, easily turns out to be the first step of a whole automatic process that comprehends:

ƒ the research of the feasible solutions to the problem of the production;

ƒ the optimization of these solutions in terms of some cost index;

ƒ finally, the implementation of the controller for the plant.

The big advantage of this method is that most part of the work is made off-line, before the

production process starts. The off-line design offers the following benefits:

1 Introduction 7

ƒ errors can be detected in the simulation environment and not in the physical factory: it is cheaper to fix problems as soon as possible;

ƒ during the simulation the plant can still run as it was designed previously; there is no need for a copy of the plant or for the stop of production;

ƒ manual work is reduced.

In this thesis the plant is represented by an assembly cell where the robots present have different tasks to perform. Nowadays, as said above, most part of the work is made manually: the robots are moved and, when a collision is imminent, the simulation is stopped and the robots have to wait for each other to avoid collisions. This method has the disadvantage that a lot of manual work is needed, with the following errors due to the uncertainty of the operations. Another disadvantage is that the simulation of the production cycle is made for only one predefined sequence of movements for each robot. This means that if the robot is allowed to perform its task in several ways, only one direction of motion has to be chosen according to some particular criterion. This criterion is often heuristic and it is not guaranteed to lead to optimal or sometimes neither feasible solutions. In fact, trying all the possible motions for each robot leads to too large times for the simulations. The problem grows exponentially with the number of motions for each robot.

Previous work has been done regarding flexible manufacturing systems and automatic modeling of stations. In particular, many papers in literature describe complete architectures for Flexible Manufacturing Systems, see [2] and [11]. Furthermore, algorithms to schedule the robot jobs are present in literature together with optimal coordination of 2D systems [10], [8]. The contribution of this work is a tool that automatically provides an accurate model of a real 3D station (with some input) and the possibility to obtain an optimal coordination of the robots tasks, based on an approach different from the previous 2D approach.

Usually, the robots have to reach prefixed points where they can make different operations,

consisting in welding, picking up an object or leaving it, or other actions, and then they

come back to their standby position. Flexibility is applied in this case, especially using the benefits given by simulation software and synthesis software already existing.

In particular, robots provided by ABB Robotics are considered and, together with them, a simulation software RobotStudio

is used to simulate their behavior. Modeling becomes, in this way, a pure gathering of information from the simulations. In fact, we provide automatic procedures that describe the workspace. Then, construction of a mathematical model for the plant and synthesis of an optimal controller are automatically made in a software environment Supremica that manipulates automata and generates PLC code. The main goals in this phase are the avoidance of collisions among robots and a good choice of the model describing the workspace.

1.1 Thesis outline

In chapter 2, the description of the problem is given together with the presentation of the software architecture used.

In chapter 3 the background theory necessary for the comprehension of the work is described. It consists of a short summary about automata and supervisory control.

The following chapters 4, 5, and 6 describe in detail how the problem is analyzed and solved. In particular, the analysis and the simulation are made at the same time in order to exploit the powerful functionalities of RobotStudio. Assumptions about characteristics of the plant are made in order to reduce the simulation time. A new methodology of controlling the robots is proposed through the introduction of via points during the robots motions.

In chapter 5 a complete description of the plant is provided by choosing specific automata models that capture the most important characteristics of the plant.

In chapter 6 a discrete event controller is synthesized using Supervisory Control and Optimization Theory. The controller is built such that the closed loop system results in being time optimal, collision free, and non-blocking.

Finally, in chapter 7, a three-robot workspace is analyzed, simulated and controlled with the methodology proposed in this thesis.

In the appendix there are a short description of the functionalities added to Supremica, utility files regarding the solution proposed in chapter 7.

In last chapter conclusions about the work are resumed and future research is suggested.

2 Problem formulation 9

2 Problem formulation

The contribution of this Master Thesis work is to provide functionalities in Supremica to analyze multi-robot systems with the support of RobotStudio and to synthesize an optimal controller for the coordination of robots. A multi-agent environment is the topic of many present researches in the entire world, from the cooperation of robotic systems and air- traffic management, to the scheduling of processes in operating systems. The robots are one example of agents and are easily simulated through appropriate software.

The main problem is to optimize the total time of work (in literature known as “makespan”) of the whole system, i.e. the time in which all the agents perform their tasks, in a way that avoids collisions. As said above, robots tasks can be of various kinds and in this case the original idea comes from car industry: in particular, robots in assembly cells are assigned tasks consisting in welding predefined points of car’s pieces.

2.1 Solving approach

The first problem arising in the coordination is that robots, during their motions, could

collide because they share the same workspace and, sometimes, this can be very small

(example of a cell at VolvoCars). In this work the approach to solve the problem is to

identify the zones (parts of the workspace) that the robots possibly share during their

movements through the simulations of their motions. Then, the idea is to allow only one

robot to be inside a zone at a time. For this reason the zones will be called zones of mutual exclusion or, simply, mutex (MUTually EXclusive) zones.

The movements of the robots will be then associated to events in a discrete event system model of the workspace, in this case automata. Once an automata model for the system is built, it will be enlarged with information about the simulation times for the motions of robots. Simple automata become timed automata and an optimal sequence of events will be found out. Through these events, a sequence of booking and releasing resources will give the correspondent optimal solution for the movements of each robot.

In particular, each robot in the station (the workspace in RobotStudio is called station in analogy with production plant) has a set of points that have to be reached in an arbitrary order. Knowledge of the times taken to go from a point to another is needed too. Then, the computation of all the possible ways in which the robots can reach the points is a mere combinatorial exercise. In the figure below there is a graphical 2D example of a general problem and on the right the possible sequences of points for each robot.

Robot B Robot A

A1

A2

A3

B1

B2

C1

Robot C

Possible sequences Robot

C

B

B

, B

B

A

A

A

, A

A

A

, A

A

A

, A

A

A

, A

A

A

, A

A

A

B

C A

Figure 2.1: Example of multi-robot workspace and possible sequences of motions.

In the whole work the points A

, A

, A

, B

, B

, C

will be referred as target points because

the end-tool of robots performs operations at these points. The initial positions for the end-

tool will be called home points (Robot A, Robot B, and Robot C in figure).

2 Problem formulation 11

A simple comparison of the sums of times needed to perform each sequence does not take care of the collision free property that we require to the system. Anyway, even a collision free solution needs to be optimized and a straightforward computation of the total time of work is not obvious. Modeling the time and facing the problem of contemporaneous events will be described and solved in paragraphs 5.2.2 and 6.4.

2.1.1 Tools

We will need theoretical instruments like supervisory control. Nonetheless, the dimensions of the problem grow rapidly with the number of robots and of points, so a tool to deal with large automata is needed too. Supremica has been developed at the Department of Signals and Systems at Chalmers, Gothenburg. It is a tool for verification and synthesis of discrete supervisors.

Furthermore, in a three dimensional environment and with real robots, that have links which do not move through straight paths, the computation of the intersections of the paths require more sophisticated calculations. The introduction of instruments that help us to deal with this problem therefore seems necessary. This tool is RobotStudio and will be presented and described in chapter 5.

2.2 Software architecture

Certainly, the simulation of the robots movements is of fundamental importance. As said

above, an ABB software named RobotStudio is used together with another software,

Supremica, in order to deal with the automata. A figure that shows the links among the

units used and how they have been connected to each other is illustrated below.

Figure 2.2: Software tools interaction

A P I Robot Studio RobotStudio^TM

Microsoft Windows Operating System

Java-COM Bridge

Supremica

The tool added in Supremica is allowed to communicate with RobotStudio through the

RobotStudio Application Program Interface (API). This interface provides methods for

external users to interact with a lot of RobotStudio’s functionalities and generates events

that can be caught externally, together with the possibility for the users to read the internal

properties of the station. The interoperability between the Java programming environment

(such as Supremica) and Microsoft Windows COM Automation components is provided by

the module Java-COM Bridge that presents a gateway to the world of COM object to Java

developers.

3 Automata Theory 13

3 Automata Theory

3.1 Automata and languages

The approach used in this work, in order to compute feasible solutions for the problem described above, uses finite state automata. The multi-robot system is regarded as a discrete event system.

Not all the systems can be conveniently modeled through continuous systems. In many cases the important features of a system are discrete states that evolve according to the occurrence of certain events. These events let the system pass from a state to another one and are observed at discrete points in time. One may think, for example, about traffic systems where vehicles go from a point to another and traffic lights are constraints, or about computer systems where the CPU schedules different tasks according to some scheduling rule.

Definition

A Discrete Event System is a discrete state, event-driven system, that is, its state evolution depends entirely on the occurrence of asynchronous discrete events over time.

The state space is a discrete set and the mechanism that rules the state transitions is event-

driven. An event may be identified with a specific action taken: a spontaneous occurrence

dictated by nature or by the result of several conditions which are suddenly met. To model

DESs, the two classes of models mostly used are automata and Petri nets. We will deal with the first one.

Definition

A (deterministic) finite state automaton P is formally modeled by the 4-tuple (Q

, ∑

, i

, δ

) where

ƒ Q

is the finite set of states,

ƒ ∑

is a finite alphabet, finite set of event-labels, the alphabet,

ƒ i

∈ Q

is the initial state,

ƒ δ

: Q

∑

→ Q

is the transition function that describes the state in which the automaton will be after an event happens in the previous state.

×

As example, we can model a robot of a manufacturing system that starts its work when a button is pushed and can accidentally break during its work. If the robot breaks it is possible to repair it and bring it back to the initial position.

Idle

Working

repair

break finished

start

Down

Figure 3.1: Automaton modeling a robot.

In this example the set of the states is Q

= {Idle, Working, Down}, the alphabet ∑

= {start, finished, break, repair}, the initial state is Idle and the transition function is described by:

δ

(Idle, start) = Working, δ

(Working, finished) = Idle, δ

(Working, break) = Down,

δ

(Down, repair) = Idle.

3 Automata Theory 15

All the possible sequences of events (called traces or strings) that can occur from the initial state form the language of the automaton. Furthermore, given the initial state, the empty trace, corresponding to no occurrence of events, is denoted with ε.

Definition

Let ∑

denote the set of all finite traces of elements of ∑

. The language of the automaton P is L(P) = { s ∈∑

| δ

(i

, s) ∈ Q

} where the transition function has been extended to traces

.

A language is empty if and only if the set of states is empty too, so, if at least the initial state is present, the empty trace will always belong to the language of the automaton. Note that, for two automata A and B, it may well hold that ∑

⊆ ∑

, while L(A) ⊆ L(B). A trace s ∈∑

has a set of prefixes

= { t ∈∑

| ∃ t’ ∈ ∑

such that tt’ = s } , that is, the set of traces consisting of any number of leading symbols of s. For example, a trace abc ∈∑

has the following set of prefixes

= {ε , a, ab, abc } . The prefix-closure of a language

L is defined as

s L

L

∈

= U s , that is, the union of all the prefixes of the traces of the language. A language L, for which L L = , is said to be prefix-closed (or simply closed).

Definition

Given the automaton P, a state q ∈ Q

such that there exists s ∈ L(P) such that q = δ

(i

, s) is said to be reachable. An automaton with only reachable states will be said to be accessible

.

The concept of automaton can be extended to marked automaton where a set of marked states is added to the 4-tuple. Marked states can represent states in which a goal has been reached or a state with some other property that one is interested in.

1 The extension is made recursively: δP(q, ε) = q and δP(q, σα) = δP(δP(q, σ), α) where σ∈∑P* and α∈∑P.

2 In this work a language is always intended as regular language, i.e. can be represented by finite state automata.

3 Only the reachable state spaces of automata are considered since now.

Definition

A marked automaton is an automaton with an additional set M

⊆ Q

of marked states.

With this definition an automaton is modeled by a 5-tuple and in the following work we will extend it to a 6-tuple (including time aspects). In the previous example the initial state represents the state in which the robot is ready to work and/or has completed its task and can be seen as marked (marked states will be identified with a circle).

Definition

A marked language for an automaton is a subset of the language of that automaton where each string reaches a marked state: L

(P) = { s ∈ L(P) | δ

(i

, s) ∈ M

} .

From the definition above we present some properties of the marked language:

ƒ L

(P) ⊆ L(P).

ƒ M

≠∅ if and only if L

(P) ≠∅ .

ƒ i

∈ M

if and only if ε ∈ L

(P).

The first property says that the marked language is a subset of the closed language but generally not prefix closed. The marked language will turn out to be fundamental for the characterization of non-blocking controllers. Now further definitions for the states that concern the marked language are necessary.

Definition

Given the automaton P, if there exists a trace s ∈∑

such that δ

(q, s) ∈ M

, then q is said to be coreachable. An automaton with only coreachable states will be said to be coaccessible.

If an automaton is both accessible and coaccessible it will be said to be trim.

4 If we only consider reachable states as said in note 3.

3 Automata Theory 17

3.1.1 Automata relations

Often automata have to interact with each other and compositions of automata regarding different goals have been proposed. Here we deal with the full synchronous composition that is the most important tool used to solve resource sharing problems. The interaction through the synchronous composition leads to an automaton that describes the possible combinations of the states of the two automata with the constraint that an event included in both alphabets happens in the resulted automaton only if it can occur simultaneously in both automata. The complete description is the following, where the operator synchronous composition is represented by ||.

Synchronous Composition

A||B = (Q

× Q

, ∑

∪ ∑

, (i

, i

), δ

, M

× M

) where

||

( ( , ), ( , )) ( ( , ), ) (( , ), )

( , ( , ))

A B A

A A

A B

B B

p q

p q

p q p q

undefined

δ σ δ σ σ

δ σ σ

δ σ

δ σ σ

B B A

∈Σ ∩ Σ

∈Σ − Σ

= ∈Σ − Σ

otherwise

 

 

 

It can be easily shown that this operator is idempotent, commutative and associative

. Note that when ∑

= ∑

, then an event occurs in the composed automaton if and only if it can occur in both automata simultaneously. In this case the languages of the composition become L(A||B) = L(A) ∩ L(B) and L

(A||B) = L

(A) ∩ L

(B).

The synchronous composition has a fundamental role in modeling the closed loop systems and together with the refinement relation is enough to describe our systems.

Definition

We will say that an automaton A refines an automaton B if and only if A||B = A. We will use the symbol .

5 Idempotent: A||A=A; Commutative: A||B = B||A; Associative: (A||B)||C = A||(B||C).

It can be shown that also this is an equivalence relation. Furthermore, we can note that, given three automata A, B, and C

A B A C

B C

 ≤

 ⇒

 p

p .

This relation will be useful in the future for the construction of a supervisor for the plants.

For two automata A and B, when Q

⊆ Q

, ∑

= ∑

, i

= i

, and δ

⊆ δ

, A is said to be a sub-automaton of B, denoted A ≤ B. A sub-automaton is a subset of its super-automaton such that it has the same initial state, and includes the same transitions between its subset of the super-automatons states. Graphically, a sub-automaton is a sub-graph of the super- automaton including the initial state.

Equality of automata can be defined on different levels of detail; we will be satisfied with two, language equivalence and isomorphism (or structural equivalence). The language equivalence regards two automata A and B as equivalent if L(A) = L(B) and ∑

= ∑

. Clearly, this is an equivalence relation (that is, it is reflexive, symmetric and transitive).

Isomorphism equates two automata A and B when A ≤ B and B ≤ A. Again, this is an equivalence relation (its transitiveness follows from the transitiveness of the sub-automata relation).

3.1.2 Example of synchronous composition

A: q0 a q1 b q2 B: q0 a q1 b q2 c∈∑B

Figure 3.2: Three different automata.

C: q0 a q1 b q2 c q3

Above we have three automata. Their synchronous compositions are shown below. We can

assume that the alphabet of respective automata above consists of the shown events, except

that c ∈∑

. When synchronizing A and B all events can occur if and only if they can

3 Automata Theory 19

simultaneously occur in both automata. The alphabet of A||B will, of course, include c.

Thus, A||B will be equal to B. In the synchronous composition of A and C, an event of A will occur if and only if it can simultaneously occur in C. However, the c event of C is not influenced by A. Thus, A||C is equal to C. Finally, since ∑

= ∑

, an event will occur in the composition if and only if it can occur in both automata simultaneously. Since the c event cannot occur in B at all, it will also not be possible in B||C.

q1,q1

A||B: q0,q0 a b q2,q2 c∈∑_A||B

q1,q1

A||C: q0,q0 a b q2,q2 c q2,q3

Figure 3.3: Synchronous composition of possible pairs of the three automata above.

q1,q1

B||C: q0,q0 a b q2,q2 c∈∑_B||C

In the state (q

,q

) of A||C, C can execute c, which is not in ∑

. What happens then is that A remains in its q

state, while C executes c and transits to q

. On the other hand, in (q

,q

) of B||C, C cannot execute the c event on its own, since c ∈∑

. Thus, C cannot transit to q

. In this way, B can “control” the c event since it has this event in its alphabet, whereas A cannot influence the execution of c.

Note that, formally, there are more states arising through the synchronous composition, such as (q

,q

) for A||C. However, we only concern ourselves with the accessible parts, which is what is shown above.

3.2 Introduction to Supervisory Control Theory

The Supervisory Control Theory (SCT) concerns a discrete event model of a process, the

plant, for which a specification is given describing the desired and required sub-behavior of

the plant.

3.2.1 Plants and specifications

The plant in the SCT, as in the common automatic control literature, is a mathematical model of some kind of process. It represents the reality that we want to control under the constraints that we need to impose.

A specification of the process is the description of its intended behavior. Typically, we want the process to be controlled to fulfill a given specification. Thus, the process itself sets physical boundaries for what is possible, while the specification expresses the desired and/or forbidden parts of this.

Thus, a specification is an automaton Sp = (Q

, ∑

, i

, δ

, M

, X

) that expresses the intended behavior of the given plant. In the previous definition X

is a set of forbidden states, that is, a subset of Q

that we do not want the automaton to reach during its execution. The assumption that is made on the alphabet of the specification is that it is a subset of the alphabet of the plant. Analyzing the alphabet of specifications, we can define

ƒ partial specification a specification whose alphabet is a strict subset of the plant alphabet,

ƒ total, a specification whose alphabet is equal to the plant’s alphabet.

A total specification can always be obtained from a partial one by synchronizing it with the plant. The new specification will be S

= P||Sp and its alphabet is equal to the alphabet of the plant, while the language is a subset of L (Sp) ∩ L (P).

Furthermore, specifications can be either

ƒ static, in which case the specification is fully described by the sets of marked and forbidden states;

ƒ dynamic, when the specification has to be described by an automaton. Thus, this can

forbid or mark a subset of the strings reaching a single state in the plant. At the

3 Automata Theory 21

contrary, for static specifications, a marked (forbidden) state marks (forbids) all the set of strings reaching that state.

The closed loop system of plant and supervisor is never to occupy any of the forbidden states while be always able to continue to a marked state.

3.2.2 The controller

In the Supervisory Control Theory of Ramadge and Wonham (see [12]) the plant was assumed to generate all the events and the supervisor’s function was to restrict the choices of the events that the plant could generate.

From a control engineering point of view, instead, the plant is interpreted as the transfer function between the input commands and the output responses. Thus, an illustration of the two ways of modeling can be done in the figure below.

Figure 3.4: The asymmetric and symmetric feedback loop.

S P

enable/disable

events

∑

P

∑

S

∑

The difference between the two models of system is that the second controller has to have an additional (respect to the first one) constraint regarding the events that the controller can generate. In other words, the controller can generate only the events that the plant can follow. On the other hand, both controllers must be designed so that they can always follow the plant-generated events.

It has been shown that both schemes for the controller can be modeled by synchronous

composition (see [3] and [9]). Furthermore, the added constraints on the second controller

do not have any additional problem. In fact, we always require the closed language of the

supervisor to be a subset of the plant language, that is L(S) ⊆ L(P), since the total

specification will always refine the plant.

Resuming, given a specification Sp whose alphabet is a subset of the plant alphabet, a total specification S

can be built by doing S

= P||Sp. Thus, now the closed loop system P||S

will be equal to S

. This means that the supervisor is a model of the closed loop system and allows shaping the loop as it is done in the classical control systems.

There is an additional aspect that we have not considered yet. The alphabet of the plant contains both controllable and uncontrollable events. The controllable events are subject to influence by the controller. The controller is allowed to disable those, in any way it sees fit.

Thus, controllable transitions (that is, transitions labeled by controllable events) are allowed to disappear in the synchronous composition between the plant and the controller. On the other hand, the uncontrollable events cannot be influenced by the controller. If the plant enters a state from which it can execute an uncontrollable event, it can do so with or without the participation of the controller.

This also means that in the synchronous composition between the plant and the controller uncontrollable transitions in the plant are not allowed to disappear. This so, since if the closed loop system reached a state from which an uncontrollable event was not defined, then the requirement above that the controller should always be able to follow the event generation of the plant is broken. The plant could still choose to execute that uncontrollable event but the controller would not be able to follow. Note that, in the model of the closed- loop system, transitions disappear from a state solely because they are not defined by the controller from its corresponding state.

A controller that is able to follow all uncontrollable events that the plant may execute is said to be controllable.

Definition

A controller S (with the same alphabet as P) is controllable with respect to a plant P and a set of uncontrollable events ∑

⊆ ∑

if

for any s ∈ L(S) ∩ L(P) and for any σ

∈∑

, δ

(i

, s σ

) ∈ Q

⇒ δ

(i

, s σ

) ∈ Q

.

This definition says that after a trace s present in both languages, for any uncontrollable

event that the plant defines in the state reached by s the controller must define the same

uncontrollable in the state it reaches by s. If this holds, no uncontrollable events will

3 Automata Theory 23

disappear in the synchronous composition between the plant and the controller.

Controllability is defined in Definition 1 from an automata point-of-view. The controllability property is also defined from a language point-of-view.

Definition

A controller S is controllable with respect to a plant P and a set of uncontrollable events ∑

⊆ ∑

if

L(S) ∑

∩ L(P) ⊆ L(S).

The existence of such controller is characterized by this theorem.

Theorem

Given a plant P and a specification S

there exists a controllable supervisor S such that P||S

= S

if and only if S

refines P and S

is controllable.

The theorem tells us that for the existence of a supervisor guaranteeing that the entire specification can be achieved, that specification must be controllable. This also means that for the specification to be used as the controller, it must be controllable.

In general, the given specification is not controllable. In that case, we have to find a controllable sub-automaton of the specification to replace S

in the Theorem above. This is emphasized in the following corollary to the Theorem.

Corollary

Given a plant P and a specification S

there exists a controllable supervisor S such that P||S

≤ S

if and only if there exists a controllable sub-automaton S’ ≤ S

such that S’ refines P.

Fortunately it can be proven that a unique largest sub-automaton exists, so that the specification can be fulfilled as much as possible.

3.2.3 Uncontrollable states

Given a specification and a plant we know now that we have to look for the largest sub-

automaton of the specification that is controllable. We can always assume that the total

specification refines the plant. This means that there exists a mapping between the specification states and the plant states based on mutual traces of the specification and the plant. If the specification is uncontrollable, then some of its states that are such that their corresponding plant-states, define transitions labeled by uncontrollable events, that label no transitions in the respective specification states. That is the Definition is violated.

Figure 3.5: Example about controllable states.

a2 c2 a1

a2

c1

q3 q2 q1

a1 c2

c1

q0 p0

p1 a2

P Sp

c1

When the plant P and the specification Sp above are synchronized (S

) the uncontrollable

states can be forbidden. The uncontrollable events are the c

events. After the a

event the

plant can always execute c

. However, in the synchronous composition there are two states

reached by transitions labeled by a

, but from where no c

are possible. These

uncontrollable states are forbidden in S

. The problem is that Sp constrains the c

event in

its p

state, so that the combinations q

p

and q

p

are uncontrollable.

4 Multi-robot system analysis 25

4 Multi-robot system analysis

The simulation of the robot systems has been made using a software product from ABB named RobotStudio. It is a software that enables offline programming and simulation of robot systems using a standard Windows PC. Its main feature is that it contains the same software (ABB Virtual Controller) of the software that runs on the real robots in the production system. Thanks to this characteristic, simulations are very accurate and are a mirror of what the real robots’ behavior will be. This software is the starting point to optimize the tasks in multi-robot systems. Indeed, before using the data about the system (number of robots, robots tasks, mutex zones) to model our problem, all the stations have to be described in the RobotStudio environment. In particular, just few characteristics have to be specified by the user/designer due to the high level of automated functions implemented in the tool added to Supremica. However, the user can modify some of the computations that are done, for example mutex zones and others. This freedom is left in order to allow flexibility during the computation of the optimal solution. The user can try different parameters and compare the different solutions.

Given a station in RobotStudio, the user has to specify the target points that have to be

reached by each robot. The important aspect, here, is to provide reachable points in the

workspace of robots; this can be easily checked using the “reachability” function inside

RobotStudio. The work “by hands” of the user is almost finished at this point, except that

for some adjustment that could be done during the following operations. They regard the deletion of zones or paths not required by the design.

4.1 Paths, mutex zones and intersections

First, for each robot, all the possible paths that connect one point to another are built. The approach used is to create linear paths, that is, straight lines between two points. Other methods could be used here, such as parts of circle or other complicated movements, but this leads to another problem that we do not treat in this work: find three dimensional curves, feasible for the robot movements, that avoid collisions. Linear paths, then, have the advantage to be the shortest (weighted with the Euclidean distance) paths between two points and, when split in several sub-paths, remain still linear. Here we talk about linear paths in the sense that the end-point (or working point of the tool held by the robot) describes straight lines during the links movements.

The simulations to create the volumes swept by the robots’ arms can be executed. Here many parameters intervene in the construction of the areas and in the following reliability of the solution.

ƒ First of all, a “good” approximation of the robot’s arm is needed. The volumes surrounding the robots’ arms can be created around every part of the robot or only around parts of robots that may collide. This can be seen through a preliminary analysis of the geometry of the workspace.

ƒ Then, one needs an appropriate “tick time”, concerning how often to create the volume surrounding the robot (we always deal with discrete-time simulations).

ƒ And, not last in importance, a margin of tolerance for the robot movements (the simulated volume should be larger than the real swept volume).

The simulations turned out to be very slow due to two main reasons:

ƒ computation of the union of the swept volumes created at each “tick time”;

4 Multi-robot system analysis 27

ƒ starting and shutting down the virtual.

Figure 4.1: Computing the swept volumes (in red) in RobotStudio.

At the end of this simulation phase all the areas occupied by the robots are known. An analysis about where they could collide leads to identify the intersections of the volumes computed as zones of mutual exclusion.

Then, the intersections between the spans are made to finally have the mutual exclusion zones. The zones (counted in RobotStudio) could result in more than the number expressed in (4.1) (see paragraph 4.1.1) because the intersection between two objects can be composed by two or more zones with null intersection. Thus, the number of zones can increase respect to the one expected, bringing, sometimes, to a useless big number of events for the automata representing the station. For this reason, here an intervention of a user that deletes the useless zones is welcome. Actually, there could be the possibility to automatically select the “important” zones from the all ones. This is not yet implemented.

A criterion of choice could be the deletion of the zone “mostly included” in the other one.

Formalizing:

For each pair of zones Z

and Z

, let us define Z

the zone with the minimum volume.

If Vol(Z

∩ Z

) ≥ α Vol(Z

) delete Z

, with 0≤α≤1 and Vol(Z) representing the function to

compute the volume of the zone.

Certainly α = 1 ensures the correctness of the result when deleting the zone, while, decreasing α, the accuracy of the solution decreases consequently.

Figure 4.2: Mutex zones (in red) computed in RobotStudio.

4.1.1 Assumptions to save simulation time

The assumptions that have been made during all the work are that

ƒ targets and via points are reached by the robots always in the same configuration

ƒ robot motions from P

to P

are always identical, for each pair of points.

The second assumption is quite obvious since, if the robots moved in a way out of the

volumes defined, no further considerations could be done. In other words, the robots

occupy always the same volume in the space during their motions. Let us not assume the

first assumption, now. Let us suppose, for example, that we do not deal and do not know in

which configuration the robots’ links are. It can happen that the same point can be reached

in two different ways depending on which path has been made. This means that, if RobotX

has to reach the point P

from P

, different motions are made if the robot came from P

or

from P

. Thus, one has to consider the simulations of path P

P

P

and P

P

P

, instead of just

independent paths P

P

, P

P

, and P

P

.

4 Multi-robot system analysis 29

Figure 4.3: Robot reaching the same point in two different configurations (RobotoStudio).

This means that we cannot concatenate the swept volumes of the robots. Instead, we are forced to compute the swept volumes for each possible complete path.

These assumptions simplify all the following work. Thus, if we are given n points to be reached and one Home point, the number of all possible paths is n!. While, assuming what we did above, it results in n(n+1) paths and of smaller length than the previous ones. This is a big step to decrease the number of simulations to be done, certainly the most important feature in terms of time for the off-line design of the coordination.

Once all the swept volumes are computed, the number of intersections results in

2 2

1 1 1

1 1

( )

( ( ))

2

N N

i i

N N

i i

i j

i j i

p p

p p

− = =

= = +

−

= ∑ ∑

∑ ∑ ^(4.1)

where p

is the number of paths for the robot i and N the total number of robots.

If we substitute in the previous formula the number of paths found above we can get an

idea of the size of the difference:

2 2

1 1

( ( !)) ( !)

2

N N

i i

i i

n n

= =

∑ − ∑

(4.2) and

2 2 2

1 1

( ( 1)) ( 1)

2

N N

i i i i

i i

n n n n

= =

+ − +

∑ ∑

(4.3)

where n

is the number of target points for the robot i.

In the case each robot has the same number n of target points (this is a quite common case in a station where each point has to be welded by all the robots) the previous ones result in

( 1)( !)

2 N N − n

(4.4) and

2 2

( 1) ( 1)

2 N N − n n +

. (4.5)

For 1, 2 or 3 points to be reached, the first approach (not splitting the motions in more paths) turns out to be more convenient. As soon as the welding points are more than 4, the gain of the solution adopted above is clearly evident. Let us take, for instance, a simple station with 3 robots, each of which has to weld 5 points. In the first case the number of paths to be simulated is 5! = 120 and the number of intersections 43200; with the assumption made, 30 paths have to be simulated and 2700 intersections computed.

4.2 Automatic introduction of via points

So far the work results in a set of mutual exclusion zones and a set of possible paths for

each robot. A hypothesis to proceed could be to associate events in the DES model to the

movements of the robots from a target to another one, and so on. But this feasible method

leads to suboptimal solutions. In particular, if the zone is booked the robot cannot move in a

direction that will book the same zone, and it is obliged to wait. This approach brings to

waiting times for the robots that can be eliminated or reduced introducing via points.

4 Multi-robot system analysis 31

Indeed, putting via points when the robot enters into or exits from a zone adds movements for the robots that before were not thought possible. A simple example clarifies the introduction of via points.

Let us take, for simplicity, a two dimensional workspace in which the target points and the robots are represented as points, and the mutual exclusion’s zone is a square.

P1

P2

V4

V3

V2

V1

Home RobotB

Home RobotA

Figure 4.4: Adding via points to the paths.

Referring to the figure above, we can, for example, state the times for RobotA and RobotB as the following:

Sub-paths Time Units

Home RobotA - V₁ 4

V1 - V2 6

V2 - P1 4

Home RobotA - V3 4

V₃ - V₄ 6

V₄ - P₂ 4

Figure 4.5: Times for robots sub-paths.

One can easily see that the time for both robots to reach respectively P

and P

is 28 time units, without occupying contemporaneously the zone in grey. Instead, by allowing the robots to split their paths, the optimal solution takes 20 time units. If we want, as we will do for the real stations, that the robots have to go back to their home positions, the solutions are, respectively without and with via points, 56 and 34 time units (the times to go backward are the same of the forward ones).

time Robot A

A-P1

28 24 4 10 14 18

time Robot A

A-P1

28 24 4 10 14 18

Robot B

time 28

24 4 10 14 18

waiting… V3- P2

B-V3

time 20 Robot B

waiting…

4 10 14 18 24 28 B-P2

Figure 4.6: Optimal sequences of motions without (a) and with (b) via points.

(a) (b)

Certainly, the approach has a larger validity than this example. Indeed, if we assume that the robots start their movements and finish them in a zero time (or infinitesimal compared to the times for the movements), the addition of via points always allows the robots to make the complete movements (i.e. without via points) in the same time that would have been taken without via points. Thus, this approach adds generality and does not restrict or does introduce constraints to the previous method. Furthermore, we note that the assumption of having infinitesimal time for the critical (starting and stopping) operations can be considered valid by assuming an infinitesimal time for the software computations about the system and for the mechanical constraints of the robots.

In RobotStudio all this can be implemented due to the possibility to catch events from the

simulations, events that tell us when a part of the robot collides with another object in the

station. A collision with an object starts when the robot has some part in common with the

4 Multi-robot system analysis 33

object and finishes when the intersection between the robot and the object is empty. The paths are simulated again to introduce via points. Via points are the points when the collisions with a zone start and finish. During the simulations, the times to reach each point (via and target) are stored. From the simulation, an event that shows the beginning of a collision happens any time a part of the robot intersects an object in the station. Since a robot is composed by several parts, a counter (increased when a collision starts and decreased when a collision ends) for each robot tells us when the robot actually goes out from an object

.

All the important characteristics of the station are now available, and the way to the supervisor just regards the manipulation of these data. It will be described in next chapter.

Here, samples of Java code are presented in order to give an idea of how everything has been implemented.

4.3 Implementation

Here is a short description about the main classes and methods used to rule RobotStudio simulations by Supremica.

4.3.1 “SpanGenerator”

The class “SpanGenerator” creates the volume swept by the robot’s arm during the simulation of the movements.

During the simulation, at any tick, the comparison between the positions of the working tool (end-point) at present and at previous time is made. If the distance is larger than the predefined step size, a new volume surrounding the robot is created.

1 Actually events happen when a part of the robot is in or close to the objects before the simulation starts, thus more subtle methods to check collisions have to be used.

// Events generated by RobotStudio.ISimulation public synchronized void tick(double time) {

// In each tick, examine if it is time to generate a new spanEntity try

{

ITransform newTransform = tool0.getTransform();

//…

if (Math.sqrt(dx*dx+dy*dy+dz*dz) > stepSize) {

createSpanEntity(newTransform);

oldTransform = transformCopy(newTransform);

} }

catch (Exception ex) {

//…

} }

Furthermore, in order to not overload the memory for RobotStudio, the geometrical union with the previous swept volume is done. At the end of the simulation the entire volume created in this way is added in RobotStudio and enabled to be referred for following elaborations.

private void createSpanEntity(ITransform transform)

throws Exception

{

// Calculate box transform // Calculate cylinder transform

…

// Create cylinder around the arm

IEntity cyl = part.createSolidCylinder(cylinderTransform,cylinderRadius+margin,cylinderLength+2*margin);

// Create box around the tooltip

IEntity box = part.createSolidBox(boxTransform,boxSize+2*margin,boxSize+2*margin,boxSize+2*margin);

IEntity boxCyl = box.join(cyl,false);

IPart dd = boxCyl.getParent();

if (spanPart.getEntities().getCount()>0) {

IEntity union = null;

try {

union = spanPart.getEntities().item(var(1)).join(boxCyl,false);

} catch (Exception e) {

//…

} // …do stuff }

else {

// …do stuff }

part.delete();

}

4 Multi-robot system analysis 35

4.3.2 “MechanismListener”

The class “MechanismListener” is derived from “_MechanismEventsAdapter” of RobotStudio API. The constructor initializes the object and detects if, before the motion starts, there are objects intersecting the robot. All these objects are put in a list of objects colliding. The main methods inherited refer to the events that happen when a collision between the robot and an object in the workspace is detected. In particular, the event

“collisionStart” checks, first of all, if the object was already colliding with the robot. In the affirmative case a variable that counts the events “collisionStart” is incremented, otherwise, in addition to increment the variable, the object is added to the initial list and the time of the simulation between the previous critical time and the present is stored. A new point is created in RobotStudio and added in the right position. The motion that the robot makes from the previous point to the one considered is set as linear.

The event “collisionEnd” decreases the variable relative to the number of events and, if this

is zero, a new point is created and added in the right position in the path, setting the motion

as linear. The points are characterized by name whether they are relative to enter to or exit

from a zone. In particular, the points created are the position of the end-point when the

intersection is detected to be started or to be finished respectively.