Background for Robotic Exploration
In this article, the robot is assumed to be a point. The polygonal environment is assumed to consist of a boundary polygon, , populated with polygonal obstacles, or holes with a total of vertices. The assemblage of and the obstacles is the polygon (see Figure 1). The free space, is the complement of the holes in the interior of . Prior to the exploration of , the robot has no knowledge of the geometry of , the number of edges, or the number of holes. However, we make three assumptions. 1) We assume that the robot can locate its current location relative to a fixed reference configuration. Denote as the coordinates of the robot relative to this fixed reference. 2) The robot can compute the visibility polygon, from a viewing point . The visibility polygon is the set of all points of visible from [9] and is bounded by some combination of polygonal edges, partial polygonal edges, and constructed edges as shown in Figure 1. For example, is a constructed edge, is a partial polygonal edge, and is a polygonal edge. One of the endpoints of a constructed edge is always a reflex vertex. 3) We assume that the viewing point and two endpoints of every constructed edge in are collinear. For example, , , and are collinear (see Figure 1).