Sep, 2023

LEA*: 机器人运动规划的改进边缘效率 A * 变种算法

PDF
TL;DR本研究提出了一种新的图搜索算法，即基于惰性边的 A*（LEA*），用于机器人运动规划，通过使用边队列和利用惰性搜索的思想，LEA * 在顶点上有效地与 A * 类似，并且相对于 A * 来说边的效率有所提高。LEA * 实现简单且易于操作，对 A * 进行最小修改，与之前的惰性搜索算法相比具有非常小的开销。我们还研究了膨胀启发函数的效果，得到加权 LEA*（wLEA*）。实验结果表明，wLEA * 的边效率接近于 LazySP，即近似最优。我们在 2D 规划问题和 7-DOF 机械臂规划中测试了 LEA * 和 wLEA*，并与之前的算法进行了全面比较，在稀疏、中等和复杂的随机环境以及小、中和大规模图中，结果显示 LEA * 和 wLEA * 是找到规划路径最快的算法。
graph search algorithmlazy edged based a*robot motion planningedge efficiencyweighted lea*
发现论文，激发创造
  • 机器人运动规划的通用惰性搜索：通过基于事件的开关交织搜索和边缘评估

    该研究提出了一个框架，名为广义 Lazy 搜索（Generalized Lazy Search），能够更有效地解决机器人运动规划中的搜索难题，其中包括了来自边缘评估的瓶颈问题和搜索努力带来的负担问题。该框架有效地平衡了这两方面的问题，可显著提高搜索效率。同时，该研究采用边缘概率技术，在 R2、SE（2）和 7-DoF 操纵等多数模拟环境中优于竞争基准。

    Apr, 2019

  • LEA: 基于学习优化策略的进化算法之外

    设计一种可学习的进化算法（LEA）来实现从手工设计的优化策略到学习的优化策略的转变，能够高效地利用目标任务的低保真信息来形成优化策略，以更少的计算成本获得更好的解决方案。

    Apr, 2023

  • 基于拉格朗日的 A * 算法用于自动推理

    本文考虑了 A* 算法的一种修改方案，引入了启发式部分的加权来提高算法的效率，以无人机路径规划为应用场景，其中速度被视为启发式规划的权重。通过变分法基于拉格朗日方程计算可以确定速度为动态系统的决定性因素，该方法可以应用于其他领域的算法以提高效率。

    Jun, 2023

  • A-ePA*SE：面向评估缓慢情况的即时边缘并行 A*

    该论文提出了一种将 Anytime 属性引入 ePA*SE 算法的方法 A-ePA*SE，使得在计算代价昂贵的边的领域中，在时间充裕的情况下比其他任意搜索方法更有效。

    May, 2023

  • 学习 A * 启发式算法

    本文利用神经演算法推导出高效的启发式路径搜索算法，结合 Dijkstra 算法和 A * 算法中的一致的启发函数，并将其推广应用于图形中的路径搜索问题，结果表明相较于 Dijkstra 算法，应用基于学习到的 A * 算法中的启发函数的改进搜索在无损质量的情况下，实现了大幅的速度提升。

    Apr, 2022

  • LaCAM: 用于快速多智体路径规划的搜索算法

    我们提出了一种新颖的完整算法用于多智能体路径规划 (LaCAM)，LaCAM 使用两级搜索快速找到解决方案，即使有数百个代理也是如此，我们的全面实验表明，LaCAM 在各种情况下可与或优于最先进的 MAPF 子最优算法，涉及成功率，计划时间和成本总和解决方案的质量。

    Nov, 2022

  • A * 中多启发式函数的合理部署

    该研究论文介绍了两种基于 Lazy A* 和 rational meta-reasoning 的启发式搜索算法，能有效减少计算所需的启发式估价函数，并在实验中证明其为最先进的启发式算法组合方式。

    May, 2013

  • GePA*SE: 用于缓慢评估的广义基于边缘的并行 A * 算法

    提出了一种名为 GePA * SE 的算法，它是 PA * SE 和 ePA * SE 的泛化，可以在具有评估时间变化区间的任务上实现并行搜索，可用于机器人领域。

    Jan, 2023

  • ERA*: 正规栅格地图中解决最短路径问题的增强松弛 A * 算法

    该研究介绍了一种新的算法，用于在静态常规 8 邻接连通（G8）网格中解决点对点最短路径问题，该算法可以看作是 Hadlock 算法对 G8 网格的泛化，并且从计算策略完全不同的角度，通过定义一组查找矩阵，以较少的时间和内存开销实现了在提供的解决方案路径长度方面与松弛型 $A^*$（$RA^*$）算法在理论上的等效性，通过对各种类型和大小的网格地图的实验研究（1290 次实验对比 43 张地图），平均比 $RA^*$ 快 2.25 倍，比原始 $A^*$ 快 17 倍，而且在内存效率上更优越，因为它不需要存储 G 分数矩阵。

    Aug, 2023

  • ORLA*: 移动操作器基于懒 A * 的物体重新排列

    移动机器人对象重新排列的时间最优解决方案，使用延迟计算和机器学习支持多层次重新排列任务以及堆稳定性考虑。

    Sep, 2023