Page 209 - 《软件学报》2025年第7期

3130 软件学报 2025 年第 36 卷第 7 期

636.3). 与 RRT 相比, DRT 在 RRT3 上的平均失效度 S ( avg )、最大失效度 S ( max )、失效度大于 40 的个数 (>40)、无
效测试用例个数分别从 17.2、43.6、6.7、150.8 变为 18.3、42.1、17.1、159.1, 除了最大失效度略有下降外, 其余
指标均有所提升. 可见, 当 RRT 的生成树最大孩子节点为 3 (即三叉树) 时, RRT 算法性能有所下降, 使得无论运
行 RT 还是 DRT, 都更容易发现具有较大失效度的测试用例. 此外, RT 和 DRT 的对比结果并没有明显变化, 即
DRT 仍然明显好于 RT.
200×200 的基本场景来规划路径规划算法, 该设计旨在对任务空间进行离散处理, 实际使用
此外, 本文采用
时离散化的精度可以根据具体需求而定, 而本文所采用的步长及离散化精度与目前路径规划算法的设计工作是一
致的 (通常选取场景边界的 1/10–1/20 作为步长) [4,16,55] . 最后, 本文针对二维空间进行测试, 二维空间假设是大部分
关于路径规划算法研究的基本假设. 由第 2.4 节的讨论可知, 无论空间的维度如何, 通过 DRT 算法生成测试用例
的代价都要远小于执行路径规划算法的代价, 因此其执行代价可以在某种程度上忽略. 在今后的研究中, 我们会对
*
更多算法 (如 RRT 、PRM 等) 进行测试. 此外, 我们还会进一步考察任务空间大小以及规划维度对 DRT 测试效率
的影响.

5 总结与展望
路径规划算法旨在规划智能体的行为轨迹, 使其在不碰到威胁障碍物的情况下安全且高效地从起始点到达目
标点. 随着物理信息系统 (CPS) 的发展, 这些算法在工业界和日常生活中得到广泛应用, 其失效也会带来巨大损
失. 然而, 由于任务场景中威胁分布的多样性, 如何生成测试用例以触发这些算法的性能风险就成为一大挑战. 为
了解决上述挑战, 本文借鉴自适应随机测试思想, 提出了面向智能体路径规划算法的动态随机测试策略 (DRT-PP).
具体来说, 我们通过对输入空间的离散化以及引入子区域的威胁概率来构建测试剖面, 并在测试过程中通过实时
提取和分析测试信息对测试剖面进行动态调整, 使得我们在得到多样的测试用例的同时, 能够触发更高的失效度,
从而提升测试效率. 实验结果表明, 与传统随机测试 (RT) 以及本文提出的 ART 测试相比, DRT-PP 能够更早地发
现多样且有价值的测试用例; DRT-PP 生成测试用例的平均失效度约为 RT 的 2.5 倍、ART 的 2.4 倍.
在未来工作中, 我们将对 DRT-PP 进行更深入的探究, 包括更多的测试剖面构建方法以及测试剖面调整幅度
*
的自适应更新等. 此外, 我们还将展开专门的实验研究, 对更多路径规划算法 (如 RRT 、PRM) 进行考察, 并提出
更多的功能及性能需求, 以全面评估 DRT-PP 的适用性.

References:
[1] Omeiza D, Webb H, Jirotka M, Kunze L. Explanations in autonomous driving: A survey. IEEE Trans. on Intelligent Transportation
Systems, 2022, 23(8): 10142–10162. [doi: 10.1109/TITS.2021.3122865]
[2] Zhang XY, Arcaini P, Ishikawa F. An incremental approach for understanding collision avoidance of an industrial path planner. IEEE
Trans. on Dependable and Secure Computing, 2023, 20(4): 2713–2730. [doi: 10.1109/TDSC.2022.3159773]
[3] Mohsan SAH, Othman NQH, Li YL, Alsharif MH, Khan MA. Unmanned aerial vehicles (UAVs): Practical aspects, applications, open
challenges, security issues, and future trends. Intelligent Service Robotics, 2023, 16(1): 109–137. [doi: 10.1007/s11370-022-00452-4]
[4] LaValle SM. Planning Algorithms. Cambridge: Cambridge University Press, 2006.
[5] Li JY, Tinka A, Kiesel S, Durham JW, Kumar TKS, Koenig S. Lifelong multi-agent path finding in large-scale warehouses. In: Proc. of
the 35th AAAI Conf. on Artificial Intelligence. Virtually: AAAI, 2021. 11272–11281. [doi: 10.1609/aaai.v35i13.17344]
[6] Colas F, Mahesh S, Pomerleau F, Liu M, Siegwart R. 3D path planning and execution for search and rescue ground robots. In: Proc. of
the 2013 IEEE/RSJ Int’l Conf. on Intelligent Robots and Systems. Tokyo: IEEE, 2013. 722–727. [doi: 10.1109/IROS.2013.6696431]
[7] Fan QJ, Wang FX, Shen XQ, Luo DL. Path planning for a reconnaissance UAV in uncertain environment. In: Proc. of the 12th IEEE Int’l
Conf. on Control and Automation (ICCA). Kathmandu: IEEE, 2016. 248–252. [doi: 10.1109/ICCA.2016.7505284]
[8] Cabreira TM, Brisolara LB, Jr Ferreira PR. Survey on coverage path planning with unmanned aerial vehicles. Drones, 2019, 3(1): 4. [doi:
10.3390/drones3010004]
[9] Wu L, Xi ZY, Zheng Z, Li XL. Application of metamorphic testing on UAV path planning software. Journal of Systems and Software,
2023, 204: 111769. [doi: 10.1016/j.jss.2023.111769]
[10] Li R, Liu H, Lou GN, Zheng X, Liu X, Chen TY. Metamorphic testing on multi-module UAV systems. In: Proc. of the 36th IEEE/ACM