Ignorance is Not Bliss: An Analysis of Central-Place Foraging Algorithms
Abhinav Aggarwal, Diksha Gupta, William F. Vining, G. Matthew Fricke, Melanie E. Moses
Abstract
Central-place foraging (CPF) is a canonical task in collective robotics with applications to planetary exploration, automated mining, warehousing, and search and rescue operations. We compare the performance of three Central-Place Foraging Algorithms (CPFAs), variants of which have been shown to work well in real robots: spiral-based, rotating-spoke, and random-ballistic. To understand the difference in performance between these CPFAs, we define the price of ignorance and show how this metric explains our previously published empirical results. We obtain upper-bounds for expected complete collection times for each algorithm and evaluate their performance in simulation. We show that site-fidelity (i.e. returning to the location of the last found target) and avoiding search redundancy are key-factors that determine the efficiency of CPFAs. Our formal analysis suggests the following efficiency ranking from best to worst: spiral, spoke, and the stochastic ballistic algorithm.
BibTeX
@inproceedings{iros2019_ignoranceisnotbl,
title = {Ignorance is Not Bliss: An Analysis of Central-Place Foraging Algorithms},
author = {Abhinav Aggarwal and Diksha Gupta and William F. Vining and G. Matthew Fricke and Melanie E. Moses},
booktitle = {IROS 2019},
year = {2019}
}