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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Autonomous Robots
Erschienen in: Autonomous Robots 7/2019

17.01.2019

3D multi-robot patrolling with a two-level coordination strategy

verfasst von: Luigi Freda, Mario Gianni, Fiora Pirri, Abel Gawel, Renaud Dubé, Roland Siegwart, Cesar Cadena

Erschienen in: Autonomous Robots | Ausgabe 7/2019

Einloggen

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

search-config
loading …

Abstract

Teams of UGVs patrolling harsh and complex 3D environments can experience interference and spatial conflicts with one another. Neglecting the occurrence of these events crucially hinders both soundness and reliability of a patrolling process. This work presents a distributed multi-robot patrolling technique, which uses a two-level coordination strategy to minimize and explicitly manage the occurrence of conflicts and interference. The first level guides the agents to single out exclusive target nodes on a topological map. This target selection relies on a shared idleness representation and a coordination mechanism preventing topological conflicts. The second level hosts coordination strategies based on a metric representation of space and is supported by a 3D SLAM system. Here, each robot path planner negotiates spatial conflicts by applying a multi-robot traversability function. Continuous interactions between these two levels ensure coordination and conflicts resolution. Both simulations and real-world experiments are presented to validate the performances of the proposed patrolling strategy in 3D environments. Results show this is a promising solution for managing spatial conflicts and preventing deadlocks.
Vorheriger Artikel Learning motion primitives for planning swift maneuvers of quadrotor
Nächster Artikel Mosquito-inspired distributed swarming and pursuit for cooperative defense against fast intruders

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
2
This can be a rotating laser range-finder or a full 3D scanner.
 
3
That is, the distance between the closest pair of points of the two planned paths is smaller than \(D_s\).
 
4
We use an “is_” prefix to denote boolean variables.
 
5
Or at a pre-fixed frequency, after a first selected is broadcast along the way to the current goal.
 
6
In our case, this depends on the idlenesses of the nodes.
 
7
The metric level modules must run on the robot main board and share computational resources with other demanding processing nodes (Kruijff-Korbayová et al. 2015).
 
8
At this stage, we found this approach to perform very well in practice without significantly limiting the robot manoeuvres in the tested scenarios.
 
9
Here we include the segmented obstacles in the map and the most recent nearby obstacle points which have been detected by the rangefinder and are not segmented yet in the map.
 
10
The sub-optimality of the solution is due to the used incremental sampling-based approach (Karaman and Frazzoli 2010; Diankov and Kuffner 2007).
 
11
As explained in Sect. 7.2, each point of \(\mathcal{M}_t\) can be associated to a robot pose.
 
12
This can be used for instance to steer the robot toward regions where an estimated WIFI radio signal strength map returns higher values (Caccamo et al. 2017).
 
13
The dynamic update of the OctoMap and its reactive behaviour is demonstrated in a video https://​youtu.​be/​caECYcYdrgo.
 
15
This aspect can be managed for instance as proposed in Zimmermann et al. (2014) and Colas et al. (2013).
 
17
Two simulation videos are available on our website and show these behaviour.
 
18
Since V-REP simulations are computationally demanding in our setup, the simulated robots were not able to move in real time and their motions were very slow (this can be observed in our simulation videos on our website). As a result, when robots got in interference, they persisted in such conditions for longer times with respect to a normal real time simulation.
 
19
Which we do not report here in order to reduce space.
 
20
This is not visible in the plot but it was observed by inspecting the recorded data.
 
22
In these cases, the path planner only considers the most interesting and useful part of the traversability map.
 
23
This laser proximity checker inhibits forward velocity commands when a close front obstacle is detected by the laser.
 
24
In our setup, V-REP is not able to stably simulate more than four robots under realistic conditions (cfr. Sect. 10.1).
 
25
The path and idleness message sizes actually depends on the number of patrolling graph nodes.
 
26
Recurring to simpler and more affordable robotic platforms is required.
 
