May, 2010

基于逐步采样的最优运动规划算法

PDF
TL;DR本文介绍了一种新型的算法 —— 快速探索随机图（RRG）及其树形版本 RRT $ ^ * $ 算法，并证明这两个算法都可以在几乎确定地收敛到最优解。此外，文章还建立起采样运动规划算法和随机几何图理论之间的新联系，以证明所提出算法的复杂度与传统 RRT 算法相比是等价的。
motion planningrapidly-exploring random treesrapidly-exploring random graphasymptotic optimalityrandom geometric graphs
发现论文，激发创造
  • 基于采样的最优路径规划算法

    本文介绍了一种新的算法 PRM * 和 RRT*，证明了它们是渐近最优的，并且在样本数增加的情况下，它们的解决方案成本几乎肯定收敛于最优值。这些算法的计算复杂度与传统的，但不是渐近最优的算法相当。

    May, 2011

  • 基于信息的 RRT*：通过合法椭球启发式直接采样聚焦于最优采样路径规划

    本文介绍一种有效的路径规划方法 Informed RRT*，通过直接采样路径长度的子集来提高搜索的效率，达到更高的收敛速度和更好的最终解决方案质量。

    Apr, 2014

  • 确定性采样式运动规划：最优性，复杂度，和性能

    该研究论文探究了将确定性的低离散度采样序列应用于机器人运动规划中的概率采样算法，并证明了其渐近最优性，并通过数值实验验证了其在路径成本和成功率方面表现出更高的性能。

    Apr, 2015

  • 可扩展渐进最优多机器人运动规划

    该研究提出了一种可扩展的多机器人路径规划方法 dRRT*，利用采样基规划器在所有机器人构型空间的复合配置空间中寻找渐近最优路径，实验表明 dRRT * 可以在高维多机器人问题中收敛到高质量路径。

    Jun, 2017

  • 多智能体 RRT*: 基于采样的合作路径规划（扩展摘要）

    提出了基于 MA-RRT * 算法的多智能体路径规划问题解决方案，该算法在解决真实世界中大型但稀疏环境的多飞机防撞等任务时性能很好，能够有效利用采样机制，比以往的正向搜索方法更具可扩展性。

    Feb, 2013

  • 批量通知树（BIT *）：通过启发式引导搜索隐式随机几何图的采样最优规划

    本文提出一种基于图形和采样基规划技术的易于操作的 Batch Informed Trees（BIT*）规划算法，展示了 BIT * 在模拟的随机环境和 CMU HERB 机器人的操作问题上的实用性，并证明了其概率上完备和渐近最优。

    May, 2014

  • 基于顶点的网络加速路径规划算法

    本论文提出了一种基于顶点网络的路径规划方法，该方法利用关键顶点来优化 RRT * 采样过程，提高了路径规划效率，实验结果表明相比基准模型提高了 400% 以上。

    Jul, 2023

  • 使用图神经网络减少基于采样的运动规划的碰撞检查

    通过训练图神经网络（GNN），我们提出了新的基于学习的方法来减少碰撞检查的计算量，加速采样空间中的路径规划，并通过随机几何图形（RGGs）和路径探索组件预测无碰撞的边来优化路径探索。

    Oct, 2022

  • 引导式运动规划框架

    随机抽样、机器人运动规划、引导空间、信息论方法、混合算法

    Apr, 2024

  • 在连续空间中可扩展的多机器人路径规划的安全间隔 RRT*

    在本文中，我们考虑了连续空间下的多机器人路径规划（Multi-Robot Path Planning，MRPP）问题，以找到无冲突的路径。为此，我们提出了一个两级方法，其中低级是一个基于采样的规划器 Safe Interval RRT*（SI-RRT*），用于找到单个机器人的无碰撞轨迹。高级方法可以使用任何能够解决机器人间冲突的方法，我们采用了两种代表性方法，即优先级规划（SI-CPP）和基于冲突搜索（SI-CCBS）。实验结果表明，SI-RRT * 能够快速找到高质量解，且样本数量较少。SI-CPP 在可扩展性方面表现较好，而 SI-CCBS 相对于现有的连续空间规划器而言，能够产生更高质量的解。与最具可扩展性的现有算法相比，SI-CPP 在保持解质量的同时，成功率提高了多达 94%，并且不会造成显著妥协。SI-CPP 还能够将完成时间缩短 45%。SI-CCBS 相对于竞争对手，将完成时间减少了 9%，尽管成功率降低了 14%。

    Apr, 2024