Exploring an unknown polygonal environment with bounded visibility

Bhattacharya, Amitava ; Ghosh, Subir Kumar ; Sarkar, Sudeep (2001) Exploring an unknown polygonal environment with bounded visibility Lecture Notes in Computer Science, 2073 . pp. 640-648. ISSN 0302-9743

Full text not available from this repository.

Official URL: http://www.springerlink.com/content/0h2k105ckrxkhp...

Related URL: http://dx.doi.org/10.1007/3-540-45545-0_74


This paper integrates constraints from visual processing and robot navigation into the well-studied computational geometry problem of exploring unknown polygonal environments with obstacles. In particular, we impose two constraints. First, we consider a robot with limited visibility, which can reliably "see" its environment only within a certain range R. Second, we allow the computation of visibility only from discrete number of points on the path. Both these constraints arise from real life cost constraints associated with robotic exploration and robot vision processing. We present an online algorithm for exploration under such constraints and show that the maximum number of views needed to explore the unknown polygon (with obstacles) P, is bounded by ]2×Perimeter(P)/R]+2×Area(P)/R2+3n + 3n, where n is the number of sides of the polygon. We also show that the competitive ratio of the algorithm is 6π+ 6π+4r+3n/max([Area(P)/ΤR2,[Perimeter(P)-2Rr)/2ΤR].

Item Type:Article
Source:Copyright of this article belongs to Springer.
Keywords:Bounded Visibility; Discrete Visibility; Polygonal Environment; Exploration; On-line Algorithm
ID Code:76292
Deposited On:31 Dec 2011 08:57
Last Modified:31 Dec 2011 08:57

Repository Staff Only: item control page