Interest to cooperate :-)

This text is an extraction from some project descriptions, project proposals,
heavily condensed. It is only to inform the OROCOS community that we here at
GMD, the German National Research Centre for Computer Science,
AiS, Institute for Autonomous Intelligient Systems
are interested in what's going on with OROCOS. Any comment (+ and/or -) is
welcome.

Contact: [email protected]

The text describes our view, how robot controller should be designed.

VerS --- Dependable Embedded Systems

VerS investigates the construction of embedded systems which are
dependable in that correct functionality and satisfaction of hard
real-time constraints are guaranteed.  Dependability is a necessary condition
for systems acting in possibly safety-critical environments.  Hard real-time
implies that a reaction will take place in an a priori specified interval of
time.  

VerS is based on the approach of synchronous object-oriented
programming.  Emphasis is on abstracting and extending engineering
techniques in cooperation with industry and research units aiming at a
robust system architecture, and on supporting the emerging technology by
formalisms and tools. 

In the future VerS will focus on dynamic modification of systems and on
distributed systems.

The researchers of team VerS are/have been engaged in two ESPRIT-projects
(SYRF and CRISYS).

1.1 Motivation

Embedded reactive systems are crucial components of controllers for robots,
plants, cars, up to household utensils.  To gain flexibility such devices are
built using micro-controllers with an increasing share of software. The
software consists out components (reactive objects) communicating with each
other and the environment by messages (signals). This is independant of
whether the system is centralized or distributed. Two paradigms are in use to
design such systems:

- event-triggered systems: the reaction of an object is effected by the
  signals from the environment and other objects. Occurence of a signal
  ("event") causes activity.

- time-triggered systems: the system itself decides at what points in time
  the objects have to react. The state of the signals (their value
  when the reaction is initiated) is given to the objects. An abstract time
  generated inside the system itself causes activity.

Industry, customers and the public depend on a reliable functionality of
embedded systems. In this context time-triggered systems are preferable.
Though they require a lot of pre-planning at design-time and are less
flexible than event-triggered systems, they offer especially in
high-load scenarios predictable service and are more robust and testable. 

1.2 The Synchronous Approach

A viable abstraction of the concrete notion of time in time-triggered systems
is achieved by synchronous languages. They have been specifically designed by
mixed teams from Control Theory and Computer Science to deal with discrete time
models, based on a precise mathematical model.

Synchronous modeling reflects the basic idea of digital hardware design
and of many engineering formalisms: All processes proceed in discrete
steps controlled by a clock.  Triggered by the tick of a clock, a system
starts to react and the reaction is finished in time before the next
tick occurs (perfect synchronization hypothesis).  This idea is unusual
in the software domain, although real-time systems (single-loop programs
e.g.) are designed according to this assumption. 

We combine the model of a clocked process and the construction of
object-oriented systems: The components of an application are objects.
At the tick of the clock, all signals provided by the
environment are made available to all objects.  The reaction causes the
execution of operations of the objects; their internal state may change and
signals may be emitted. The activities (and communication) of of all objects
must be (provable) finished before the next tick occurs. 

Advantages of this hypothesis are: understandable and highly abstract
design; deterministic and reproducible behavior of the program. 
Concerning system validation, the synchronous approach has many
advantages.  Verification on finite-state models (model-checking,
automata abstraction) is quite successful, because generated models are
smaller as the standard models generated by finite automata.  Moreover,
synchronous languages offer an original way for specifying critical
properties by means of synchronous observers.  These properties may be
proven at compile-time or, complimentarily, tested at run-time. 

We forecast that the synchronous model will gain a similar prominence in
controller design as the object-oriented model nowadays has in SW-engineering
community.

1.3 State Of The Art

... Petri nets ... message sequence charts ... annotated FSM ... Statecharts
... Esterel ... Lustre/Scade ... timed automata ... OMITTED

2. Results

Our past and current research adresses [Literatur:sync,dsgn]

- a small ''semantic engine'' for highly compact generation of models and code.

- integration of object-oriented and synchronous design.

- integration of design styles based on continous state information
  (e.g. difference equations) with discrete state information (e.g. finite
  state machines).

The team VerS has been the first group in the synchronous community to
have a smooth integration of the different synchronous formalisms based
on a precise mathematical model.  It is the first group which supports
this integration by a programming environment, too. 

We generate target code for small micro-controllers (or directly
hardware formats) which is highly efficient with regard to time as well
as space constraints, even for object-oriented programs.

2.1 sE

The team has developed the Java dialect sE.  sE integrates synchronous
and object-oriented modeling, thus enabling proofs of system assertions
by model-checking as well as a robust and flexible design of complex
systems.  In sE

- a system is defined by classes, which encapsulate both real-time
  behavior and data.

