A-ePA*SE:面向评估缓慢情况的即时边缘并行 A*
本论文将A*启发式搜索算法转化为逐步改进的任意时间算法,采用加权启发式搜索找到近似解,继续weighted search以找到更好的解并改善当前解的低下性,形成了一个能够在搜索时间和解决方案质量之间灵活权衡的任意启发式搜索算法,具有较高的适用性和广泛性。
Oct, 2011
ASAGA是SAGA的异步并行版本,具有快速线性收敛率。通过重新访问并澄清了一些细微但重要的技术问题,ASAGA不需要稀疏假设即可在多核系统上获得线性加速,并通过40核架构的实现结果展示了实际加速以及硬件开销。
Jun, 2016
提出了一种名为GePA * SE的算法,它是PA * SE和ePA * SE的泛化,可以在具有评估时间变化区间的任务上实现并行搜索,可用于机器人领域。
Jan, 2023
本研究提出了一种新的图搜索算法,即基于惰性边的A*(LEA*),用于机器人运动规划,通过使用边队列和利用惰性搜索的思想,LEA*在顶点上有效地与A*类似,并且相对于A*来说边的效率有所提高。LEA*实现简单且易于操作,对A*进行最小修改,与之前的惰性搜索算法相比具有非常小的开销。我们还研究了膨胀启发函数的效果,得到加权LEA*(wLEA*)。实验结果表明,wLEA*的边效率接近于LazySP,即近似最优。我们在2D规划问题和7-DOF机械臂规划中测试了LEA*和wLEA*,并与之前的算法进行了全面比较,在稀疏、中等和复杂的随机环境以及小、中和大规模图中,结果显示LEA*和wLEA*是找到规划路径最快的算法。
Sep, 2023
任何时候启发式搜索算法试图尽快找到一个(潜在的次优解)并努力寻找越来越好的解决方案,直到获得一个最优解或时间用尽。本文提出了一种新的算法,矩形搜索,它基于广度优先搜索的一种变体束搜索,重复地在所有深度层面上探索替代方案,因此最适用于具有深度局部极小值的问题。使用多种流行的搜索基准进行的实验表明,矩形搜索与固定宽度束搜索相竞争,并且通常比先前最好的任何时候搜索算法表现更好。
Dec, 2023
在多智能体路径规划领域的一个研究方向是确定在执行过程中代理被延迟时如何高效地重新规划。我们提出了Switchable-Edge Search (SES)算法,一种基于A*的算法,旨在找到最佳的经过次序。我们证明了SES的最优性,并通过模拟评估了它的效率。SES的最佳变体在小和中型问题上只需要不到1秒,并且在大型问题上比基准算法运行速度快4倍。
Mar, 2024
本研究解决了当前最先进规划求解器与广义规划之间的性能差距。文章提出了一种将并行搜索技术应用于最佳优先广义规划(BFGP)的方法,强调了BFGP在并行化方面的优势及其与经典规划器的区别。研究结果表明,所提的并行策略在核心数增加时具有良好的扩展性,能够显著提升广义规划的效率。
Jul, 2024
本研究解决了目前最佳优先广义规划(BFGP)在性能上与先进规划求解器之间的差距。通过引入并行搜索技术,提出了两种共享内存的并行策略,显示出良好的可扩展性。研究表明,这些策略能有效提升BFGP在解决多重经典规划实例中的表现,具有显著的理论和实践意义。
Jul, 2024
本研究针对贪心最佳优先搜索(GBFS)并行化过程中的高代价问题进行了探讨。提出了一种新颖的方法,通过将状态生成与状态评估分离,从而提升了状态评估率,改善了搜索性能。这一改进为贪心最佳优先搜索的有效并行化提供了有益的解决方案,可能会对相关领域产生深远影响。
Aug, 2024