Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Autonomous Robots
Published in: Autonomous Robots 4/2016

01-04-2016

Assistance networks for dynamic multirobot tasks

Authors: Haluk Bayram, H. Iṣıl Bozma

Published in: Autonomous Robots | Issue 4/2016

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper, we consider dynamic multirobot tasks that can be done by any of the robots, but only with the assistance of any other robot. We propose a novel approach based on the concept of ‘assistance networks’ with two complementary aspects, namely assistant finding and network topology update. Each robot, encountering a new task, seeks an assisting robot among its immediate neighbors in the assistance network in a decentralized manner. The network topology is defined based on pairwise stability via payoff functions that consider general task-related guidelines. As such, the number of potential assisting robots can be ensured a priori depending on tasks’ requirements. As robots move around, the topology is updated via pairwise games. If the games are conducted by a network coordinator, each game is shown to result in a pairwise stable network. A series of simulation and experimental results in a variety of different scenarios demonstrate that the robots are able to get assistance or give assistance flexibly.
previous article Punctual versus continuous auction coordination for multi-robot and multi-task topological navigation
next article Aerial robotic contact-based inspection: planning and control

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Footnotes
1
While we consider tasks that can be completed with assistance from one robot, our approach can be extended to multi-robot assistance problems.
 
2
For the interested reader, the detailed algorithm of task automaton is given in Appendix 2.
 
3
For notational brevity, the time argument will be omitted whenever it is clear from the context.
 
4
Although not investigated in this paper, the unit cost c may become varying for each robot.
 
5
The details of the experimental setup are described in Appendix 1.
 
