随机救援任务的路径规划：一种CVaR引导的RRT*方法

《Robotics and Autonomous Systems》：Path planning for stochastic rescue mission: A CVaR-guided RRT* methodology

　　

Abstract
在紧急救援任务中，智能机器人可以为被困人员提供灵活的救援服务。鲁棒的路径规划策略有助于提高救援效率并降低人员风险。然而，天气变化、人为干扰和机器人机械状况等因素使得固定路线上的旅行时间不确定。本文引入条件风险价值 (CVaR) 作为风险指标来衡量机器人旅行时间的不确定性，并将其与 RRT* 算法相结合。此外，为了解决传统 RRT* 的局限性，特别是由盲目均匀采样导致的收敛速度慢、由固定步长导致的适应性差以及在复杂环境中容易陷入局部陷阱的问题，我们结合了自适应目标偏置采样、自适应动态步长策略和停滞感知逃逸机制，从而提出了 CVaR-自适应 RRT*（CVaR-ARRT*）算法。此外，使用高斯混合模型 (GMM) 量化旅行时间的不确定性。CVaR 捕捉潜在的极端损失案例，调整风险倾向参数可以灵活控制机器人路径选择。首先，约束机器人的转向角和最大救援时间。其次，使用具有停滞检测和逃逸采样策略的 CVaR-ARRT* 算法进行搜索优化。最后，使用 B 样条函数对生成的航点进行曲线拟合。仿真实验表明，所提出的算法有效地平衡了不同风险倾向条件下路径的鲁棒性和最优性。此外，与最先进的机会约束 RRT* 和避险 RRT* 等方法相比，它始终表现更优，与传统 RRT 基准相比，平均旅行时间减少 13.8%，平均任务成功率提高 13.7%。

Introduction
随着智能机器人系统的快速发展，这些平台在各种救援场景中发挥了越来越重要的作用，例如自然灾害应对、医疗物资输送和失踪人员搜索。世界各国投入巨资开发具有更强计算效率和更快响应速度的机器人 [1], [2]。在地震和暴雨等灾区的救援任务中，极端天气条件往往会引入机器人旅行时间的不确定性。如果不考虑这种不确定性，将构成严重的安全隐患并增加救援任务失败的风险。因此，如何在旅行时间不确定的情况下规划高效且鲁棒的旅行路径，以确保机器人能够快速准确地执行救援任务，已成为一个紧迫的问题。

现有的路径规划算法从根本上可以分为两类主要类型：全局路径规划算法和局部路径规划算法。全局路径规划包括 A* 算法 [3]、迪杰斯特拉算法 [4]、灰狼优化器 (GWO) [5] 以及基于采样的快速扩展随机树 (RRT) 算法 [6]。诸如 A* 算法等启发式算法对于不可达目标效率低下，不适合复杂的灾害环境。原始迪杰斯特拉算法通过选择最近的未访问节点来构建树以找到最短路径，但在高不确定性下容易陷入局部最优。GWO 是一种模仿灰狼的群体智能算法，需要大量的计算资源。相比之下，RRT 能够实现快速收敛、易于实现且不敏感于初始条件，使其广泛应用于复杂环境中的路径规划。