- real-time behavior of a class is defined as synchronous behaviour.
  As notation we use well known formalisms similar to Esterel, Lustre
  and Statecharts. The styles are smootly integrated.

- data of a class consists of methods and fields as usual, which may
  be used by the synchronous part exclusively.

- the application is a tree-like structure of objects of these classes,
  rooted in one instance of a configuration class, which is responsible
  for initialization.

- Synchronous Automata (SyA, see 2.2) are used as intermediate language.

- based on SyAs, re-targetable C-code is produced. For this C-code
  timing constraints are checked and then target hardware selected.

Note, that validation, including model-checking, is done on the same
intermediate language as code generation, i.e. no separate model has to be
constructed for validation. This increases substantially the designer's
belief, that the application fulfills proven assertions.

The synchronous model enables us to apply hardware evaluation techniques to
the real-time behavior of the whole application.  From an operating
system point of view the generated target-code can be considered as a
compiler-generated static scheduler for the functions and procedures of the
abstract data types, where the activation conditions are boolean
formulas made from signal and state information.

2.2 Synchronous Automata SyA

Synchronous Automata (SyA) are used to capture the reactive behavior.  A
SyA defines the reaction to some input signals producing output signals.
A reaction may depend on previous reactions.  This memory is encoded by
a finite set of registers. 

We present a SyA by statements of the form "o <- e" and "r <- e". 
The signal "o" is present, resp.  the register "r" is active, if the
boolean expression "e" evaluates to true.  The expression "e" contains
signals as well as registers. 

The reaction function "P!" is a set of equations, which defines
the instantaneous reaction of the synchronous program: whether output
signals are present or absent in a reaction.  The synchronous compiler
defines the sequence for evaluating the assignments "o <- e".
This step is called causality analysis. 

The next state function "P>" is a set of equations, which
defines the value of the registers for the next reaction, i.e.  the state
for the next reaction.  This evaluation terminates a reaction.  The
assignments "r <- e" may be executed in parallel.  As an
example consider the reactive definition:

loop
   await next i; emit s;
end;

"i" is input signal, "s" is output signal. The
await-statement introduces a register "r", because it has to be
remembered, whether the program waits for "i" to be present in an
input event.  Thus one equation for the register "r" defines the next
state function, and one equations for the output signal "s"
defines the reaction function. 

The program is compiled into the SyA with

P! :  s <- i&r
P> :  r <- alpha or (r & !i) or (r & i)

The next state function "P>" consists out of three parts: (1) "alpha",
the system initialization state, is true when the loop is entered, (2)
"(r & !i" if the program stays waiting when "i" is not present, (3) "r &
i" if the program got "i" in an instant, the wait terminated and the
loop is re-executed.  The next state function is later optimized to
"r <- alpha or r". 

It works as follows: Initially all the registers are set
to false, "alpha" is set to true since "alpha" is the initial state.
At the initial reaction no signal will be emitted. The next state is
{ r } ("alpha" does not belong to any follower state by definition).
Then signal "s" will be emitted in any reaction  the
input signal "i" is present. { r } is its own successor state.       

A reactive SyA computes a unique reaction in a finite amount of time. Because
of synchronous communication, outputs are immediately available to calculate
more outputs and this process has to terminate for the automaton to be
reactive. This is captured by the existence of a fixed-point for the function
"P!". Programs with a unique fixed-point are called causally correct.
This is checked by sE and excludes anomalies like programs in which
emission of a signal triggers a program component, that cancels the component,
that made the emission.

A SyA only contains boolean expressions.  Advantages are, that equations
(1) can be processed by BDD systems (e.g. model checking), and (2) they
can be linked, comparable to the linking of modules based on external
names.  Equations of the reaction function with the same left-hand-side
are or-ed, all others are merged.  The causality check has to be redone.
Thus we can successfully circumvent the state explosion problem which
burdens the building of cross products in other FSM formalisms. 

But the distinctive advantage is that a SyA can be expressed in virtually any
hardware or software description language. sE has back-end drivers for Verilog,
BLIF, DC and C. Using the first alternative the scheduler can be burned into an
FPGA thus ensuring very fast response times.  The last alternative maps the
SyA to C code which in turn can be compiled for the microcontroller present
in almost all embedded systems anyhow.

3. Future Work

Our main research will be to extend the technology into two directions:

- dynamic creation and deletion of reactive objects
- distributed controller.

4. Literature

{sync}  A.Poign\'e, M.Morley, O.Maffeis, L.Holenderski, R.Budde,
        The Synchronous approach to Designing Reactive Systems, 
        Formal Methods in System design, Vol 12, No.2, 1998

{dsgn}  R.Budde, P.Ploeger, K.H. Sylla,
        A Synchronous Object-Oriented Design Flow for Embedded
        Applications
        FDL '99, Kluwer, 1999