Sampling-Based Algorithm for Testing and Validating Robot Controllers.

摘要

We address the problem of testing complex reactive control systems and validating the effectiveness of multi-agent controllers. 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. We choose to apply sampling-based algorithms to the testing and validation problem. Our work is based on the Rapidly-exploring Random Trees (RRT) algorithm. First we analyse some of the factors that govern the exploration rate of the RRT algorithm. The analysis serves to motivate our enhancements. Then we pro- pose three modifications to the original RRT algorithm, suited for use on uncontrollable systems. First, we introduce a new distance function which incorporates information about the system's dynamics to select nodes for extension. Second, we introduce a weighting to penalize nodes which are repeatedly selected but fail to extend. Third, we propose a scheme for adaptively modifying the sampling probability distribution, based on tree growth. We demonstrate the application of the algorithm via several examples and provide computational statistics 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. Our algorithms are also applicable to motion planning for systems that are not small time locally controllable.