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