nach oben

Autonomous Robots

Erschienen in:

16.04.2022

Decentralised coverage of a large structure using flocking of autonomous agents having a dynamic hierarchy model

verfasst von: Suryadeep Nath, Manoj Baishya, Debasish Ghose

Erschienen in: Autonomous Robots | Ausgabe 5/2022

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we present a decentralised algorithm to form a coverage around a large structure using autonomous sensor agents. Forming a coverage around a structure is defined using a set of objectives. Structures are formally categorised into objects and obstacles, and defined based on the application. We use the notion of a multi-species flocking algorithm for achieving a proper coverage formation. We modify the basic algorithm substantially by introducing a new virtual agent that aids in positioning of the flocking agents along with stability analysis, incorporating a dynamic hierarchy among the flocking agents, and defining novel controls based on shearing and screwing actions to spread the agents uniformly around the structure. Each species of agents is defined and their roles in the algorithm justified. We discuss special cases and challenging scenarios that can potentially hinder smooth implementation of the algorithm and suggest approaches to overcome them. The method is applied to both convex and non-convex objects in 2D, as well as, 3D. Time of convergence and coverage energy are used as metrics to assess the performance of the system and are studied through extensive simulations.

Vorheriger Artikel Analysis and acceleration of TORM: optimization-based planning for path-wise inverse kinematics

Nächster Artikel A hybrid inductive learning-based and deductive reasoning-based 3-D path planning method in complex environments

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

Nur mit Berechtigung zugänglich

Acar, E. U., & Choset, H. (2002). Sensor-based coverage of unknown environments: Incremental construction of Morse decompositions. The International Journal of Robotics Research, 21, 345–366. https://journals.sagepub.com/doi/abs/10.1177/027836402320556368.CrossRef

Almadhoun, R., Taha, T., Seneviratne, L., Dias, J., & Cai, G. (2016). A survey on inspecting structures using robotic systems. International Journal of Advanced Robotic Systems, 13, 1–18. https://journals.sagepub.com/doi/full/10.1177/1729881416663664.CrossRef

Bircher, A., Kamel, M., Alexis, K., Burri, M., Oettershagen, P., Omari, S., Mantel, T., & Siegwart, R. (2016). Three-dimensional coverage path planning via viewpoint resampling and tour optimization for aerial robots. Autonomous Robots, 40, 1059–1078. https://link.springer.com/article/10.1007/s10514-015-9517-1.CrossRef

Bixia, D., & Wei, L. (2014). https://ieeexplore.ieee.org/abstract/document/6896818Flocking of Multi-Agents with Arbitrary Shape Obstacle. Proceedings of the 33rd Chinese Control Conference, Nanjing, China.

Choset, H. (2001). Coverage for robotics-A survey of recent results. Annals of Mathematics and Artificial Intelligence, 31, 113–126. https://link.springer.com/article/10.1023/A:1016639210559.MATHCrossRef

Choset, H., & Pignon, P. (1998). Coverage path planning: The boustrophedon cellular decomposition. Field and service robotics pp 203–209 https://link.springer.com/chapter/10.1007/978-1-4471-1273-0_32.

Cortes, J., & Bullo, F. (2005). Coordination and geometric optimization via distributed dynamical systems. SIAM Journal on Control and Optimization, 44(5), 1543–1574. https://epubs.siam.org/doi/abs/10.1137/S0363012903428652.MathSciNetMATHCrossRef

Cortes, J., Martinez, S., Karatas, T., & Bullo, F. (2004). Coverage control for mobile sensing networks. IEEE Transactions on Robotics and Automation, 20, 243–255. https://ieeexplore.ieee.org/abstract/document/1284411.CrossRef

Ellefsen, K. O., Lepikson, H. A., & Albiez, J. C. (2017). Multiobjective coverage path planning: Enabling automated inspection of complex, real-world structures. Applied Soft Computing, 61, 264–282. https://www.sciencedirect.com/science/article/pii/S1568494617304714#bib0005.CrossRef

Englot, B., & Hover, F. (2010). Inspection planning for sensor coverage of 3D marine structures. 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems pp 4412–4417 https://ieeexplore.ieee.org/abstract/document/5648908.

Englot, B., & Hover, F. (2012). Sampling-based coverage path planning for inspection of complex structures. Proceedings of the International Conference on Automated Planning and Scheduling, 22, 1445–1464. https://ojs.aaai.org/index.php/ICAPS/article/view/13529.

Franchi, A., Stegagno, P., & Oriolo, G. (2016). Decentralized multi-robot encirclement of a 3D target with guaranteed collision avoidance. Autonomous Robots, 40, 245–265. https://link.springer.com/content/pdf/10.1007/s10514-015-9450-3.pdf.CrossRef

