Foraging in the Presence of Obstacles

This thesis focuses on investigating searching algorithms which can solve the Ants Nearby Treasure Search (ANTS) Problem in the presence of obstacles. In the ANTS problem, there are k ants initially located at the origin in a two-dimensional grid. Pheromones are used as physical markers to allow the ants to perform a collaborative search. The target treasure is located at an unknown location at distance D from the origin. A simple deterministic foraging algorithm is provided first, which is improved later by using an additional marker to achieve a global termination. The Zig-Zag foraging algorithms and the Up-Down foraging algorithms solve the searching problem using one ant in a bounded environment with large obstacles. The spiral searching algorithms work with k ants in a wrap-around environment having randomly placed single cell obstacles. All algorithms are implemented in NetLogo and the corresponding simulations and explanations are presented by using examples.