Abstract
We study the topology of the space of coverings for a metric tree with disks embedded in the tree. Focusing on the coverings with excess one disk, we prove that its topological structure is that of a Cayley graph of the permutation group \(S_{n}\). What follows is a centralized algorithm for stabilizing periodic swarm coverings based upon feedback control with the designed vector field on a maximal subset of the space, removing discontinuity loci.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We point out that coverage on a graph in our setting is completely different from [4], where the coverage on a graph means exhaustive visits of all the vertices of the graph.
- 2.
We use cycle \((\sigma _{1},\ldots ,\sigma _{n+1})\) to indicate the visiting order for each disk on every edge of \(\varGamma _{n}\). This notation is not to be confused with a permutation. It means \(\sigma _{i}\) is switched with \(\sigma _{i+1}\) and \(\sigma _{n+1}\) is switched with \(\sigma _{1}\).
References
Anthony Armstrong, M.: Basic Topology. McGraw-Hill, London (1979)
Baryshnikov, Y.: On the spaces of coverings. Preprint (2014)
Baryshnikov, Y., Shapiro, B.: How to run a centipede: a topological perspective. Geometric Control Theory and sub-Riemannian Geometry. Springer INdAM Series, vol. 5, pp. 37–51 (2014)
Batalin, M.A., Sukhatme, G.: The design and analysis of an efficient local algorithm for coverage and exploration based on sensor network deployment. IEEE Trans. Robot. 23(4), 661–675 (2007)
Björner, A.: Subspace arrangements. In: First European Congress of Mathematics, pp. 321–370. Springer, Berin (1994)
Cheng, W., Li, Z., Liu, K., Liu, Y., Li, X., Liao, X.: Sweep coverage with mobile sensors. In: IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2008, pp. 1–9 (2008)
Choset, H.: Coverage for robotics-a survey of recent results. Ann. Math. Artif. Intell. 31(1–4), 113–126 (2001)
Cortés, J., Bullo, F.: Nonsmooth coordination and geometric optimization via distributed dynamical systems. SIAM Rev. 51(1), 163–189 (2009)
Cortes, J., Martinez, S., Karatas, T., Bullo, F.: Coverage control for mobile sensing networks. IEEE Trans. Robot. Autom. 20(2), 243–255 (2004)
Farbe, M.: Invitation to topological robotics. Eur. Math. Soc. (2008)
Friedman, J.: On Cayley graphs on the symmetric group generated by transpositions. Combinatorica 20(4), 505–519 (2000)
Ghrist, R.W., Koditschek, D.E.: Safe cooperative robot dynamics on graphs. SIAM J. Control Optim. 40(5), 1556–1575 (2002)
Guo, Y., Qu, Z.: Coverage control for a mobile robot patrolling a dynamic and uncertain environment. In: Fifth World Congress on Intelligent Control and Automation, WCICA 2004, vol. 6, pp. 4899–4903 (2004)
Hatcher, A.: Algebraic Topology. Cambridge UP, Cambridge (2002)
Hubenko, A., Fonoberov, V.A., Mathew, G., Mezic, I.: Multiscale adaptive search. IEEE Trans. Syst. Man, Cybern. Part B: Cybern. 41(4), 1076–1087 (2011)
Liberzon, D.: Switching in Systems and Control. Springer, Berlin (2003)
Mathew, G., Mezić, I.: Metrics for ergodicity and design of ergodic dynamics for multi-agent systems. Phys. D: Nonlinear Phenom. 240(4), 432–442 (2011)
Michael LaValle, S.: Planning Algorithms. Cambridge University Press, Cambridge (2006)
Schwager, M., Rus, D., Slotine, J.-J.: Decentralized, adaptive coverage control for networked robots. Int. J. Robot. Res. 28(3), 357–375 (2009)
Song, D., Kim, C.-Y., Yi, J.: On the time to search for an intermittent signal source under a limited sensing range. IEEE Trans. Robot. 27(2), 313–323 (2011)
Sontag, E.D.: Stability and stabilization: discontinuities and the effect of disturbances. Nonlinear Analysis, Differential Equations and Control, pp. 551–598. Springer, Berlin (1999)
Wang, H.: Covering with excess one: seeing the topology. arXiv:1312.7477 [math.GN] (2013)
Zharnitsky, V., Baryshnikov, Y.: Search on the brink of chaos. Nonlinearity 25, 3023–3047 (2012)
Zhong, M., Cassandras, C.G.: Distributed coverage control and data collection with mobile sensor networks. IEEE Trans. Autom. Control 56(10), 2445–2455 (2011)
Ziegler, G.M.: Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer, New York (1995)
Acknowledgments
The research is sponsored by ONR under the grant number N00014-11-1-0178.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Wang, H., Chen, C., Baryshnikov, Y. (2015). A Topological Perspective on Cycling Robots for Full Tree Coverage. In: Akin, H., Amato, N., Isler, V., van der Stappen, A. (eds) Algorithmic Foundations of Robotics XI. Springer Tracts in Advanced Robotics, vol 107. Springer, Cham. https://doi.org/10.1007/978-3-319-16595-0_38
Download citation
DOI: https://doi.org/10.1007/978-3-319-16595-0_38
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-16594-3
Online ISBN: 978-3-319-16595-0
eBook Packages: EngineeringEngineering (R0)