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

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

国内外研究进展. 第 2 节介绍 DRT-PP 测试方法, 包括基于测试剖面的构建及更新策略. 第 3 节对 DRT-PP 的有效
性进行实验评估. 第 4 节对本研究进行风险分析. 最后在第 5 节对全文进行总结.

1 背景及相关工作

1.1 智能体路径规划问题的定义及描述
智能体的路径规划是机器人领域的核心问题之一. 最早对该问题的研究始于 20 世纪 70 年代 [4] , 研究者通过
将其转化为在位形空间中搜索无碰撞点的问题来构造完整且连续的路径或运动序列. 目前路径规划问题已经在多
个领域被广泛讨论, 而在应用到某个具体场景时, 通常需要考虑该场景的特定约束. 无论是自动驾驶汽车的寻路 [2] 、
无人机的航迹生成 [3] 、自动机械臂的行为规划 [4] , 还是仓储机器人的物流调度 [5] ，这些典型任务场景均可转化为
(或部分转化为) 路径规划问题。例如, 自动驾驶的感知约束 [20] 、无人机场景需考虑气动模型及参数 [21] 、智能物
流场景需要考虑具体的物流任务约束 (如多次分配) [22] , 而机械臂则需要考虑其自由度以及各自由度之间的运动约
束 [23] . 本文为了方法的通用性, 考虑最基本的智能体路径规划问题, 具体的表述如下.
定义 1 (环境). 定义智能体执行任务时的任务空间 M 为一个 X ×Y 的连续二维空间, 该空间中的一个点 p 可以
用其坐标 (x, y) 来表示. 令 Obs = {obs 1 ,obs 2 ,...} 为空间中的威胁障碍物 (以下简称“威胁”) 集合, 其中每个威胁
obs ∈ Obs 都可以看成是任务空间 M 中的子区域, 即 obs ⊂ M. 我们假设任何该区域中的点 p ∈ obs 都被该威胁占
据. 任务空间 M 和威胁集合 Obs 共同组成了某次规划任务的环境, 记为 E = ⟨M,Obs⟩ .
定义 2 (智能体). 我们将智能体 ag 定义为任务空间 M 中一个具备运动能力的质点. 假设在 τ 时刻该智能体的
x y x 2 y 2 2
位置为 p τ = (x,y), 则在下一时刻, 即 τ+1 时刻, 其位置可以是 p τ+1 = (x+δ , x+δ ), 满足 (δ ) +(δ ) = r , 其中, r > 0
表示智能体在单位时间内的行动步长, 即智能体在单位时间内移动的距离.
为了简化问题, 本文采用固定的智能体行动步长, 这也是经典 RRT 算法的基本假设. 在实际规划问题中, 智能
体步长可以是动态可变的, 在某个时刻, 智能体也可以停在原来位置不动, 然而仅考虑路径生成本身, 这些假设可
以通过取较小的步长进行近似.
定义 3 (路径). 假设智能体 ag 在任务空间 M 中运动, 定义智能体 ag 在连续时刻 τ 0 ,τ 1 ,...,τ N time 的位置序列
[ ⟨ ⟩]
⟨ ⟩ ⟨ ⟩
为其在该时段的路径, 记为 . 这里, 为了简化问题, 为 ag 在
pth = τ 0 , p τ 0 , τ 1 , p τ 1 ,..., τ N time, p τ time p τ 0 , p τ 1 ,..., p τ time
N N
各时刻的位置信息, 其满足定义 2 中智能体的基本运动规律, 即 (在后面的公式中, 我们统一用 A.B 表示 A 的子元
素 B):
.x+δ x .y+δ y ) (1)
(p τ i+1 .x, p τ i+1 .y) = (p τ i , p τ i
τ i ,τ i+1 τ i ,τ i+1
其中, [δ x y τ i+1 时刻的运动向量, 其满足:
,δ τ i ,τ i+1 ] 表示智能体从 τ i 时刻到
τ i ,τ i+1
2
2
(δ x ) +(δ y ) = r 2 (2)
τ i ,τ i+1 τ i ,τ i+1
需要指出, 相较于以上 3 个定义, 实际场景可能会更加复杂, 例如任务空间并非定义 1 中所说的矩形, 空间中
的障碍物也可能有很多种 (如建筑物这样的实体威胁以及自然灾害或恶劣天气这样的概率威胁 [24] ), 而智能体也可
能不是定义 2 中的质点, 而是具有复杂几何形状的三维刚体 (如智能车、物流机器人、无人机等), 其在某时刻的
行为也可能是多样的 (如加速、减速、换挡等) [25] . 为了测试方法的通用性及简洁性, 本文讨论路径规划问题的最
基本假设, 并试图通过设计通用的测试方法发现路径规划算法本身的性能问题. 基于以上 3 个定义, 智能体的路径
规划问题 (如图 1 所示) 可如下表示.
智能体路径规划问题: 现有环境 E, 包含的任务空间 M 以及障碍物集合 Obs. 假设环境中有一智能体 ag, 令
⟨ ⟩ B E
B
task = p , p E 为智能体的规划任务, 其中 p 表示智能体的初始位置, p 表示智能体的目标位置. 智能体路径规划
问题要求智能体在规定时间内生成从起始位置 p B 到达目标位置 p E 的安全可行的路径, 即生成路径 pth =
[ ⟨ ⟩]
⟨ ⟩ ⟨ ⟩
满足以下条件.
τ 0 , p τ 0 , τ 1 , p τ 1 ,..., τ N time, p τ time
N
B E
(1) 智能体从起点出发到达终点, 即 = p 且 = p .
p τ 0 p τ time
N