| 摘要: |
| 智能体路径规划算法旨在规划某个智能体的行为轨迹, 使其在不碰到障碍物的情况下安全且高效地从起始点到达目标点. 目前智能体路径规划算法已经被广泛应用到各种重要的物理信息系统中, 因此在实际投入使用前对算法进行测试, 以评估其性能是否满足需求就非常重要. 然而, 作为路径规划算法的输入, 任务空间中威胁障碍物的分布形式复杂且多样. 此外, 路径规划算法在为每个测试用例规划路径时, 通常需要较高的运行代价. 为了提升路径规划算法的测试效率, 将动态随机测试思想引入到路径规划算法中, 提出了面向智能体路径规划算法的动态随机测试方法(dynamic random testing approach for intelligent agent path planning algorithms, DRT-PP). 具体来说, DRT-PP 对路径规划任务空间进行离散划分, 并在每个子区域内引入威胁生成概率, 进而构建测试剖面, 该测试剖面可以作为测试策略在测试用例生成过程中使用. 此外, DRT-PP在测试过程中通过动态调整测试剖面, 使其逐渐优化, 从而提升测试效率. 实验结果显示, 与随机测试及自适应随机测试相比, DRT-PP方法能够在保证测试用例多样性的同时, 生成更多能够暴露被测算法性能缺陷的测试用例. |
| 关键词: 软件测试 路径规划算法 动态随机测试 快速扩展随机树生成算法 测试剖面生成 |
| DOI：10.13328/j.cnki.jos.007340 |
| 分类号: |
| 基金项目:国家自然科学基金(62302035, 62403044, 62372021); 中央高校基本科研业务费专项资金(2023JBMC017, FRF-IDRY-23-016) |
|
| Dynamic Random Testing Approach for Intelligent Agent Path Planning Algorithms |
|
ZHANG Xiao-Yi1, LI Xing1, LIU Yang2, ZHENG Zheng3, SUN Chang-Ai1
|
|
1.School of Computer and Communication Engineering, University of Science and Technology Beijing, Beijing 100083, China;2.School of Mechanical, Electronic and Control Engineering, Beijing Jiaotong University, Beijing 100044, China;3.School of Automation Science and Electronic Engineering, Beihang University, Beijing 100191, China
|
| Abstract: |
| Path planning algorithms for intelligent agents are designed to plan the behavior trajectory of an agent so that it can safely and efficiently reach the target point from the starting point without colliding with obstacles. Currently, path planning algorithms have been widely applied in various critical cyber-physical systems. Therefore, it is essential that the path planning algorithms be tested before being put into use to evaluate whether their performance can meet the requirements. However, the distribution patterns of threat obstacles in the task space, which are the inputs of the path planning algorithm, are complex and diverse. Moreover, a relatively high operational cost is usually required when the path planning algorithm plans a path for each test case. To improve the testing efficiency of the path planning algorithms, this study adapts the concept of dynamic random testing into path planning algorithms and proposes the dynamic random testing approach for intelligent agent path planning algorithms (DRT-PP). Specifically, DRT-PP discretely divides the path planning task space and introduces the threat generation probability within each sub-region, thus constructing the test profile. This test profile can be used as a testing strategy in the process of test case generation. Furthermore, the test profile is dynamically adjusted by DRT-PP during the testing process to make it gradually optimized, thereby improving the testing efficiency. Experimental results show that, compared with random testing and adaptive random testing, the DRT-PP approach can not only ensure the diversity of test cases but also generate more test cases that can expose the performance defects of the tested algorithm. |
| Key words: software testing path planning algorithm dynamic random testing (DRT) rapidly-exploring random tree (RRT) test profile generation |
