Robotics: Science and Systems IX
Optimal Market-based Multi-Robot Task Allocation via Strategic Pricing
Lantao Liu, Dylan ShellAbstract:
Auction and market-based mechanisms are among the most popular methods for distributed task allocation in multi-robot 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(n^3 lg n)) close to the fastest state-of-the-art algorithms (O(n^3)) 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.
Bibtex:
@INPROCEEDINGS{Liu-RSS-13, AUTHOR = {Lantao Liu AND Dylan Shell}, TITLE = {Optimal Market-based Multi-Robot Task Allocation via Strategic Pricing}, BOOKTITLE = {Proceedings of Robotics: Science and Systems}, YEAR = {2013}, ADDRESS = {Berlin, Germany}, MONTH = {June}, DOI = {10.15607/RSS.2013.IX.033} }