# Actions and Abstractions

Here the HA from Lazy Hybrid Automaton is extended with actions, in the form of an algebraic equation system. Actions are then seen in action as we define and illustrate a method of creating piewise affine abstractions through simulation.

## Actions in Theory

Actions (also known as jumps) describe a computation to be made during a transition, from [Schaft2000]:

The transition from the discrete state $$l$$ to $$l^\prime$$ is enabled when the continuous state $$x$$ is in $$\text{Guard}_{ll\prime}$$, while during the transition the continuous state $$x$$ jumps to a value $$x^\prime$$ given by the relation $$(x,x^\prime) \in \text{Jump}_{ll^\prime}$$.

When simulating a HA, in the absence of actions, the final continuous state of the current continuous problem is the initial continuous state of the next:

Actions explicitly transform these final continuous states to initial continuous states. Note that these initial states are still subject to the computation of consistent intitial conditions when constructing the continuous problem:

Unlike the definition of a HA in [Schaft2000] we do not bother with the invariant, which seem like a redundant feature whose functionality is covered by transitions and guards. We also pick the transition apart, even moreso than in Structured Transition Guards. Instead of using a 5-tuple of source, target, symbol, guard and action, we take a more decoupled approach.

We deconstruct the transition into a symbol-function, $$S \colon L \to A$$, a target-function, $$T \colon L \times A \to L$$, and a guard-function $$G \colon L \times A \to X \to \mathbb{B}$$, where $$A$$ is the alphabet. These are all lifted up into the tuple defining the HA. The actions are also lifted up, and defined as a function mapping locations and symbols to algebraic equations:

\begin{equation*} H \colon L \times A \to X \times X \to X \end{equation*}

Thus, given a location $$l$$, we can compute the symbols of the edges $$S(l) = \{ s^\prime \dots \}$$, as well as their corresponding targets $$T(l,s^\prime)$$, guards $$G(l,s^\prime)$$, and actions $$H(l,s^\prime)$$. Given a final state of a continuous problem, $$X^-$$, the initial state of the next continuous problem is here any $$X^+$$ that satisfies $$H(l,s^\prime)(X^-,X^+) = 0$$. A HA with the action $$H(l,s^\prime)(X^-,X^+) = X^- - X^+$$, is equivalent to a HA without an action, as it will be the case that $$X^+ = X^-$$.

We can now restate the definition of the HA:

\begin{equation*} H^M_N = (L,X,A,F,S,T,G,H) \end{equation*}

And its components:

\begin{equation*} \begin{aligned} L &\subseteq \Z^M & S &\colon L \to A \\ X &= \R^N \times \R^N \times \R & T &\colon L \times A \to L \\ A &\subseteq \Z & G &\colon L \times A \to X \to \mathbb{B} \\ F &\colon L \to X \to \R^N & H &\colon L \times A \to X \times X \to X \end{aligned} \end{equation*}

## An abstractor so primitive

We put actions to work by constructing, in a primitive fashion, abstractions through simulation. An abstraction, in the context of system-theory, is described in f.ex. [Pappas1996]:

Webster's dictionary defines the word abstraction as "the act or process of separating the inherent qualities or properties of something from the actual physical object or concept to which they belong". In system theory, the objects are usually dynamical or control systems, the properties are usually the behaviors of certain variables of interest and the act of separation is essentially the act of capturing all interesting behaviors. In summary, Webster's definition can be applied to define the abstraction of a system to be another system which captures all system behavior of interest. Behaviors of interest are captured by an abstracting map denoted by $$\alpha$$. Abstracting maps are provided by the user depending on what information is of interest.

And is illustrated in Fig. 1 System Abstractions which is reconstructed below:

Our method of abstraction-through-simulation is parametrized on a concrete system, $$c$$, a measure of badness, $$\beta$$, and an interval $$T = [t_0,t_1]$$. It constructs a piecewise affine abstraction, a, over $$T$$, whose abstracted behaviour $$a(t)$$, satisifies $$\left\lVert a(t) - c(t)\right\rVert_2 < \beta$$, $$\forall t \in T$$.

For a given conrete function, $$f$$ and constant $$\beta$$, we start by defining the HA, $$H_{abstractor}(f,\beta)$$, as:

\begin{equation*} \begin{aligned} L &= \{ 0 \} & S(l) &= \{ 0 \} & T(l,s) &= l\\ F(l,s) &= \dot{x} & G(l,s) &= \left\lVert x - c(t) \right\rVert_2 - \beta & H(l,s) &= x^+ - c(t) \end{aligned} \end{equation*}

