Kinodynamic Motion Planning for Mobile Robot Navigation across Inconsistent World Models
作者: Eric R. Damm, Thomas M. Howard
分类: cs.RO
发布日期: 2025-09-30
备注: Presented at the Robotics: Science and Systems (RSS) 2025 Workshop on Resilient Off-road Autonomous Robotics (ROAR)
💡 一句话要点
针对不一致环境模型的移动机器人运动规划方法GEGRH
🎯 匹配领域: 支柱一：机器人控制 (Robot Control) 支柱二：RL算法与架构 (RL & Architecture)
关键词: 运动规划 移动机器人 环境不确定性 路径规划 自主导航
📋 核心要点
- 现有移动机器人运动规划方法在环境模型不一致时，难以保证规划的安全性，尤其是在成本地图频繁切换障碍物和自由空间时。
- 论文提出GEGRH方法，通过跟踪世界模型历史，延迟子搜索到目标区域，并根据发散节点修改图，从而生成更安全的轨迹。
- 在非结构化越野环境的实验表明，GEGRH比VEH方法找到成本更低的轨迹，规划时间更快，且比单假设搜索更保守。
📝 摘要（中文）
移动地面机器人在缺乏环境先验知识的情况下，必须依赖传感器数据来构建周围环境模型。由于噪声和算法缺陷，一致性地识别障碍物和地形特征可能很困难，这使得运动规划系统难以生成安全运动。一个特别需要克服的难题是，成本地图的区域在连续的规划周期中会在被标记为障碍物和自由空间之间切换。一种潜在的解决方案，我们称之为“在每个假设中有效”（VEH），是让规划系统规划在世界模型的历史中保证安全的运动。另一种方法是跟踪世界模型的历史，并根据需要绕过先前危险区域的潜在惩罚来调整节点成本。这项工作讨论了这一想法的三个主要迭代。第一个迭代，称为PEH，为每个穿过世界模型中发散点的节点扩展调用一个子搜索。第二个和第三个迭代，分别称为GEH和GEGRH，将子搜索推迟到边缘扩展到目标区域之后。GEGRH使用额外的步骤来根据每个世界中的发散节点修改图。初步结果表明，虽然PEH和GEH比VEH找到更乐观的解决方案，但它们无法在不到一秒的时间内生成解决方案，这超出了我们对现场部署的要求。在Clearpath Robotics Warthog UGV上进行的非结构化越野环境的现场实验结果分析表明，GEGRH比VEH找到成本更低的轨迹，并且具有更快的平均规划时间。与仅考虑最新世界模型的单假设（SH）搜索相比，GEGRH生成更保守的计划，平均规划时间略有增加。
🔬 方法详解
问题定义：移动机器人在未知环境中导航时，传感器数据存在噪声和算法缺陷，导致环境模型（例如成本地图）在不同时间步之间不一致，即同一区域可能在不同时刻被标记为障碍物或自由空间。现有的运动规划方法难以在这种不一致的环境模型下生成安全可靠的轨迹，容易导致碰撞或规划失败。
核心思路：论文的核心思路是维护一个世界模型的历史记录，并基于这些历史记录来调整运动规划过程。具体来说，不是只考虑当前时刻的环境模型，而是考虑过去一段时间内的所有环境模型，并对那些在不同模型中状态不一致的区域（即发散点）进行特殊处理，从而生成在所有历史模型中都相对安全的轨迹。
技术框架：GEGRH方法的整体流程如下： 1. 初始规划：使用A或其他搜索算法，基于当前环境模型进行初始路径规划。 2. 边缘扩展：在扩展节点时，如果扩展的边缘穿过世界模型历史中的发散点，则记录该边缘。 3. 延迟子搜索：将针对发散点的子搜索延迟到边缘扩展到目标区域之后。 4. 图修正：在找到初始路径后，根据每个世界模型中的发散节点，对图进行修正，调整节点成本。 5. 路径优化*：基于修正后的图，重新进行路径规划，得到最终的安全轨迹。
关键创新：GEGRH的关键创新在于其延迟子搜索和图修正策略。与PEH和GEH方法不同，GEGRH不是在每次节点扩展时都进行子搜索，而是将子搜索延迟到边缘扩展到目标区域之后，从而减少了计算量。此外，GEGRH还通过图修正步骤，根据每个世界模型中的发散节点来调整节点成本，从而更好地考虑了环境模型的不确定性。与现有方法的本质区别在于，GEGRH不是简单地基于单个环境模型进行规划，而是考虑了环境模型的历史信息，从而提高了规划的安全性。
关键设计：GEGRH的关键设计包括： 1. 发散点检测：需要定义一个合适的阈值来判断一个区域是否为发散点，即在多少个历史模型中状态不一致才被认为是发散点。 2. 子搜索策略：需要设计一个高效的子搜索算法，用于在发散点周围寻找安全路径。 3. 图修正策略：需要设计一个合适的成本函数，用于根据发散节点来调整节点成本，例如可以根据发散节点在历史模型中被标记为障碍物的频率来增加节点成本。
🖼️ 关键图片
📊 实验亮点
实验结果表明，GEGRH方法在非结构化越野环境中，相比于VEH方法，能够找到成本更低的轨迹，并且具有更快的平均规划时间。与单假设（SH）搜索相比，GEGRH生成更保守的计划，平均规划时间略有增加，但安全性更高。这些结果表明GEGRH方法在保证安全性的前提下，能够有效地进行运动规划。
🎯 应用场景
该研究成果可应用于各种需要在不确定或动态环境中导航的移动机器人，例如：无人驾驶车辆、仓储机器人、农业机器人、搜救机器人等。尤其是在环境感知存在误差或环境快速变化的情况下，该方法能够提高机器人导航的安全性与可靠性，降低碰撞风险，具有重要的实际应用价值和推广前景。
📄 摘要（原文）
Mobile ground robots lacking prior knowledge of an environment must rely on sensor data to develop a model of their surroundings. In these scenarios, consistent identification of obstacles and terrain features can be difficult due to noise and algorithmic shortcomings, which can make it difficult for motion planning systems to generate safe motions. One particular difficulty to overcome is when regions of the cost map switch between being marked as obstacles and free space through successive planning cycles. One potential solution to this, which we refer to as Valid in Every Hypothesis (VEH), is for the planning system to plan motions that are guaranteed to be safe through a history of world models. Another approach is to track a history of world models, and adjust node costs according to the potential penalty of needing to reroute around previously hazardous areas. This work discusses three major iterations on this idea. The first iteration, called PEH, invokes a sub-search for every node expansion that crosses through a divergence point in the world models. The second and third iterations, called GEH and GEGRH respectively, defer the sub-search until after an edge expands into the goal region. GEGRH uses an additional step to revise the graph based on divergent nodes in each world. Initial results showed that, although PEH and GEH find more optimistic solutions than VEH, they are unable to generate solutions in less than one-second, which exceeds our requirements for field deployment. Analysis of results from a field experiment in an unstructured, off-road environment on a Clearpath Robotics Warthog UGV indicate that GEGRH finds lower cost trajectories and has faster average planning times than VEH. Compared to single-hypothesis (SH) search, where only the latest world model is considered, GEGRH generates more conservative plans with a small increase in average planning time.