From selfish auctioning to incentivized marketing Academic Article uri icon

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.

published proceedings

  • AUTONOMOUS ROBOTS

altmetric score

  • 0.75

author list (cited authors)

  • Liu, L., Shell, D. A., & Michael, N.

citation count

  • 2

complete list of authors

  • Liu, Lantao||Shell, Dylan A||Michael, Nathan

publication date

  • December 2014