Galceran, E., & Carreras, M. (2013). A survey on coverage path planning for robotics. Robotics and Autonomous Systems, 61, 1258–1276. https://www.sciencedirect.com/science/article/pii/S092188901300167X.CrossRef

Hafez, A. T., Marasco, A. J., Givigi, S. N., Iskandarani, M., Yousefi, S., & Rabbath, C. A. (2015). Solving multi-UAV dynamic encirclement via model predictive control. IEEE Transactions on Control Systems Technology, 23, 2251–2265. https://ieeexplore.ieee.org/abstract/document/7066874/.CrossRef

Hover, F. S., Eustice, R. M., Kim, A., Englot, B., Johannsson, H., Kaess, M., & Leonard, J. J. (2012). Advanced perception navigation and planning for autonomous in-water ship hull inspection. The International Journal of Robotics Research, 31, 1445–1464. https://journals.sagepub.com/doi/abs/10.1177/0278364912461059.CrossRef

Howard, A., Mataric, M.J., & Sukhatme, G.S. (2002). Mobile sensor network deployment using potential fields: A distributed scalable solution to the area coverage problem. Proceedings of International Conference on Distributed Autonomous Robotic Systems p 299–308 https://link.springer.com/chapter/10.1007/978-4-431-65941-9_30.

Huang, W., Huang, Y., & Chen, S. (2018). Robust consensus control for a class of second-order multi-agent systems with uncertain topology and disturbances. Neurocomputing, 313, 426–435.CrossRef

Jadbabaie, A., Lin, J., & Morse, A. S. (2003). Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transactions on Automatic Control, 48(6), 988–1001. https://ieeexplore.ieee.org/abstract/document/1205192.MathSciNetMATHCrossRef

Jafari, M., & Xu, H. (2019). A biologically-inspired distributed fault tolerant flocking control for multi-agent system in presence of uncertain dynamics and unknown disturbance. Engineering applications of artificial intelligence, 79, 1–12.CrossRef

Jia, Y., & Vicsek, T. (2019). Modelling hierarchical flocking. New Journal of Physics 21 https://iopscience.iop.org/article/10.1088/1367-2630/ab428e/meta.

Jia, Y., & Wang, L. (2015). Leader-follower flocking of multiple robotic fish. IEEE/ASME Transactions on Mechatronics, 20, 1372–1383. https://ieeexplore.ieee.org/abstract/document/6876179.CrossRef

Jung, H., & Kim, D. H. (2014). Potential-function-based shape formation in swarm simulation. International Journal of Control, Automation, and Systems, 12, 442–449. https://link.springer.com/content/pdf/10.1007/s12555-013-0133-6.pdf.CrossRef

Kass, M., Witkin, A., & Terzopoulos, D. (1988). Snakes: Active contour models. International Journal of Computer Vision, 1, 321–331. http://graphics.hallym.ac.kr/teach/2009/tcg/src/IJCV98Kass.pdf.MATHCrossRef

Khatib, O. (1986). Real-time obstacle avoidance for manipulators and mobile robots. The International Journal of Robotics Research, 5, 90–98. https://journals.sagepub.com/doi/10.1177/027836498600500106.CrossRef

Lam, K. M., & Yan, H. (1994). Fast algorithm for locating head boundaries. Journal of Electronic Imaging, 3, 352–359. https://spie.org/Publications/Journal/10.1117/12.183806?SSO=1.CrossRef

Leonard, N.E., & Fiorelli, E. (2001). Virtual leaders, artificial potentials, and coordinated control of groups. Proceedings of the 40th IEEE Conference on Decision and Control p 2968–2973 https://www.princeton.edu/~naomi/FLcdc_flocks_submission.pdf.

Li, G., St-Onge, D., Pinciroli, C., Gasparri, A., Garone, E., & Beltrame, G. (2019). Decentralized progressive shape formation with robot swarms. Autonomous Robots, 43, 1505–1521. https://link.springer.com/article/10.1007/s10514-018-9807-5.CrossRef

Li, S., Liu, X., Tang, W., & Zhang, J. (2014). Flocking of multi-agents following a leader with adaptive protocol in a noisy environment. Asian Journal of Control, 16, 1771–1778. https://onlinelibrary.wiley.com/doi/full/10.1002/asjc.799.MathSciNetMATHCrossRef

Lifen, L., Ruoxin, S., Shuandao, L., & Jiang, W. (2016). Path planning for UAVS Based on Improved Artificial Potential Field Method through Changing the Repulsive Potential Function. Proceedings of 2016 IEEE Chinese Guidance, Navigation and Control Conference pp 2011–2015 https://ieeexplore.ieee.org/abstract/document/7829099.

