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

张逍怡 等: 面向智能体路径规划算法的动态随机测试方法 3111

为了解决上述挑战, 本文提出面向智能体路径规划算法设计的测试方法, 以有效生成能够暴露被测算法潜在
性能失效的测试用例. 具体来说, 本文借鉴了动态随机测试 (dynamic random testing, DRT) [18] 的思想, 提出了面向智
能体路径规划算法的动态随机测试方法 (dynamic random testing approach for intelligent agent path planning
algorithms, DRT-PP). DRT 通过构建测试剖面, 将输入空间划分为若干区域, 各个区域具有不同的概率被选为测试
用例生成区域. 因此, 测试剖面可以看成是一个基于输入空间的概率分布, 而 DRT 将测试剖面视为一个暂时的测
试策略, 在测试过程中依照当前的测试剖面按概率从输入空间生成测试用例, 这样既可以保持测试的随机性又能
在测试用例生成时具有一定的倾向性. 此外, DRT 引入反馈机制, 即在测试过程中实时对当前的测试信息进行提
取和分析, 并根据这些测试信息动态地调整测试剖面, 使那些有价值测试用例的生成概率逐渐升高, 进而提升测试
效率. 可见, DRT 的基本思想与智能体路径规划算法的测试需求相契合.
目前关于 DRT 的相关研究大致可以分为两个方面. 一方面是对 DRT 的相关理论进行分析, 例如, 文献 [18]
讨论了在 DRT 中引入聚类方法来划分子空间的可能性. 然而, 与模型测试、变异测试等测试思想类似, DRT 是较
高层次的测试思想或方法论, 不能直接作为具体的测试方法使用. 另一方面, 由于被测软件种类繁多, 不同的被测
对象可能拥有不同的输入空间, 其错误的触发机理也各不相同, 因此对于不同的被测对象, 我们都需要根据相应的
领域知识, 重新设计完整的测试方法和测试策略. 而本文将 DRT 思想引入到路径规划算法中, 基于路径规划的领
域知识对测试方法进行了如下设计.
(1) 测试剖面构建. 路径规划问题的输入是连续空间上障碍物的分布, 因此我们不易基于传统的等价类划分思
想建测试剖面. 为此, 我们首先对规划的任务空间进行离散化, 将其划分为一个个格子, 每个格子被视作子区域; 接
着在每个子区域内引入一个包含威胁的概率, 进而构建测试整个输入空间的测试剖面. 也就是说, 一个测试剖面就
是被分成若干格子的空间以及每个子区域包含威胁的概率. 通过此方法构建的测试剖面既能保证随机的测试的执
行, 且保证了测试剖面的连续性, 使我们能够进一步设计合理的测试剖面更新策略.
(2) 测试剖面更新. 评价路径规划算法的性能指标很多, 本文考虑路径长度方面的性能需求, 因为路径的长度
是衡量路径质量的首要指标 [19] , 其同时可以间接反映任务的执行时间、耗油量等指标. 由于作为被测对象的 RRT
路径规划算法具有不确定性, 我们无法直接度量某场景下生成路径的质量. 为此, 本文借鉴蜕变测试 (metamorphic
testing, MT) 思想 [9,10] , 通过对一个测试用例进行多次仿真得到多条生成路径并计算这些路径长度的方差来评估测
试用例的失效度. 在该定义下, 失效度较大的测试用例一方面意味着被测算法在执行该测试用例时稳定性较差, 另
一方面也说明该测试用例下生成的路径与最优路径差距较大 (实际上, 我们还可以根据其他性能需求定义各种评
价指标 (如路径平滑性), 而这些指标理论上同样适用于 DRT-PP), 而这些现象都反映了算法在实际应用场景中的
性能风险. 在此基础上, 我们设计了反馈机制来动态调整测试剖面: 当发现某个测试用例具有较大的生成路径方差
时, 测试剖面中与该测试用例威胁分布相关的子区域包含威胁的概率就会增加; 反之, 相关子区域包含威胁概率
减小.
由于目前尚未发现面向路径规划算法的完整的动态测试方法, 我们基于软件测试领域经典且高效的随机测
试 (random testing, RT) 及自适应随机测试 (adaptive random testing, ART) 思想设计了的面向路径规划算法的 RT
及 ART 测试方法, 并将其作为基线与 DRT-PP 进行对比. 实验结果表明, DRT-PP 在保证测试多样性的同时能够生
成更多有效的测试用例, 平均失效度提升了约 1.5 倍 (与 RT 和 ART 相比). 此外, DRT-PP 能够发现 RT 和 ART 无
法找到的具有高失效度的测试用例. 总的来说, 本文的贡献如下.
(1) 将动态随机思想引入路径规划算法的测试中, 以高效地生成有价值的路径规划场景.
(2) 通过引入威胁生成概率矩阵来构建路径规划算法的测试剖面, 解决了场景空间划分问题.
(3) 设计了基于多次执行路径差异的测试评价指标以及测试剖面矩阵的更新策略, 解决了对失效测试用例的
寻优问题.
本文第 1 节介绍智能体路径规划问题、作为本文被测对象的 RRT 路径规划算法以及与路径规划测试相关的