Robotics: Science and Systems IX

Optimal Market-based Multi-Robot Task Allocation via Strategic Pricing

Lantao Liu, Dylan Shell


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.



    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}