Online Algorithms with Discrete Visibility - Exploring Unknown Polygonal Environments

The context of this work is the exploration of unknown polygonal environments with obstacles. Both the outer boundary and the boundaries of obstacles are piecewise linear. The boundaries can be nonconvex. The exploration problem can be motivated by the following application. Imagine that a robot has to explore the interior of a collapsed building, which has crumbled due to an earthquake, to search for human survivors. It is clearly impossible to have a knowledge of the building's interior geometry prior to the exploration. Thus, the robot must be able to see, with its onboard vision sensors, all points in the building's interior while following its exploration path. In this way, no potential survivors will be missed by the exploring robot. The exploratory path must clearly reflect the topology of the free space, and, therefore, such exploratory paths can be used to guide future robot excursions (such as would arise in our example from a rescue operation).

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).