A Caltech Library Service

Online Algorithms with Discrete Visibility - Exploring Unknown Polygonal Environments

Ghosh, Subir Kumar and Burdick, Joel Wakeman and Bhattacharya, Amitava and Sarkar, Sudeep (2008) Online Algorithms with Discrete Visibility - Exploring Unknown Polygonal Environments. IEEE Robotics and Automation Magazine, 15 (2). pp. 67-76. ISSN 1070-9932.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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

Item Type:Article
Related URLs:
URLURL TypeDescription
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.
Subject Keywords:Polygon exploration, online algorithms, point robot, competitive ratio, art gallery problem, discrete visibility, visibility polygon
Issue or Number:2
Record Number:CaltechAUTHORS:20190612-155948867
Persistent URL:
Official Citation:S. K. Ghosh, J. W. Burdick, A. Bhattacharya and S. Sarkar, "Online Algorithms with Discrete Visibility - Exploring Unknown Polygonal Environments," in IEEE Robotics & Automation Magazine, vol. 15, no. 2, pp. 67-76, June 2008. doi: 10.1109/MRA.2008.921542
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:96353
Deposited By: Tony Diaz
Deposited On:13 Jun 2019 15:00
Last Modified:03 Oct 2019 21:21

Repository Staff Only: item control page