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

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

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
路径规划算法旨在规划某个智能体的行为轨迹, 使其能够在不碰到威胁障碍物 (以下简称威胁) 的情况下
安全且高效地从起始点到达目标点 [1] . 目前, 智能体的路径规划算法 (path planning algorithm) 在工业界和日常
生活的各种系统中被广泛应用, 如自动驾驶汽车的寻路 [2] 、无人机的航迹生成 [3] 、自动机器臂的行为规划 [4] 、
智能仓库机器人物流 [5] 等各种任务都能够被转换为 (或部分转换为) 路径规划问题. 然而, 随着路径规划算法被
应用在各种复杂且重要的任务 (如救援 [6] 、侦察 [7] 、运输 [8] 等) 中, 任何相关系统的失效都会造成巨大的经济损
失. 因此, 在实际投入使用前对这些路径规划算法进行充分测试, 以确认该算法能够满足系统的性能需求就至
关重要.
近 5 年学者们陆续开展面向路径规划算法测试的相关研究工作. 例如, 文献 [9] 基于场景的对称性以及生成
路径的连通性等属性构建蜕变规则, 并提出蜕变测试方法. Li 等人 [10] 针对 UAV 内部的模块提出了蜕变测试方法.
这些研究大都基于路径规划的测试预期问题提出特定的解决方案或工具 [11] . 总体来说, 相关研究仍处于起步阶段,
尚未发现有学者针对智能体的路径规划算法提出完整的动态测试方法, 而规划场景的复杂性以及规划算法的不确
定性为路径规划算法带来了巨大挑战, 具体表现为以下两个方面.
(1) 场景的复杂性. 实际的路径规划场景十分复杂 [12] , 场景中的威胁 (如建筑物、极端天气等) 可能存在多样
的分布. 通常情况下, 路径规划算法的失效表现为智能体按照算法生成的路径行动时做出了一系列错误决策, 导致
相关系统功能或性能需求无法得到满足, 而这种错误的决策序列通常是由多个威胁的特定分布模式所触发的. 例
如, 算法生成的路径会倾向于进入由多个威胁共同构成的“陷阱”中 [13] , 从而导致生成路径的总长度增加, 进而违反
性能需求, 而这种特定的威胁分布模式很难通过传统随机测试 [14] 方法找到.
(2) 规划算法的不确定性. 另一方面, 现实任务场景 (如机器人、无人机救援等) 通常会对算法有较高的性能需
求 [15] , 即需要智能体在短时间内规划出可行且质量较高的路径. 为了同时照顾计算效率及生成路径的质量, 当前
应用最广泛的路径规划算法大多通过对地图的随机采样来快速寻找规划问题的可行解, 例如本文所讨论的快速扩
展随机树算法 (rapidly-exploring random tree, RRT) 就通过在安全区域随机采点来生成一棵覆盖整个任务空间的
随机树, 然后再通过从目标叶子节点向根节点进行回溯来构建一条安全的路径 [16,17] . 然而这一类算法都具有一定
程度的不确定性: 即使是任务场景相同, 算法生成的路径也会不同. 也就是说, 智能体在某个场景中完成了任务并
不意味着其在相同场景中总会做出正确的决策, 即我们无法通过现有执行结果直接判断算法在特定场景是否存在
性能风险 (如是否路径过长). 因此, 如何制定合理的测试策略, 以发现路径规划算法的性能失效风险就成为一大
挑战.
由于上述挑战的存在, 所采用的测试方法应具备以下两个特点.
(1) 测试方法应具备一定的随机性, 以保证生成测试用例的多样性. 无论所采用的测试方法是基于何种理论或
是启发式策略, 其都需要具备探索整个输入空间的能力, 因为只有这样才能保证所有失效测试用例都有一定概率
被生成, 即在某种程度上避免陷入局部最优.
(2) 测试方法应具备寻优能力, 即能够在测试过程中逐渐能够生成更有价值的测试用例. 一条低质量 (如长度
过长等) 的路径通常是由多个威胁的特定分布模式导致的, 而这种威胁分布通常比较隐蔽且不易被发现. 这就要求
测试方法能够根据当前的测试信息进行搜索, 以逐步找到能够暴露算法问题的威胁分布模式.