SpringerLink
Log in

Mechanism Selection for Multi-Robot Task Allocation

  • Conference paper
  • First Online:
Towards Autonomous Robotic Systems (TAROS 2017)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 10454))

Included in the following conference series:

  • 3418 Accesses

Abstract

The work presented here investigates how environmental features can be used to help select a task allocation mechanism from a portfolio in a multi-robot exploration scenario. In particular, we look at clusters of task locations and the positions of team members in relation to cluster centres. In a data-driven approach, we conduct experiments that use two different task allocation mechanisms on the same set of scenarios, providing comparative performance data. We then train a classifier on this data, giving us a method for choosing the best mechanism for a given scenario. We show that selecting a mechanism via this method, compared to using a single state-of-the-art mechanism only, can improve team performance in certain environments, according to our metrics.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    http://wiki.ros.org/global_planner.

  2. 2.

    These are the same arrangements as used in [23, 24].

  3. 3.

    https://github.com/scikit-learn-contrib/imbalanced-learn.

  4. 4.

    http://scikit-learn.org/stable/modules/grid_search.html.

References

  1. Berhault, M., Huang, H., Keskinocak, P., Koenig, S., Elmaghraby, W., Griffin, P.M., Kleywegt, A.: Robot exploration with combinatorial auctions. In: Proceedings of the International Conference on Intelligent Robotics and Systems (IROS) (2003)

    Google Scholar 

  2. Densham, P.J., Rushton, G.: A more efficient heuristic for solving large p-median problems. Pap. Reg. Sci. 71(3), 307–329 (1992)

    Article  Google Scholar 

  3. Dias, M.B., Zlot, R., Kalra, N., Stentz, A.: Market-based multirobot coordination: a survey and analysis. Proc. IEEE 94(7), 1257–1270 (2006)

    Article  Google Scholar 

  4. Dias, M.B., Stentz, A.: Opportunistic optimization for market-based multirobot control. In: Proceedings of the International Conference on Intelligent Robots and Systems (IROS), vol. 3, pp. 2714–2720 (2002)

    Google Scholar 

  5. Gerkey, B., Vaughan, R.T., Howard, A.: The player/stage project: tools for multi-robot and distributed sensor systems. In: Proceedings of the 11th International Conference on Advanced Robotics (2003)

    Google Scholar 

  6. Gomes, C.P., Selman, B.: Algorithm portfolios. Artif. Intell. 126(1–2), 43–62 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  7. Hakimi, S.L.: Optimum locations of switching centers and the absolute centers and medians of a graph. Oper. Res. 12(3), 450–459 (1964)

    Article  MATH  Google Scholar 

  8. Hart, P., Nilsson, N., Raphael, B.: A formal basis for the heuristic determination of minimal cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)

    Article  Google Scholar 

  9. Heap, B.: Sequential single-cluster auctions for multi-robot task allocation. Ph.D. thesis, The University of New South Wales, November 2013

    Google Scholar 

  10. Huberman, B.A., Lukose, R.M., Hogg, T.: An economics approach to hard computational problems. Science 275(5296), 51–54 (1997)

    Article  Google Scholar 

  11. Kariv, O., Hakimi, S.L.: An algorithmic approach to network location problems. ii: the p-medians. SIAM J. Appl. Math. 37(3), 539–560 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  12. Koenig, S., Tovey, C., Lagoudakis, M., Kempe, D., Keskinocak, P., Kleywegt, A., Meyerson, A., Jain, S.: The power of sequential single-item auctions for agent coordination. In: Proceedings of National Conference on Artificial Intelligence (2006)

    Google Scholar 

  13. Kraus, S.: Automated negotiation and decision making in multiagent environments. In: Luck, M., Mařík, V., Štěpánková, O., Trappl, R. (eds.) ACAI 2001. LNCS, vol. 2086, pp. 150–172. Springer, Heidelberg (2001). doi:10.1007/3-540-47745-4_7

    Chapter  Google Scholar 

  14. Kuhn, H.W.: The Hungarian method for the assignment problem. Naval Res. Logistics Q. 2(1–2), 83–97 (1955)

    Article  MathSciNet  MATH  Google Scholar 

  15. Leyton-Brown, K., Nudelman, E., Andrew, G., McFadden, J., Shoham, Y.: A portfolio approach to algorithm selection. In: International Joint Conference on Artificial Intelligence (IJCAI), vol. 1543, pp. 1542–1543 (2003)

    Google Scholar 

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

    Article  Google Scholar 

  17. Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., Duchesnay, E.: Scikit-learn: machine learning in Python. J. Mach. Learn. Res. 12, 2825–2830 (2011)

    MathSciNet  MATH  Google Scholar 

  18. Quigley, M., Conley, K., Gerkey, B.P., Faust, J., Foote, T., Leibs, J., Wheeler, R., Ng, A.Y.: ROS: an open-source robot operating system. In: ICRA Workshop on Open Source Software (2009)

    Google Scholar 

  19. Reese, J.: Solution methods for the p-median problem: an annotated bibliography. Networks 48(3), 125–142 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  20. Rice, J.R.: The algorithm selection problem. Adv. Comput. 15, 65–118 (1976)

    Article  Google Scholar 

  21. Sandholm, T.: Contract types for satisficing task allocation: I theoretical results. In: Proceedings of the AAAI Spring Symposium: Satisficing Models, pp. 68–75 (1998)

    Google Scholar 

  22. Schneider, E., Balas, O., Özgelen, A.T., Sklar, E.I., Parsons, S.: Evaluating auction-based task allocation in multi-robot teams. In: Workshop on Autonomous Robots and Multirobot Systems (ARMS) at Autonomous Agents and MultiAgent Systems (AAMAS), Paris, France, May 2014

    Google Scholar 

  23. Schneider, E., Sklar, E.I., Parsons, S.: Evaluating multi-robot teamwork in parameterised environments. In: Alboul, L., Damian, D., Aitken, J.M.M. (eds.) TAROS 2016. LNCS (LNAI), vol. 9716, pp. 301–313. Springer, Cham (2016). doi:10.1007/978-3-319-40379-3_32

    Google Scholar 

  24. Schneider, E., Sklar, E.I., Parsons, S., Özgelen, A.T.: Auction-based task allocation for multi-robot teams in dynamic environments. In: Dixon, C., Tuyls, K. (eds.) TAROS 2015. LNCS, vol. 9287, pp. 246–257. Springer, Cham (2015). doi:10.1007/978-3-319-22416-9_29

    Chapter  Google Scholar 

  25. Smith, R.G.: The contract net protocol: high-level communication and control in a distributed problem solver. In: Bond, A.H., Gasser, L. (eds.) Distributed Artificial Intelligence. Morgan Kaufmann Publishers Inc. (1988)

    Google Scholar 

  26. Teitz, M.B., Bart, P.: Heuristic methods for estimating the generalized vertex median of a weighted graph. Oper. Res. 16(5), 955–961 (1968)

    Article  MATH  Google Scholar 

  27. **ao, N.: GIS Algorithms. SAGE Publications, Thousand Oaks (2015)

    Google Scholar 

  28. Xu, L., Hoos, H.H., Leyton-Brown, K.: Hydra: automatically configuring algorithms for portfolio-based selection. In: Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, pp. 210–216. AAAI Press (2010)

    Google Scholar 

  29. Xu, L., Hutter, F., Hoos, H.H., Leyton-Brown, K.: Satzilla: portfolio-based algorithm selection for sat. J. Artif. Intell. Res. 32, 565–606 (2008)

    MATH  Google Scholar 

  30. Zlot, R., Stentz, A., Dias, M.B., Thayer, S.: Multi-robot exploration controlled by a market economy. In: Proceedings of the IEEE Conference on Robotics and Automation (2002)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Informatics, King’s College London, London, UK

    Eric Schneider, Elizabeth I. Sklar & Simon Parsons

  2. Department of Computer Science, University of Liverpool, Liverpool, UK

    Eric Schneider

Authors
  1. Eric Schneider
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Elizabeth I. Sklar
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Simon Parsons
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Eric Schneider .

Editor information

Editors and Affiliations

  1. University of Surrey, Guildford, United Kingdom

    Yang Gao

  2. University of Surrey, Guildford, United Kingdom

    Saber Fallah

  3. University of Surrey, Guildford, United Kingdom

    Yaochu **

  4. University of Surrey, Guildford, United Kingdom

    Constantina Lekakou

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

Schneider, E., Sklar, E.I., Parsons, S. (2017). Mechanism Selection for Multi-Robot Task Allocation. In: Gao, Y., Fallah, S., **, Y., Lekakou, C. (eds) Towards Autonomous Robotic Systems. TAROS 2017. Lecture Notes in Computer Science(), vol 10454. Springer, Cham. https://doi.org/10.1007/978-3-319-64107-2_33

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-64107-2_33

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-64106-5

  • Online ISBN: 978-3-319-64107-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation