Optimized algorithms for multi-agent routing
Optimized algorithms for multi-agent routing
复制标题
多代理路由的优化算法
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Nathan R Sturtevant
中科院分区：
文献类型：
--
作者：
Akihiro Kishimoto;Nathan R Sturtevant
多机器人路由问题是多智能体协调的一个代表性领域，拍卖方法已被成功地用于协调机器人团队。这个问题的解决方案通常使用地图上不同位置之间的最短距离来计算标值。但是，这种最短距离计算的成本在以前的研究中并没有考虑到。本文提出了一种新的基于竞价的算法FASTBID，该算法可以减少多机器人路由问题中与竞价相关的计算成本。我们还分析了投标算法的一个小修改如何减少投标过程的计算量。实验表明，FASTBID不仅比以前的方法伸缩性好得多，而且在解决方案质量上几乎没有损失。
Auction methods have been successfully used for coordinating teams of robots in the multi-robot routing problem, a representative domain for multi-agent coordination. Solutions to this problem typically use bids computed using the shortest distance between various locations on a map. But, the cost of this shortest-distance computation has not been considered in previous research. This paper presents a new auction-based algorithm, FASTBID, that works to reduce the computational costs associated with bidding in the multi-robot routing problem. We also analyze how a small modification in the bidding algorithm can reduce the computational load of the bidding process. Experiments demonstrate that FASTBID not only scales much better than previous approaches, but does so with little or no loss in solution quality.