混合整数规划与高效启发式算法的多机器人时间最优覆盖路径规划
我们研究基于图的多机器人覆盖路径规划 (MCPP),旨在计算多个机器人覆盖给定 2D 网格图 $G$ 的所有顶点的路径。我们提出了一种新的算法框架 LS-MCPP,利用局部搜索直接在图 $D$ 上操作,通过扩展 STC 实现 MCPP 在任何分解图上的完全覆盖,并结合三种新颖的邻域操作符来引导搜索过程。我们的实验结果表明,LS-MCPP 在优化 makespan 方面显著优于现有算法,并且在运行时间方面具有数量级的优势,对于大规模实际覆盖任务具有重要的好处。
Dec, 2023
通过与网络流的等价性和整数线性规划,我们设计了用于解决四个不同目标的新颖和完整算法,从而解决了最佳多机器人路径规划问题。采用基于 ILP 算法模型和启发式算法的组合方法,能够在几秒钟内计算出包含数百个机器人,环境密集的问题的 1.x - 最优解。
Jul, 2015
本文研究基于图的多机器人路径规划问题,提出两种多流基于整数线性规划算法,计算最小到达时间和最小总距离的解决方案,其算法性能表现得到评估,并能够适应其他 MPP 问题变体。
Apr, 2012
本文提出了一种基于多机器人系统、强化学习与分布式规划相结合的方法,用于解决多机器人覆盖路径规划问题,并成功减少环境中随机干扰物的影响和避免碰撞,实现了任务完成时间的优化。
Aug, 2022
在本文中,我们考虑了连续空间下的多机器人路径规划(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
该研究论文关注于多方多目标优化问题(MPMOPs),着眼于冲突目标的多个决策者,如无人机路径规划。通过鼓励研究人员探索定制建模方法,致力于填补 MPMOPs 相对传统多目标优化的研究空白。测试套件由两个部分组成:具有常见帕累托最优解的问题和未知解的两方多目标无人机路径规划(BPMO-UAVPP)问题。第一部分的优化算法使用多方反转生成距离(MPIGD)进行评估,第二部分则使用多方超体积(MPHV)指标进行评估。所有问题上的平均算法排名作为性能基准。
Feb, 2024
本文提出了基于三分图的方法表示 MIP 问题,该问题可以通过图卷积网络结合机器学习方法来预测二进制变量的解,以生成一种局部分支类型切割,从而提高求解 MIP 问题的性能。
Jun, 2019