We then simulate this HA over $$T$$, starting out at $$(0,c(t_0))$$. Each self-transition marks the end of an interval, $$T_i = [t_{i},t_{i+1}]$$, where $$\left\lVert a(t) - c(t) \right\rVert_2 < \beta$$, $$\forall t \in T_i$$. Note that this can hold outside $$T_i$$, and that $$T_i$$ is a conservative approximation. The action, $$H$$, will at each self-transition move the continous state of the HA to the current state of the concrete system, and ready itself to compute the next interval. The result of this simulation is a set of intervals $$\{T_0,\ldots,T_{n-1}\}$$, or points in time $$\{t_0, \ldots, t_n\}$$, which let us define the abstracted system, a PWA:

\begin{equation*} \begin{aligned} L &= \{ l_i \mid i \in n \} & S(l) &= \begin{cases} l \neq n \to \{ 0 \} \\ l = n \to \emptyset\end{cases} & T(l,s) &= l + 1\\ F(l,s) &= \dot{x} - \frac{c(t_{l+1}) - c(t_{l})}{t_{l+1} - t_{l}} & & & G(l,s) &= t_{l + 1} - t \end{aligned} \end{equation*}

We illustrate the method for $$f(t) = \sin({\pi \cdot t})$$, $$\beta \in \{ 0.25, 0.5, 0.75 \}$$, and $$T = [0,5]$$. The simulations are done with hysj and sundials, and illustrated with matplotlib1. The abstraction functions are labelled $$a_{\beta}$$, and the concrete function is labelled $$c$$. First $$H_{abstraction}(f,\beta)$$ is simulated over $$T$$ to construct $$\{t_0, \ldots, t_n\}$$:

We then compute the PWA abstractions, and finally simulate them over the same interval:

1

Code listing below.

PWA

Piecewise affine

HA

Hybrid automaton

## Bibliography

Pappas1996

"George J. Pappas and Shankar Sastry", "Towards Continuous Abstractiosn of Dynamical and Control Systems"

Schaft2000(1,2)

"Arjan van der Schaft and Hans Schumacher", "An introduction to hybrid dynamical systems"

## Code

import hysj

continuous = hysj.simulators.continuous
discrete   = hysj.simulators.discrete
hybrid     = hysj.simulators.hybrid

print('modelling...')
abstractions = range(number_of_abstractions)

#NOTE: discrete model - jeh
bad_abstraction_symbols = [ i for i in abstractions ]

#NOTE: continuous model - jeh
ir = hysj.mathematics.Program()

t = ir.symbol()
pi = ir.pi()

concrete = ir.sine(ir.multiplication([pi,t]))
abstract_variables = [ ir.variable(t,1) for i in abstractions ]

for i in abstractions ]

