Abstract

Foraging is the process of looking for food or other resources to survive in an unknown
environment. Various animals exhibit foraging behavior to fend for themselves in the
wild. We study group foraging by a swarm of robots, which involves collectively
searching for an object of interest and bringing it back to a central location.
We assume n robots start at the center of a g x g grid, called the nest. They are
looking for some units of food placed at an unknown location in the grid. When the
food is found by one of the robots, it must communicate its location to the other
robots, which then collectively transport the food back to the nest. We divide the
task into three phases: the exploration phase, in which the robots search different parts
of the grid for the food; the communication phase, in which robots communicate the
location of the food to each other; and the transportation phase, in which the robots
transport the food back to the nest. We give five novel algorithms for the exploration
phase, and analyze their competitive ratios. For the transportation phase, we give two
different approaches, and give a theoretical analysis of a simple case. We implemented
all our algorithms and compared their performance to an existing algorithm in the
literature.