Multi-vehicle refill scheduling with queueing

Research output: Contribution to journalArticleScientificpeer-review

Researchers

  • Giovanni D'Urso
  • Stephen L. Smith
  • Ramgopal Mettu
  • Timo Oksanen

  • Robert Fitch

Research units

  • University of Sydney
  • University of Waterloo
  • Tulane University
  • University of Technology Sydney

Abstract

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.

Details

Original languageEnglish
Pages (from-to)44-57
Number of pages14
JournalComputers and Electronics in Agriculture
Volume144
Publication statusPublished - 1 Jan 2018
MoE publication typeA1 Journal article-refereed

    Research areas

  • Agricultural robotics, Broadcast spraying, Multi-robot scheduling, Multi-robot systems, Multi-vehicle scheduling, Queuing, Refill scheduling, Slurry application, Spot spraying

ID: 16443151