Abstract
The main goal of this paper is to address the problem of deploying a team of heterogeneous, autonomous robots in a partially known environment. To handle such arbitrary environments, we first represent them as a weighted directed graph. Then, a new partitioning algorithm is given that is capable of capturing the heterogeneity of robots in terms of the speed and onboard power. It is shown that the proposed partitioning method assigns a larger subgraph to a robot that has more resources or better capabilities compared to its neighbors. Next, a distributed deployment strategy is proposed to optimally distribute robots on the graph with the aim of monitoring specified regions of interest in the environment. It will be proved that the proposed combined partitioning and deployment strategy is an optimal solution in the sense that any other arbitrary partition than the proposed one results in a larger coverage cost, and that our deployment strategy also minimizes the considered cost. Moreover, the application of the proposed methodology for monitoring an agricultural field is studied, where a series of simulations and experimental studies are carried out to demonstrate that the proposed approach can yield an optimal partitioning and deployment and offer promise to be used in practice.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Abdul Razak, R., Srikant, S., Chung, H.: Decentralized and adaptive control of multiple nonholonomic robots for sensing coverage. Int. J. Robust Nonlinear Control 28(6), 2636–2650 (2018)
Bhandari, S., Raheja, A., Green, R.L., Do, D.: Towards collaboration between unmanned aerial and ground vehicles for precision agriculture (2017)
Busemeyer, L., Mentrup, D., Moller, K., Wunder, E., Alheit, K., Hahn, V., Maurer, H., Reif, J., Wurschum, T., Muller, J., Rahe, F., Ruckelshausen, A.: Breedvision—a multi-sensor platform for non-destructive field-based phenotyping in plant breeding. Sensors 13(3), 2830–2847 (2013)
Conesa-Muñoz, J., Valente, J., Del Cerro, J., Barrientos, A., Ribeiro, A.: A multi-robot sense-act approach to lead to a proper acting in environmental incidents. Sensors 16(8), 1269 (2016)
Cortes, J.: Coverage optimization and spatial load balancing by robotic sensor networks. IEEE Trans. Autom. Control 55(3), 749–754 (2010)
Cortes, J., Martinez, S., Karatas, T., Bullo, F.: Coverage control for mobile sensing networks. IEEE Trans. Robot. Autom. 20(2), 243–255 (2004)
Cortez, J., Egerstedt, M.: Coordinated control of multi-robot systems: a survey. SICE J. Control Meas. Syst. Integr. 10(6), 495–503 (2017). https://doi.org/10.9746/jcmsi.10.495
Davoodi, M., Velni, J.M., Li, C.: Coverage control with multiple ground robots for precision agriculture. ASME Mech. Eng. 140(06), S4–S8 (2018)
Del Cerro, J., Barrientos, A., Sanz, D., Valente, J.: Aerial fleet in RHEA project: a high vantage point contributions to robot 2013. In: ROBOT2013: First Iberian Robotics Conference, pp 457–468. Springer (2014)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269–271 (1959)
Durham, J.W., Carli, R., Frasca, P., Bullo, F.: Discrete partitioning and coverage control for gossiping robots. IEEE Trans. Robot. 28(2), 364–378 (2012)
Garey, M., Johnson, D., Witsenhausen, H.: The complexity of the generalized Lloyd - max problem. IEEE Trans. Inf. Theory 28(2), 255–256 (1982)
Gonzalez-de Santos, P., Ribeiro, A., Fernandez-Quintanilla, C., Lopez-Granados, F., Brandstoetter, M., Tomic, S., Pedrazzi, S., Peruzzi, A., Pajares, G., Kaplanis, G., Perez-Ruiz, M., Valero, C., del Cerro, J., Vieri, M., Rabatel, G., Debilde, B.: Fleets of robots for environmentally-safe pest control in agriculture. Precis. Agric. 18(4), 574–614 (2017)
Guruprasad, K., Ghose, D.: Heterogeneous locational optimisation using a generalised voronoi partition. Int. J. Control 86(6), 977–993 (2013)
Gusrialdi, A., Hirche, S., Asikin, D., Hatanaka, T., Fujita, M.: Voronoi-based coverage control with anisotropic sensors and experimental case study. Intell. Serv. Robot. 2, 195–204 (2009)
iRobot Create2. https://www.irobot.com/
Javanmard Alitappeh, R., Pereira, G.A.S., Araujo, A.R., Pimenta, L.C.A.: Multi-robot deployment using topological maps. J. Intell. Robot. Syst. 86(3), 641–661 (2017)
Kantaros, Y., Thanou, M., Tzes, A.: Distributed coverage control for concave areas by a heterogeneous robot–swarm with visibility sensing constraints. Automatica 53, 195–207 (2015)
Kim, J., Son, H.I.: A voronoi diagram-based workspace partition for weak cooperation of multi-robot system in orchard. IEEE Access 8, 20676–20686 (2020)
Lee, S., Diaz-Mercado, Y., Egerstedt, M.: Multirobot control using time-varying density functions. IEEE Trans. Robot. 31(2), 489–493 (2015)
Li, W., Liu, Y.: Dynamic coverage control for mobile robot network with limited and nonidentical sensory ranges. In: IEEE International Conference on Robotics and Automation (ICRA), pp 775–780 (2017)
Lloyd, S.: Least squares quantization in PCM. IEEE Trans. Inf. Theory 28(2), 129–137 (1982)
Marier, J., Rabbath, C.A., Léchevin, N.: Health-aware coverage control with application to a team of small uavs. IEEE Trans. Control Syst. Technol. 21(5), 1719–1730 (2013)
Martinez, S.: Distributed interpolation schemes for field estimation by mobile sensor networks. IEEE Trans. Control Syst. Technol. 18(2), 491–500 (2010)
Marvelmind GPS. https://marvelmind.com/
Miah, M.S., Knoll, J.: Area coverage optimization using heterogeneous robots: algorithm and implementation. IEEE Trans. Instrum. Meas. 67(6), 1380–1388 (2018)
Mueller-Sim, T., Jenkins, M., Abel, J., Kantor, G.: The robotanist: a ground-based agricultural robot for high-throughput crop phenotyping. In: IEEE International Conference on Robotics and Automation (ICRA), pp 3634–3639 (2017)
Nolan, P., Paley, D.A., Kroeger, K.: Multi-uas path planning for non-uniform data collection in precision agriculture. In: IEEE Aerospace Conference, pp 1–12 (2017)
Nowzari, C., Cortes, J.: Self-triggered coordination of robotic networks for optimal deployment. Automatica 48(6), 1077–1087 (2012)
Pavone, M., Arsie, A., Frazzoli, E., Bullo, F.: Equitable partitioning policies for robotic networks. In: 2009 IEEE International Conference on Robotics and Automation, pp 2356–2361 (2009)
Pierson, A., Figueiredo, L.C., Pimenta, L.C., Schwager, M.: Adapting to sensing and actuation variations in multi-robot coverage. Int. J. Robot. Res. 36(3), 337–354 (2017)
Rabbath, C.A., Léchevin, N.: Coverage with a team of wheeled mobile robots. J. Intell. Robot. Syst. 78(3–4), 553–575 (2015)
Roldan, J.J., Garcia-Aunon, P., Garzon, M., de Leon, J., del Cerro, J., Barrientos, A.: Heterogeneous multi-robot system for mapping environmental variables of greenhouses. Sensors 16(7), 1–24 (2016)
Ru, Y., Martinez, S.: Coverage control in constant flow environments based on a mixed energy–time metric. Automatica 49(9), 2632–2640 (2013)
Schwager, M., Rus, D., Slotine, J.J.: Decentralized, adaptive coverage control for networked robots. Int. J. Rob. Res. 28(3), 357–375 (2009)
Shafiekhani, A., Kadam, S., Fritschi, F.B., de Souza, G.N.: Vinobot and vinoculer: two robotic platforms for high-throughput field phenotyping. Sensors 17(214), 1–23 (2017)
Sharifi, F., Chamseddine, A., Mahboubi, H., Zhang, Y., Aghdam, A.G.: A distributed deployment strategy for a network of cooperative autonomous vehicles. IEEE Trans. Control Syst. Technol. 23(2), 737–745 (2015)
Song, C., Fan, Y.: Coverage control for mobile sensor networks with limited communication ranges on a circle. Automatica 92, 155–161 (2018)
Sun, S., Li, C., Paterson, A.: In-field high-throughput phenotyping of cotton plant height using lidar. Remote Sens. 9(4), 1–21 (2017)
Tokekar, P., Hook, J.V., Mulla, D., Isler, V.: Sensor planning for a symbiotic UAV and UGV system for precision agriculture. IEEE Trans. Robot. 32(6), 1498–1511 (2016)
Yan, M., Guo, Y., Zuo, L., Yang, P.: Information-based optimal deployment for a group of dynamic unicycles. Int. J. Control Autom. Syst. 16(4), 1824–1832 (2018)
Yun, S.K., Rus, D.: Distributed coverage with mobile robots on a graph: locational optimization and equal-mass partitioning. Robotica 32(2), 257–277 (2014)
Zhang, J., Zhou, P., Ma, L.: Coverage control of multiple heterogeneous mobile robots with nonholonomic constraints. In: 35th Chinese Control Conference (CCC), pp 6272–6277 (2016)
Zuo, L., Chen, J., Yan, W., Shi, Y.: Time-optimal coverage control for multiple unicycles in a drift field. Inf. Sci. 373, 571–580 (2016)
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This work was supported by the NSF/NIFA National Robotics Initiative (NIFA grant #2017-67021-25928).
Rights and permissions
About this article
Cite this article
Davoodi, M., Faryadi, S. & Velni, J.M. A Graph Theoretic-Based Approach for Deploying Heterogeneous Multi-agent Systems with Application in Precision Agriculture. J Intell Robot Syst 101, 10 (2021). https://doi.org/10.1007/s10846-020-01263-4
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10846-020-01263-4