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 5tuple of source, target, symbol, guard and action, we take a more decoupled approach.
We deconstruct the transition into a symbolfunction, \(S \colon L \to A\), a targetfunction, \(T \colon L \times A \to L\), and a guardfunction \(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:
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:
And its components:
An abstractor so primitive
We put actions to work by constructing, in a primitive fashion, abstractions through simulation. An abstraction, in the context of systemtheory, 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 abstractionthroughsimulation 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:
We then simulate this HA over \(T\), starting out at \((0,c(t_0))\). Each selftransition 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 selftransition 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_{n1}\}\), or points in time \(\{t_0, \ldots, t_n\}\), which let us define the abstracted system, a PWA:
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:
Glossary
 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 def make_concrete_problem(abstraction_badness_limit_constants): print('modelling...') number_of_abstractions = len(abstraction_badness_limit_constants) 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 ] abstraction_badness = [ ir.power(ir.subtraction([concrete,abstract_variables[i][0]]),ir.constant(2)) for i in abstractions ] abstraction_badness_limits = [ ir.constant(l) for l in abstraction_badness_limit_constants ] abstraction_is_bad = [ ir.assertion( ir.strict_inequality( abstraction_badness_limits[i], abstraction_badness[i])) 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_symbols = lambda l: bad_abstraction_symbols, 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_constraint = lambda m,l,s: abstraction_is_bad[s]), make_action = lambda m,l,s: [([s,0],concrete)]) problem.time = t problem.concrete = concrete problem.abstractions = abstractions problem.abstract_variables = abstract_variables problem.abstraction_badness = abstraction_badness problem.abstraction_badness_limits = abstraction_badness_limits 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.0e2, absolute = 1.0e3), 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 ] def make_abstraction_badness_limits(concrete_problem): calculator = hysj.calculators.Basic(concrete_problem.program) return [ calculator(l) for l in concrete_problem.abstraction_badness_limits ] 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) def make_abstraction_badness_series(): return [ [ calculator([problem.abstraction_badness[i]], [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_series = make_abstraction_badness_series() abstraction_badness_colors = [ colormap(i + len(problem.abstractions) + 1) for i in problem.abstractions ] series = [ [concrete_series,*abstract_series], [*abstraction_badness_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.0margin,1.0+margin)) abstraction_badness_limits = make_abstraction_badness_limits(problem) axes[1].set_ylim(margin,max(abstraction_badness_limits) + margin) axes[1].set_xlabel(f'${latex_renderer(variables.independent)}$') for i in problem.abstractions: axes[1].axhline(y = abstraction_badness_limits[i], 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[1].title.set_text('abstraction badness') 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/actionsandabstractions0.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.0margin,1.0+margin)) abstraction_badness_limits = make_abstraction_badness_limits(concrete_problem) 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/actionsandabstractions1.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()