Anytime Motion Planning

• 又称: anytime planning, anytime planner
• 类别: Planning & manipulation › Motion planning
• 标签: motion-planning, sampling-based-planning, optimal-planning, real-time, bounded-computation

一种运动规划方式：先快速返回一条有效路径，再在时间允许时持续改进它，因此无论规划器何时被停止，都有一个可用的答案。

定义

随时运动规划器（anytime motion planner）会尽早给出第一个可行、无碰撞的解，然后把剩余的时间用于改进它，通常是降低路径长度、执行时间或其他代价。在得到第一个解之后的每一时刻，它都持有一个迄今最好的答案，如果被中断就可以返回这个答案。这一思路来自人工智能中更广泛的随时算法概念，由 Dean 和 Boddy 在 1980 年代后期提出：解的质量与计算时间相互权衡，两者之间的关系用性能曲线（performance profile）来描述。

在图搜索中，随时行为通常这样获得：先用加权、放大的启发式运行搜索，再在复用先前搜索工作的同时逐步收紧权重，Anytime Repairing A（ARA）就是如此。在基于采样的规划中，RRT 以及概率路线图的 PRM 变体等渐近最优规划器天然就是随时的：它们在得到第一个解后继续采样和重连，随着样本数增加，当前最佳路径的代价趋于最优值。Informed RRT 和 Batch Informed Trees（BIT）把样本限制在仍可能包含更优路径的区域内，从而加快改进阶段。普通的快速探索随机树**在这个意义上不是随时的，因为它一旦连接到目标就会停止，不过可以在它外面套上重启或后处理。

随时间的改进很少是平滑的。代价往往呈阶梯式下降，尤其是当规划器找到一条穿过障碍物之间另一处空隙的路线时，也就是一条处于新的同伦类中的路径；而且很长的时段可能几乎没有收益。这使得何时停止本身成为一个问题：停得太早会损失质量，停得太晚则浪费机器人本可用于运动的时间。固定的时间预算是常见做法，而元推理方法则学习或估计何时进一步计算已不再值得。

为何重要

机器人很少拥有固定且已知的规划时间。随时规划器几乎立刻就能给出一个安全的后备方案，并把任何空余时间转化为更好的运动，这适合那些必须在截止时间前行动、但仍在意路径质量、能耗或节拍时间的系统。

主要应用

• 在操作流水线中按每次查询的时间预算进行机械臂运动规划
• 必须按固定控制周期行动的移动机器人和车辆的重规划
• 空中机器人的路径规划，更短的路径可以节省电池
• 在栅格和格网上采用 ARA* 式权重递减的启发式图搜索
• 关于何时停止规划、开始行动的元推理研究

实际应用

一台移动操作臂使用 OMPL 等库中的渐近最优、基于采样的规划器来规划手臂运动。每次查询都有一个时间预算：规划器通常在预算的早期就找到第一条路径，然后继续缩短它。团队在大量记录下来的查询上记录最佳代价随已用时间的变化，发现大部分收益来得很早，偶尔在后期找到绕过障碍物的更短路线时会出现大幅下降。他们不再总是用满整个预算，而是在代价在设定的时间间隔内没有改进时停止，或者使用学习得到的停止规则，然后对结果进行捷径优化和时间参数化，再把它发送给控制器。

常见误解

• 随时意味着第一个解接近最优 — 第一个解往往离最优很远，质量取决于规划器运行多长时间
• 代价随时间稳定下降 — 它通常以不均匀的阶梯下降，阶梯之间有很长的平台期
• 渐近最优性保证在时间预算内得到一条好路径 — 它只描述计算量无限增长时的极限，对有限的截止时间没有任何说明
• 用满整个时间预算总是最好的 — 花在规划上的时间就是没有用于运动的时间，因此提前停止往往是更好的取舍

谁需要了解

• 配置基于采样或基于搜索的规划器的运动规划工程师
• 在实时限制下工作的移动机械臂操作与导航开发者
• 研究有限计算条件下规划的机器人研究人员
• 学习最优运动规划的学生

相关技术

• ARA（Anytime Repairing A）
• RRT*
• Informed RRT*
• BIT*（Batch Informed Trees）
• OMPL

相关术语

• RRT*
• Rapidly-exploring random tree
• Probabilistic Roadmap
• Homotopy Class
• Warm Start
• Motion Planning

相关项目

• GENESIS: World's fastest physics engine: 43M FPS for embodied AI learning
• Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
• FAST-LIVO2: Fast, direct LiDAR-inertial-visual odometry from HKU-MARS, published in IEEE T-RO
• Dora AI: Dataflow middleware for AI robotics applications, built in Rust
• OpenMind OM1: AI-native operating system for robots with modular perception, cognition, and action
• Fast DDS: eProsima's high-performance DDS middleware — the default transport under ROS 2