From selfish auctioning to incentivized marketing
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
2014, Springer Science+Business Media New York. 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 buyers selfish bidding perspective as in previous auction/market-based approaches, the proposed method approaches auctioning from a merchants point of view, producing a pricing policy that responds to cliques of customers and their preferences. The algorithm uses price escalation to clear a market of all its items, producing a state of equilibrium that satisfies both the merchant and customers. This effectively assigns all robots to their tasks. The proposed method can be used as a general assignment algorithm as it has a time complexity (Formula presented.) close to the fastest state-of-the-art algorithms (Formula presented.) 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.