在确定性路径规划背景下，利用最先进的技术（如图形搜索或采样算法）可以高效地解决最短时间问题。一个例子是渐近最优 RRT* 算法 [7]。在不确定路径规划框架下，一些研究探讨了不确定时间对机器人路径规划的影响。Rivière [8] 引入了谱扩展树搜索 (SETS) 算法，该算法利用蒙特卡洛树搜索来优化具有随机旅行时间的静态环境中的路径规划。通过集成自适应决策策略，与传统采样方法相比，SETS 实现了更高效的路径优化，并显著减少了计算开销。Hong [9] 研究了有限时间范围内受约束随机最短路径问题的启发式前向搜索算法。Zhan [10] 研究了具有刚性重访周期约束且旅行时间不确定的连续监控问题，并通过引入机会约束将随机优化问题转化为确定性优化问题。Tian [11] 解决了无人机 - 地面车辆 (UAV-UGV) 协作取送中的时间不确定性问题，制定了不确定性下的时间窗约束路径规划模型，并提出了一种自适应遗传大邻域搜索算法进行优化。Miranda [12] 研究了具有硬时间窗、随机旅行时间和服务时间的车辆路径问题。他们开发了一种方法来计算到达时间的累积概率函数，以估计车辆满足时间窗约束的概率。另一方面，Prorok [13] 使用冗余机器人来应对物流和运输中的不确定旅行时间，以及单任务、多机器人场景。他们提出了一种超级模型优化框架来选择机器人及其路径，从而减少在目标位置的平均等待时间。Kim [14] 讨论了当机器人由于各种因素超过计划能耗限制时的重新规划问题。他们引入了机会约束规划来解决机器人飞行时间不确定性问题。该方法旨在确定满足安全要求同时最小化未完成任务惩罚的路径。同样，Yang [15] 使用机会约束规划解决具有随机成本的多无人机任务分配问题，确保机器人组的成本始终低于给定界限。Dong [16] 将机会约束规划扩展到信息物理系统通信拓扑规划，提出了一种凸松弛方法，动态调整决策依赖的不确定需求场景下的不确定性集系数。然而，机会约束遵循特定公式化的路径以简化计算，这种松弛方法显示出一定的保守性 [17]。

为了克服凸松弛方法的保守性，研究社区开始探索更灵活的风险敏感方法 [18], [19]，这些方法通过风险约束规划路径并引入风险意识概念。具体来说，风险敏感方法不仅考虑路径的可行性和效率，还通过定量指标衡量路径的风险水平。在风险敏感方法中，条件风险价值 (CVaR) 为自主系统和机器人的风险感知规划提供了合理且灵活的解决方案。

最近，在将 CVaR 及相关风险指标应用于机器人运动规划方面取得了重大进展。近期的基础性工作极大地丰富了风险感知导航领域。例如，Jasour 等人 [20] 开发了一个凸风险有界连续时间轨迹规划框架，通过先进的管设计确保在不确定的非凸环境中的安全性。此外，在采样算法领域，最近的进展成功地将机器学习整合以加速风险敏感探索。Meng 等人 [21] 提出了 NR-RRT，一种神经风险感知算法，利用基于示教深度学习来指导近最优路径规划。他们进一步将该概念扩展到严重环境不确定性下的广义基于学习的风险有界运动规划 [22]。虽然这些基于学习和基于优化的方法非常有效，但它们通常需要大量的离线训练数据或复杂的数学松弛。相比之下，我们的方法明确地将 CVaR 直接纳入 RRT 目标中，保留了在线采样的灵活性，而不依赖预训练神经网络。例如，Yang 等人开发了一系列面向大规模机器人集群的风险感知规划器，在模型预测控制 (MPC) 框架内利用 CVaR 来处理智能体之间的碰撞风险并增强可扩展性 [23], [24], [25]。同样，Bian 等人将 CVaR 应用于四旋翼飞行器路径规划以减轻环境干扰 [26]，而 Ahmadi 等人提出了 CVaR 势垒函数以确保不确定性下双足步行的安全性 [27]。虽然基于优化和控制理论的方法对于局部轨迹生成是有效的，但它们通常依赖于凸近似或线性化。相比之下，基于采样的方法更适合非凸环境中的全局规划。然而，传统规划器如 RRT* 通常优化期望成本，使其本质上对风险中性。这可能导致选择平均旅行时间低但方差高的路径。因此，将 CVaR 与基于采样的规划器结合对于量化和控制尾部风险（特别是源自旅行时间不确定性的风险）至关重要，从而确保全局探索中的鲁棒避险。

CVaR 通过选择最坏情况场景和期望值之间的合适风险指标，有效地平衡了路径的风险和效益，从而提高了路径规划的鲁棒性和安全性 [28]。在风险优化领域，现有研究为风险敏感随机路径规划方法奠定了坚实的理论基础。[29] 指出，在阶段成本有界的场景中，通过优化风险约束目标函数，可以建立累积成本上尾概率的概率保证。这一结果在关于风险敏感强化学习的近期研究中得到进一步验证 [30]。在此基础上，CVaR 理论的最新突破为有界噪声方差下的最优旅行时间提供了概率保证，为我们提出的风险敏感随机路径规划方法提供了多方面的理论支持。这增强了复杂环境中规划路径的可靠性和稳定性。

