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

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

fin
作最后生成的节点 nd , 并停止随机树的构建.
(2) 生成路径. 通过上述方法, 我们可以构建一棵在任务空间 M 中的随机树 Tree, 并且保证以下条件, 那么我
们可以通过回溯的方法来生成最后的路径.
1) 该随机树中的所有节点都是安全的 (即在威胁的外部).
2) 最后加入的新节点能够到达目标点.
具体来说, 从最后生成的节点 nd fin 开始, 沿着前驱节点反向回溯至随机树的根节点 nd 0 , 就可以生成最终路径
了, 即 RRT 算法最后生成的路径为:

[ ⟨ ⟩]
⟨ ⟩ ⟨ ⟩
(10)
pth = τ 0 , p τ 0 , τ 1 , p τ 1 ,..., τ N time, p τ time
N
满足:

B
c
= task.p = nd 0 .p ,
p τ 0

E
fin
c
p N time = task.p = nd .p ,

c
∀i ∈ (0,N time ), p τ i = nd i .p ,
其中,

p
nd i = nd i+1 .nd .
若当前随机树包含节点总数为 N tree , 则每添加一个新节点的复杂度为 O(N tree ), 而通过回溯法生成最终路径的
复杂度为 log(N tree ). 此外, 我们还可以通过划分子区域并进行哈希映射的方式来减少 Step 2 的计算时间. 因此,
RRT 算法可以在多项式时间内迅速生成扩展到整个任务空间的随机树, 并最终找到路径, 如图 2 所示. 此外, 从概
率意义上来说, 随机树中最先到达目标点的分支很可能具有较短的路径长度, 因此 RRT 在一定程度上保证了生成
路径的质量. 此外, 许多 RRT 的改进方法, 如改进快速随机探索树算法 (RRT*) [16] 、快速行进树算法 (FMT) [33] 等,
都具有渐近最优性, 即随着迭代次数或样本数量的增加而收敛到最优解. 本研究旨在提供多智能体路径规划的通
用框架, 因此我们将最基本 RRT 路径规划算法作为被测对象.

1.3 面向路径规划算法的软件测试方法
软件测试旨在通过设计合理的测试用例并将其作为输入运行被测系统, 来发现被测软件中的问题 [34] . 针对软
件本身、软件的功能及性能需求、软件的错误形式及触发机理的多样性和复杂性, 学者们基于不同的思想及理念
提出了各种测试方法及策略, 如解决 Oracle 问题的蜕变测试 [35] 、解决测试充分性问题的变异测试 [36] 等.
随机测试 (random) 被认为是最基本的自动化测试用例生成方法 [37] , 该方法通过在被测系统的输入空间进行
随机采样的方式来构造测试用例. 尽管 RT 方法简单, 但随机测试能够保证输入空间中任何可能的测试用例都有
一定概率被选中, 这就为测试效率提供了一个下界 [37] . 因此, 目前很多测试方法都将随机测试与被测软件的自身
属性以及相关领域知识结合, 提出新的测试方法, 旨在保留测试用例多样性的同时提升测试效率. 例如, 大量测试
与调试的经验都表明导致失效的测试用例往往在输入域中聚集成连续的区域. 基于此 Chen 等人 [38] 提出了自适应
随机测试 (adaptive random testing, ART) 方法. ART 在测试用例生成阶段引入反馈, 试图使生成的测试用例均匀地
分布于输入域, 以提高失效检测效率, 例如最著名的 ART 算法 FSCS-ART 通过从固定大小的候选测试集中选择
与当前测试信息差异最大的测试用例作为下一个测试输入来达成 ART 的目标 [39] . 目前基于不同测试需求, 学者
还提出了 DF-FSCS [40] 等多种 ART 算法.
尽管与 RT 相比, ART 能够在较短的时间内生成多样的测试用例, 然而 ART 算法大多在被测软件的输入空间
完成闭环, 无法根据测试结果进行搜索或寻优; 然而被测软件的失效或其他性能缺陷的相关信息很可能在其输出
信息上得到反映, 而这些信息很可能被 ART 忽略. 为此, Cai 等人 [41] 将控制论思想引入软件工程中, 提出自适应测
试 (AT) 方法, 同时将测试的输入和输出作为反馈信息, 并以此来控制测试的执行过程. 此外, 文献 [18,42] 将 AT
与 RT 结合, 提出了动态随机测试 (dynamic random testing, DRT) 算法. DRT 引入测试剖面的概念, 将其作为测试
策略, 并根据历史测试信息动态调整测试剖面本身, 使得测试策略逐渐优化, 进而更好地发现软件的缺陷.