Navigating in unfamiliar geometric terrain
Navigating in unfamiliar geometric terrain
复制标题
在不熟悉的几何地形中导航
DOI：
10.1145/103418.103419
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
B. Schieber
中科院分区：
文献类型：
--
作者：
Avrim Blum;P. Raghavan;B. Schieber
考虑一个机器人，必须在具有不透明障碍物的环境中从开始位置$ s $转移到目标$ t $。机器人始终知道其当前的绝对位置和目标。但是，它不知道事先知道障碍的位置和范围。相反，它发现了遇到它们的障碍。我们将机器人从$ s $到$ t $的距离与现场$ s $和$ t $之间的最短（无障碍物）路径的长度相比。我们描述和分析机器人策略，以最大程度地减少各种场景的比率。特别是，我们考虑了与轴相一致的矩形障碍物，更一般方向的矩形障碍物以及两个维度和三个维度的凸形体的更广泛的凸体。对于许多这样的情况，我们的算法是最佳的恒定因素。我们研究具有与迷宫遍历研究有关的非凸障碍的场景。我们还展示了随机算法比确定性算法要好的场景。
Consider a robot that has to travel from a start location $s$ to a target $t$ in an environment with opaque obstacles that lie in its way. The robot always knows its current absolute position and that of the target. It does not, however, know the positions and extents of the obstacles in advance; rather, it finds out about obstacles as it encounters them. We compare the distance walked by the robot in going from $s$ to $t$ to the length of the shortest (obstacle-free) path between $s$ and $t$ in the scene. We describe and analyze robot strategies that minimize this ratio for different kinds of scenes. In particular, we consider the cases of rectangular obstacles aligned with the axes, rectangular obstacles in more general orientations, and wider classes of convex bodies both in two and three dimensions. For many of these situations, our algorithms are optimal up to constant factors. We study scenes with nonconvex obstacles, which are related to the study of maze traversal. We also show scenes where randomized algorithms are provably better than deterministic algorithms.