以往的安全感知机器人路径规划方法要么使用保守的公式假设最坏情况，导致旅行时间成本过高，要么使用平均条件，导致潜在不安全的路径。本文研究将 CVaR 纳入机器人路径规划问题的目标函数中，使风险容忍度介于平均情况和最坏情况之间。主要贡献如下：
• 本文引入 CVaR 作为风险指标来量化机器人旅行时间不确定性，并构建了基于 CVaR 的救援路径规划模型。通过将 CVaR 直接纳入优化目标函数而不是仅仅将其作为约束，我们的方法增强了风险偏好的灵活性，使决策者能够生成针对特定环境条件和风险容忍度的多样化路径策略。
• 引入了一种 CVaR 引导的自适应 RRT*（CVaR-ARRT*）路径规划算法，包含三种新机制：自适应目标偏置、自适应步长和停滞感知逃逸策略。目标偏置和步长根据环境反馈动态调整，以调节采样和树扩展。同时，停滞感知逃逸策略监控收敛进度，并在检测到停滞时增强探索。这些机制共同提高了收敛效率、脱离被困区域的能力以及在复杂高风险环境中的规划鲁棒性。

Section snippets
章节片段
Environmental model
环境模型
为了通过仿真验证所提出的方法，我们现在着手对仿真环境进行建模。环境模型由两部分组成：一部分是障碍物，另一部分是风险，如图 1 所示。在本文中，风险被定义为围绕机器人在给定区域旅行时间的不确定性。这种不确定性源于各种因素，例如天气变化、信号干扰和地形复杂性的意外变化。例如，强风
Uncertainty quantification
不确定性量化
设 Tk 为表示第 k 段路径旅行时间的随机变量。我们假设 Tk 服从高斯分布 Tk～N(μk,σk2)，其中 μk 表示预期旅行时间，σk2 表示源自风险场的方差。引入一个机会约束以确保机器人总旅行时间不超过给定阈值 Tmax 的概率至少为 1-δ。P∑k=0N?1Tk≤Tmax≥1?δ，其中 P 表示概率。由于 Tk 服从正态分布，总和
Experiment and analysis
实验与分析
为了评估 CVaR-ARRT* 算法的有效性和鲁棒性，我们在模拟工作区 W=[0,1500]×[0,1500]m2 中构建了三个不同的场景，即单通道地图（起点：[100,600]，终点：[1300,400]）、多通道地图（起点：[500,1250]，终点：[1200,150]）和散落障碍物地图（起点：[0,0]，终点：[1200,1200]），如图 4 所示。对于单通道地图，风险中心位于 μ1=[780,650], μ2=[400,1000], μ3=[990,870], μ4=[1300,1300], μ5=[
Conclusion
结论
本文提出了一种基于 CVaR 的机器人救援路径规划方法 CVaR-RRT*。通过将 CVaR 应用于目标函数，这种新颖的方法具有对风险偏好灵活的优点，同时也在存在不确定性的情况下考虑了尾部风险，并能够在不确定环境中提供鲁棒的路径规划方案。与传统的期望优化和机会约束方法相比，CVaR-ARRT* 算法显示出显著
CRediT authorship contribution statement
CRediT 作者贡献声明
Cheng Liu：撰写 - 原稿。Yang Chen：撰写 - 审阅与编辑，方法学。Yanhua Yang：撰写 - 审阅与编辑，资源，资金获取。Mengfei Xu：撰写 - 审阅与编辑。

Hann Woei Ho：撰写 – 审阅与编辑。未引用参考文献 [40] 利益冲突声明 作者声明他们不存在任何已知的竞争性财务利益或个人关系，这些利益或关系可能会影响本文所报告的工作。致谢 本工作部分得到中国国家自然科学基金（批准号：62173262 和 61703314）的支持。Cheng Liu|Yang Chen|Yanhua Yang|Mengfei Xu|Hann Woei Ho