Intelligent Algorithms for Maze Exploration and Exploitation

Abstract

The purpose of the project is to develop maze exploration algorithms for a multi-agent system, using autonomous robots, that allows the agents to successfully navigate through an array of different mazes based on the game Theseus and the Minotaur. Theseus and the Minotaur is a maze game in which Theseus tries to get to the exit of each maze without being eaten by the Minotaur. For every one move Theseus makes, the Minotaur can make two. The mazes become progressively harder as each maze is completed. A single intelligence system is made up of algorithms for the robots to use in order successfully simulate the Theseus and the Minotaur game. One of the robots will represent Theseus and the other robot will represent the Minotaur. The Theseus robot will work to traverse the maze while avoiding the Minotaur. The Minotaur robot will work to navigate through the maze in order to catch the Theseus robot. The goal is to have the robots simulate the Theseus and the Minotaur game without any human interaction. The next step is to validate the developed algorithms in a laboratory experiment using programmable mobile robots.