Solving the Exploration's Problem with Several Creatures More Efficiently

摘要

We are presenting results of the creature's exploration problem with several creatures. The task of the creatures is to visit all empty cells in an environment with obstacles in shortest time and with a maximum of efficiency. The cells are arranged in a regular 2D grid and the underlying processing model is a Cellular Automaton (CA). We have investigated the question how many creatures and which algorithm should be used in order to fulfill the task most efficiently with lowest cost. We use a set of 10 different behaviors (algorithms) for the creature which have proved to be very efficient in the case where only one creature explores the environment. These algorithms were found by exhaustive search and evaluation by the aid of hardware (FPGA) implementation. Different environments and a varying number (1 to 64) of creatures were used in simulations in order to evaluate the cooperative work and efficiency. It turned out that for each environment a certain number of creatures and a certain algorithm is cost optimal in terms of work units. The total amount of work using one creature with the best algorithm X is many cases higher than the work using n creature with an adequate algorithm Y. Using several creatures, positive conflicts arise which may help to solve the problem more efficiently.