A Graph Theoretic-Based Approach for Deploying Heterogeneous Multi-agent Systems with Application in Precision Agricultu
- PDF / 8,699,233 Bytes
- 15 Pages / 595.224 x 790.955 pts Page_size
- 75 Downloads / 208 Views
A Graph Theoretic-Based Approach for Deploying Heterogeneous Multi-agent Systems with Application in Precision Agriculture Mohammadreza Davoodi1
· Saba Faryadi1 · Javad Mohammadpour Velni1
Received: 16 March 2020 / Accepted: 17 September 2020 © Springer Nature B.V. 2020
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. Keywords Multi-robots deployment · Mixed time- and energy-based partitioning · Heterogeneity · Precision agriculture
1 Introduction Coverage control using cooperative multi-robot systems has received considerable attention in the past decade due to the many potential applications including in area exploration and mapping, search and rescue, and intruder detection [7, 18, 32, 38]. The main goal of coverage control is to explore an environment using multiple agents, which in general leads to a non-deterministic polynomial-time (NP)-hard problem [12]. The objective is then to find a local solution to the underlying locational optimization problem while This work was supported by the NSF/NIFA National Robotics Initiative (NIFA grant #2017-67021-25928). Mohammadreza Davoodi
[email protected] Saba Faryadi [email protected] Javad Mohammadpour Velni [email protected] 1
School of Electrical, Computer Engineering, University of Georgia, Athens, GA 30602, USA
ensuring the desired convergence. The Voronoi partitions and the Lloyd’s algorithm are now widely accepted as solution methods for the coverage problem [6, 20, 22, 24, 35], in which the centroid of each agent’s Voronoi cell is considered as the (locally) optimal position [15, 29, 30]. In this coverage approach, a given area is partitioned into Voronoi sub-regions, and each agent moves to the centroid of its Voronoi cell. Although there exist few other approaches for coordinating multiple mobile robots (
Data Loading...
