nach oben

Swarm Intelligence

Erschienen in:

28.04.2016

Modeling multi-robot task allocation with limited information as global game

verfasst von: Anshul Kanakia, Behrouz Touri, Nikolaus Correll

Erschienen in: Swarm Intelligence | Ausgabe 2/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Continuous response threshold functions to coordinate collaborative tasks in multi-agent systems are commonly employed models in a number of fields including ethology, economics, and swarm robotics. Although empirical evidence exists for the response threshold model in predicting and matching swarm behavior for social insects, there has been no formal argument as to why natural swarms use this approach and why it should be used for engineering artificial ones. In this paper, we show, by formulating task allocation as a global game, that continuous response threshold functions used for communication-free task assignment result in system level Bayesian Nash equilibria. Building up on these results, we show that individual agents not only do not need to communicate with each other, but also do not need to model each other’s behavior, which makes this coordination mechanism accessible to very simple agents, suggesting a reason for their prevalence in nature and motivating their use in an engineering context.

Vorheriger Artikel Medoid-based clustering using ant colony optimization

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

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!

Jetzt informieren

Amstutz, P., Correll, N., & Martinoli, A. (2008). Distributed boundary coverage with a team of networked miniature robots using a robust market-based algorithm. Annals of Mathematics and Artificial Intelligence, 52(2–4), 307–333.MathSciNetCrossRefMATH

Arslan, G., Marden, J. R., & Shamma, J. S. (2007). Autonomous vehicle-target assignment: A game-theoretical formulation. Journal of Dynamic Systems, Measurement, and Control, 129(5), 584–596.CrossRef

Berman, S., Halász, Á., Hsieh, M. A., & Kumar, V. (2009). Optimized stochastic policies for task allocation in swarms of robots. IEEE Transactions on Robotics, 25(4), 927–937.CrossRef

Bonabeau, E., Sobkowski, A., Theraulaz, G., & Deneubourg, J.-L. (1997). Adaptive task allocation inspired by a model of division of labor in social insects. In Biocomputing and emergent computation: Proceedings of BCEC97 (pp. 36–45). World Scientific Press.

Bonabeau, E., Theraulaz, G., & Deneubourg, J.-L. (1996). Quantitative study of the fixed threshold model for the regulation of division of labour in insect societies. Proceedings of the Royal Society of London Series B: Biological Sciences, 263(1376), 1565–1569.CrossRef

Bonabeau, E., Theraulaz, G., & Deneubourg, J.-L. (1998). Fixed response thresholds and the regulation of division of labor in insect societies. Bulletin of Mathematical Biology, 60(4), 753–807.CrossRefMATH

Border, K. C. (1990). Fixed point theorems with applications to economics and game theory. Cambridge: Cambridge Books.MATH

Brambilla, M., Ferrante, E., Birattari, M., & Dorigo, M. (2013). Swarm robotics: A review from the swarm engineering perspective. Swarm Intelligence, 7(1), 1–41.CrossRef

Camilli, G. (1994). Teachers corner: Origin of the scaling constant d = 1.7 in item response theory. Journal of Educational and Behavioral Statistics, 19(3), 293–295.MathSciNet

Carlsson, H., & Van Damme, E. (1993). Global games and equilibrium selection. Econometrica: Journal of the Econometric Society, 61(5), 989–1018.MathSciNetCrossRefMATH

Castello, E., Yamamoto, T., Dalla Libera, F., Liu, W., Winfield, A. F., Nakamura, Y., et al. (2016). Adaptive foraging for simulated and real robotic swarms: The dynamical response threshold approach. Swarm Intelligence, 10(1), 1–31.CrossRef

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

Choi, H.-L., Brunet, L., & How, J. P. (2009). Consensus-based decentralized auctions for robust task allocation. IEEE Transactions on Robotics, 25(4), 912–926.CrossRef

Conradt, L., & Roper, T. J. (2003). Group decision-making in animals. Nature, 421(6919), 155–158.CrossRef