Marasco, A. J., Givigi, S. N., & Rabbath, C. A. (2012). Model Predictive Control for the Dynamic Encirclement of a Target. American Control Conference pp 2004–2009 https://ieeexplore.ieee.org/abstract/document/6315602.

Nguyen, T., La, H. M., Le, T. D., & Jafari, M. (2016). Formation control and obstacle avoidance of multiple rectangular agents with limited communication ranges. IEEE Transactions on Control of Network Systems, 4(4), 680–691.MathSciNetMATHCrossRef

Olcay, E., Schuhmann, F., & Lohmann, B. (2020). Collective navigation of a multi-robot system in an unknown environment. Robotics and Autonomous Systems, 132, 103604.CrossRef

Olfati-Saber, R. (2006). Flocking for multi-agent dynamic systems: Algorithms and theory. IEEE Transactions on Automatic Control, 51(3), 401–420. https://ieeexplore.ieee.org/abstract/document/1605401.MathSciNetMATHCrossRef

Olfati-Saber, R., & Murray, R. M. (2002). Distributed cooperative control of multiple vehicle formations using structural potential functions. Proceedings of 15th IFAC World Congress 32, 495–500 https://www.sciencedirect.com/science/article/pii/S1474667015386651.

Olfati-Saber, R., & Murray, R. M. (2003). Flocking with obstacle avoidance: Cooperation with limited communication in mobile networks. 42nd IEEE International Conference on Decision and Control 2:2022–2028 https://ieeexplore.ieee.org/abstract/document/1272912.

Olfati-Saber, R., Fax, J. A., & Murray, R. M. (2007). Consensus and cooperation in networked multi-agent systems. Proceedings of the IEEE, 95(1), 215–233. https://ieeexplore.ieee.org/abstract/document/4118472.MATHCrossRef

O’Rourke, J. (1987). Art gallery theorems and algorithms. Oxford University Press, Inc. https://dl.acm.org/doi/book/10.5555/40599.

Paranjape, A. A., Chung, S., Kim, K., & Shim, D. H. (2018). Robotic Herding of a flock of birds using an unmanned aerial vehicle. IEEE Transactions on Robotics, 34, 901–915. https://ieeexplore.ieee.org/abstract/document/8424544/.CrossRef

Parrish, J. K., Viscido, S. V., & Grunbaum, D. (2002). Self-organized fish schools: An examination of emergent properties. The Biological Bulletin, 202, 296–305. https://www.journals.uchicago.edu/doi/abs/10.2307/1543482.CrossRef

Paternain, S., Koditschek, D. E., & Ribeiro, A. (2018). Navigation functions for convex potentials in a space with convex obstacles. IEEE Transactions on Automatic Control, 63, 2944–2959. https://ieeexplore.ieee.org/abstract/document/8114216.MathSciNetMATHCrossRef

Potts, W. K. (1984). The chorus-line hypothesis of manoeuvre coordination in avian flocks. Nature, 309, 344–345. https://www.nature.com/articles/309344a0.CrossRef

Reyes, L., & Tanner, H. G. (2015). Flocking, formation control, and path following for a group of mobile robots. IEEE Transactions on Control Systems Technology, 23(4), 1268–1282. https://ieeexplore.ieee.org/abstract/document/6963394.CrossRef

Reynolds, C. W. (1987). Flocks, herds, and schools: A distributed behavioral model. SIGGRAPH ’87: Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques 21, 25–34 https://dl.acm.org/doi/abs/10.1145/37401.37406.

Rezaee, H., Abdollahi, F. (2011). Mobile robots cooperative control and obstacle avoidance using potential field. In: 2011 IEEE/ASME International Conference on Advanced Intelligent Mechatronics (AIM), IEEE, pp 61–66.

Rezaee, H., & Abdollahi, F. (2017). Adaptive consensus control of nonlinear multiagent systems with unknown control directions under stochastic topologies. IEEE Transactions on Neural Networks and Learning Systems, 29(8), 3538–3547.MathSciNet

Rezaee, H., & Abdollahi, F. (2019). A cyclic pursuit framework for networked mobile agents based on vector field approach. Journal of the Franklin Institute, 356(2), 1113–1130.MathSciNetMATHCrossRef

Rimon, E., & Koditschek, D. E. (1992). Exact robot navigation using artificial potential functions. IEEE Transactions on Robotics and Automation, 8, 501–518. https://ieeexplore.ieee.org/document/163777.CrossRef

