search space (map) and location of obstacles within the map, and communication. While

maximum coverage of the map is desired it is also necessary that the communication

repeater robots maintain line-of-sight communication among one another. Optimal

positioning of all robots requires maximizing coverage while maintaining line-of-sight

communication. When positioning the robots they must be able to communicate to at

least one additional robot. Lastly, the scope of this research is limited to a two-

dimensional case where the region of operation and the obstacles can be represented by

polygons.

 One area of concern involving this type of simulation problem is the need to have a

general approach such that it can apply to different maps, a different number of robots

and different types (shapes) of obstacles. This problem is addressed by modeling the

map using a grid-based approach. The map is discretized into grid points and the

obstacles within the map are represented by a series of grid points. The robots can be

placed at any of these grid points as long as they do not coincide with an obstacle. This

method eliminates the need for calculating complex areas and provides a simplified

technique for representing the desired map.

 Optimization

 Another area of concern is the how to determine the position of all robots such that

they satisfy the stated requirements. This is an optimal placement problem and can be

solved using many different techniques and an overview of these techniques is presented

in Chapter 3. There are several variables in this problem: number of robots, size of the

search space (map), and number of obstacles in the map. Due to this variability, genetic

algorithms will be used to determine optimal robot positioning.