Literatur
Acevedo, J. J., Arrue, B. C., Daz-Bez, J. M., Ventura, I., Maza, I., & Ollero, A. (2013). Decentralized strategy to ensure information propagation in area monitoring missions with a team of UAVs under limited communications. In 2013 International Conference on Unmanned Aircraft Systems (ICUAS) (pp. 565–574).
Acevedo, J. J., Arrue, B. C., Maza, I., & Ollero, A. (2016). A distributed algorithm for area partitioning in grid-shape and vector-shape configurations with multiple aerial robots. Journal of Intelligent & Robotic Systems, 84(1), 543–557.CrossRef
Agmon, N., Kaminka, G. A., & Kraus, S. (2014). Multi-robot adversarial patrolling: Facing a full-knowledge opponent. CoRR abs/1401.3903.
Agmon, N., Kraus, S., & Kaminka, G. A. (2008a). Multi-robot perimeter patrol in adversarial settings. In ICRA (pp. 2339–2345).
Agmon, N., Sadov, V., Kaminka, G. A., & Kraus, S. (2008b). The impact of adversarial knowledge on adversarial planning in perimeter patrol. In Proceedings of the 7th international joint conference on autonomous agents and multiagent systems—Volume 1, AAMAS’08 (pp. 55–62). International Foundation for Autonomous Agents and Multiagent Systems.
Ahmadi, M., & Stone, P. (2006). A multi-robot system for continuous area sweeping tasks. In ICRA (pp. 1724–1729).
Aksaray, D., Leahy, K., & Belta, C. (2015). Distributed multi-agent persistent surveillance under temporal logic constraints. IFAC-PapersOnLine, 48(22), 174–179.CrossRef
Andrade, R. D. C., Macedo, H. T., Ramalho, G. L., & Ferraz, C. A. (2001). Distributed mobile autonomous agents in network management. In Proceedings of international conference on parallel and distributed processing techniques and applications.
Baran, P. (1964). On distributed communications networks. IEEE Transactions on Communications Systems, 12(1), 1–9.CrossRef
Barraquand, J., Langlois, B., & Latombe, J. C. (1992). Numerical potential field techniques for robot path planning. IEEE Transactions on Systems, Man, and Cybernetics, 22(2), 224–241.MathSciNetCrossRef
Bereg, S., Caraballo, L. E., Díaz-Báñez, J. M., & Lopez, M. A. (2016). Resilience of a synchronized multi-agent system. ArXiv e-prints.
Cabrita, G., Sousa, P., Marques, L., & De Almeida, A. (2010). Infrastructure monitoring with multi-robot teams. In IROS (pp. 18–22).
Caccamo, S., Parasuraman, R., Freda, L., Gianni, M., & Ögren, P. (2017). Rcamp: A resilient communication-aware motion planner for mobile robots with autonomous repair of wireless connectivity. In 2017 IEEE/RSJ international conference on intelligent robots and systems (IROS). IEEE.
Cadena, C., Carlone, L., Carrillo, H., Latif, Y., Scaramuzza, D., Neira, J., et al. (2016). Past, present, and future of simultaneous localization and mapping: Towards the robust-perception age. IEEE Transactions on Robotics, 32(6), 1309–1332.CrossRef
Chen, H., Cheng, T., & Wise, S. (2017). Developing an online cooperative police patrol routing strategy. Computers, Environment and Urban Systems, 62, 19–29.CrossRef
Chevaleyre, Y. (2004). Theoretical analysis of the multi-agent patrolling problem. In Proceedings of the IEEE/WIC/ACM international conference on intelligent agent technology (pp. 302–308).
Colas, F., Mahesh, S., Pomerleau, F., Liu, M., & Siegwart, R. (2013). 3D path planning and execution for search and rescue ground robots. In 2013 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 722–727). IEEE.
Diankov, R., Kuffner, J. (2007). Randomized statistical path planning. In IEEE/RSJ international conference on intelligent robots and systems. IROS 2007 (pp. 1–6). IEEE.
Douillard, B., Underwood, J., Kuntz, N., Vlaskine, V., Quadros, A., Morton, P., et al. (2011). On the segmentation of 3D lidar point clouds. In ICRA.
Du, T. C., Li, E. Y., & Chang, A. P. (2003). Mobile agents in distributed network management. Communications of the ACM, 46(7), 127–132.CrossRef
Dubé, R., Dugas, D., Stumm, E., Nieto, J., Siegwart, R., & Cadena, C. (2017a). Segmatch: Segment based place recognition in 3D point clouds. In ICRA (pp. 5266–5272). IEEE.
Dubé, R., Gawel, A., Sommer, H., Nieto, J., Siegwart, R., & Cadena, C. (2017b). An online multi-robot slam system for 3D lidars. In IROS.
Elmaliach, Y., Agmon, N., & Kaminka, G. A. (2007). Multi-robot area patrol under frequency constraints. In ICRA (pp. 385–390).
Elmaliach, Y., Agmon, N., & Kaminka, G. A. (2009a). Multi-robot area patrol under frequency constraints. Annals of Mathematics and Artificial Intelligence, 57(3), 293–320.MathSciNetMATHCrossRef
Elmaliach, Y., Agmon, N., & Kaminka, G. A. (2009b). Multi-robot area patrol under frequency constraints. Annals of Mathematics and Artificial Intelligence, 57(3–4), 293–320.MathSciNetMATHCrossRef
Farinelli, A., Iocchi, L., & Nardi, D. (2004). Multirobot systems: A classification focused on coordination. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 34(5), 2015–2028.CrossRef
Farinelli, A., Iocchi, L., & Nardi, D. (2017). Distributed on-line dynamic task assignment for multi-robot patrolling. Autonomous Robots, 41(6), 1321–1345.CrossRef
Ferri, F., Gianni, M., Menna, M., & Pirri, F. (2014). Point cloud segmentation and 3D path planning for tracked vehicles in cluttered and dynamic environments. In Proceedings of the 3rd IROS Workshop on Robots in Clutter: Perception and Interaction in Clutter.
Franchi, A., Freda, L., Oriolo, G., & Vendittelli, M. (2009). The sensor-based random graph method for cooperative robot exploration. IEEE/ASME Transaction on Mechatronics, 14(2), 163–175.CrossRef
Grisetti, G., Kümmerle, R., Stachniss, C., & Burgard, W. (2010). A tutorial on graph-based slam. Intelligent Transportation Systems Magazine, IEEE, 2(4), 31–43.CrossRef
Haït, A., Simeon, T., & Taïx, M. (2002). Algorithms for rough terrain trajectory planning. Advanced Robotics, 16(8), 673–699.CrossRef
Hernández, E., Barrientos, A., & Cerro, J. D. (2014). Selective smooth fictitious play: An approach based on game theory for patrolling infrastructures with a multi-robot system. Expert Systems With Applications, 41(6), 2897–2913.CrossRef
Hornung, A., Wurm, K. M., Bennewitz, M., Stachniss, C., & Burgard, W. (2013). OctoMap: An efficient probabilistic 3D mapping framework based on octrees. Autonomous Robots, 34(3), 189–206.CrossRef
Iocchi, L., Marchetti, L., & Nardi, D. (2011). Multi-robot patrolling with coordinated behaviours in realistic environments. In IROS (pp. 2796–2801).
Jung, M. F., Beane, M., Forlizzi, J., Murphy, R., & Vertesi, J. (2017). Robots in group context: Rethinking design, development and deployment. In Proceedings of the 2017 CHI conference extended abstracts on human factors in computing systems (pp. 1283–1288). ACM.
Karaman, S., & Frazzoli, E. (2010). Incremental sampling-based algorithms for optimal motion planning. Robotics Science and Systems VI, 104, 2.
Kleiner, A., Heintz, F., & Tadokoro, S. (2016). Special issue on safety, security, and rescue robotics (SSRR), part 2. Journal of Field Robotics, 33(4), 409–410.CrossRef
Kruijff, G. J. M., Kruijff-Korbayová, I., Keshavdas, S., Larochelle, B., Janíček, M., Colas, F., et al. (2014). Designing, developing, and deploying systems to support human-robot teams in disaster response. Advanced Robotics, 28(23), 1547–1570.CrossRef
Kruijff, G. J. M., Pirri, F., Gianni, M., Papadakis, P., Pizzoli, M., Sinha, A., et al. (2012). Rescue robots at earthquake-hit Mirandola, Italy: A field report. In 2012 IEEE international symposium on safety, security, and rescue robotics (SSRR) (pp. 1–8). IEEE.
Kruijff-Korbayová, I., Colas, F., Gianni, M., Pirri, F., Greeff, J., Hindriks, K., et al. (2015). Tradr project: Long-term human-robot teaming for robot assisted disaster response. KI-Künstliche Intelligenz, 29(2), 193–201.CrossRef
Kruijff-Korbayová, I., Freda, L., Gianni, M., Ntouskos, V., Hlaváč, V., Kubelka, V., et al. (2016). Deployment of ground and aerial robots in earthquake-struck amatrice in Italy (brief report). In 2016 IEEE international symposium on safety, security, and rescue robotics (SSRR) (pp. 278–279). IEEE.
Krüsi, P., Furgale, P., Bosse, M., & Siegwart, R. (2017). Driving on point clouds: Motion planning, trajectory optimization, and terrain assessment in generic nonplanar environments. Journal of Field Robotics, 34(5), 940–984.CrossRef
Kubelka, V., Oswald, L., Pomerleau, F., Colas, F., Svoboda, T., & Reinstein, M. (2015). Robust data fusion of multimodal sensory information for mobile robots. Journal of Field Robotics, 32(4), 447–473.CrossRef
Machado, A., Ramalho, G., Zucker, J. D., & Drogoul, A. (2002). Multi-agent patrolling: An empirical analysis of alternative architectures. In International workshop on multi-agent systems and agent-based simulation (pp. 155–170). Springer.
Menna, M., Gianni, M., Ferri, F., & Pirri, F. (2014). Real-time autonomous 3D navigation for tracked vehicles in rescue environments. In IROS (pp. 696–702).
Nagatani, K., Kiribayashi, S., Okada, Y., Otake, K., Yoshida, K., Tadokoro, S., et al. (2013). Emergency response to the nuclear accident at the fukushima daiichi nuclear power plants using mobile rescue robots. Journal of Field Robotics, 30(1), 44–63.CrossRef
Panagou, D., Stipanovi, D. M., & Voulgaris, P. G. (2016). Distributed coordination control for multi-robot networks using lyapunov-like barrier functions. IEEE Transactions on Automatic Control, 61(3), 617–632.MathSciNetMATHCrossRef
Park, C. H., Kim, Y. D., & Jeong, B. (2012). Heuristics for determining a patrol path of an unmanned combat vehicle. Computers & Industrial Engineering, 63(1), 150–160.CrossRef
Pasqualetti, F., Durham, J. W., & Bullo, F. (2012). Cooperative patrolling via weighted tours: Performance analysis and distributed algorithms. IEEE Transactions on Robotics, 28(5), 1181–1188.CrossRef
Pippin, C., & Christensen, H. (2014). Trust modeling in multi-robot patrolling. In ICRA (pp. 59–66).
Portugal, D., & Rocha, R. (2010). Msp algorithm: Multi-robot patrolling based on territory allocation using balanced graph partitioning. In Proceedings of the 2010 ACM symposium on applied computing (pp. 1271–1276). New York, NY, USA: ACM.
Portugal, D., & Rocha, R. (2011). A survey on multi-robot patrolling algorithms. In Technological Innovation for Sustainability (pp. 139–146).
Portugal, D., & Rocha, R. P. (2013a). Distributed multi-robot patrol: A scalable and fault-tolerant framework. Robotics and Autonomous Systems, 61(12), 1572–1587.CrossRef
Portugal, D., & Rocha, R. P. (2013b). Multi-robot patrolling algorithms: Examining performance and scalability. Advanced Robotics, 27(5), 325–336.CrossRef
Portugal, D., & Rocha, R. P. (2013c). Retrieving topological information for mobile robots provided with grid maps (pp. 204–217). Berlin: Springer.
Portugal, D., & Rocha, R. P. (2013d). Scalable, fault-tolerant and distributed multi-robot patrol in real world environments. In IROS (pp. 4759–4764).
Portugal, D., & Rocha, R. P. (2016). Cooperative multi-robot patrol with bayesian learning. Autonomous Robots, 40(5), 929–953.CrossRef
Robin, C., & Lacroix, S. (2016). Multi-robot target detection and tracking: Taxonomy and survey. Autonomous Robots, 40(4), 729–760.CrossRef
Rohmer, E., Singh, S. P. N., & Freese, M. (2013). V-rep: A versatile and scalable robot simulation framework. In Proceedings of The International Conference on Intelligent Robots and Systems (IROS).
Sak, T., Wainer, J., & Goldenstein, S. K. (2008). Probabilistic multiagent patrolling (pp. 124–133). Berlin: Springer.
Santana, H., Ramalho, G., Corruble, V., & Ratitch, B. (2004). Multi-agent patrolling with reinforcement learning. In Proceedings of the 3rd international joint conference on autonomous agents and multiagent systems—Volume 3, AAMAS’04 (pp. 1122–1129). IEEE Computer Society.
Sempé, F., & Drogoul, A. (2003). Adaptive patrol for a group of robots. In 2003 IEEE/RSJ international conference on intelligent robots and systems. (IROS 2003). Proceedings (Vol. 3, pp. 2865–2869). IEEE.
Shahriari, M., & Biglarbegian, M. (2016). A new conflict resolution method for multiple mobile robots in cluttered environments with motion-liveness. IEEE Transactions on Cybernetics, PP(99), 1–12.
Song, C., Liu, L., Feng, G., & Xu, S. (2014). Optimal control for multi-agent persistent monitoring. Automatica, 50(6), 1663–1668.MathSciNetMATHCrossRef
Tardioli, D., Sicignano, D., Riazuelo, L., Romeo, A., Villarroel, J. L., & Montano, L. (2016). Robot teams for intervention in confined and structured environments. Journal of Field Robotics, 33(6), 765–801.CrossRef
Walcott-Bryant, A., Kaess, M., Johannsson, H., & Leonard, J. J. (2012). Dynamic pose graph slam: Long-term mapping in low dynamic environments. In 2012 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 1871–1878). IEEE.
Weinmann, M., Jutzi, B., & Mallet, C. (2014). Semantic 3d scene interpretation: A framework combining optimal neighborhood size selection with relevant features. ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2(3), 181.CrossRef
Yan, C., & Zhang, T. (2016). Multi-robot patrol: A distributed algorithm based on expected idleness. International Journal of Advanced Robotic Systems, 13(6), 1729881416663,666.
Yan, Z., Jouandeau, N., & Cherif, A. A. (2013). A survey and analysis of multi-robot coordination. International Journal of Advanced Robotic Systems, 10(12), 399.CrossRef
Yehoshua, R., Agmon, N., & Kaminka, G. A. (2013). Robotic adversarial coverage: Introduction and preliminary results. In IROS (pp. 6000–6005).
Zimmermann, K., Zuzanek, P., Reinstein, M., & Hlavac, V. (2014). Adaptive traversability of unknown complex terrain with obstacles for mobile robots. In 2014 IEEE international conference on robotics and automation (ICRA) (pp. 5177–5182). IEEE.
Metadaten
Titel
3D multi-robot patrolling with a two-level coordination strategy
verfasst von
Luigi Freda
Mario Gianni
Fiora Pirri
Abel Gawel
Renaud Dubé
Roland Siegwart
Cesar Cadena
Publikationsdatum
17.01.2019
Verlag
Springer US
Erschienen in
Autonomous Robots / Ausgabe 7/2019
Print ISSN: 0929-5593
Elektronische ISSN: 1573-7527
DOI
https://doi.org/10.1007/s10514-018-09822-3

Weitere Artikel der Ausgabe 7/2019

Autonomous Robots 7/2019 Zur Ausgabe

OriginalPaper

Synthesis of kinematically constrained full-body motion from stochastic motion model

OriginalPaper

Effects of the weighting matrix on dynamic manipulability of robots

OriginalPaper

Learning motion primitives for planning swift maneuvers of quadrotor

OriginalPaper

Mosquito-inspired distributed swarming and pursuit for cooperative defense against fast intruders

OriginalPaper

A lightweight and scalable visual-inertial motion capture system using fiducial markers

OriginalPaper

Selective image registration for efficient visual SLAM on planar surface structures in underwater environment

Neuer Inhalt

    Bildnachweise