HMEC: a robot number optimization algorithm for coverage path planning with heterogeneous multiple robots

Multi-robot coverage path planning (MCPP) has gained increasing attention in agricultural automation. In various agricultural applications, employing heterogeneous multi-robot systems to perform coverage tasks better aligns with complex task requirements. However, due to the heterogeneous characteristics and kinematic constraints, optimizing the number of robots and their coverage paths under task requirements remains a critical issue. Most existing MCPP methods are designed for homogeneous multi-robot systems or assume a fixed number of robots— the former inapplicable to heterogeneous systems, and the latter prone to wasting robotic resources. To address these challenges, this paper proposes a resource-optimized multi-robot coverage path planning method for heterogeneous multi-robot systems. First, we develop a generalized Reed-Shepp (RS) model. This model introduces intermediate variables to simplify the original RS path combinations, thereby reducing computational complexity. Second, we propose the HMEC algorithm specifically designed for heterogeneous multi-robot systems. HMEC optimizes the computation process through a knowledge reuse mechanism and is capable of determining the (near-)minimum heterogeneous robot fleet required to complete a coverage task, along with their corresponding coverage paths. We evaluate the HMEC algorithm against baseline and state-of-the-art algorithms under various target environments, robot fleets, and task requirements. Experimental results demonstrate that HMEC consistently identifies the minimum number of robots required to complete the coverage task, achieving up to 25% savings in robotic resources in the best-case scenario.