Foraging Algorithms for Robotic Swarms

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