Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Autonomous Robots
Erschienen in: Autonomous Robots 5/2016

01.06.2016

Cooperative multi-robot patrol with Bayesian learning

verfasst von: David Portugal, Rui P. Rocha

Erschienen in: Autonomous Robots | Ausgabe 5/2016

Einloggen

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

search-config
loading …

Abstract

Patrolling indoor infrastructures with a team of cooperative mobile robots is a challenging task, which requires effective multi-agent coordination. Deterministic patrol circuits for multiple mobile robots have become popular due to their exceeding performance. However their predefined nature does not allow the system to react to changes in the system’s conditions or adapt to unexpected situations such as robot failures, thus requiring recovery behaviors in such cases. In this article, a probabilistic multi-robot patrolling strategy is proposed. A team of concurrent learning agents adapt their moves to the state of the system at the time, using Bayesian decision rules and distributed intelligence. When patrolling a given site, each agent evaluates the context and adopts a reward-based learning technique that influences future moves. Extensive results obtained in simulation and real world experiments in a large indoor environment show the potential of the approach, presenting superior results to several state of the art strategies.
Vorheriger Artikel A modular approach to learning manipulation strategies from human demonstration

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 "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
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
3
The degree (or valency) of a vertex of a graph \(deg(v_i)\), is the number of edges incident to the vertex.
 
4
Entropy is a general measure for the uncertainty of a belief. When applied to a discrete random variable, it evaluates to its shortest description, being as high as the variable’s uncertainty (Rocha et al. 2005).
 
5
The source code of the patrolling approaches tested are available at: https://​github.​com/​davidbsp/​patrolling_​sim.
 
7
A video of an experiment with 6 robots running CBLS is available at: https://​sites.​google.​com/​site/​davidbsp2014/​videos/​auro.
 