Conradt, L., & Roper, T. J. (2005). Consensus decision making in animals. Trends in Ecology and Evolution, 20(8), 449–456.CrossRef

Correll, N. (2007). Coordination schemes for distributed boundary coverage with a swarm of miniature robots: Synthesis, analysis and experimental validation. PhD thesis, Ecole Polytechnique Fédérale, Lausanne, CH.

Correll, N. (2008). Parameter estimation and optimal control of swarm-robotic systems: A case study in distributed task allocation. In IEEE international conference on robotics and automation (ICRA) (pp. 3302–3307). IEEE.

Dantu, K., Berman, S., Kate, B., & Nagpal, R. (2012). A comparison of deterministic and stochastic approaches for allocating spatially dependent tasks in micro-aerial vehicle collectives. In IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 793–800). IEEE.

Durrett, R. (2010). Probability: Theory and examples (4th ed.). Cambridge: Cambridge University Press.CrossRefMATH

Fudenberg, D. (1998). The theory of learning in games (Vol. 2). Cambridge, MA: MIT Press.MATH

Gerkey, B. P. (2004). A formal analysis and taxonomy of task allocation in multi-robot systems. The International Journal of Robotics Research, 23(9), 939–954.CrossRef

Gerkey, B. P., & Mataric, M. J. (2003). Multi-robot task allocation: Analyzing the complexity and optimality of key architectures. In IEEE international conference on robotics and automation (Vol. 3, pp. 3862–3868). IEEE.

Gordon, D. M. (1996). The organization of work in social insect colonies. Nature, 380(6570), 121–124.CrossRef

Grenager, T., Powers, R., & Shoham, Y. (2002). Dispersion games: General definitions and some specific learning results. In AAAI innovative applications of artificial intelligence conference (IAAI) (pp. 398–403). AAAI.

Harsanyi, J. C. (2004). Games with incomplete information played by Bayesian players, I-III Part I. The basic model. Management Science, 50(12–supplement), 1804–1817.MathSciNetCrossRef

Kalra, N., & Martinoli, A. (2006). Comparative study of market-based and threshold-based task allocation. In Distributed autonomous robotic systems 7 (pp. 91–101). Springer.

Kanakia, A., & Correll, N. (2016). A response threshold sigmoid function model for swarm robot collaboration. Distributed and autonomous robotic systems (DARS), volume 112 of the series springer tracts in advanced robotics (pp. 193–206). Heidelberg: Springer.CrossRef

Krieger, M. J., Billeter, J.-B., & Keller, L. (2000). Ant-like task allocation and recruitment in cooperative robots. Nature, 406(6799), 992–995.CrossRef

Kube, C. R., & Bonabeau, E. (2000). Cooperative transport by ants and robots. Robotics and Autonomous Systems, 30(1), 85–101.CrossRef

Lerman, K., Galstyan, A., Martinoli, A., & Ijspeert, A. (2001). A macroscopic analytical model of collaboration in distributed robotic systems. Artificial Life, 7, 375–393.CrossRef

Lerman, K., Jones, C., Galstyan, A., & Matarić, M. J. (2006). Analysis of dynamic task allocation in multi-robot systems. The International Journal of Robotics Research, 25(3), 225–241.CrossRef

Liu, W., & Winfield, A. (2010). Modelling and optimisation of adaptive foraging in swarm robotic systems. The International Journal of Robotics Research, 29(14), 1743–1760.CrossRef

Marden, J. R., Arslan, G., & Shamma, J. S. (2009). Joint strategy fictitious play with inertia for potential games. IEEE Transactions on Automatic Control, 54(2), 208–220.MathSciNetCrossRef

Martinoli, A., Easton, K., & Agassounon, W. (2004). Modeling swarm robotic systems: A case study in collaborative distributed manipulation. The International Journal of Robotics Research, 23(4–5), 415–436.CrossRef

