Genetic algorithms are directed, randomized search techniques that are conceptually
analogous to the process of natural selection in nature. A genetic algorithm library,
GAlib [12], will be implemented to perform reproduction, crossover, and mutation. The
initial population will be selected randomly and will consist of the desired number of
robots and their corresponding positions. Possible solutions are represented by fixed-
length strings of bits. The best-fit individuals are determined from a fitness function and
they are selected for reproduction to form the next generation. The fitness function
measures how well the map is covered by the current robot configuration. Mutation is
introduced by flipping a bit in a randomly chosen string. This process is repeated in
succession until an acceptable solution is obtained.
This research will use a genetic algorithm to determine the optimal robot positions for
a given map. It should be noted that while genetic algorithms provide a method to
finding a solution to a particular problem, it might not always be the globally 'optimal'
solution. The benefit of using genetic algorithms over other optimization techniques is
that the algorithm will always converge to a solution albeit not always optimal, and will
converge in a relatively short time for a fairly large search space. Traditional
optimization techniques require a well-defined function that can be optimized and
convergence can take time, but in most instances the optimal solution will be found.
This software will allow the user to select the number of robots and a map. The
program interprets the map and then proceeds to minimize the combined shadow area or
unseen area. This area is the cumulative area that cannot be seen by any of the robots for
the current robot configuration. Minimization of the shadow area allows for the
maximum map coverage. The algorithm will terminate when it obtains the optimal