Abstract
This paper presents a framework for going from specifications to implementations of decentralized control strategies for multi-robot systems. In particular, we show how the use of Embedded Graph Grammars (EGGs) provides a tool for characterizing local interaction and control laws. This paper highlights some key implementation aspects of the EGG formalism, and develops and discusses experimental results for a hexapod-based multi-robot system, as well as a multi-robot system of wheeled robots.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Brockett, R. W. (1988). On the computer control of movement. In IEEE international conference on robotics and automation, New York, April 1988 (pp. 534–540).
Cortes, J., Martinez, S., & Bullo, F. (2006). Robust rendezvous for mobile autonomous agents via proximity graphs in arbitrary dimensions. IEEE Transactions on Automatic Control, 51(8), 1289–1298.
Egerstedt, M., & Brockett, R. (2003). Feedback can reduce the specification complexity of motor programs. IEEE Transactions on Automatic Control, 48(2), 213–223.
Hendrickx, J. M., Anderson, B. D. O., Delvenne, J.-C., & Blondel, V. D. (2007). Directed graphs for the analysis of rigidity and persistence in autonomous agent systems, International Journal of Robust and Nonlinear Control.
Henneberg, L. (1911). Die graphische statik der starren systeme.
Henzinger, T. (1996). The theory of hybrid automata. In 11th annual symposium on logic in computer science (LICS). Los Alamitos: IEEE Comput. Soc.
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.
Klavins, E. (2004). A language for modeling and programming cooperative control systems. In IEEE international conference on robotics and automation.
Klavins, E., Ghrist, R., & Lipsky, D. (2004). Graph grammars for self-assembling robotic systems. In IEEE international conference on robotics and automation.
Lygeros, J., Tomlin, C., & Sastry, S. (1999). Controllers for reachability specifications for hybrid systems. Automatica, 35(3), 349–370.
Manikonda, V., Krishnaprasad, P. S., & Hendler, J. (1998). Languages, behaviors, hybrid architectures and motion control. In Mathematical control theory (pp. 199–226). Berlin: Springer.
McLurkin, J., & Smith, J. (2004). Distributed algorithms for dispersion in indoor environments using a swarm of autonomous mobile robots. In Distributed autonomous robotic systems conference.
McLurkin, J., & Yamins, D. (2005). Dynamic task assignment in robot swarms. In Robotics: science and systems conference.
McLurkin, J., Smith, J., Frankel, J., Sotkowitz, D., Blau, D., & Schmidt, B. (2006). Speaking swarmish: Human-robot interface design for large swarms of autonomous mobile robots. In AAAI spring symposium.
McNew, J. M., & Klavins, E. (2005). A grammatical approach to cooperative control: The scouts and intruders example. In S. Butenko, R. Murphey, & P. Pardalos (Eds.), Cooperative control and optimization.
McNew, J.-M., & Klavins, E. (2006). Locally interacting hybrid systems with embedded graph grammars. In 45th IEEE conference on decision and control (pp. 6080–6087).
McNew, J. M., Egerstedt, M., & Klavins, E. (2007). Solving coverage problems with embedded graph grammars. In Lecture notes in computer science : Vol. 4416. Hybrid systems: computation and control, Pisa, Italy (pp. 413–427). Berlin: Springer.
Mesbahi, M. (2005). On state-dependent dynamic graphs and their controllability properties. IEEE Transactions on Automatic Control, 50(3), 387–392.
Samad, T., & Bay, J. (2006). Multiagent sensing and control: Surveillance and reconnaissance for urban operations. In Mathematical theory of networks and systems, Kyoto, Japan.
Smith, B. S., Egerstedt, M., & Howard, A. (2007). Automatic generation of persistent formations for multi-agent networks under range constraints. In Proceedings of the first international conference on robot communication and coordination.
Smith, B. S., Egerstedt, M., & Howard, A. (2008). Automatic deployment and formation control of decentralized multi-agent networks. In Proceedings of the IEEE international conference on robotics and automation.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Smith, B., Howard, A., McNew, JM. et al. Multi-robot deployment and coordination with Embedded Graph Grammars. Auton Robot 26, 79–98 (2009). https://doi.org/10.1007/s10514-008-9107-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10514-008-9107-6