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

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

(1) 路径的质量不满足需求. 如果实际生成路径的长度与最优路径相差很大, 那么智能体按照实际路径行动时
会花费大量额外的时间成本.
(2) 算法的稳定性较差. 由于算法的不确定性, 即使当前生成路径满足需求, 也无法保证算法相同场景下总能
生成满足需求的路径.
由于上述风险的存在, 路径规划算法的测试存在测试预期 (oracle) 问题 [51] , 即在最优解未知的情况下我们无
法判断当前的测试结果是否失效. 经验表明, 尽管算法的用户对路径长度 (或规划时间) 有需求, 但由于场景的复
杂性, 通常无法在不考虑最优解的情况下对该需求进行量化. 例如, 假设算法在某个场景下生成路径很长, 其原因
既可能是算法在性能上的失效也可能是场景本身过于复杂, 而我们也不能确定该路径与最优路径的偏差是否过
大, 是否能够满足实际的性能需求.
为此, 本文借鉴蜕变测试思想来设计测试用例的评估准则. 假设用被测路径规划算法重复运行 N repeat 次测试
t
t
t
t
用例 t, 得到各次运行后生成路径的集合 PTH = {pth , pth ,..., pth N repeat }, 则我们得到蜕变关系: 若所有路径都具有
1 2
较高的质量, 即与最优路径 pth t∗ 的差距不大, 则这些路径彼此之间的差异也不会很大. 因此, 我们可以通过 PTH t
t
中路径彼此之间的差异来评价被测算法在测试用例 t 上的表现, 因为尽管最优路径 pth t∗ 未知, 但当 PTH 中的路径
t t t∗
之间差异较大时, 则一定存在一条生成路径 pth ∈ PTH 与最优路径 pth 具有更大的差异, 即:

t
t

∃i, j, pth − pth ⩾ d → ∃k, pth − pth > d (11)
t
t∗
i j k
此外, 路径彼此之间具有较大的差距也能反映出被测算法具有较差的稳定性. 基于以上分析, 本文将同一个测
试用例多次执行后生成路径的长度样本方差作为该测试用例输出结果的失效度, 即被测算法在测试用例 t 上的表
现的失效度为:

 
/
 ∑ ( 
 ) 2
  repeat
t
 pth −|pth |  (N −1) (12)
t 
S (t) = 
 i 
 
i∈[1,N repeat )
在软件测试及程序证伪 (falsification) 领域, 度量需求满足程度的一种经典方法是计算实际输出与规格说
明 (specification) 的差异度. 现考虑路径规划算法测试, 假设某个测试场景下最优路径为 pth , 且重复执行 N repeat 次
∗
∗ ∗ S (t), 但我们却可以证明
∗
得到各路径的长度距离最优路径的离差为 S (t), 则尽管我们不易得到 pth 并计算
∗ S (t) > S (t) 是测试输出与最优结果离差的一个下界, 其能够反映测试输出与最优路
∗
S (t) > S (t). 也就是说, 失效度
径的差异度, 这与基于路径长度的需求满足程度的概念相符. 因此尽管我们无法确切判断一个测试用例是否失效,
S (t) 尽可
但对于 S (t) 值较大的测试用例, 其不满足需求的可能性就越大. 而我们测试的目标也可以量化为生成使
能大的测试用例.
总的来说, 作为智能体路径规划算法的测试框架包含以下部分.
t 1 ,t 2 ,... 形成测试用例集 T, 其中, 每个测试用例
(1) 测试用例生成. 基于某种测试用例生成策略生成测试用例
t 为特定的路径规划环境, 其特征可以量化为场景中的威胁分布, 即 t.Obs.
t
t
(2) 测试用例集执行. 多次执行每个测试用例 t ∈ T , 并记录测试结果, 生成路径 pth , pth ,..., pth t N repeat .
1 2
(3) 测试结果的评估. 根据公式 (12) 计算测试用例 t 生成路径之间的标准差 S (t), 并将其作为失效度. 对那些
S (t) 值较大的测试用例做进一步分析.

2.2 动态随机测试方法框架
本文试图将 DRT 思想引入到路径规划算法中, 提出面向路径规划算法的自适应随机测试方法, 其总体框架如
图 3 所示. 自适应随机测试属于软件控制论范畴, 其引入测试剖面概念, 并将其作为“控制器”或是“测试策略”来控
制测试用例的生成和执行. 作为核心概念, 测试剖面可以看成是被测系统输入空间的一个概率分布 (或概率密度函
数), 表示被测系统的每个输入被选取的概率或概率密度. 而 DRT 的基本思想与强化学习类似, 通过在测试过程中
动态调整测试剖面, 来高效地达成测试目标. 具体来说, 在测试开始时, DRT 通常采取随机测试策略; 而在测试过
程中, DRT 持续收集测试信息, 逐步加深对被测对象及其潜在失效的了解. 以此为依据, DRT 在每次执行后对测试
剖面进行动态更新, 使得当前的测试策略能够更好地适配被测对象的特性, 以达到快速发现失效的目的.