The exact cost of exploring streets with a CAB

dc.contributor.authorLopez-Ortiz, Alejandro
dc.contributor.authorSchuierer, Sven
dc.date.accessioned2023-03-01T18:27:14Z
dc.date.available2023-03-01T18:27:14Z
dc.date.issued1998
dc.description.abstractA fundamental problem in robotics is to compute a path for a robot from its current location to a given target. In this paper we consider the problem of a robot equipped with an on-board vision system searching for a target t in an unknown environment. We assume that the robot is located at a points in a polygon that belongs to the well investigated class of polygons called streets. A street is a simple polygon where s and t are located on the polygon boundary and the part of the polygon boundary from s to t is weakly visible to the part from t to s and vice versa. We are interested in the ratio of the length of the path traveled by the robot to the length of the shortest path from s to t which is called the competitive ratio of the strategy. In this work we present the first exact analysis of the continuous angular bisector (CAB) strategy, which has been considered several times before, and show that it has a competitive ratio of ≃ 1.6837 in the worst case.
dc.description.copyrightCopyright @ Alejandro Lopez-Ortiz and Sven Schuierer, 1998.
dc.identifier.urihttps://unbscholar.lib.unb.ca/handle/1882/14717
dc.rightshttp://purl.org/coar/access_right/c_abf2
dc.subject.disciplineComputer Science
dc.titleThe exact cost of exploring streets with a CAB
dc.typetechnical report

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
item.pdf
Size:
482.29 KB
Format:
Adobe Portable Document Format

Collections