Actions and Abstractions

John Eivind Helset

2021-03-06 22:21

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.

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.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 ]

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.0-margin,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/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))


  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/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()