Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-22T08:53:15.466Z Has data issue: false hasContentIssue false

Cohesion and segregation in swarm navigation

Published online by Cambridge University Press:  07 April 2014

Vinicius Graciano Santos*
Affiliation:
Computer Science Department, Universidade Federal de Minas Gerais, Belo Horizonte, Minas Gerais 31270-901, Brazil
Luiz Chaimowicz
Affiliation:
Computer Science Department, Universidade Federal de Minas Gerais, Belo Horizonte, Minas Gerais 31270-901, Brazil
*
*Corresponding author. E-mail: [email protected]

Summary

The use of large groups of robots in the execution of complex tasks has received much attention in recent years. Generally called robotic swarms, these systems employ a large number of simple agents to perform different types of tasks. A basic requirement for most robotic swarms is the ability for safe navigation in shared environments. Particularly, two desired behaviors are to keep robots close to their kin and to avoid merging with distinct groups. These are respectively called cohesion and segregation, which are observed in several biological systems. In this paper, we investigate two different approaches that allow swarms of robots to navigate in a cohesive fashion while being segregated from other groups of agents. Our first approach is based on artificial potential fields and hierarchical abstractions. However, this method has one drawback: It needs a central entity which is able to communicate with all robots. To cope with this problem, we introduce a distributed mechanism that combines hierarchical abstractions, flocking behaviors, and an efficient collision avoidance mechanism. We perform simulated and real experiments to study the feasibility and effectiveness of our methods. Results show that both approaches ensure cohesion and segregation during swarm navigation.

