Sampling-based Algorithm for Testing and Validating Robot Controllers
Sampling-based Algorithm for Testing and Validating Robot Controllers
复制标题
用于测试和验证机器人控制器的基于采样的算法
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Vijay R. Kumar
中科院分区：
文献类型：
--
作者：
Jongwoo Kim;J. Esposito;Vijay R. Kumar
解决了测试复杂无功控制系统和验证多智能体控制器有效性的问题。测试和验证包括通过探索所有对抗性输入和错误轨迹的干扰来搜索导致系统故障的条件。这个测试问题与运动规划有关。在这两种情况下，都有一个目标或规范集，由状态空间中感兴趣的一组点组成，用于查找计划、演示失败或验证。与运动规划问题不同的是，测试问题通常涉及到对于干扰或对抗性输入而言不可控的系统，因此，可到达的状态集是整个状态空间的一个小子集。在这项工作中，基于快速探索随机树（RRT）算法的基于采样的算法应用于测试和验证问题。首先，分析了影响RRT算法搜索率的一些因素，这种分析有助于激发一些改进。然后，对原RRT算法进行了三种改进，使其适用于不可控系统。首先，引入了一个新的距离函数，该函数结合了系统的动态信息来选择节点进行扩展。其次，引入加权来惩罚重复选择但未能扩展的节点。第三，提出了一种基于树生长的自适应修改采样概率分布的方案。通过几个例子说明了该算法的应用，并提供了计算统计来说明每次修改的效果。最后的算法在一个25状态的例子中得到了验证，与传统的RRT相比，计算时间减少了近一个数量级。该算法同样适用于非小时间局部可控系统的运动规划。
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.