Zero crossing

During the past week Jan has implemented event detection using first-order interval polynomial arithmetic. For the purpose of simulating hybrid ODEs it is necessary to determine when an event must have happened and when an event may have happened in a given time interval. Below follow two plots showing zero-crossing detection for solutions to the ODE 

x'' = -10, x'(0) = 0, x(0) = 5 for times t in [0,2] 

where the solution is computed with a uniform step size of 0.2. In the following plot solving is halted when there is certainty that the solution must have crossed zero somewhere in the last time step.  

and in the following plot solving is halted when there is a possibility that the solution may have crossed zero somewhere in the last time step.  

Symbolic differentiation with subexpression sharing

This week Yingfu and Adam started working on an implementation of symbolic differentiation for expressions in Scala. A differential operator implementation is ready for a small expression type including a few operators. An interesting part of the implementation is the subexpression sharing mechanism. Here, an "expression context" is used to maintain a collection of references to intermediate expressions (corresponding to a list of let bindings). Constructors of the expression types are not called directly in the program. Instead, factory methods are used for instantiation, which first look in the expression context to see if an existing instance can be referenced. A simple way to implement the expression context is to use a Scala Map object. Here, it is possible to leverage the default implementations of the hashCode method which come with Scala case classes, making it possible to use the expressions themselves as keys in the map.

As a concrete example, consider differentiating the expression x^2 + x^2 with respect to x. The result of applying our symbolic differentiation operator is the following (in pseudocode):

let

  x_4 = Plus(x_0,x_0)

  x_1 = Times(x_0,x_0)

  x_5 = Plus(x_4,x_4)

  x_2 = Plus(x_1,x_1)

  x_3 = Literal(1.0)

  x_0 = Variable("x")

in

  x_5

Who can handle Zeno

During the past week's CyPhy workshop Jan learned that there are no general purpose tools for simulation of hybrid systems that correctly handle Zeno points. Zeno points of a hybrid system are those times that have a bounded neighborhood in which the system makes an infinite number of transitions. The state of the art is to employ symbolic heuristics to detect Zeno points, but even mature tools such as OpenModelica can generate erroneous simulations at and following Zeno points. There is thus a need for hybrid simulators that can detect, or at least indicate the presence of Zeno points.

Amber model and Modelica tutorial

The two most interesting point Mingkun picked up from CyPhy workshop are the mathematical model of Amber robot and the way how tutorials of Modelica are presented. Amber model illustrates how simple the model could become once the most significant parts of the problem are identified. However, the performance of simulation is limited by the poor symbolic computation ability, which demands quick improving. Despite of the issue of platform-dependent, the process of following tutorials of Modelica is very enjoying. Users can get immediate feedback from this.

A formidable optimization challenge

This week Adam participated in CyPhy 2012, a workshop on Cyber-Physical Systems. He found it interesting to see people with such varied backgrounds as programming languages, robotics, communication and bioinformatics come together in a common discussion. A particular eye-opener for Adam was how much room for improvement there can be in simulation models implemented in industrial-strength (but generic) tools such as Mathematica and Matlab. A specific model from robotics presented at the workshop would require a computation that currently takes two hours to be performed in ten milliseconds in order to be considered real-time. This is a formidable optimization challenge, one where current research can be applied to great benefit (see paper Mathematical Equations as Executable Models of Mechanical Systems) and a great example of why computer scientists and domain experts have a lot to gain from talking to each other.

Integration in first-order arithmetic

Jan has finished an implementation of a primitive function operation on first-order polynomials with interval coefficients. This is one of the main components of the Picard operators that are the basis for the hybrid interval ODE solver that is under development. The main difficulty was in the choice of degree reduction algorithm, which maps the nonlinear terms generated buy integration back to first-order form. The next component Jan will target is the containment relation, which is used to detect when iterated application of the Picard operator may be terminated.

Language support for dynamic models

This week Adam continued reading Languages and Tools for Hybrid Systems Design by Carloni, Passerone, Pinto, and  Sangiovanni-Vincentelli. Among the languages covered by the survey is Shift, which differs from the other languages in the survey in that it supports models whose structure can change during a simulation. Two modern modeling languages which support this type of dynamic models are Acumen and Yampa. Acumen supports this feature in a manner similar to Shift, through the creation, movement and destruction of its natural objects. In Yampa, you can implement a similarly dynamic model by defining it in terms of switching combinators, one of which was discussed in an earlier post. It is still not clear to Adam to what degree languages which support dynamic collections of data need to support dynamic reconfiguration of the model itself. This question is interesting because the latter tends to lead to programs which are difficult to understand.