BnB-ADOPT:一种异步分支界限DCOP算法
该论文提出了用于解决分布式约束优化问题(DisCOPs)的一种新的搜索算法,即基于异步边界计算的异步前向绑定算法(AFB),该算法通过处理候选目标队列来进行分布式回溯搜索,实验结果表明,AFB相对于同步分支和界限搜索算法的效率提高了许多个数量级,并且在问题紧度增加时,产生相变的效果。而AFB-BJ算法则通过引入回跳机制进一步提高了算法效率,是DisCOPs的一种非常有效的算法。
Jan, 2014
本文旨在探究利用基于逻辑编程技术的基础设施,通过使用一种通用约束求解器(此处为约束逻辑编程系统)来处理代理层次的约束求解,以解决分布式约束优化问题,并通过初步实验表明其在性能和可扩展性方面较目前最先进的 DCOP 系统有所提高,为解决DCOP问题提供更先进的技术手段(例如搜索策略和复杂约束) 。
May, 2014
本文探讨了Answer Set Programming在解决Distributed Constraint Optimization Problems方面的应用。其贡献包括:将DCOPs表示为逻辑程序;介绍了基于逻辑编程的第一个DCOP算法ASP-DPOP;实验证明ASP-DPOP可以比DPOP快两个数量级,并且可以解决DPOP无法解决的一些问题;以及演示了ASP在当前被建模为DCOPs的各种多代理问题中的适用性。
May, 2017
通过基于在线学习的inadmissible估计和EES算法,在研究现有的bounded-suboptimal MAPF算法的基础上,提出一种新的bounded-suboptimal算法EECBS,相较于ECBS,BCP-7和eMDD-SAT等先进算法,在运行时间上表现更快,希望其可推广到更多bounded-suboptimal MAPF算法的应用中。
Oct, 2020
该论文提出了一种基于图神经网络的DCOPs解决方案,通过预训练的优化标签数据构建出有效的启发式方法,在分布式环境中实现了去中心化的模型推理,并结合局部搜索或回溯搜索算法,在各种测试中都取得了显著的优异表现。
Dec, 2021
本文研究了多智能体路径规划中的Conflict-Based Search算法,证明了权重cost-to-go和冲突启发式算法可以被用于低级规划器,旨在提高算法效率和解决冲突问题。此外,该文章进一步表明算法性能与高低级之间的权衡有关,对现有算法进行了优化。
May, 2022
本研究提出了一种名为ITA-CBS的增量目标指派CBS方法,该方法不需要计算K个最佳任务分配,只在搜索过程中增量计算新的最佳分配,有效避免了多个搜索树中的冲突,保证了最优解和计算效率。
Jul, 2023
多智能体路径规划 (MAPF) 的一个变种是综合目标分配和路径规划 (TAPF) 问题,本文引入了 ITA-ECBS 作为 ITA-CBS 的边界次优变体,并采用聚焦搜索和基于新的下界矩阵确定目标分配,经测试在 54,033 个案例中表现出优于基线方法 ECBS-TA 的结果占据了 87.42%。
Apr, 2024