From selfish auctioning to incentivized marketing | Autonomous Robots Skip to main content
Springer Nature Link
Log in

From selfish auctioning to incentivized marketing

  • Published:
Autonomous Robots Aims and scope Submit manuscript

Abstract

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 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 (\(O(n^3 \text {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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. The main algorithm was first presented in the 2013 Robotics: Science and Systems conference (Liu and Shell 2013).

  2. Note that the word pricing is also used in the linear programming literature, in particular for branch-and-bound and cutting plane methods. Therein the term is used to describe the dynamic introduction of new variables. That use is distinct and should not be confused with the economic use in the present paper.

References

  • Agmon, N., Kaminka, G. A., Kraus, S., & Traub, M. (2010). Task reallocation in multi-robot formations. Journal of Physical Agents, 4(2), 1–10.

    Google Scholar 

  • Bertsekas, D. P. (1979). A distributed algorithm for the assignment problem. Cambridge: Laboratory for Information and Decision Systems Report, MIT.

    Google Scholar 

  • Bertsekas, D. P. (1990). The auction algorithm for assignment and other network flow problems: A tutorial. Interfaces, 20(4), 133–149.

    Article  Google Scholar 

  • Bertsekas, D. P. (1992). Auction algorithms for network flow problems: A tutorial introduction. Computational Optimization and Applications, 1, 7–66.

    Article  MathSciNet  MATH  Google Scholar 

  • Bradley, S., Hax, A., & Magnanti, T. (1977). Applied mathematical programming. Reading: Addison-Wesley.

    Google Scholar 

  • Burkard, R. E., Dell’Amico, M., & Martello, S. (2009). Assignment problems. New York, NY: Society for Industrial and Applied Mathematics.

    Book  MATH  Google Scholar 

  • Derigs, U. (1985). The shortest augmenting path method for solving assignment problems: Motivation and computational experience. Annals of Operations Research, 4, 57–102.

    Article  MathSciNet  Google Scholar 

  • Dias, M. B., & Stentz, A. (2002). Opportunistic optimization for market-based multirobot control. In Proceedings of the IROS (pp. 2714–2720).

  • Dias, M. B., Zlot, R., Kalra, N., & Stentz, A. (2006). Market-based multirobot coordination: A survey and analysis. Proceedings of the IEEE, 94(7), 1257–1270.

    Article  Google Scholar 

  • Dinic, E. A., & Kronrod, M. A. (1969). An algorithm for the solution of the assignment problem. Soviet Mathematics Doklady, 10, 1324–1326.

    MATH  Google Scholar 

  • Gerkey, B. P. & Matarić, M. J. (2000). Murdoch: Publish/subscribe task allocation for heterogeneous agents. In Fourth International Conference on Autonomous Agents (pp. 203–204).

  • Gerkey, B. P., & Matarić, M. J. (2002). Sold!: auction methods for multirobot coordination. IEEE Transactions on Robotics and Automation, 18(5), 758–768.

    Article  Google Scholar 

  • Gerkey, B. P., & Matarić, M. J. (2004). A formal analysis and taxonomy of task allocation in multi-robot systems. International Journal of Robotics Research, 23(9), 939–954.

    Article  Google Scholar 

  • Giordani, S., Lujak, M., & Martinelli, F. (2010). A distributed algorithm for the multi-robot task allocation problem. LNCS: Trends in Applied Intelligent Systems, 6096, 721–730.

    Google Scholar 

  • Goldberg, D., Cicirello, V. A., Dias, M. B., Simmons, R. G., Smith, S. F., & Stentz, A. (2003). Task allocation using a distributed market-based planning mechanism. In Proceedings of the International Joint Conference on Autonomous Agents & Multiagent Systems, (AAMAS), Melbourne (pp. 996–997).

  • Koenig, S., Keskinocak, P., & Tovey, C. A. (2010). Progress on agent coordination with cooperative auctions. In Proceedings of the AAAI.

  • Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistic Quarterly, 2, 83–97.

    Article  Google Scholar 

  • Lagoudakis, M. G., Markakis, E., Kempe, D., Keskinocak, P., Kleywegt, A., Koenig, S., et al. (2005). Auction-based multi-robot routing. In Robotics: Science and Systems.

  • Liu, L., & Shell, D. A. (2012a). A distributable and computation-flexible assignment algorithm: From local task swapping to global optimality. In Proceedings of Robotics: Science and Systems.

  • Liu, L., & Shell, D. A. (2012b). Large-scale multi-robot task allocation via dynamic partitioning and distribution. Autonomous Robots, 33(3), 291–307.

    Article  Google Scholar 

  • Liu, L., & Shell, D. A. (2013). Optimal market-based multi-robot task allocation via strategic pricing. In Proceedings of Robotics: Science and Systems, Berlin, Germany.

  • Luo, L., Chakraborty, N., & Sycara, K. (2013). Distributed algorithm design for multi-robot task assignment with deadlines for tasks. In ICRA.

  • Mankiw, N. (2011). Principles of economics. Economics series. Melbourne: Cengage Learning.

    Google Scholar 

  • McLurkin, J., & Yamins, D. (2005). Dynamic task assignment in robot swarms. In Proceedings of Robotics: Science and Systems.

  • Michael, N., Zavlanos, M. M., Kumar, V., & Pappas, G. J. (2008). Distributed multi-robot task assignment and formation control. In IEEE International Conference on Robotics and Automation, Pasadena, CA.

  • Nanjanath, M. & Gini, M. (2006). Dynamic task allocation for robots via auctions. In Proceedings of the ICRA (pp. 2781–2786).

  • Parker, L. E. (1998). Alliance: An architecture for fault-tolerant multi-robot cooperation. IEEE Transactions on Robotics and Automation, 14(2), 220–240.

    Article  Google Scholar 

  • Pentico, D. W. (2007). Assignment problems: A golden anniversary survey. European Journal of Operational Research, 176, 774–793.

    Article  MathSciNet  MATH  Google Scholar 

  • Sandholm, T. (2002). Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence, 135(1–2), 1–54.

    Article  MathSciNet  MATH  Google Scholar 

  • Smith, S. L. & Bullo, F. (2007a). A geometric assignment problem for robotic networks. In Modeling, Estimation and Control: Festschrift in Honor of Giorgio Picci on the Occasion of his 65 Birthday (Vol. 364, pp. 271–284).

  • Smith, S. L. & Bullo, F. (2007b). Target assignment for robotic networks: Asymptotic performance under limited communication. In American Control Conference (pp. 1155–1160).

  • Turpin, M., Michael, N., & Kumar, V. (2012). Trajectory planning and assignment in multirobot systems. In International Workshop on the Algorithmic Foundations of Robotics (WAFR).

  • Vail, D., & Veloso, M. (2003). Multi-robot dynamic role assignment and coordination through shared potential fields. In A. Schultz, L. Parker, & F. Schneider (Eds.), Multi-robot systems. Dordrecht: Kluwer.

    Google Scholar 

  • Vincent, R., Fox, D., Ko, J., Konolige, K., Limketkai, B., Morisset, B., et al. (2008). Distributed multirobot exploration, mapping, and task allocation. Annals of Mathematics and Artificial Intelligence, 52(2–4), 229–255.

    Article  MathSciNet  MATH  Google Scholar 

  • Wolfstetter, E. (1994). Auctions: An introduction. Journal of Economic Surveys, 10(4), 367–420.

    Article  Google Scholar 

  • Zavlanos, M. M., Spesivtsev, L., & Pappas, G. J. (2008). A distributed auction algorithm for the assignment problem. Proceedings of the IEEE Conference on Decision and Control (pp. 1212–1217). Mexico: Cancun.

  • Zhang, Y., & Parker, L. E. (2013). Considering inter-task resource constraints in task allocation. Autonomous Agents and Multi-Agent Systems, 26(3), 389–419.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. The Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, USA

    Lantao Liu & Nathan Michael

  2. Department of Computer Science and Engineering, Texas A&M University, College Station, TX, USA

    Dylan A. Shell

Authors
  1. Lantao Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dylan A. Shell
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Nathan Michael
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lantao Liu.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Liu, L., Shell, D.A. & Michael, N. From selfish auctioning to incentivized marketing. Auton Robot 37, 417–430 (2014). https://doi.org/10.1007/s10514-014-9403-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10514-014-9403-2

Keywords

Search

Navigation