Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-23T19:23:29.208Z Has data issue: false hasContentIssue false
  • English
  • Français

Understanding the communication complexity of the robotic Darwinian PSO

Published online by Cambridge University Press:  13 February 2014

Micael S. Couceiro ,
Amadeu Fernandes ,
Rui P. Rocha  and
Nuno M. F. Ferreira
Micael S. Couceiro*
Affiliation:
Institute of Systems and Robotics (ISR), Department of Electrical and Computer Engineering, University of Coimbra, Pólo II, 3030-290 Coimbra, Portugal RoboCorp, Engineering Institute of Coimbra, Quinta da Nora, 3030-199 Coimbra, Portugal
Amadeu Fernandes
Affiliation:
Institute of Systems and Robotics (ISR), Department of Electrical and Computer Engineering, University of Coimbra, Pólo II, 3030-290 Coimbra, Portugal
Rui P. Rocha
Affiliation:
Institute of Systems and Robotics (ISR), Department of Electrical and Computer Engineering, University of Coimbra, Pólo II, 3030-290 Coimbra, Portugal
Nuno M. F. Ferreira
Affiliation:
RoboCorp, Engineering Institute of Coimbra, Quinta da Nora, 3030-199 Coimbra, Portugal
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

An extension of the well-known Particle Swarm Optimization (PSO) to multi-robot applications has been recently proposed and denoted as Robotic Darwinian PSO (RDPSO), benefited from the dynamical partitioning of the whole population of robots. Although such strategy allows decreasing the amount of required information exchange among robots, a further analysis on the communication complexity of the RDPSO needs to be carried out so as to evaluate the scalability of the algorithm. Moreover, a further study on the most adequate multi-hop routing protocol should be conducted. Therefore, this paper starts by analyzing the architecture and characteristics of the RDPSO communication system, thus describing the dynamics of the communication data packet structure shared between teammates. Such procedure will be the first step to achieving a more scalable implementation of RDPSO by optimizing the communication procedure between robots. Second, an ad hoc on-demand distance vector reactive routing protocol is extended based on the RDPSO concepts, so as to reduce the communication overhead within swarms of robots. Experimental results with teams of 15 real robots and 60 simulated robots show that the proposed methodology significantly reduces the communication overhead, thus improving the scalability and applicability of the RDPSO algorithm.

Keywords

