Access Restriction

Author Deng, Xiaotie ♦ Kameda, Tiko ♦ Papadimitriou, Christos
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1998
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword L1 metric ♦ Competitive algorithms ♦ Computational geometry ♦ Gallery tour ♦ On-line algorithms ♦ Polygon with obstacles ♦ Shortest path
Abstract We consider the problem faced by a robot that must explore and learn an unknown room with obstacles in it. We seek algorithms that achieve a bounded ratio of the worst-case distance traversed in order to see all visible points of the environment (thus creating a map), divided by the optimum distance needed to verify the map, if we had it in the beginning. The situation is complicated by the fact that the latter off-line problem (the problem of optimally verifying a map) is NP-hard. Although we show that there is no such “competitive” algorithm for general obstacle courses, we give a competitive algorithm for the case of a polygonal room with a bounded number of obstacles in it. We restrict ourselves to the rectilinear case, where each side of the obstacles and the room is parallel to one of the coordinates, and the robot must also move either parallel or perpendicular to the sides. (In a subsequent paper, we will discuss the extension to polygons of general shapes.)We also discuss the off-line problem for simple rectilinear polygons and find an optimal solution (in the L1 metric) in polynomial time, in the case where the entry and the exit are different points.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1998-03-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 45
Issue Number 2
Page Count 31
Starting Page 215
Ending Page 245

Open content in new tab

   Open content in new tab
Source: ACM Digital Library