ir.assertion(
ir.strict_inequality(
for i in abstractions ]

equations = [ ir.equality(abstract_variable[1],ir.zero())
for abstract_variable in abstract_variables ]

problem = hybrid.Problem(
program = ir,
discrete = discrete.Problem(
make_target  = lambda l,s: l,
is_immediate = lambda l,s: False),
continuous = hybrid.ContinuousProblem(
variables = continuous.Variables(independent = t,
dependent   = abstract_variables),
make_equations  = lambda m,l: equations,
make_action = lambda m,l,s: [([s,0],concrete)])

problem.time = t
problem.concrete = concrete
problem.abstractions = abstractions
problem.abstract_variables = abstract_variables

problem.initial_valuation = hybrid.Valuation(
discrete = [0],
continuous = continuous.Valuation(
independent = 0.0,
dependent = [[0.0,0.0] for i in problem.abstractions]))

problem.config = hybrid.Config(
discrete   = discrete.Config(),
continuous = continuous.Config(
tolerance = continuous.Tolerance(
relative = 1.0e-2,
absolute = 1.0e-3),
step = continuous.Step(
mode  = continuous.StepMode.fixed,
delta = 0.001),
stop = 5.01)) #FIXME: need to check if tstop reached when overlapping with constraint - jeh

print('done...')
return problem

def simulate_concrete_problem(problem):
from copy import deepcopy
print('simulating...')

solution = hybrid.make_solution(
problem           = problem,
initial_valuation = problem.initial_valuation,
config            = problem.config)

trajectories = []

events = []
while event := solution():
if(event == discrete.Event.vertex):
trajectories.append((
tuple(solution.discrete().state().location()),
[]))
if(event == continuous.Event.start or
event == continuous.Event.step):
trajectories[-1][-1].append(deepcopy(solution.continuous().state().valuation))
if(event == continuous.Event.stop or
event == continuous.Event.fail):
break
events.append(event)
print('done...')
return events,trajectories

def make_abstract_problem(concrete_problem,concrete_trajectories):
import itertools

ir = hysj.mathematics.Program()

T = [ s.independent for t in concrete_trajectories for s in t[1] ]
P = [ [ s.dependent[i][0] for t in concrete_trajectories for s in t[1] ] for i in concrete_problem.abstractions ]

I = [ [ next(g)
for i,g in itertools.groupby(range(len(T)),lambda j:P[i][j]) ]
for i in concrete_problem.abstractions ]
A = [ [ir.constant((P[i][I[i][j+1]] - P[i][I[i][j]])/(T[I[i][j+1]] - T[I[i][j]]))
for j in range(len(I[i]) - 1) ]
for i in concrete_problem.abstractions ]

t = ir.symbol()
zero = ir.zero()

X = [ ir.variable(t,1)
for i in concrete_problem.abstractions ]
F = [ [ ir.equality(ir.subtraction([a,X[i][1]]),zero)
for a in A[i] ]
for i in concrete_problem.abstractions ]

T_next = [ [ T[I[i][j + 1]]
for j in range(len(I[i]) - 1) ]
for i in concrete_problem.abstractions ]
G = [ [ ir.assertion(ir.strict_inequality(ir.constant(T_next[i][j]),t))
for j in range(len(I[i]) - 1) ]
for i in concrete_problem.abstractions ]

def make_equations_fn(m,l):
return [F[i][j] for i,j in enumerate(l)]
def make_constraint_fn(m,l,s):
return G[s][l[s]]

abstract = hybrid.Problem(
program = ir,
discrete = discrete.Problem(
make_symbols = lambda l: [ i for i in concrete_problem.abstractions if l[i] != (len(I[i]) - 2)],
make_target  = lambda l,s: l[:s] + [l[s]+1] + l[s+1:],
is_immediate = lambda l,s: False),
continuous = hybrid.ContinuousProblem(
variables = continuous.Variables(independent = t,
dependent   = X),
make_equations = make_equations_fn,
make_constraint = make_constraint_fn))

abstract.initial_valuation = hybrid.Valuation(
discrete = [ 0 for i in concrete_problem.abstractions ],
continuous = continuous.Valuation(
independent = 0.0,
dependent = [[0.0,0.0] for i in concrete_problem.abstractions ]))
return abstract

def simulate_abstract_problem(concrete_problem,abstract_problem):
from copy import deepcopy
print('simulating...')
solution = hybrid.make_solution(
problem           = abstract_problem,
initial_valuation = abstract_problem.initial_valuation,
config            = concrete_problem.config)

trajectories = []
events = []
while event := solution():
if(event == discrete.Event.vertex):
trajectories.append((
tuple(solution.discrete().state().location()),
[]))
if(event == continuous.Event.start or
event == continuous.Event.step):
trajectories[-1][-1].append(deepcopy(solution.continuous().state().valuation))
if(event == continuous.Event.stop or
event == continuous.Event.fail):
break
events.append(event)
print('done...')
return events,trajectories

def make_concrete_series(concrete_problem,
trajectories):
calculator = hysj.calculators.Basic(concrete_problem.program)
time = [ s.independent for t in trajectories for s in t[1] ]
return [ calculator([concrete_problem.concrete],[concrete_problem.time],[t]) for t in time ]

calculator = hysj.calculators.Basic(concrete_problem.program)
return [ calculator(l) for l in

def illustrate_concrete_simulation(problem,trajectories):
print('illustrating...')
import hysj.latex
from matplotlib import pyplot as plot
from matplotlib.animation import FuncAnimation as Animation
from matplotlib.animation import writers as animation_writers

variables = problem.continuous.variables

def latex_symbol_renderer(s,d):
return {
tuple(variables.independent.index()): 't'
}.get(tuple(s.index()),f'a_{d}')

latex_renderer = hysj.latex.Renderer(problem.program,latex_symbol_renderer)

time = [ s.independent for t in trajectories for s in t[1] ]

abstract_series = [ [ s.dependent[i][0] for t in trajectories for s in t[1] ] for i in problem.abstractions ]

number_of_series = 2*len(abstract_series) + 1
colormap = plot.get_cmap('Dark2')

concrete_color = colormap(len(problem.abstractions))
abstraction_colors = [ colormap(i) for i in problem.abstractions ]

concrete_series = make_concrete_series(problem,trajectories)

calculator = hysj.calculators.Basic(problem.program)
[problem.time,problem.abstract_variables[i][0]],
[t,a])
for t,a in zip(time,abstract_series[i]) ]
for i in problem.abstractions ]

abstraction_badness_colors = [ colormap(i + len(problem.abstractions) + 1) for i in problem.abstractions ]