Distributed searchSwarm roboticsScalabilityMANETCommunication complexityRouting protocol
Type
Articles
Information
Robotica , Volume 33 , Issue 1 , January 2015 , pp. 157 - 180
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Parker, L. E., “Multiple Mobile Robot Systems,” In: Springer Handbook of Robotics (Siciliano, B. and Khatib, O., eds.) (Springer, New York, NY, 2008), pp. 921–941.Google Scholar
2.Mataric, M. J., “Issues and approaches in the design of collective autonomous agents,” Robot. Auton. Syst. 16, 321–331 (1995).CrossRefGoogle Scholar
3.Onn, S. and Tennenholtz, M., “Determination of social laws for multi-agent mobilization,” Artif. Intell. 95, 155–167 (1997).CrossRefGoogle Scholar
4.Werger, B. B., “Cooperation without deliberation: A minimal behavior-based approach to multi-robot teams,” Artif. Intell. 110 (2), 293–320 (1999).Google Scholar
5.Kernbach, S., Häbe, D., Kernbach, O., Thenius, R., Radspieler, G., Kimura, T. and Schmickl, T., “Adaptive collective decision-making in limited robot swarms without communication,” Int. J. Robot. Res. 32 (1), 35–55 (2013).Google Scholar
6.Huber, M. J. and Durfee, E., “Deciding When to Commit to Action During Observation-Based Coordination,” Proceedings of the First International Conference on Multi-Agent Systems (1995) pp. 163–170.Google Scholar
7.Tambe, M., “Towards flexible teamwork,” J. Artif. Intell. Res. 7, 83–124 (1997).CrossRefGoogle Scholar
8.Parker, L. E., “ALLIANCE: An Architecture for fault-tolerant multi-robot cooperation,” IEEE Trans. Robot. Autom. 14 (2), 220–240 (1998).CrossRefGoogle Scholar
9.Couceiro, M. S., Rocha, R. P. and Ferreira, N. M. F., “Ensuring Ad Hoc Connectivity in Distributed Search with Robotic Darwinian Swarms,” Proceedings of the IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR2011), Kyoto, Japan (2011) pp. 284–289.Google Scholar
10.Sheng, W., Yang, Q., Tan, J. and Xi, N., “Distributed multi-robot coordination in area exploration,” Robot. Auton. Syst. 54, 945–955 (2006).Google Scholar
11.Tardioli, D. and Villarroel, J. L., “Real Time Communications Over 802.11: RT-WMP,” IEEE Internatonal Conference on Mobile Ad Hoc and Sensor Systems (2007) pp. 1–11.Google Scholar
12.Couceiro, M. S., Figueiredo, C. M., Rocha, R. P. and Ferreira, N. M. F., “Darwinian Swarm Exploration Under Communication Constraints: Initial Deployment and Fault-Tolerance Assessment,” Robot. Auton. Syst. (2013; In Press).Google Scholar
13.Couceiro, M. S., Figueiredo, C. M., Luz, J. M. A., Ferreira, N. M. F. and Rocha, R. P., “A low-cost educational platform for swarm robotics,” Int. J. Robots Educ. Art 2 (1), 1–15 (Feb. 2012).Google Scholar
14.Sabattini, L., Chopra, N. and Secchi, C., “On Decentralized Connectivity Maintenance for Mobile Robotic Systems,” 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC), Orlando, FL (2011) pp. 988–993.Google Scholar
15.Casteigts, A., Albert, J., Chaumette, S., Nayak, A. and Stojmenovic, I., “Biconnecting a Network of Mobile Robots Using Virtual Angular Forces,” IEEE 72nd Vehicular Technology Conference, Fall (VTC 2010-Fall), Ottawa, ON (2010) pp. 1038–1046.Google Scholar
16.Rocha, R. P., “Efficient Information Sharing and Coordination in Cooperative Multi-Robot Systems,” Proceedings of II European-Latin-American Workshop on Engineering Systems (SELASI'2006), Porto, Portugal (2006) pp. 1–6.Google Scholar
17.Hereford, J. and Siebold, M., “Multi-robot search using a physically embedded particle swarm optimization,” Int. J. Comput. Intell. Res. 4 (2), 197–209 (2008).Google Scholar
18.Shah, K. and Meng, Y., “Communication-Efficient Dynamic Task Scheduling for Heterogeneous Multi-Robot Systems,” Proceedings of the 2007 IEEE International Symposium on Computational Intelligence in Robotics and Automation, Jacksonville, FL (2007) pp. 230–235.Google Scholar
19.Abedi, O., Fathy, M. and Taghiloo, J., “Enhancing AODV routing protocol using mobility parameters in VANET,” IEEE/ACS International Conference on Computer Systems and Applications, (AICCSA 2008), Doha, Qatar (2008) pp. 229–235.Google Scholar
20.Asenov, H. and Hnatyshin, V., “GPS-Enhanced AODV Routing,” Proceedings of the International Conference on Wireless Networks (ICWN'09), Las Vegas, NV (2009) pp. 1–7.Google Scholar
21.Ayash, M., Mikki, M. and Kangbin, Y., “Improved AODV Routing Protocol to Cope with High Overhead in High Mobility MANETs,” Sixth International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing (IMIS), Palermo, Sicily (2012) pp. 244–251.Google Scholar
22.Couceiro, M. S., Rocha, R. P. and Ferreira, N. M. F., “A Novel Multi-Robot Exploration Approach based on Particle Swarm Optimization Algorithms,” IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR 2011), Kyoto, Japan (2011) pp. 327–332.Google Scholar
23.Tillett, J., Rao, T. M., Sahin, F., Rao, R. and Brockport, S., “Darwinian Particle Swarm Optimization,” Proceedings of the 2nd Indian International Conference on Artificial Intelligence (2005) pp. 1474–1487.Google Scholar
24.Kennedy, J. and Eberhart, R., “A New Optimizer Using Particle Swarm Theory,” Proceedings of the IEEE Sixth International Symposium on Micro Machine and Human Science (1995) pp. 39–43.Google Scholar
25.Couceiro, M. S., Martins, F. M. L., Rocha, R. P. and Ferreira, N. M. F., “Introducing the Fractional Order Robotic Darwinian PSO,” Proceedings of the 9th International Conference on Mathematical Problems in Engineering, Aerospace and Sciences (ICNPAA'2012), Vienna, Austria (2012) pp. 242–252.Google Scholar
26.Couceiro, M. S., Machado, J. A. T., Rocha, R. P. and Ferreira, N. M. F., “A Fuzzified Systematic Adjustment of the Robotic Darwinian PSO,” Robot. Auton. Syst. 60 (12), 1625–1639 (2012).Google Scholar
27.Podlubny, I., Fractional Differential Equations, Mathematics in Science and Engineering, vol. 198 (Academic Press, San Diego, CA, 1999).Google Scholar
28.Couceiro, M. S., Luz, J. M. A., Figueiredo, C. M. and Ferreira, N. M. F., “Modeling and control of biologically inspired flying robots,” J. Robotica 30 (1), 107–121 (2012).Google Scholar
29.Jatmiko, W., Sekiyama, K. and Fukuda, T., “Modified particle swarm robotic odor source localization in dynamic environments,” Int. J. Intell. Control Syst. 11 (2), 176–184 (2006).Google Scholar
30.Marjovi, A. and Marques, L., “Multi-robot olfactory search in structured environments,” Robot. Auton. Syst. 52 (11), 867–881 (2011).Google Scholar
31.Miller, L. E., “Multihop Connectivity of Arbitrary Networks,” Project Report, Wireless Communication Technologies Group (NIST), Gaithersburg, MD, . (2001).Google Scholar
32.Rybski, P. E., Papanikolopoulos, N. P., Stoeter, S. A., Krantz, D. G., Yesin, K. B., Gini, M., Voyles, R., Hougen, D. F., Nelson, B. and Erickson, M. D., “Enlisting rangers and scouts for reconnaissance and surveillance,” IEEE Robot. Autom. Mag. 7 (4), 14–24 (2000).Google Scholar
33.Kulkarni, R. V. and Venayagamoorthy, G. K., “Bio-inspired algorithms for autonomous deployment and localization of sensor nodes,” IEEE Trans. Syst. Man Cybern. 40 (6), 663–675 (2010).Google Scholar
34.Couceiro, M. S., Rocha, R. P., Figueiredo, C. M., Luz, J. M. A. and Ferreira, N. M. F., “Multi-Robot Foraging Based on Darwin's Survival of the Fittest,” IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS'2012), Vilamoura, Algarve (2012).Google Scholar
35.Natesapillai, K., Palanisamy, V. and Duraiswamy, K., “A performance evaluation of proactive and reactive protocols using NS2 simulation,” Int. J. Eng. Res. Ind. Appl. 2 (11), 309–326 (2009).Google Scholar
36.Lee, S. J., Gerla, M. and Toh, C. K., “A simulation study of table-driven and on-demand routing protocols for mobile ad hoc networks,” Network. IEEE 13 (4), 48–54 (1999).Google Scholar
37.Bertocchi, F., Bergamo, P., Mazzini, G. and Zorzi, M., “Performance Comparison of Routing Protocols for Ad Hoc Networks,” IEEE GLOBECOM, San Fransisco, CA (2003) pp. 1033–1037.Google Scholar
38.Wu, X., Xu, H., Sadjadpour, H. R. and Garcia-Luna-Aceves, J. J., “Proactive or Reactive Routing: A Unified Analytical Framework in MANETs,” Proceedings of 17th International Conference on Computer Communications and Networks (ICCCN'08), St. Thomas, VI (2008) pp. 1–7.Google Scholar
39.Perkins, C. E. and Royer, E. M., “Ad Hoc On-Demand Distance Vector Routing,” In: Mobile Computing Systems and Applications (1999) pp. 90–100.Google Scholar
40.Digi International (Online) (2007). Available at: http://alumni.ipt.pt/~lrafael/manual_XBee_Series2_OEM_RF-Modules_ZigBee.pdf. Accessed July 28, 2013.Google Scholar
41.Broch, J., Maltz, D. A., Johnson, D. B., Hu, Y.-C. and Jetcheva, J., “A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols,” Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom'98), Dallas, TX (1998) pp. 85–97.Google Scholar
42.Couceiro, M. S., Martins, F. M. L., Rocha, R. P. and Ferreira, N. M. F., “Mechanism and convergence analysis of a multi-robot swarm,” J. Intell. Robot. Syst. (2013; In Press).Google Scholar
43.Beni, G., “From Swarm Intelligence to Swarm Robotics,” Proceedings of the Swarm Robotics Workshop, Heidelberg, Germany (2004) pp. 1–9.Google Scholar
44.University of Technology. (Online) (2001). Available http://www.uamt.feec.vutbr.cz/robotics/simulations/amrt/simrobot_en.html. Accessed July 28, 2013.Google Scholar
45.Couceiro, M. S., Portugal, D. and Rocha, R. P., “A Collective Robotic Architecture in Search and Rescue Scenarios,” Proceedings of the 28th Symposium On Applied Computing (SAC2013), Coimbra, Portugal (2013) pp. 64–69.Google Scholar
46.Luca, D. D., Mazzenga, F., Monti, C. and Vari, M., “Performance Evaluation of Indoor Localization Techniques Based on RF Power Measurements from Active or Passive Devices,” EURASIP J. Appl. Signal Process. 2006, 1–11 (2006).Google Scholar
47.Sklar, B., “Rayleigh fading channels in mobile digital communication systems. I. Characterization,” IEEE Commun. Mag. 35 (7), 90–100 (1997).Google Scholar
48.Mondada, F., Bonani, M., Raemy, X., Pugh, J., Cianci, C., Klaptocz, A., Magnenat, S., Zufferey, J. C., Floreano, D. and Martinoli, A., “The E-Puck – A Robot Designed for Education in Engineering,” Proceedings of the 9th Conference on Autonomous Robot Systems and Competitions (2009) pp. 59–65.Google Scholar
49.Tsai, W., “Social structure of “coopetition” within a multiunit organization: Coordination, competition, and intraorganizational knowledge sharing,” Organ. Sci. 13 (2), 179–190 (2002).Google Scholar
50.Bonabeau, E., Dorigo, M. and Theraulaz, G., Swarm Intelligence: From Natural to Artificial Systems (Oxford University Press, New York, NY, 1999).Google Scholar