Literature
Al-Yafi, K. & Lee, H. (2009). Centralized versus market-based approaches to mobile task allocation problem: State-of-the-art. In European and mediterranean conference on information systems.
Bayram, H. & Bozma, H. I. (2013). Multirobot communication network topology via centralized pairwise games. In: IEEE international conference on robotics and automation (pp. 2506–2511). IEEE.
Bayram, H., & Bozma, H. I. (2014). Decentralized network topologies in multirobot systems. Advanced Robotics, 28(14), 967–982.
Bertsekas, D., & Tsitsiklis, J. (1991). Some aspects of parallel and distributed iterative algorithms—A survey. Automatica, 27(1), 3–21.CrossRefMathSciNetMATH
Billand, P., Bravard, C., & Sarangi, S. (2013). A note on local spillovers, convexity, and the strategic substitutes property in networks. Theor Decis, 75(2), 293–304.CrossRefMathSciNetMATH
Bloch, B., & Jackson, M. O. (2006). Definitions of equilibrium in network formation games. International Journal of Game Theory, 34(3), 305–318.CrossRefMathSciNetMATH
Botelho, S. & Alami, R. (1999). M+: A scheme for multi-robot cooperation through negotiated task allocation and achievement. In: IEEE international conference on robotics and automation (Vol. 2, pp. 1234–1239).
Brunet, L., Choi, H.L., & How, J.P. (2008). Consensus-based auction approaches for decentralized task assignment. In AIAA guidance, navigation, and control conference (GNC).
Cai, Y. & Yang, S.X. (2012). A survey on multi-robot systems. In World automation congress (WAC) (pp. 1–6).
Calvo-Armengol, A., & Ilkilic, R. (2009). Pairwise-stability and Nash equilibria in Network Formation. International Journal of Game Theory, 38, 51–79.CrossRefMathSciNetMATH
Cao, Y., Fukunaga, A., & Kahng, A. (1997). Cooperative mobile robotics: Antecedents and directions. Autonomous Robots, 4(1), 7–27.
Chaimowicz, L., Campos, M. F. M., & Kumar, V. (2002). Dynamic role assignment for cooperative robots. IEEE International Conference on Robotics and Automation, 1, 293–298.
Chaudhry, S., Xu, X., & Amato, N. (2008). Nearest neighbor search methods. Tech. rep., Department of Computer Science, Texas A&M University.
Chen, J., & Sun, D. (2011). Resource constrained multirobot task allocation based on leader-follower coalition methodology. The International Journal of Robotics Research, 30(12), 1423–1434.CrossRef
Dang, V.D., & Jennings, N.R. (2006). Coalition structure generation in task-based settings. In 17th European conference on artificial intelligence (pp. 210–214).
Dankers, A., Barnes, N., & Zelinsky, A. (2002). Line-of-sight constrained exploration for reactive multiagent robotic teams. In 7th international workshop on advanced motion control, Maribor, Slovenia (pp. 455–461).
de Vries, S. & Vohra, R. V. (2003). Combinatorial auctions: A survey. INFORMS J Comput, 15(3), 284–309.
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.CrossRef
Fousse, L., Hanrot, G., Lefèvre, V., Pélissier, P., & Zimmermann, P. (2007). MPFR: A multiple-precision binary floating-point library with correct rounding. ACM Trans Math Softw, 33(2).
Gerkey, B., & Mataric, M. (2002). Sold!: Auction methods for multirobot coordination. IEEE Transactoions on Robotics and Automation, 18(5), 758–768.CrossRef
Gerkey, B. P., & Mataric, M. J. (2004). A formal analysis and taxonomy of task allocation in multi-robot Ssystems. The International Journal of Robotics Research, 23(9), 939–954.CrossRef
Giordani, S., Lujak, M., & Martinelli, F. (2010). A distributed algorithm for the multi-robot task allocation problem. In Garca-Pedrajas, N., Herrera, F., Fyfe, C., Bentez, J., Ali, M. (Eds.) Trends in applied intelligent systems. Lecture notes computer science (Vol. 6096, pp. 721–730). Heidelberg: Springer.
Gottlob, G., Greco, G., & Scarcello, F. (2003). Pure Nash equilibria: Hard and easy games. Journal of Artificial Intelligence Research, 24, 215–230.
Hoeing, M., Dasgupta, P., Petrov, P., & O’Hara, S. (2007). Auction-based multi-robot task allocation in comstar. In: Proceedings of the 6th international joint conference on autonomous agents and multiagent systems (pp. 280:1–280:8). ACM, New York, NY, USA, AAMAS ’07.
Jackson, M. O. (2003). A survey of models of network formation: Stability and efficiency. Tech. Rep. 0303011, EconWPA.
Jackson, M. O. (2010). Social and economic networks. Princeton, NJ: Princeton University Press.MATH
Jackson, M. O., & Watts, A. (2001). The existence of pairwise stable networks. Seoul Journal of Economics, 14(3), 299–321.
Jiang, Y., Zhou, Y., & Wang, W. (2013). Task allocation for undependable multiagent systems in social networks. IEEE Transactions on Parallel and Distributed Systems, 24(8), 1671–1681.
Karagöz, C. S., Bozma, H. I., & Koditschek, D. E. (2014). Coordinated navigation of multiple independent disk-shaped robots. IEEE Transactions on Robotics, 30(6), 1289–1304.CrossRef
Karaoguz, H., Bayram, H., & Bozma, H. I. (2013). Communication integrated control architecture in multirobot systems. In: ICRA workshop on “Towards fully decentralized multi-robot systems: Hardware, Software and Integration”.
Koenig, S., Tovey, C., Lagoudakis, M., Markakis, V., Kempe, D., Keskinocak, P., Kleywegt, A., Meyerson, A., & Jain, S. (2006). The power of sequential single-item auctions for agent coordination. In Proceedings of the 21st national conference on artificial intelligence—-Volume 2, AAAI (pp. 1625–1629).
Koes, M., Nourbakhsh, I., & Sycara, K. (2005). Heterogeneous multirobot coordination with spatial and temporal constraints. In Proceedings of the 20th national conference on artificial intelligence—Volume 3, AAAI’05 (pp. 1292–1297).
Korsah, G. A., Stentz, A., & Dias, M. B. (2013). A comprehensive taxonomy for multi-robot task allocation. The International Journal of Robotics Research, 32(12), 1495–1512.CrossRef
Lau, H.C., & Zhang, L. (2003). Task allocation via multi-agent coalition formation: Taxonomy, algorithms and complexity. In 15th IEEE international conference on tools with artificial intelligence (pp. 346–350).
Lerman, K., Jones, C., Galstyan, A., & Mataric, M. J. (2006). Analysis of dynamic task allocation in multi-robot systems. The International Journal of Robotics Research, 25(3), 225–241.CrossRef
Liu, C. & Kroll, A. (2012). A centralized multi-robot task allocation for industrial plant inspection by using a* and genetic algorithms. In L. Rutkowski, M. Korytkowski, R. Scherer, R. Tadeusiewicz, L. Zadeh, & J. Zurada (Eds.), Artificial intelligence and soft computing. Lecture Notes in Computer Science (Vol. 7268, pp. 466–474). Berlin Heidelberg: Springer.
McMillen, C., Rybski, P., & Velosa, M. (2005). Levels of multi-robot coordination for dynamic environments. In Parker, L. E., Schultz, A. C., Schneider, F. E. (Eds) Multi-robot systems: From swarms to intelligent automata (Vol. III, pp. 53–65). Berlin: Springer.
Murray, J. & Stolzenburg, F. (2005). Hybrid state machines with timed synchronization for multi-robot system specification. In Portuguese conference on artificial intelligence (pp. 236–241).
Parker, L. (1998). Alliance: An architecture for fault tolerant multirobot cooperation. IEEE Transactions on Robotics and Automation, 14(2), 220–240.CrossRef
Parker, L., & Tang, F. (2006). Building multirobot coalitions through automated task solution synthesis. Proceedings of the IEEE, 94(7), 1289–1305.CrossRef
Ramchurn, S. D., Polukarov, M., Farinelli, A., Jennings, N., & Trong, C. (2010). Coalition formation with spatial and temporal constraints. In International joint conference on autonomous agents and multi-agent systems (AAMAS 2010) (pp. 1181–1188).
Rekleitis, I., Lee-Shue, V., New, A. P., & Choset, H. (2004). Limited communication, multi-robot team based coverage. In IEEE international conference on robotics and automation (pp. 3462–3468).
Sandholm, T., Larson, K., Andersson, M., Shehory, O., & Tohm, F. (1999). Coalition structure generation with worst case guarantees. Artificial Intelligence, 111(12), 209–238.CrossRefMathSciNetMATH
Schwager, M., Michael, N., Kumar, V., & Rus, D. (2011). Time scales and stability in networked multi-robot systems. In IEEE international conference on robotics and automation (pp. 3855–3862).
Service, T., & Adams, J. (2011). Coalition formation for task allocation: Theory and algorithms. Autonomous Agents and Multi-Agent Systems, 22(2), 225–248.CrossRef
Smith, R. G. (1980). The contract net protocol: High-level communication and control in a distributed problem solver. IEEE Transactions on Computers, C–29(12), 1104–1113.CrossRef
Smith, S.L., & Bullo, F. (2009). The dynamic team forming problem: Throughput and delay for unbiased policies. In Systems & control letters, 58(10), 709–715.
Tang, F. & Parker, L. (2005). Asymtre: Automated synthesis of multi-robot task solutions through software reconfiguration. In Proceedings of the 2005 IEEE international conference on robotics and automation (pp. 1501–1508).
Vig, L., & Adams, J. A. (2006). Multi-robot coalition formation. IEEE Transactions on Robotics, 22(4), 637–649.CrossRef
Wawerla, J., & Vaughan, R. (2010). A fast and frugal method for team-task allocation in a multi-robot transportation system. In IEEE international conference on robotics and automation (pp. 1432–1437).
Weerdt, M., Zhang, Y., & Klos, T. (2012). Multiagent task allocation in social networks. Autonomous Agents and Multi-Agent Systems, 25(1), 46–86.CrossRef
Yan, Z., Jouandeau, N., & Cherif, A. A. (2012). On the problem of task planning in multi-robot systems. In 9th international conference on informatics in control, automation and robotics (pp. 423–426).
Ye, D., Zhang, M., & Sutanto, D. (2011). DGF: Decentralized group formation for task allocation in complex adaptive systems. In Q. Bai & N. Fukuta (Eds.), Advances in practical multi-agent systems, studies in computational intelligence (Vol. 325, pp. 3–19). Berlin, Heidelberg: Springer.
Zhang, Y., & Parker, L. (2013a). Considering inter-task resource constraints in task allocation. Autonomous Agents and Multi-Agent Systems, 26(3), 389–419.CrossRef
Zhang, Y., & Parker, L. (2013b). Iq-asymtre: Forming executable coalitions for tightly coupled multirobot tasks. IEEE Transactions on Robotics, 29(2), 400–416.CrossRef
Zlot, R., & Stentz, A. (2006). Market-based multirobot coordination for complex tasks. Int J Robot Res, 25(1), 73–101.CrossRef
Metadata
Title
Assistance networks for dynamic multirobot tasks
Authors
Haluk Bayram
H. Iṣıl Bozma
Publication date
01-04-2016
Publisher
Springer US
Published in
Autonomous Robots / Issue 4/2016
Print ISSN: 0929-5593
Electronic ISSN: 1573-7527
DOI
https://doi.org/10.1007/s10514-015-9484-6

Other articles of this Issue 4/2016

Autonomous Robots 4/2016 Go to the issue

OriginalPaper

Incremental statistical learning for integrating motion primitives and language in humanoid robots

OriginalPaper

Punctual versus continuous auction coordination for multi-robot and multi-task topological navigation

OriginalPaper

A variant of cyclic pursuit for target tracking applications: theory and implementation

OriginalPaper

Implementation of a Gaussian process-based machine learning grasp predictor

OriginalPaper

Multi-robot target detection and tracking: taxonomy and survey

OriginalPaper

Aerial robotic contact-based inspection: planning and control