series = [ [concrete_series,*abstract_series],

frame_step   = 5
frame_count  = len(time) // frame_step

figure, axes = plot.subplots(2,1,sharex=True,gridspec_kw={'height_ratios': [3,1]})

margin = 0.1
axes[0].set_xlim((time[0],time[-1]))
axes[0].set_ylim((-1.0-margin,1.0+margin))

axes[1].set_xlabel(f'${latex_renderer(variables.independent)}$')

for i in problem.abstractions:
color = abstraction_colors[i],
linestyle='--')

labels = [ [ 'c', *[f'$a_{{{l}}}$' for l in abstraction_badness_limits ] ],
[f'$a^{{\ast}}_{{{l}}}$' for l in abstraction_badness_limits ] ]
styles = [ [ '-', *['-' for i in problem.abstractions] ],
['-' for i in problem.abstractions]]
colors = [ [concrete_color, *abstraction_colors],
abstraction_colors ]
lines = [ [ axes[i].plot([],[],color=colors[i][j],linestyle=styles[i][j],label=labels[i][j])[0]
for j,s in enumerate(S) ]
for i,S in enumerate(series) ]

axes[0].title.set_text(f'abstracting ${latex_renderer(problem.concrete)}$')

axes[0].legend(loc='lower left')

def animate(frame_index):
first, last = 0, min((frame_index + 1) * frame_step,len(time) - 1)

for i,S in enumerate(series):
for j,s in enumerate(S):
lines[i][j].set_data(time[first:last],series[i][j][first:last])
for a in axes:
a.relim()
a.autoscale_view()

return [ l for L in lines for l in L ]

animation = Animation(figure,
animate,
frames = frame_count,
interval = 1,
blit = True)

animation.save('files/actions-and-abstractions-0.mp4',
writer = animation_writers['ffmpeg'](fps=30),
dpi = 150.0)
print('done...')

def illustrate_abstract_simulation(concrete_problem,abstract_problem,
concrete_trajectories,abstract_trajectories):
print('illustrating...')
import hysj.latex
from matplotlib import pyplot as plot
from matplotlib.animation import FuncAnimation as Animation
from matplotlib.animation import writers as animation_writers

variables = abstract_problem.continuous.variables

abstractions = range(len(variables.dependent))

def latex_symbol_renderer(s,d):
return {
tuple(variables.independent.index()): 't'
}.get(tuple(s.index()),f'a_{d}')

latex_renderer = hysj.latex.Renderer(abstract_problem.program,latex_symbol_renderer)

time = [ s.independent for t in abstract_trajectories for s in t[1] ]
series = [ make_concrete_series(concrete_problem,abstract_trajectories),
*[ [ s.dependent[i][0] for t in abstract_trajectories for s in t[1] ] for i in abstractions ] ]

colormap = plot.get_cmap('Dark2')

concrete_color = colormap(len(concrete_problem.abstractions))
abstraction_colors = [ colormap(i) for i in concrete_problem.abstractions ]

colors = [ concrete_color, *abstraction_colors ]

calculator = hysj.calculators.Basic(abstract_problem.program)

frame_step   = 5
frame_count  = len(time) // frame_step

figure, axes = plot.subplots(1,1)

margin = 0.1
axes.set_xlim((time[0],time[-1]))
axes.set_ylim((-1.0-margin,1.0+margin))

labels = [ 'c', *[f'$a_{{{l}}}$' for l in abstraction_badness_limits ] ]
linestyles = [ '--', *['-' for l in abstraction_badness_limits ] ]
lines = [ axes.plot([],[],color=colors[i],label=labels[i],linestyle=linestyles[i])[0]
for i in range(len(series)) ]

axes.title.set_text(f'abstractions')
axes.legend(loc='lower left')

def animate(frame_index):
first, last = 0, min((frame_index + 1) * frame_step,len(time) - 1)

for i,S in enumerate(series):
lines[i].set_data(time[first:last],
series[i][first:last])
axes.relim()
axes.autoscale_view()

return lines

animation = Animation(figure,
animate,
frames = frame_count,
interval = 1,
blit = True)

animation.save('files/actions-and-abstractions-1.mp4',
writer = animation_writers['ffmpeg'](fps=30),
dpi = 150.0)
print('done...')

try:
concrete_problem = make_concrete_problem([0.25,0.5,0.75])
_,concrete_trajectories = simulate_concrete_problem(concrete_problem)
abstract_problem = make_abstract_problem(concrete_problem,concrete_trajectories)
_,abstract_trajectories = simulate_abstract_problem(concrete_problem,abstract_problem)

illustrate_concrete_simulation(concrete_problem,concrete_trajectories)
illustrate_abstract_simulation(concrete_problem,abstract_problem,
concrete_trajectories,abstract_trajectories)

except Exception as e:
import traceback
traceback.print_exc()