Abstract
We show how Embedded Graph Grammars (EGGs) are used to specify local interaction rules between mobile robots in a natural manner. This formalism allows us to treat local network topologies, geometric transition conditions, and individual robot dynamics and control modes in a unified framework. An example EGG is demonstrated that achieves sensor coverage in a provably stable and correct manner. The algorithm results in a global network with a lattice-like triangulation.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Egerstedt, M., Brockett, R.W.: Feedback can reduce the specification complexity of motor programs. IEEE Transactions on Automatic Control (2003)
Manikonda, V., Krishnaprasad, P.S., Hendler, J.: Languages, Behaviors, Hybrid Architectures and Motion Control. In: Mathematical Control Theory (1998)
Lygeros, J., et al.: Dynamical properties of hybrid automata. IEEE Transactions on Automatic Control (2003)
Henzinger, T.: The theory of hybrid automata. In: 11th Annual Symposium on Logic in Computer Science (LICS), IEEE Computer Society Press, Los Alamitos (1996)
Klavins, E., Burden, S., Napp, N.: Optimal rules for programmed stochastic self-assembly. In: Robotics: Science and Systems, Philadelphia, PA (2006)
Cortes, J., Martinez, S., Bullo, F.: Robust rendezvous for mobile autonomous agents via proximity graphs in arbitrary dimensions. IEEE Transactions on Automatic Control (2006)
Leonard, N., Fiorelli, E.: Virtual leaders, artificial potentials and coordinated control of groups. In: Proc. of the IEEE Conference on Decision and Control, IEEE Computer Society Press, Los Alamitos (2001)
McNew, J.M., Klavins, E.: Locally interacting hybrid sytems using embedded graph grammars. In: Proc. of the Conference on Decision and Control (2006)
Smith, B., et al.: Embedded graph grammars for multi-robot coordination. In: Proc. of the International Conference on Robotics and Automation, submitted (2007)
Shucker, B., Murphey, T., Bennett, J.K.: A method of cooperative control using occasional non-local interactions. In: Proc. of the American Control Conference (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
McNew, JM., Klavins, E., Egerstedt, M. (2007). Solving Coverage Problems with Embedded Graph Grammars. In: Bemporad, A., Bicchi, A., Buttazzo, G. (eds) Hybrid Systems: Computation and Control. HSCC 2007. Lecture Notes in Computer Science, vol 4416. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-71493-4_33
Download citation
DOI: https://doi.org/10.1007/978-3-540-71493-4_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-71492-7
Online ISBN: 978-3-540-71493-4
eBook Packages: Computer ScienceComputer Science (R0)