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

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

近年来, 随着集群路径规划逐渐成为研究热点, 相关的测试问题也逐渐受到学者的关注. 例如, 在自动驾驶领
域, 文献 [25,43,44] 就通过引入可避免碰撞的概念以及考虑实际交通中的车辆的行为模式对智能车的路径规划器
进行测试, 以发现关键的交通事故以及其他需求违反模式. Gambi 等人 [45] 则通过构建事故示意图的方式对自动驾
驶的规划器进行测试. Zhang 等人 [2] 则基于自动驾驶路径规划器的测试信息对其失效的原因进行了分析. 朱宇等
人 [46] 讨论了自动驾驶汽车在变道 (lane-change) 场景下的测试方法, 而夏春燕等人 [47] 则面向自动驾驶汽车建立了
路口 (crossing) 场景的测试生成模型. 然而针对通用路径规划算法本身的测试研究还未系统性地展开, 现有面向智
能体路径规划算法的测试方法还相对较少. 现有工作主要着眼于针对这一领域的某些特定属性来生成测试用例.
例如, 文献 [9,13] 基于场景的对称性以及威胁对路径的影响关系构建蜕变规则, 进而提出蜕变测试方法. 文献 [19,48]
基于多智能规划分别提出了蜕变测试方法和自适应随机测试方法.
总体来说, 目前对路径规划算法的测试研究尚处于起步阶段. 现有相关工作大多基于算法的特定应用领域 (如
自动驾驶) 进行测试. 尽管这些系统可能包含路径规划模块, 然而这些测试工作主要着眼于检查多个模块间的协作
能否适应相应的任务需求, 而并非着眼于路径规划算法本身的性能风险. 现有针对路径规划算法测试的文章则主
要针对路径规划的测试预期问题提出具体的蜕变规则和策略, 并没有涉及测试用例的生成策略. 截至目前, 尚未发
现有学者为智能体路径规划算法提出一个完整的动态测试框架. 本文面向该问题提出了具有较强普适性的测试用
例生成及优化方法: 该方法构建了通用且合理的测试剖面, 并基于较为通用的测试输入输出信息设计反馈机制来
更新测试剖面. 此外, 我们还借鉴差分 [49,50] 和蜕变测试的思想定义了面向基于随机采样的路径规划算法的测试结
果评价指标.

2 面向智能体路径规划算法的动态随机测试方法 (DRT-PP)

本节介绍面向智能体路径规划算法的动态随机测试方法. 具体来说, 第 2.1 节介绍智能体路径规划算法的测
试框架, 第 2.2 节介绍 DRT-PP 的流程, 第 2.3 和 2.4 节分别介绍该方法的两个重要组成部分: 测试剖面的构建以
及测试剖面的更新策略.

2.1 面向智能体路径规划算法的测试
软件测试旨在通过生成并运行一系列的测试用例, 来发现被测系统中潜在的失效风险. 本文讨论智能体路径
规划算法的测试问题, 希望生成多样的路径规划场景作为测试用例来运行被测算法, 并对测试结果进行分析和评估.
定义 4 (测试用例). 将路径规划算法的测试用例 t 定义为元组 ⟨E,task⟩, 其中, E = ⟨M,obs⟩ 为规划环境, 包括
X ×Y 的任务空间 M 以及威胁集合 Obs; task = p , p E ⟩ 为规划任务, 其中, p 和 p 为起始点和目标点. 本文主要针
⟨
E
B
B
E
B p 的分布来设计测试用例, 并在测试过程中固定 task 和 M, 因此测试用例 t 的量化特征可以用
对威胁集合 p 和
t.Obs 来表示 (在实际测试时, 我们可以通过调节环境 E 中 Obs 的分布以及仿真时的步长来等效不同的任务 task
以及各种形状的任务空间 M, 因此, 这种简化并不失一般性).
一般来说, 软件测试的目的是发现被测软件中潜在的失效风险, 而本文旨在通过对智能体路径规划算法进行测
试来暴露其失效风险. 在实际应用场景中, 根据不同的需求可以采用不同的标准来评价生成路径的质量, 如在自动
驾驶场景会考虑路径的光滑度、最大转角、最大加速度减速度, 无人机场景会考虑油耗等指标. 本文讨论路径规划
算法的一般需求, 即在不考虑特定场景约束的情况下, 将路径长度作为评估指标. 在相同条件下生成的路径越短, 路
径质量就越高, 因为在一般情况下, 算法生成路径越短, 智能体在执行过程中所消耗的时间和资源就越低. 目前经典
路径规划算法的概率收敛性都经过了证明, 因此只要算法实现正确且规划时间足够, 这些智能体都能够找到一条完
整且无碰撞路径. 然而, 实际问题中受到时间和资源的限制, 规划算法无法求出最优路径, 其只能寻求在短时间内找
到满足任务需求的可行解. 此外, 基于采样的路径规划算法大多包含一定程度的不确定性. 例如本文的被测对象, 即
被广泛应用的 RRT 算法作为概率收敛算法能够保证智能体在较短的时间内规划出从起点到终点的连通路径, 但该
路径并非最优的. 此外, 由于 RRT 的核心是随机树的构架, 因此其在同一场景下生成的路径与不相同. 因此, 在实际
场景中 RRT 的性能 (如稳定性、寻优性等) 是需要被进一步考察的. 具体来说, 算法可能存在以下风险.