positions for two robots are known, it can be determined if the path between the two

robots is obstructed. This is accomplished by checking for intersection between the robot

path and all obstacle line segments (see figure 2.9).

Shadow Area Calculation

 The shadow area is calculated by calling the linesintersect function to check for

possible intersection between the robot path and all obstacle line segments. The shadow

area function checks a single robot and an arbitrary point for possible intersection with

the obstacle line segments. If intersection exists, a matrix containing the combined

shadow area is set to '1' at that arbitrary point. This is done for all robots and the

combined shadow area is calculated simply by adding all of the cells set to '1' in the

shadow area matrix.

 The final algorithm proceeds to place the robots at grid points in the map and then

calculate the corresponding shadow area. However, a problem arises when a grid point

that lies within an obstacle is chosen. If a grid point contained within an obstacle is

selected, the algorithm will return the maximum shadow area for that particular robot

position, i.e. the total number of grid points for that particular map.

Preliminary results

 These methods have been applied to the single robot case in which a robot is placed at

a point and the shadow area is calculated for that particular position. After implementing

the linesintersect function for the single robot case all possible shadow areas are

calculated for a 50x50 grid in approximately 18 seconds. This is a vast improvement

from the previous method, which took seven minutes.

 An exhaustive search technique was applied to the two-robot case. Every possible

two-robot configuration was checked for the line-of-sight criteria and the corresponding