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

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

(2) 路径 pth 中任意两个相邻的位置点 p τ i 与 p τ i+1 满足运动约束, 即公式 (1) 和公式 (2).

(3) 为了避免规划中出现“死循环”“死胡同”等情况, 要求每次规划时间不能超过 τ limit , 即 τ N time ⩽ τ limit .

E
p (目标位置)
obs 2
obs 3
obs 1
(障碍物) pth[τ 0··· τ N p]

(路径)
obs 4
obs 6
obs 5
B
p (起始位置)
M (任务空间)
图 1 智能体路径规划问题示意图

1.2 基于快速随机探索树的路径规划算法
路径规划算法旨在解决第 1.1 节中提出的智能体路径规划问题. 算法根据智能体获取到的当前环境信息, 在
满足问题约束前提下生成合理的路径, 使得智能体按照该路径行动能够快速、准确地到达目标点, 并且避开沿途
的威胁区域. 目前的相关研究工作大致可分为基于图搜索的算法、基于进化的算法、基于随机采样的算法. 基于
*
图搜索的路径规划算法将路径规划问题转化为图论中的路径搜索问题, 并使用 A *[26] 、混合 A 以及跳点搜
索 [27] 等算法生成路径. 一般的智能体路径规划问题可以转化为钢琴搬运问题, 其规划可行解的复杂度已经被 Reif
*
证明具有 PSPACE-hard 的下界 [28] , 这意味着没有能够解决该问题所有实例的多项式时间算法. 因此, 像是 A 这样
的最优搜索算法很可能无法满足实际规划的时间约束, 而目前很多研究工作都试图在有限时间内产生近似最优的
可行路径. 例如, 基于进化的路径规划算法 (如遗传算法 (GE) [29] 、差分进化算法 (DE) [30] 、蚁群优化算法 (ACO) [31] 、
粒子群优化算法 (PSO) [30] 等) 将环境及路径进行编码, 并通过多次迭代的方式找到可行解并逐步提高可行解的质
量. 然而进化算法的普遍问题是容易陷入局部最优, 这使得生成的路径质量很可能无法随着规划时间的增加而得
到改善, 有些情况下甚至无法得到可行解. 因此, 目前在各种物理信息系统中应用最广泛的是基于随机采样的路径
规划算法 [1,8] . 该类算法结合了随机几何图 (random geometric graph, RGG) 理论, 将路径的生成转化为基于随机图
论的路径搜索问题 [32] . 以 RGG 理论为支撑, 基于随机采样方法具有许多优秀的数学特性, 包括概率完备性和渐近
最优性 [16] . 具体来说, 基于随机采样的路径规划方法在考虑各种约束的同时, 通过随机扩展的方式将搜索引导向
未知区域, 进而快速地将搜索覆盖到整个任务空间, 最终找到可行路径. 此外, 由于该类方法在默认条件下对整个
任务空间的初始搜索概率是均等的, 并不依赖特定领域的启发式信息, 因此其具有良好的普适性. 其中, 本文所采
用的快速扩展随机树算法 (RRT) 就是目前应用最广泛的智能体路径规划方法 [8] . RRT 算法利用了树结构的优势,
通过随机采样策略, 快速地生成一棵遍布于整个空间的随机树 (如图 2 所示), 并通过反向回溯的方式以线性的时
间复杂度生成一条叶子节点到根节点的路径作为规划问题的解. 具体来说, 通过 RRT 算法进行路径规划时可以分
为构建随机树和生成路径两个环节.
(1) 构建随机树. 任务空间 M 中的一棵树可以表示为 Tree = {nd 0 ,nd 1 ,...,nd N tree}, 其中, 任意节点 nd ∈ Tree 可以
s
p
c
⟨nd , p ,ND ⟩ 的形式, 这里, p 表示该节点在 M 中的坐标, nd ∈ Tree 表示节点 nd 的前驱节点 (树结构每个节
p
c
写成
S
点只有一个前驱), 节点集合 ND ⊂ Tree 表示节点 nd 的后继节点集合 (树结构的每个节点可以有多个后继节点).
需指出, RRT 随机树的后继节点上限个数是可以设置的, 本文采用经典的二叉树设置, 即固定每个节点的最大后
继节点个数为 2. 此外, 为了验证算法的稳定性, 还将在第 4 节特别探讨当生成树呈现为三叉树结构时测试算法的