| J. Kim University
of Pennsylvania, Philadelphia, PA, USA, J.M. Esposito US Naval Academy,
Annapolis, MD, USA and V. Kumar University of Pennsylvania,
Philadelphia, PA, USA |
| The problem of testing complex
reactive control systems and validating the effectiveness
of multi-agent controllers is addressed. Testing and validation involve
searching for conditions
that lead to system failure by exploring all adversarial inputs and disturbances
for errant
trajectories. This problem of testing is related to motion planning. In
both cases, there is a goal or
specification set consisting of a set of points in state space that is of
interest, either for finding a
plan, demonstrating failure or for validation. Unlike motion planning problems,
the problem of
testing generally involves systems that are not controllable with respect
to disturbances or
adversarial inputs and therefore, the reachable set of states is a small
subset of the entire state
space. In this work, sampling-based algorithms based on the Rapidly-exploring
Random Trees
(RRT) algorithm are applied to the testing and validation problem. First,
some of the factors that
govern the exploration rate of the RRT algorithm are analysed, this analysis
serving to motivate
some enhancements. Then, three modifications to the original RRT algorithm
are proposed,
suited for use on uncontrollable systems. First, a new distance function
is introduced which
incorporates information about the system's dynamics to select nodes for
extension. Second, a
weighting is introduced to penalize nodes which are repeatedly selected
but fail to extend. Third,
a scheme for adaptively modifying the sampling probability distribution
is proposed, based on
tree growth. Application of the algorithm is demonstrated using several
examples, and
computational statistics are provided to illustrate the effect of each modification.
The final
algorithm is demonstrated on a 25 state example and results in nearly an
order of magnitude
reduction in computation time when compared with the traditional RRT. The
proposed
algorithms are also applicable to motion planning for systems that are not
small time locally
controllable. |
