Multi-vehicle refill scheduling with queueing

doi:10.1016/j.compag.2017.11.014

Multi-vehicle refill scheduling with queueing

2018-01-01

12

OA

AI

DOI：10.1016/j.compag.2017.11.014

Original

Save

View PDF

Abstract

En 中文

We consider the problem of refill scheduling for a team of vehicles or robots that must contend for access to a single physical location for refilling. The objective is to minimise time spent in travelling to/from the refill station, and also time lost to queuing (waiting for access). In this paper, we present principled results for this problem in the context of agricultural operations. We first establish that the problem is NP-hard and prove that the maximum number of vehicles that can usefully work together is bounded. We then focus on the design of practical algorithms and present two solutions. The first is an exact algorithm based on dynamic programming that is suitable for small problem instances. The second is an approximate anytime algorithm based on the branch and bound approach that is suitable for large problem instances with many robots. We present simulated results of our algorithms for three classes of agricultural work that cover a range of operations: spot spraying, broadcast spraying and slurry application. We show that the algorithm is reasonably robust to inaccurate prediction of resource utilisation rate, which is difficult to estimate in cases such as spot application of herbicide for weed control, and validate its performance in simulation using realistic scenarios with up to 30 robots.

Keywords:

Agricultural robotics

Multi-robot systems

Multi-robot scheduling

Multi-vehicle scheduling

Refill scheduling

Queuing

Spot spraying

Broadcast spraying

Slurry application

Multi-vehicle refill scheduling with queueing

Abstract

AI Summary

Journal

Organization