Literatur
Agmon, N., Fok, C. L., Emaliach, Y., Stone, P., Julien, C., & Vishwanath, S. (2012). On coordination in practical multi-robot patrol. In Proceedings of the IEEE international conference on robotics and automation (ICRA 2012) (pp. 650–656), May 14–18. Saint Paul, MN.
Agmon, N., Urieli, D., & Stone, P. (2011). Multiagent patrol generalized to complex environmental conditions. In Proceedings of the 25th conference on artificial intelligence (AAAI 2011), San Francisco, CA, August 7–11.
Agmon, N., Kaminka, G. A., & Kraus, S. (2011). Multi-robot adversarial patrolling: Facing a full-knowledge opponent. Journal of Artificial Intelligence Research, 42, 887–916.MathSciNetMATH
Aguirre, O., & Taboada, H. (2012). An evolutionary game theory approach for intelligent patrolling. In Procedia computer science (Vol. 12, Part II, pp. 140–145). Amsterdam: Elsevier.
Ahmadi, M., & Stone, P. (2006). A multi-robot system for continuous area sweeping tasks. In Proceedings of the international conference on robotics and automation (ICRA 2006). Orlando, FL, May 15–19.
Almeida, A., Ramalho, G., Santana, H., Tedesco, P., Menezes, T., Corruble, V., & Chaveleyre, Y. (2004). Recent advances on multi-agent patrolling. In Advances in artificial intelligence—SBIA 2004. Lecture Notes in Computer Science (Vol. 3171, pp 474-483). Berlin: Springer.
Applegate, D., Cook, W., & Rohe, A. (2003). Chained Lin-Kernighan for large traveling salesman problems. INFORMS Journal on Computing, 15, 82–92.
Baglietto, M., Cannata, G., Capezio, F., & Sgorbissa, A. (2009). Multi-robot uniform frequency coverage of significant locations in the environment. In Distributed autonomous robotic systems (Vol. 8, pp. 3–14). Berlin: Springer.
Basilico, N., Gatti, N., Rossi, T., Ceppi, S., & Amigoni, F. (2009). Extending algorithms for mobile robot patrolling in the presence of adversaries to more realistic settings. In Proceedings of the 2009 IEEE/WIC/ACM international conference on intelligent agent technology (IAT’09) (pp. 557–564). Milan.
Cannata, G., & Sgorbissa, A. (2011). A minimalist algorithm for multirobot continuous coverage. IEEE Transactions on Robotics, 27(2), 297–312.CrossRef
Chevaleyre, Y. (2004). Theoretical analysis of the multi-agent patrolling problem. In Proceedings of the 2004 international conference on agent intelligent technologies (IAT’04), (pp. 30–308). Beijing, September 20–24.
Elmaliach, Y., Shiloni, A., & Kaminka, G. A. (2008). A realistic model of frequency-based multi-robot polyline patrolling. In Proceedings of the 7th international joint conference on autonomous agents and multiagent systems (AAMAS 2008), (Vol. 1, pp. 63–70).
Fabrizi, E., & Saffiotti, A. (2000). Extracting topology-based maps from gridmaps. In Proceedings of the 2000 IEEE international conference on robotics and automation (ICRA’2000) (pp. 2972–2978). San Francisco, CA, April 2000.
Fazli, P., Davoodi, A., & Mackworth, A. K. (2013). Multi-robot repeated area coverage. Autonomous Robots, 34(4), 251–276. Springer Science.CrossRef
Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(2), 298–305.MathSciNetMATH
Gabriely, Y., & Rimon, E. (2001). Spanning-tree based coverage of continuous areas by a mobile robot. Annals of mathematics and artificial intelligence (Vol. 31, pp. 77–98). Hingham, MA: Kluwer Academic Publishers.
Iocchi, L., Marchetti, L., & Nardi, D. (2011). Multi-robot patrolling with coordinated behaviours in realistic environments. In Proceedings of the international conference on intelligent robots and systems (IROS’2011) (pp. 2796–2801).
Ishiwaka, Y., Sato, T., & Kakazu, Y. (2003). An approach to the pursuit problem on a heterogeneous multiagent system using reinforcement learning. Robotics and Autonomous Systems (RAS), 43(4), 245–256. Elsevier.CrossRef
Jansen, M., & Sturtevant, N. (2008). Direction maps for cooperative pathfinding. In Proceedings of the 4th artificial intelligence and interactive digital entertainment conference (AAAIDE’08). Stanford, CA, October 22–24.
Jansen, F., & Nielsen, T. (2007). Bayesian networks and decision graphs (2nd ed.). Berlin: Springer.CrossRef
Keskin, B. B., Li, S., Steil, D., & Spiller, S. (2012). Analysis of an integrated maximum covering and patrol routing problem. Transportation Research Part E, 48, 215–232. Elsevier.CrossRef
Lauri, F., & Koukam, A. (2014). Robustness analysis of multi-agent patrolling strategies using reinforcement learning. In Proceedings of the international conference on swarm intelligence based optimization (ICSIBO 2014), Mulhouse, May 13–14.
Marier, J., Besse, C., & Chaib-draa, B. (2010). Solving the continuous time multiagent patrol problem. In Proceedings of the 2010 IEEE international conference on robotics and automation (ICRA 2010), Anchorage, AK.
Marino, A., Antonelli, G., Aguiar, A. P., & Pascoal, A. (2012). A new approach to multi-robot harbour patrolling: Theory and experiments. In Proceedings of the 2012 IEEE/RSJ international conference on intelligent robots and systems (IROS 2012). Vilamoura, Portugal, October 7–12.
Marino, A., Parker, L. E., Antonelli, G., & Caccavale, F. (2013). A decentralized architecture for multi-robot systems based on the null-space-behavioral control with application to multi-robot border patrolling. Journal of Intelligent and Robotic Systems, 71, 423–444.CrossRef
Murphy, R. (2004). Human–robot interaction in rescue robotics. IEEE Transactions on Systems, Man and Cybernetics Part C, 34(2), 138–153.CrossRef
Panait, L., & Luke, S. (2005). Cooperative multi-agent learning: The state of the art. Journal of Autonomous Agents and Multi-Agent Systems, 11(3), 387–434.CrossRef
Parker, L. E. (2008). Distributed intelligence: Overview of the field and its application in multi-robot systems. Journal of Physical Agents, 2(2), 5–14. Special issue on Multi-robot systems.
Pasqualetti, F., Franchi, A., & Bullo, F. (2012). On cooperative patrolling: Optimal trajectories, complexity analysis, and approximation algorithms. IEEE Transactions on Robotics, 28(3), 592–606.CrossRef
Pippin, C., Christensen, H., & Weiss, L. (2013). Performance based task assignment in multi-robot patrolling. In Proceedings of the 2013 ACM symposium on applied computing (SAC ’13) (pp. 70–76). Coimbra, March 18–22.
Portugal, D., & Rocha, R. P. (2013). Retrieving topological information for mobile robots provided with grid maps. In Agents and artificial intelligence. Communications in Computer and Information Science (CCIS) series, (Vol. 358, pp. 204-217). Berlin: Springer.
Portugal, D., Couceiro, M. S., & Rocha, R. P. (2013). Applying bayesian learning to multi-robot patrol. In Proceedings of the 2013 international symposium on safety, security and rescue robotics (SSRR 2013), Linköping, Oct 21–26.
Portugal, D., Couceiro, M., & Rocha, R. P. (2013). Concurrent Bayesian learners for multi-robot patrolling missions. In Proceedings of the 2013 IEEE international conference on robotics and automation (ICRA 2013), Workshop on Towards Fully Decentralized Multi-Robot Systems: Hardware, Software and Integration, Karlsruhe, May 6–10.
Portugal, D., Pippin, C., Rocha, R. P., & Christensen, H. (2014). Finding optimal routes for multi-robot patrolling in generic graphs. In Proceedings of the 2014 IEEE/RSJ international conference on intelligent robots and systems (IROS 2014). Chicago, Sep. 14–18.
Portugal, D., & Rocha, R. P. (2013). Multi-robot patrolling algorithms: examining performance and scalability. Advanced Robotics Journal, 27(5), 325–336.CrossRef
Portugal, D., & Rocha, R. P. (2013). Distributed multi-robot patrol: A scalable and fault-tolerant framework. Robotics and Autonomous Systems (RAS), 61(12), 1572–1587.CrossRef
Poulet, C., Corruble, V., & Seghrouchini, A. (2012). Working as a team: Using social criteria in the timed patrolling problem. In Proceedings of the international conference on tools with artificial intelligence (ICTAI’2012). Athens, GR, Nov. 7–9.
Quigley, M., Gerkey, B., Conley, K., Faust, J., Foote, T., Leibs, J., Berger, E., Wheeler, R., & Ng, A. (2009). ROS: an open-source robot operating system. In Proceedings of the IEEE international conference on robotics and automation (ICRA’2009), Workshop On Open Source Software, Kobe, May 12–17.
Robotics, Activ Media. (2006). Pioneer 3 operations manual, version 3. : Mobile Robots Inc.
Rocha, R., Dias, J., & Carvalho, A. (2005). Cooperative multi-robot systems: A study of vision-based 3-D mapping using information theory. Robotics and Autonomous Systems (RAS), 53(3–4), 282–311. Elsevier.CrossRef
Ruan, S., Meirina, C., Yu, F., Pattipati, K. R., & Popp, R. L. (2005). Patrolling in a stochastic environment. In Proceedings of the 10th international command and control research and technology symposium, McLean, VA, June 13–16.
Sak, T., Wainer, J., & Goldenstein, S. (2008). Probabilistic Multiagent Patrolling. In Advances in Artificial Intelligence, SBIA 2008. Lecture Notes in Computer Science, (Vol. 5249, pp. 124–133). Berlin: Springer.
Sampaio, P., Ramalho, G., & Tedesco, P. (2010). The gravitational strategy for the timed patrolling. In Proceedings of the IEEE international conference on tools with artificial intelligence (ICTAI’10) (pp. 113-120). Arras, France, Oct. 27–29.
Santana, H., Ramalho, G., Corruble, V., & Ratitch, B. (2004). Multi-agent patrolling with reinforcement learning. In Proceedings of the third international joint conference on autonomous agents and multiagent systems (Vol. 3, pp. 1122–1129), New York, NY.
Sempé, F., & Drogoul, A. (2003). Adaptive patrol for a group of robots. In Proceedings of the international conference on intelligent robots and systems (IROS 2003). Las Vegas.
Smith, S., & Rus, D. (December 2010). Multi-robot monitoring in dynamic environments with guaranteed currency of observations. In Proceedings of the IEEE conference on decision and control (pp. 514–521). Atlanta, GA.
Stone, P., & Veloso, M. (2000). Multiagent systems: A survey from a machine learning perspective. Autonomous Robots, 8(3), 345–383.CrossRef
Stranders, R., de Cote, E. M., Rogers, A., & Jennings, N. R. (2012). Near-optimal continuous patrolling with teams of mobile information gathering agents. In Artificial intelligence. Amsterdam: Elsevier.
Vaughan, R. (2008). Massively multi-robot simulation in stage. Journal of Swarm Intelligence, 2(2–4), 189–208.CrossRef
Yanovski, V., Wagner, I. A., & Bruckstein, A. M. (2003). A distributed ant algorithm for efficiently patrolling a network. Algorithmica, 37, 165–186.MathSciNetCrossRefMATH
Metadaten
Titel
Cooperative multi-robot patrol with Bayesian learning
verfasst von
David Portugal
Rui P. Rocha
Publikationsdatum
01.06.2016
Verlag
Springer US
Erschienen in
Autonomous Robots / Ausgabe 5/2016
Print ISSN: 0929-5593
Elektronische ISSN: 1573-7527
DOI
https://doi.org/10.1007/s10514-015-9503-7

Weitere Artikel der Ausgabe 5/2016

Autonomous Robots 5/2016 Zur Ausgabe

OriginalPaper

Humanoid odometric localization integrating kinematic, inertial and visual information

OriginalPaper

Simultaneous localization and mapping for aerial vehicles: a 3-D sensor-based GAS filter

OriginalPaper

Design and integration of a spatio-temporal memory with emotional influences to categorize and recall the experiences of an autonomous mobile robot

OriginalPaper

Unsupervised segmentation of unknown objects in complex environments

OriginalPaper

A modular approach to learning manipulation strategies from human demonstration

OriginalPaper

A method for ego-motion estimation in micro-hovering platforms flying in very cluttered environments

Neuer Inhalt

    Bildnachweise