Rubenstein, M., Cornejo, A., & Nagpal, R. (2014). Programmable self-assembly in a thousand-robot swarm. Science, 345, 795–799. https://science.sciencemag.org/content/345/6198/795.abstract.CrossRef

Ruchti, J., Senkbeil, R., Carroll, J., Dickinson, J., Holt, J., & Biaz, S. (2014). Unmanned aerial system collision avoidance using artificial potential fields. Journal of Aerospace Information Systems, 11, 140–144. https://arc.aiaa.org/doi/full/10.2514/1.I010022.CrossRef

Sakalli, M., Lam, K., & Yan, H. (2006). A faster converging snake algorithm to locate object boundaries. IEEE Transactions on Image Processing, 15, 1182–1191. https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1621240.CrossRef

Shang, Z., Bradley, J., & Shen, Z. (2020). A co-optimal coverage path planning method for aerial scanning of complex structures. Expert Systems with Applications, 158, 1–16. https://www.sciencedirect.com/science/article/pii/S0957417420303596#b0070.

Shaw, E. (1978). Schooling Fishes: The school, a truly egalitarian form of organization in which all members of the group are alike in influence, offers substantial benefits to its participants. American Scientist, 66, 166–175. https://www.jstor.org/stable/27848512?seq=1#metadata_info_tab_contents.

Toner, J., & Tu, Y. (1998). Flocks, herds, and schools: A quantitative theory of flocking. Physical Review E, 58(4), 4828–4858. https://journals.aps.org/pre/abstract/10.1103/PhysRevE.58.4828.MathSciNetCrossRef

Topaz, C. M., & Bertozzi, A. L. (2004). Swarming patterns in a two-dimensional kinematic model for biological groups. SIAM Journal on Applied Mathematics, 65(1), 152–174. https://epubs.siam.org/doi/abs/10.1137/S0036139903437424.MathSciNetMATHCrossRef

Vicsek, T., Cziroók, A., Ben-Jacob, E., Cohen, I., & Shochet, O. (1995). Novel type of phase transition in a system of self-driven particles. Physical Review Letters, 75(6), 1226–1229. https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.75.1226.MathSciNetCrossRef

Vásárhelyi, G., Virágh, C., Somorjai, G., Nepusz, T., Eiben, A. E., & Vicsek, T. (2018). Optimized flocking of autonomous drones in confined environments. Science Robotics 3(20) https://robotics.sciencemag.org/content/3/20/eaat3536.short.

Wang, H., & Rubenstein, M. (2020). Shape formation in homogeneous swarms using local task swapping. IEEE Transactions on Robotics, 36, 597–612. https://ieeexplore.ieee.org/abstract/document/9000788.CrossRef

Titel: Decentralised coverage of a large structure using flocking of autonomous agents having a dynamic hierarchy model
verfasst von: Suryadeep Nath
Manoj Baishya
Debasish Ghose
Publikationsdatum: 16.04.2022
Verlag: Springer US
Erschienen in: Autonomous Robots / Ausgabe 5/2022
Print ISSN: 0929-5593
Elektronische ISSN: 1573-7527
DOI: https://doi.org/10.1007/s10514-022-10041-0

Neuer Inhalt

Bildnachweise

VDI-Icon, Profil Icon, inhalt2, Springer Professional Modul/© Springer Fachmedien Wiesbaden GmbH, Nachhaltigkeitsaward Key Visual/© Cometis AG/Global ESG Monitor | Daniel Rupp | Generiert mit KI, Search Icon, Banner Hanser, Beijing Auto Show 2024: Deutsche Hersteller wollen angreifen./© EKH-Pictures / Generated with AI / Stock.adobe.com, Buchstaben, die aus einem Megaphon kommen/© MicroStockHub/Getty Images/iStock, Digitale Lieferkette/© zapp2photo / stock.adobe.com, Zeitschrift Wissensmanagement Cover, PatentFit-Logo/© Springer Fachmedien Wiesbaden GmbH, Sustainibility Finance/© Robert Kneschke / stock.adobe.com / Springer Fachmedien Wiesbaden GmbH, Zukunftswerkstatt Sales Excellence 2024/© AndreyPopov / Getty Images / iStock, 2023_Antrieb/© supervisuell

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 "Technik"

Weitere Artikel der Ausgabe 5/2022

External force observer aided push recovery for torque-controlled biped robots

Analysis and acceleration of TORM: optimization-based planning for path-wise inverse kinematics

A hybrid inductive learning-based and deductive reasoning-based 3-D path planning method in complex environments

Motion planning and control for mobile robot navigation using machine learning: a survey

Neuer Inhalt

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

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