Martinoli, A., Ijspeert, A. J., & Mondada, F. (1999). Understanding collective aggregation mechanisms: From probabilistic modelling to experiments with real robots. Robotics and Autonomous Systems, 29(1), 51–63.CrossRef

Matarić, M. J., Sukhatme, G. S., & Astergaard, E. H. (2003). Multi-robot task allocation in uncertain environments. Autonomous Robots, 14(2–3), 255–263.CrossRefMATH

Mather, T. W., Hsieh, M. A., & Frazzoli, E. (2010). Towards dynamic team formation for robot ensembles. In IEEE international conference on robotics and automation (ICRA) (pp. 4970–4975). IEEE.

McEvoy, M., & Correll, N. (2015). Materials that couple sensing, actuation, computation, and communication. Science, 347(6228), 1261689.CrossRef

Morris, S. E., & Shin, H. S. (2000). Global games: Theory and applications. New Haven, CT: Cowles Foundation for Research in Economics.

Nisan, N., Roughgarden, T., Tardos, E., & Vazirani, V. V. (2007). Algorithmic game theory (Vol. 1). Cambridge: Cambridge University Press.CrossRefMATH

Parsons, S., & Wooldridge, M. (2002). Game theory and decision theory in multi-agent systems. Autonomous Agents and Multi-Agent Systems, 5(3), 243–254.MathSciNetCrossRefMATH

Pini, G., Gagliolo, M., Brutschy, A., Dorigo, M., & Birattari, M. (2013). Task partitioning in a robot swarm: A study on the effect of communication. Swarm Intelligence, 7(2–3), 173–199.CrossRef

Pynadath, D. V., & Tambe, M. (2002). Multiagent teamwork: Analyzing the optimality and complexity of key theories and models. In Proceedings of the first international joint conference on autonomous agents and multiagent systems (AAMAS): Part 2 (pp. 873–880). ACM.

Raafat, R. M., Chater, N., & Frith, C. (2009). Herding in humans. Trends in Cognitive Sciences, 13(10), 420–428.CrossRef

Robinson, G. E. (1987). Modulation of alarm pheromone perception in the honey bee: Evidence for division of labor based on hormonally regulated response thresholds. Journal of Comparative Physiology A, 160(5), 613–619.CrossRef

Seeley, T. D. (1989). Social foraging in honey bees: How nectar foragers assess their colony’s nutritional status. Behavioral Ecology and Sociobiology, 24(3), 181–199.CrossRef

Shehory, O., & Kraus, S. (1998). Methods for task allocation via agent coalition formation. Artificial Intelligence, 101(1), 165–200.MathSciNetCrossRefMATH

Suzuki, S., Adachi, R., Dunne, S., Bossaerts, P., & O’Doherty, J. P. (2015). Neural mechanisms underlying human consensus decision-making. Neuron, 86(2), 591–602.CrossRef

Theraulaz, G., Bonabeau, E., & Deneubourg, J.-L. (1998). Response threshold reinforcements and division of labour in insect societies. Proceedings of the Royal Society of London Series B: Biological Sciences, 265(1393), 327–332.CrossRefMATH

Tumer, K., & Wolpert, D. (2004). A survey of collectives. In Collectives and the design of complex systems (pp. 1–42). Springer.

Vig, L., & Adams, J. A. (2007). Coalition formation: From software agents to robots. Journal of Intelligent and Robotic Systems, 50(1), 85–118.CrossRef

Yoshida, W., Seymour, B., Friston, K. J., & Dolan, R. J. (2010). Neural mechanisms of belief inference during cooperative games. Journal of Neuroscience, 30(32), 10744–10751.CrossRef

Titel: Modeling multi-robot task allocation with limited information as global game
verfasst von: Anshul Kanakia
Behrouz Touri
Nikolaus Correll
Publikationsdatum: 28.04.2016
Verlag: Springer US
Erschienen in: Swarm Intelligence / Ausgabe 2/2016
Print ISSN: 1935-3812
Elektronische ISSN: 1935-3820
DOI: https://doi.org/10.1007/s11721-016-0123-4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"