Optimal Market-based Multi-Robot Task Allocation via Strategic Pricing
Optimal Market-based Multi-Robot Task Allocation via Strategic Pricing
复制标题
通过战略定价实现基于市场的最优多机器人任务分配
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Dylan A. Shell
中科院分区：
文献类型：
--
作者：
Lantao Liu;Dylan A. Shell
拍卖和市场机制是多机器人系统中最常用的分布式任务分配方法。大多数这些机制的设计是在一个启发式的方式和质量的分析所产生的分配解决方案是罕见的。本文提出了一种新的基于市场的多机器人任务分配算法，产生最优分配。而不是采用买方的“自私”的投标的角度来看，在以前的拍卖/基于市场的方法，所提出的方法的方法拍卖从商家的角度来看，产生的定价政策，响应于客户的派系。该算法使用价格上涨来清除市场上的所有商品，从而产生一种平衡状态，使商家和客户都满意。该方法的时间复杂度（O（nlgn））接近最快的最新算法（O（n）），但非常容易实现，因此可以作为一种通用的分配算法。在以前的研究中，经济模型反映了市场的分布式本质：在本文中，它直接导致一个分散的方法，非常适合分布式多机器人系统。
Auction and market-based mechanisms are among the most popular methods for distributed task allocation in multirobot systems. Most of these mechanisms were designed in a heuristic way and analysis of the quality of the resulting assignment solution is rare. This paper presents a new market-based multi-robot task allocation algorithm that produces optimal assignments. Rather than adopting a buyer’s “selfish” bidding perspective as in previous auction/market-based approaches, the proposed method approaches auctioning from a merchant’s point of view, producing a pricing policy that responds to cliques of customers. The algorithm uses price escalation to clear a market of all its goods, producing a state of equilibrium that satisfies both the merchant and customers. The proposed method can be used as a general assignment algorithm as it has a time complexity (O(nlgn)) close to the fastest state-of-the-art algorithms (O(n)) but is extremely easy to implement. As in previous research, the economic model reflects the distributed nature of markets inherently: in this paper it leads directly to a decentralized method ideally suited for distributed multi-robot systems.