Figure 6.13 plots the refinement state versus time.
Lee & Varaiya, Signals and Systems
259
6.5. SUPERVISORY CONTROL
e( t)
( t)
AGV
y( t)
track
global
coordinate
frame
x( t)
Figure 6.14: Illustration of the automated guided vehicle of example 6.10. The
vehicle is shown as a large arrow on the left and as a small arrow on the right. On
the right, the vehicle is following a curved painted track, and has deviated from
the track by a distance e(t). The coordinates of the vehicle at time t with respect
to the global coordinate frame are (x(t), y(t), φ(t)).
6.5
Supervisory control
We introduce supervisory control through a detailed example. A control system involves
four components. There is a system called the plant—the physical process that is to be
controlled; the environment in which the plant operates; the sensors that measure some
variables of the plant and the environment; and the controller that determines the mode
transition structure and selects the time-based inputs to the plant. The controller has
two levels: the supervisory control that determines the mode transition structure, and
the ‘low-level’ control that selects the time-based inputs which control the behavior of
the refinements. A complete design includes both levels of control as in the following
example.
260
Lee & Varaiya, Signals and Systems
6. HYBRID SYSTEMS
goStraight= {( u( t), x( t), y( t), φ ( t)) | u( t) != stop, | e( t)| < ε1}
goRight ={( u( t), x( t), y( t), φ ( t)) | u( t) != stop, ε2 < e( t)}
goLeft = {( u( t), x( t), y( t), φ ( t)) | u( t) != stop, - ε2 > − e( t)}
goStop = {( u( t), x( t), y( t), φ ( t)) | u( t) = stop}
goStart = {( u( t), x( t), y( t), φ ( t)) | u( t) = start}
. x ( t) = 10 cos
.
φ( t)
.
x ( t) = 10 cos φ ( t)
y .( t) = 10 sin
.
φ( t)
y ( t) = 10 sin φ ( t)
.
φ ( t) = - π
φ ( t) = 0
e ( t) = f( x( t), y( t))
e ( t) = f( x( t), y( t))
Vehicle
goRight/
goStraight/
right
straight
u( t) e { stop, start, absent}
goRight/
goStraight/
goStop/
goStart/ goStop/
goLeft/
stop
left
goStop/
x = x 0
y = y 0
φ = φ0
goLeft/
.
x .( t) = 0
x ( t) = 10 cos φ ( t)
.
. y .( t) = 0
y .( t) = 10 sin φ ( t)
φ ( t) = 0
φ = π
e ( t) = f( x( t), y( t))
e ( t) = f( x( t), y( t))
Figure 6.15: The automatic guided vehicle of example 6.10 has four modes: stop,
261
6.5. SUPERVISORY CONTROL
Example 6.10:
The plant is an automated guided vehicle or AGV that moves
along a closed track painted on a warehouse or factory floor. We will design a
controller so that the vehicle closely follows the track.
The vehicle has two degrees of freedom. At any time t, it can move forward along
its body axis at speed u(t) with the restriction that 0 ≤ u(t) ≤ 10 mph. It can also
rotate about its center of gravity with an angular speed ω(t) restricted to −π ≤
ω(t) ≤ π radians/second. We ignore the inertia of the vehicle.
Let (x(t), y(t)) ∈ 2
R be the position and φ(t) ∈ [−π, π] the angle (in radians) of the
vehicle at time t relative to some fixed coordinate frame, as shown on the left in
Figure 6.14. In terms of this coordinate frame, the motion of the vehicle is given
by a system of three differential equations,
˙
x(t)
=
u(t) cos φ(t),
˙
y(t)
=
u(t) sin φ(t),
(6.7)
˙φ(t) = ω(t).
The track and the vehicle are shown on the right of Figure 6.14. Equations (6.7) describe the plant. The environment is the closed painted track. It could be described
by an equation, but instead we will use a sensor to detect it.
The two-level controller design is based on a simple idea. The vehicle always
moves at its maximum speed of 10 mph. If the vehicle strays too far to the left
of the track, the controller steers it towards the right; if it strays too far to the
right of the track, the controller steers it towards the left. If the vehicle is close
to the track, the controller maintains the vehicle in a straight direction. Thus the
controller guides the vehicle in four modes, left, right, straight, and stop. In stop
mode an operator may bring the vehicle to a halt.
The following differential equations govern the AGV’s motion in the refinement
of the four modes. They describe the low-level controller, i.e. the selection of the
time-based inputs in each mode.
straight
˙
x(t)
=
10 cos φ(t)
˙
y(t)
=
10 sin φ(t)
˙φ(t) = 0
262
Lee & Varaiya, Signals and Systems
6. HYBRID SYSTEMS
left
˙
x(t)
=
10 cos φ(t)
˙
y(t)
=
10 sin φ(t)
˙φ(t) = π
right
˙
x(t)
=
10 cos φ(t)
˙
y(t)
=
10 sin φ(t)
˙φ(t) = −π
stop
˙
x(t)
=
0
˙
y(t)
=
0
˙φ(t) = 0
In the stop mode, the vehicle is stopped, x(t), y(t), φ(t) are constant. In the left
mode, φ(t) increases at the rate of π radians/second, so from Figure 6.14 we see
that the vehicle moves to the left. In the right mode, it moves to the right. In the
straight mode, φ(t) is constant, and the vehicle moves straight ahead with a constant
heading. The refinements of the four modes are shown in the boxes of Figure 6.15.
We design the supervisory control governing transitions between modes in such
a way that the vehicle closely follows the track, using a sensor that determines
how far the vehicle is to the left or right of the track. We can build such a sensor
using photodiodes. Let’s suppose the track is painted with a light-reflecting color,
whereas the floor is relatively dark. Underneath the AGV we place an array of
photodiodes as shown in figure 6.16. The array is perpendicular to the AGV body
axis. As the AGV passes over the track, the diode directly above the track generates
more current than the other diodes. By comparing the magnitudes of the currents
through the different diodes, the sensor gives the displacement e(t) of the center of
the array (hence, the center of the AGV) from the track. We adopt the convention
that e(t) < 0 means that the AGV is to the right of the track and e(t) > 0 means it
is to the left.
We model the sensor output as a function f of the AGV’s position,
∀t, e(t) = f (x(t),y(t)).
Lee & Varaiya, Signals and Systems
263
6.5. SUPERVISORY CONTROL
The function f of course depends on the environment—the track. We now specify
the supervisory controller precisely. We select two thresholds, 0 < ε1 < ε2, as
shown in Figure 6.16. If the magnitude of the displacement is small, |e(t)| < ε1,
we consider that the AGV is close enough to the track, and the AGV can move
straight ahead, in straight mode. If 0 < ε2 < e(t) (e(t) is large and positive), the
AGV has strayed too far to the left and must be steered to the right, by switching
to right mode. If 0 > −ε2 > e(t) (e(t) is large and negative), the AGV has strayed
too far to the right and must be steered to the left, by switching to left mode. This
control logic is captured in the mode transitions of Figure 6.15. The input events
are {stop, start, absent}. By selecting events stop and start an operator can stop or
start the AGV. There is no time-based input. There is no external output. The initial
mode is stop, and the initial values of its refinement are (x0, y0, φ0).
We analyze how the AGV will move. Figure 6.17 sketches one possible trajectory.
Initially the vehicle is within distance ε1 of the track, so it moves straight. At some
later time, the vehicle goes too far to the left, the guard
goRight = {(u(t), x(t), y(t), φ(t)) | u(t) = stop, ε2 < e(t)}
is satisfied, and there is a mode switch to right. After some time, the vehicle is
close enough to the track, the guard
goStraight = {(u(t), x(t), y(t), φ(t)) | u(t) = stop, |e(t)| < ε1}
is satisfied, and there is a mode switch to straight. Some time later, the vehicle is
too far to the right, the guard
goLeft = {(u(t), x(t), φ(t)) | u(t) = stop | − ε2 > e(t)}
is satisfied, there is a mode switch to left, and so on.
The example illustrates the four components of a control system. The plant is described
by the differential equations (6.7) that govern the evolution of the refinement state at time
t, (x(t), y(t), φ(t)), in terms of the time-based input, (u(t), ω(t)). The second component
is the environment—the closed track. The third component is the sensor, whose output
at time t, e(t) = f (x(t), y(t)), gives the position of the AGV relative to the track. The
fourth component is the two-level controller. The supervisory controller comprises the
four modes and the guards that determine when to switch between modes. The low-level
264
Lee & Varaiya, Signals and Systems
6. HYBRID SYSTEMS
2
e
1
track
photodiode
Figure 6.16: An array of photodiodes under the AGV is used to estimate the
displacement e of the AGV relative to the track. The photodiode directly above
the track generates more current.
right
straight
center of track
straight
1
left
2
Initial position
of vehicle
Figure 6.17: A trajectory of the AGV, annotated with modes.
Lee & Varaiya, Signals and Systems
265
6.6. FORMAL MODEL
controller specifies how the time-based inputs to the plant, u and ω, are selected in each
mode.
6.6
Formal model
We develop a formal model of a hybrid system similar to the ‘sets and functions’ model
of Section 3.1. A hybrid system HybridSystem is a 5-tuple,
HybridSystem = (States, Inputs, Outputs, TransitionStructure, initalState),
where, States, Inputs, Outputs are sets, and initalState ∈ States is the initial state. TransitionStructure
consists of several items that determine how the hybrid system evolves in time t ∈ T . T
may be R+ or N0. Here we assume T = R+.
States = Modes × RefinementStates is the state space. Modes is the finite set of modes.
RefinementStates is the state space of the refinements. If the current state at time t is
(m(t), s(t)) we say that the system is in mode m(t) and its refinement is in state s(t).
Inputs = InputEvents ×TimeBasedInputs is the set of input symbols. The finite alphabet of
discrete input symbols is InputEvents, which includes a stuttering symbol. TimeBasedInputs
is the set of input values to which the refinement reacts. An input signal consists of a pair
of functions (u, x) where u : R+ → InputEvents and x : R+ → TimeBasedInputs. For all
except a discrete set of times t, u(t) is the stuttering symbol, absent.
Outputs = OutputEvents×TimeBasedOutputs is the set of output symbols, where OutputEvents
is the finite alphabet of discrete output symbols, including a stuttering output, absent, and
TimeBasedOutputs is the set of continuous output values. An output signal consists of a
pair of functions (v, y) where v : R+ → OutputEvents and y : R+ → TimeBasedOutputs.
For all except a discrete set of times, v(t) = absent.
The transition structure determines how a mode transition occurs and how the refinement
state changes over time. Suppose the inputs signal is (u, x). Suppose at time t the mode is
m and the refinement state is s. For each destination mode d there is a guard
Gm,d = Um,d × Xm,d × Sm,d
⊂ InputEvents × TimeBasedInputs × RefinementStates.
There is also an output event, say vm,d, and an action Am,d : RefinmentStates → RefinmentStates
that assigns a (possibly new) value to each refinement state, (possibly) depending on the
266
Lee & Varaiya, Signals and Systems
6. HYBRID SYSTEMS
current value of the refinement state. If there is a match (u(t), x(t), s(t)) ∈ Gm,d, then there
is a discrete transition at t; the mode after the transition is d, the output event v(t) = vm,d is
produced, and the refinement state in mode d at time t+ immediately after the transition
is set to s(t+) = Am,d(s(t).
If no guard is satisfied at time t, then the refinement state s(t) and the time-based output
y(t) are determined by the time-based input signal x according to the equations governing
the refinement dynamics. Here we will need to be concrete. In all of the examples above,
we have taken
RefinementStates
=
N
R ,
TimeBasedInputs
=
M
R , and
TimeBasedOutputs
=
K
R .
In this concrete setting, the refinement dynamics are given as
∀t ∈ Tm, ˙s(t) = fm(s(t),x(t)),
(6.8)
y(t)
=
gm(s(t), x(t),
(6.9)
where Tm ⊂ T is the set of times t when the system is in mode m, and the functions
f
N
M
N
m : R
× R : → R ,
g
N
M
K
m : R
× R : → R
characterize the behavior of the refinement system in mode m. The function
s : R+ → RefinementStates
is the trajectory of the refinment states.
We can now see how the hybrid system evolves over time. At time t = 0, the system
starts in the initial state, say (m(0), s(0)). It evolves in alternating phases of time passage,
(t0 = 0,t1], (t1,t2], · · · , and discrete transitions at t1,t2, · · · . During the first interval (t0,t1],
no guard is satisfied and the system remains in mode m(0); the refinement state s(t)
and time-based output y(t) are determined by (6.8), (6.9); and the discrete event output
v(t) = absent.
At time t1, the guard Gm(0),m(1) for some destination mode m(1) is matched by (u(t1),x(t1),s(t1)).
There is a mode transition to m(1), the output event v(t1) is produced, and the continuous
state is set to s(t1+) = Am(0)m(1)(s(t1)). The discrete transition phase is now over, and
the system begins the time passage phase in the new mode m(1) and the continuous state
s(t1+).
Lee & Varaiya, Signals and Systems
267
6.7. SUMMARY
6.7
Summary
Hybrid systems bridge time-based models and state-machine models. The combination of
the two families of models provides a rich framework for describing real-world systems.
There are two key ideas. First, discrete events are embedded in a time base. Second, a
hierarchical description is particularly useful, where the system undergoes discrete tran-
sitions between different modes of operation. Associated with each mode of operation
is a time-based system called the refinement of the mode. Mode transitions are taken
when guards that specify the combination of inputs and refinement states are satisfied.
The action associated with a transition, in turn, sets the refinement state in the destination
mode.
The behavior of a hybrid system is understood using the tools of state machine analysis
for mode transitions the tools of time-based analysis for the refinement systems. The
design of hybrid systems similarly proceeds on two levels: state machines are designed
to achieve the appropriate logic of mode transitions, and refinement systems are designed
to secure the desired time-based behavior in each mode.
268
Lee & Varaiya, Signals and Systems
6. HYBRID SYSTEMS
Exercises
In some of the following exercises you are asked to design state machines that carry
out a given task. The design is simple and elegant if the state space is properly chosen.
Although the state space is not unique, there often is a natural choice. As usual, each
problem is annotated with the letter E, T, C which stands for exercise, requires some
thought, requires some conceptualization. Problems labeled E are usually mechanical,
those labeled T require a plan of attack, those labeled C usually have more than one
defensible answer.
1. C Consider the loudness compensation of example 6.3. Suppose that instead of a
switch on the front panel, the system automatically selects from among four com-
pensation filters with state-space models [A, b, c1, d1], [A, b, c2, d2], [A, b, c3, d3], and
[A, b, c4, d4]. The A matrix and b vector are the same for all four. Which filter is
used depends on a discrete-time v input, where at index n, v(n) represents the cur-
rent volume level. When the volume is high, above some threshold, filter 4 should
be used. When it is low, filter 1 should be used. Design a hybrid system that does
this.
2. E Construct a timed automaton similar to that of Figure 6.4 which produces tick at
times 1, 2, 3, 5, 6, 7, 8, 10, 11, · · · . That is, ticks are produced with intervals between
them of 1 second (three times) and 2 seconds (once).
3. E The objective of this problem is to understand a timed automaton, and then to
modify it as specified.
(a) For the timed automaton shown in Figure 6.18, describe the output y. Avoid
imprecise or sloppy notation.
(b) Assume there is a new input u : R → Inputs with alphabet
Inputs = {reset, absent},
and that when the input has value reset, the hybrid system starts over, behaving
as if it were starting at time 0 again. Modify the hybrid system from part (a)
so that it behaves like the system in (a).
4. E You have an analog source that produces a pure tone. You can switch the source
on or off by the input event on or off . Construct a system that upon receiving
Lee & Varaiya, Signals and Systems
269
EXERCISES
a = {( r( t), s( t)) | r( t) = 1}
b = {( r( t), s( t)) | r( t) = 2}
b / s( t)
s(0) := 0
r( t) := 0
r(0) := 0
y( t) ∈ Integers
∪ { absent}
two
one
a / s( t)
r( t) := 0
.
.
s( t) = 1
s( t) = 1
.
.
r( t) = 1
r( t) = 1
Fig