Type
Articles
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.Abe, Y. and Yoshiki, M.. “Collision Avoidance Method for Multiple Autonomous Mobile Agents by Implicit CooperationProceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS), Maui, HI, Vol. 3 (2001) pp. 12071212.Google Scholar
2.Alonso-Mora, J., Breitenmoser, A., Beardsley, P. and Siegwart, R.. “Reciprocal Collision Avoidance for Multiple Car-Like RobotsProceedings of the IEEE International Conference on Robotics and Automation (ICRA), St. Paul, MN (2012), pp. 360366.Google Scholar
3.Alonso-Mora, J., Breitenmoser, A., Rufli, M., Beardsley, P. and Siegwart, R., “Optimal Reciprocal Collision Avoidance for Multiple Non-Holonomic RobotsIn:International Symposium on Distributed Autonomous Robotic Systems, Baltimore, MD (Martinoli, Alcherio, et al., eds), Springer Tracts in Advanced Robotics Series, Vol. 83 (Springer, Berlin, Germany, 2013) pp. 203216. ISBN: 978-3-642-32722-3.CrossRefGoogle Scholar
4.Balch, T. and Hybinette, M., “Social Potentials for Scalable Multirobot FormationsProceedings of the IEEE International Conference on Robotics and Automation (ICRA), San Francisco, CA (2000), pp. 7380.Google Scholar
5.Barnes, L., Fields, M. and Valavanis, K.. “Swarm formation control utilizing elliptical surfaces and limiting functionsIEEE Trans. Syst. Man Cybern. B Cybernetics, 39 (6), 14341445 (2009).Google Scholar
6.Belta, C. and Kumar, V.. “Abstraction and control for groups of robots.IEEE Trans. Robot. 20 (5), 865875 (2004).CrossRefGoogle Scholar
7.Belta, C., Pereira, G. and Kumar, V.. “Control of a Team of Car-Like Robots Using AbstractionsProceedings of the 42nd IEEE Conference on Decision and Control, Maui, HI, Vol. 2, (2003) pp. 15201525.Google Scholar
8.van den Berg, J., Guy, S. J., Lin, M. C. and Manocha, D.. “Reciprocal n-body collision avoidanceIn:Proceedings of the 14th International Symposium on Robotics Research (Pradalier, Cédric, et al, eds.), Springer Tracts in Advanced Robotics, Vol. 70 (Springer Berlin, Germany, 2011) pp. 319. ISBN: 978-3-642-19456-6.Google Scholar
9.van den Berg, J., Lin, M. and Manocha, D.. “Reciprocal Velocity Obstacles for Real-Time Multi-Agent NavigationProceedings of the IEEE International Conference on Robotics and Automation (ICRA), Pasadena, CA (2008) pp. 19281935.Google Scholar
10.Chaimowicz, L. and Kumar, V.. “Aerial Shepherds: Coordination Among UAVs and Swarms of RobotsIn:Proceedings of the 7th International Symposium on Distributed Autonomous Robotic Systems (Springer, Japan, 2007) pp. 243252. ISBN: 978-4-431-35869-5.Google Scholar
11.Chaimowicz, L., Michael, N. and Kumar, V.. “Controlling Swarms of Robots using Interpolated Implicit FunctionsProceedings of the IEEE International Conference on Robotics and Automation (ICRA), Barcelona, Spain (2005) pp. 24982503.Google Scholar
12.Chen, J., Gauci, M., Price, M. J. and Groß, R.. “Segregation in swarms of e-puck robots based on the brazil nut effectProceedings of the Autonomous Agents and MultiAgent Systems (AAMAS) Conference, Valencia, Venezuela (2012) pp. 163170.Google Scholar
13.Choset, H., Lynch, K. M., Hutchinson, S., Kantor, G. A., Burgard, W., Kavraki, L. E. and Thrun, S., Principles of Robot Motion: Theory, Algorithms, and Implementations (MIT Press, Cambridge, MA, 2005).Google Scholar
14.Claes, D., Hennes, D., Tuyls, K. and Meeussen, W.. “Multi-Robot Collision Avoidance with Localization UncertaintyProceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2012), Valencia, Spain (Jun 2012) pp. 147154.Google Scholar
15.Edelsbrunner, H., Kirkpatrick, D. and Seidel, R.. “On the shape of a set of points in the planeIEEE Trans. Inf. Theory 29 (4), 551559 (1983).Google Scholar
16.Egerstedt, M. and Hu, X.. “Formation constrained multi-agent controlIEEE Trans. Robot. Autom. 17 (6), 947951 (2001).CrossRefGoogle Scholar
17.Fiorini, P. and Shillert, Z.. “Motion planning in dynamic environments using velocity obstaclesInt. J. Robot. Res. 17, 760772 (1998).Google Scholar
18.Fulgenzi, C., Spalanzani, A. and Laugier, C.. “Dynamic Obstacle Avoidance in Uncertain Environment Combining pvos and Occupancy GridProceedings of the IEEE International Conference on Robotics and Automation (ICRA), Roma, Italy (2007) pp. 16101616.Google Scholar
19.Gerkey, B. P., Vaughan, R. T. and Howard, A.. “The Player/Stage Project: Tools for Multi-Robot and Distributed Sensor SystemsProceedings of the 11th International Conference on Advanced Robotics, Coimbra, Portugal (2003) pp. 317323.Google Scholar
20.Groß, R., Magnenat, S. and Mondada, F., “Segregation in Swarms of Mobile Robots Based on the Brazil Nut EffectProceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS), St. Louis, MO (2009) pp. 43494356.Google Scholar
21.Guy, S. J., Chhugani, J., Kim, C., Satish, N., Lin, M., Manocha, D. and Dubey, P., “Clearpath: Highly Parallel Collision Avoidance for Multi-Agent SimulationProceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, New Orleans, LA (ACM, New York, NY, 2009) pp. 177187.Google Scholar
22.He, L. and van den Berg, J.. “Meso-Scale Planning for Multi-Agent NavigationProceedings of the IEEE International Conference on Robotics and Automation (ICRA), Karlsruhe, Germany (2013) pp. 28392844.Google Scholar
23.Hou, S., Cheah, C. and Slotine, J.. “Dynamic Region Following Formation Control for a Swarm of RobotsProceedings of the IEEE International Conference on Robotics and Automation (ICRA), Kobe, Japan (2009) pp. 19291934.Google Scholar
24.Howard, A., Mataric, M. and Sukhatme, G., “Mobile Sensor Network Deployment Using Potential Fields: A Distributed, Scalable Solution to the Area Coverage ProblemProceedings of the 6th International Symposium on Distributed Autonomous Robotic Systems, Fukuoka, Japan (2002).Google Scholar
25.Hsieh, M. A., Kumar, V. and Chaimowicz, L.. “Decentralized controllers for shape generation with robotic swarmsRobotica 26 (5), 691701 (2008).CrossRefGoogle Scholar
26.Kamphuis, A. and Overmars, M., “Motion Planning for Coherent Groups of EntitiesProceedings of the IEEE International Conference on Robotics and Automation (ICRA), New Orleans, LA, vol. 4 (2004a) pp. 38153822.Google Scholar
27.Kamphuis, A. and Overmars, M. H.. “Finding Paths for Coherent Groups Using ClearanceProceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Grenoble, France (2004b), pp. 1928.Google Scholar
28.Kavraki, L., Svestka, P., Latombe, J.-C. and Overmars, M.. “Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration SpacesProceedings of the IEEE International Conference on Robotics and Automation (ICRA), Minneapolis, MN 12 (4), 566580 (1996).Google Scholar
29.Khatib, O., “Real-Time Obstacle Avoidance for Manipulators and Mobile RobotsProceedings of the IEEE International Conference on Robotics and Automation (ICRA), St. Louis, MO, Vol. 2 (1985) pp. 500505.Google Scholar
30.Kimmel, A., Dobson, A. and Bekris, K., “Maintaining Team Coherence Under the Velocity Obstacle FrameworkProceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, Valencia, Spain, Vol. 1 (2012) pp. 247256.Google Scholar
31.Koren, Y. and Borenstein, J., “Potential Field Methods and Their Inherent Limitations for Mobile Robot NavigationProceedings of the IEEE International Conference on Robotics and Automation (ICRA), Sacramento, CA (1991) pp. 13981404.Google Scholar
32.Kumar, M., Garg, D. and Kumar, V.. “Segregation of heterogeneous units in a swarm of robotic agentsIEEE Trans. Autom. Control 55 (3), 743748 (2010).Google Scholar
33.Li, T.-Y. and Chou, H.-C.. “Motion Planning for a Crowd of RobotsProceedings of the IEEE International Conference on Robotics and Automation (ICRA), Taipei, Taiwan, Vol. 3 (2003) pp. 42154221.Google Scholar
34.Lien, J.-M., Bayazit, O., Sowell, R., Rodriguez, S. and Amato, N., “Shepherding Behaviors.Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), New Orleans, LA (2004) pp. 41594164.Google Scholar
35.Lozano-Perez, T., “Spatial planning: A configuration space approachIEEE Trans. Comput. C-32 (2), 108120 (1983).Google Scholar
36.Luca, A. D., Oriolo, G. and Vendittelli, M., “Stabilization of the Unicycle via Dynamic Feedback LinearizationProceedings of the 6th IFAC Symposium on Robot Control, Vienna, Austria (2000) pp. 397402.Google Scholar
37.Marcolino, L. and Chaimowicz, L., “Traffic Control for a Swarm of Robots: Avoiding Group ConflictsProceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS), St. Louis, MO (2009) pp. 19491954.Google Scholar
38.de Medio, C. and Oriolo, G.. “Robot Obstacle Avoidance Using Vortex FieldsAdvances in Robot Kynematics (Stifter, S. and Lenarčič, J., eds.) (Springer-Verlag, Berlin, Germany, 1991), pp. 227235.Google Scholar
39.Michael, N., Belta, C. and Kumar, V.. “Controlling Three-Dimensional Swarms of RobotsProceedings of the IEEE International Conference on Robotics and Automation (ICRA), Orlando, Florida (2006) pp. 964969.Google Scholar
40.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 EngineeringProceedings of the 9th Conference on Autonomous Robot Systems and Competitions, Castelo Branco, Portugal, Vol. 1 (2009) pp. 5965.Google Scholar
41.Reif, J. H. and Wang, H.. “Social potential fields: A distributed behavioral control for autonomous robotsRobot. Auton. Syst. 27 (3), 171194 (1999).CrossRefGoogle Scholar
42.Reynolds, C. W., “Flocks, herds, and schools: A distributed behavioral model” Comput. Graph. (1987), pp. 2534.Google Scholar
43.Santos, V., Campos, M. and Chaimowicz, L., “On Segregative Behaviors Using Flocking and Velocity ObstaclesProceedings of the 11th International Symposyum on Distributed Autonomous Robotic Systems, Baltimore, MD (2012) pp. 377389 (electronic proceedings).Google Scholar
44.Santos, V. and Chaimowicz, L.. “Hierarchical Congestion Control for Robotic SwarmsProceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS), San Francisco, CA (2011) pp. 43724377.Google Scholar
45.Snape, J., van den Berg, J., Guy, S. and Manocha, D.. “The hybrid reciprocal velocity obstacleIEEE Trans. Robot. 27 (4), 696706 (2011).Google Scholar
46.Tan, K.-H. and Lewis, M.. “Virtual Structures for High-Precision Cooperative Mobile Robotic ControlProceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS), Osaka, Japan, Vol. 1 (1996) pp. 132139.Google Scholar