This week’s BEACON Researchers at Work post is by MSU graduate student Andres Ramirez.

Recently, I found myself driving on the wrong side of the road. No, I did not fall asleep. I drove through some parts of New Zealand, where the custom is to drive on the left side of the road. While this experience was exciting, it was also awkward, as I have always driven on the right side of the road. Although we adapted to these new driving conditions, would it not have been great if the vehicle had driven itself instead? In the near future, this might actually become a reality. Specifically, an intelligent vehicle system (IVS) performs adaptive cruise control, lane keeping, and collision avoidance features. As such, an IVS is intended to provide autonomous navigation to facilitate the safe and efficient transportation of passengers across major roadways.

As it turns out, an IVS is just an instance of a more general type of application known as a dynamically adaptive system (DAS). In particular, a DAS uses its sensors to first measure properties about itself and its execution environment at run time. This monitoring information enables the DAS to identify when it should self-adapt in response to changes in its environment. If an adaptation is necessary, then the DAS determines when and how to change the structure and behavior of the application in order to continue satisfying its client’s objectives. Though this is a rather simplistic description of a DAS, designing and implementing a DAS is actually an extremely difficult task.

A key challenge in successfully engineering a DAS is being able to anticipate conditions that might warrant adaptation at run time. This challenge arises because of uncertainty in both the execution environment and the DAS itself. Specifically, it is often infeasible, sometimes even impossible, for a human designer to identify all possible combinations of environmental inputs that a DAS will encounter throughout its lifetime. For instance, humans can interact with a DAS in unpredictable and undesirable ways. Similarly, the monitoring information that a DAS analyzes to detect conditions that warrant adaptation is only “as good” as the sensors it uses to collect that data. These sensors, however, can be imprecise, inaccurate, and unreliable. This uncertainty about what the DAS perceives about its environment can severely limit the adaptation capabilities of the DAS.

To address these concerns, we designed and implemented Loki, an evolutionary computation technique that can automatically discover combinations of system and environmental conditions that prevent a DAS from satisfying its objectives and requirements. Loki’s primary objective is to alter how a DAS perceives its environment at run time such that it self-adapts in undesirable ways. In contrast to other approaches and techniques for evaluating how a DAS responds to different system and environmental stimuli, Loki leverages evolutionary computation techniques to discover interesting combinations of system and environmental conditions that produce undesirable behaviors in a DAS. In particular, Loki is capable of discovering both requirements violations and latent behaviors (unknown behaviors). While a requirements violation prevents the satisfaction of a given design-level objective, a latent behavior manages to satisfy requirements while introducing previously unknown and potentially undesirable behaviors. To achieve these objectives, Loki applies the concept of novelty search to generate environmental conditions that produce the most distinct behaviors in a DAS from those already examined. A key benefit of applying novelty search is that it enables Loki to generalize many behaviors into a more manageable set of representative behaviors that a requirements engineer can manually inspect.

We applied Loki to a simulated IVS prototype that we implemented in the Webots simulation platform. The results obtained thus far have been positive and encouraging.  When compared with other testing techniques, such as randomized testing, Loki managed to discover a significantly larger quantity of different requirements violations and latent behaviors. For instance, Loki discovered a set of system and environmental conditions that prevented the IVS from accurately computing its current velocity, thereby producing a collision with another vehicle in front of the IVS. Similarly, Loki also discovered a slightly different set of system and environmental conditions that produced a more complex interaction between the adaptive cruise control and lane keeping requirements. Specifically, after the IVS collided with the vehicle in front of it, as in the previous example, it then departed from its lane and, in an attempt to re-satisfy its lane-keeping objectives, the IVS side-swiped the same vehicle several times as it steered towards its original lane.

Applying Loki enables a requirements engineer to analyze the set of system and environmental conditions that produce different kinds of undesirable behaviors in a DAS. This information can guide the revision of either the requirements or the design of the DAS in order to disallow these undesirable behaviors. For instance, in our IVS case study, we identified a set of system and environmental conditions that frequently affected distance sensors in the IVS.  Without an accurate estimate of the distance between the IVS and another vehicle in front, the adaptive cruise control module in the IVS might be unable to prevent a collision. Based on this information, we revised the process that the IVS uses to compute its distance to vehicles in front such that the computation is more robust to sensor noise and failures.

In the future, we will investigate how to combine Loki with a probabilistic framework for evaluating the partial satisfaction of requirements. In addition, we will also explore how to leverage the behaviors discovered by Loki to automatically refine a requirements model of the DAS. Perhaps driving through New Zealand will be easier next time?

For more information about Andres’ work, you can contact him at ramir105 at cse dot msu dot edu.