Project Results

The class split up into three groups, each of which did this project independently. Here are abstracts and final project reports for each group:

  • Group 1 - In this paper we study different approaches to distributed search, or solving simply-connected perfect mazes, in both a simulator environment and on Khepera II robots. The goal is to explore the feasibility and advantages of ant-inspired distributed multi agent algorithms in comparison to single agent wall following. The rest part of this paper discusses our choice of algorithms: a simple wall follower, as well as a customized version of Tremaux's algorithm, which marks visited dead-end maze paths as blocked. We also consider variations on Tremaux's algorithm, studying the benets of the distributed method under different assumptions. In addition to computer simulation, we implement the wall following algorithm on Khepera II robots and attempt to understand the impact of noise on the robot's behavior. The results of our experiments show wall following to be good for small numbers of robots, or small mazes, but variations on Tremaux's algorithm are competitive as both of these numbers increase. (Report here.)
  • Group 2 - This work explores the problem of collective maze solving. Inspired by swarms of ants foraging for food, using pheromones to indicate better food sources, we implement two maze-solving algorithms which use stigmergy for communication. The key difference is that “bad” paths are marked in our solutions. We compare the performance of using pheromones to using agents themselves as means of communication. (Report here.)
  • Group 3 - The purpose of this paper is to investigate maze solving in the multi-robot setting and to compare several multi-agent maze solving algorithms that make differing assumptions on the inter-robot communication mechanism and capabilities. (Report here.)
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License