A Graph Theoretic-Based Approach for Deploying Heterogeneous Multi-agent Systems with Application in Precision Agriculture

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.