Abstract
This paper presents deployment strategies to achieve full visibility of 1.5D and 2.5D polyhedral environments for a team of mobile robots. Agents may only communicate if they are within line-of-sight. In 1.5D polyhedral terrains we achieve this by algorithmically determining a set of locations that the robots can occupy in a distributed fashion. We characterize the time of completion of the resulting algorithm, which is dependent on the number of peaks and the initial condition. In 2.5D polyhedral terrains we achieve full visibility by asynchronously deploying groups of agents who utilize graph coloring and may start from differential initial conditions. We characterize the total number of agents needed for deployment as a function of the environment properties and allow the algorithm to activate additional agents if necessary. We provide lower and upper bounds for the time of completion as a function of the number of vertices in a planar graph representing the environment. We illustrate our results in simulation and an implementation on a multi-agent robotics platform.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Almadhoun, R., Taha, T., Seneviratne, L., Zweiri, Y.: A survey on multi-robot coverage path planning for model reconstruction and mapping. SN Applied Sciences 1(8), 847 (2019)
Appel, K., Haken, W.: Every planar map is four colorable. Part i: Discharging. Illinois J. Math 21, 429–490 (1977)
Ashok, P., Fomin, F.V., Kolay, S., Saurabh, S., Zehavi, M.: Exact algorithms for terrain guarding. ACM Transactions on Algorithms (T,ALG) 14(2), 1–20 (2018)
Barenboim, L., Elkin, M.: Distributed graph coloring: Fundamentals and recent developments. Synthesis Lectures on Distributed Computing Theory 4(1), 1–171 (2013)
de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational geometry: Algorithms and Applications, 2 edn, Springer (2000)
Bose, P., Shermer, T., Toussaint, G., Zhu, B.: Guarding polyhedral terrains. Comput. Geom. 7, 173–185 (1997)
Bullo, F., Cortés, J., Martinez, S.: Distributed control of robotic networks. Applied mathematics series. Princeton University Press (2009)
Chiba, N., Nishizeki, T., Saito, N.: A linear 5-coloring algorithm of planar graphs. Journal of Algorithms 2, 317–327 (1981)
Chvátal, V.: A combinatorial theorem in plane geometry. Journal of Combinatorial Theory. Series B 18, 39–41 (1975)
Friedrichs, S., Hemmer, M., Schmidt, C.: A PTAS for the Continuous 1.5D Terrain Guarding Problem. In: Canadian Conference on Computational Geometry. Halifax, Nova Scotia, Canada, Electronic Proceedings (2014)
Ganguli, A., Cortés, J., Bullo, F.: Distributed deployment of asynchronous guards in art galleries. In: American Control Conference, pp 1416–1421, Minneapolis (2006)
Ghaffari, M., Lymouri, C.: Simple and near-optimal distributed coloring for sparse graphs. arXiv:1708.06275 (2017)
Gibson, M., Kanade, G., Krohn, E., Varadarajan, K.: Guarding terrains via local search. Journal of Computational Geometry 5(1), 168–178 (2014)
Hurtado, F., Loffler, M., Matos, I., Sacristan, V., Saumell, M., Silveria, R.I., Staals, F.: Terrain visibility with multiple viewpoints. In: International Symposium on Algorithms and Computation, pp 317–327, Jeonju, Korea (2014)
Khodakarami, F., Didehvar, F., Mohades, A.: 1.5 d terrain guarding problem parameterized by guard range. Theor. Comput. Sci. 661, 65–69 (2017)
Ma, A., Cortés, J.: Visibility-based distributed deployment of robotic teams in polyhedral terrains. In: ASME Dynamic Systems and Control Conference. Minneapolis, MN, DSCC2016-9820 (2016)
Maini, P., Gupta, G., Tokekar, P., Sujit, P.: Visibility-based monitoring of a path using a heterogeneous robot team. In: IEEE/RSJ Int. Conf. On Intelligent Robots & Systems, pp. 3765–3770 (2018)
Mesbahi, M., Egerstedt, M.: Graph theoretic methods in multiagent networks. Applied mathematics series. Princeton University Press (2010)
O’Rourke, J.: Art gallery theorems and algorithms. Oxford University Press (1987)
Patwary, M., Rahman, S.: Minimum face-spanning subgraphs of plane graphs. AKCE International Journal of Graphs and Combinatorics 7(2), 133–150 (2010)
Pickem, D., Glotfelter, P., Wang, L., Mote, M., Ames, A., Feron, E., Egerstedt, M.: The Robotarium: A remotely accessible swarm robotics research testbed. In: IEEE Int. Conf. On Robotics and Automation, pp. 1699–1706. Singapore (2017)
Robertson, N., Sanders, D.P., Seymour, P., Thomas, R.: Efficiently four-coloring planar graphs. In: ACM Symposium on Theory of Computing, pp 571–575, Philadelphia (1996)
Savkin, A.V., Huang, H.: Proactive deployment of aerial drones for coverage over very uneven terrains: a version of the 3d art gallery problem. Sensors 19(6), 1438 (2019)
Shermer, T.C.: Recent results in art galleries. Proc. IEEE 80(9), 1384–1399 (1992)
Veenstra, K., Obraczka, K.: Guiding Sensor-Node Deployment over 2.5D Terrain, In: 2015 IEEE International Conference on Communications (ICC), pp. 6719–6725 (2015)
Williams, M.H.: A linear algorithm for colouring planar graphs with five colours. Comput. J. 28, 78–81 (1985)
Acknowledgments
This work was supported by ONR Award N00014-16-1-2836.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
A preliminary version of this paper appeared as [16] at the 2016 ASME Dynamics and Control Conference.
Rights and permissions
About this article
Cite this article
Ma, A., Cortés, J. Distributed Multi-agent Deployment for Full Visibility of 1.5D and 2.5D Polyhedral Terrains. J Intell Robot Syst 100, 1111–1127 (2020). https://doi.org/10.1007/s10846-020-01229-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10846-020-01229-6