Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 2008 | Published
Journal Article Open

Online Algorithms with Discrete Visibility - Exploring Unknown Polygonal Environments

Abstract

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

Additional Information

© 2008 IEEE. The extended abstract of this article was reported in two parts [2]. In [10], we claimed that the point robot computes at most r + 1 - h views to explore the entire free space. However, it has been pointed out that our bound mentioned in [10] is not correct. We have now modified the algorithm by positioning the next viewing point on a constructed edge. This restriction ensures that the algorithm computes at most r + 1 views. The authors would like to thank Sudeb Prasant Pal and Partha Goswami for their helpful comments.

Attached Files

Published - 04539724.pdf

Files

04539724.pdf
Files (887.4 kB)
Name Size Download all
md5:359f8f743dee9ba1ef74f210dbfedbfb
887.4 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 20, 2023