Multi-robot coverage planning with resource constraints for horticulture applications

T. Patten, R. Fitch, S. Sukkarieh
A multi-robot system is a team of autonomous robots that work together to perform a given task. Multi-robot systems have great potential for use in horticulture applications. Robots have the potential to perform crop surveillance, efficiently apply fertiliser and chemical inputs, and perform weeding and harvesting. In all of these tasks, robots must visit many trees or plants over a large area in a time-sensitive manner. Multi-robot systems are appropriate because many robots can work efficiently in parallel. However, a fundamental challenge to be addressed is how to coordinate the motion of many robots while also respecting resource constraints such as limited energy storage, liquid payload, and harvested product storage. The algorithmic problem of multi-robot coverage planning with resource constraints is similar to the NP-hard vehicle routing problem, but the computational complexity of general resource-constrained coverage remains unknown. We show that one variant of this problem, coverage with fixed replenishment stations and zero queuing time, can be solved in polynomial time using area partitioning and graph search. We present algorithms and analysis for this variant, and demonstrate the behaviour of our algorithms in simulation experiments with up to 100 robots. The robots cover a large area organised as a collection of sub-areas with defined boundaries and row orientations. Robots plan to visit one of several possible replenishment stations in order to satisfy resource constraints. Each robot may replenish itself multiple times throughout its mission. This work is practically applicable to systems where refill time is short relative to working time.
Patten, T., Fitch, R. and Sukkarieh, S. (2016). Multi-robot coverage planning with resource constraints for horticulture applications. Acta Hortic. 1130, 655-662
DOI: 10.17660/ActaHortic.2016.1130.97
agricultural robotics, motion planning, refill planning, resource-constrained coverage

Acta Horticulturae