Adaptive sample bias for rapidly-exploring random trees with applications to test generation

Abstract

We are developing a randomized approach to test generation for hybrid systems, and control systems in general, inspired by the rapidly-exploring random trees (RRTs) technique from robotic motion planning which has proved successful in solving high dimensional nonlinear problems. The approach represents an automated analysis alternative for systems where computing the reachable set is intractable. The standard RRTs method creates a tree in the state space by uniformly generating random sampling point and trying to find inputs which connect them. In this paper we propose a novel adaptive sampling strategy. We initially bias the distribution so that states near the "unsafe" set are selected. We continually monitor the growth of the tree. As the growth rate of the tree declines we adjust the sampling distribution to be less biased. This adaptive search strategy varies bias between "greedy" and global, often finding test trajectories more quickly than the traditional algorithm.