next up previous
Next: The Autonomous Mobile Robot Up: wafr2004 Previous: wafr2004

Introduction

Visibility Problems. Visibility-based problems of surveying, guarding, or searching have a long-standing tradition in the area of computational optimization; they may very well be considered a field of their own. Using stationary positions for guarding a region is the well-known art gallery problem [15]. The watchman problem [18,19,3] asks for a short tour along which one mobile guard can see the entire region. If the region is unknown in advance, we are faced with the online watchman problem. For a simple polygon, Hoffmann et al.[7] achieve a constant competitive ratio of 26.5, while Albers et al. [1] show that no constant competitive factor exists for a region with holes, and unbounded aspect ratio. Kalyanasundaram and Pruhs [12] consider the problem in graphs and give a competitive factor of 16.

In the context of geometric searching, a crucial issue is the question of how to look around a corner: Given a starting position, and a known distance to a corner, how should one move in order to see a hidden object (or the other part of the wall) as quickly as possible? This problem was solved by Icking et al.[9,10] who show that an optimal strategy can be characterized by a differential equation that yields a competitive factor of 1.2121..., which is optimal. Note that actually using this solution requires numerical evaluation.

An Autonomous Mobile Robot. From the practical side, our work is motivated by an actual application in robotics: The Fraunhofer Institute for Autonomous Intelligent Systems (AIS) has developed autonomous mobile robots that can survey their environment by virtue of a high-resolution, 3D laser scanner [17]. By merging several 3D scans acquired in a stop, scan, plan, go fashion, the robot Kurt3D builds a virtual 3D environment that allows it to navigate, avoid obstacles, and detect objects[14]. This makes the visibility problems described above quite practical, as actually using good trajectories is now possible and desirable.

However, while human mobile guards are generally assumed to have full vision at all times, our autonomous robot has to stop and take some time for taking a survey of its environment. This makes the objective function (minimize total time to locate an object or explore a region) a sum of travel time and scan time; a somewhat related problem is searching for an object on a line in the presence of turn cost [5], which turns out to be a generalization of the classical linear search problem. Somewhat surprisingly, scan cost (however small it may be) causes a crucial difference to the well-studied case without scan cost, even in the limit of infinitesimally small scan times.

Independent from our work, the problem of looking around a corner in the presence of scan cost has been studied by Isler et al. [11], who described two deterministic strategies achieving competitive ratios of 3.14 and 2.22, and also considered a probabilistic framework dealing with prior knowledge about the possible values of corners. We improve on these results with a different, asymptotically optimal strategy, and prove a matching lower bound.

Other Related Work. Visbility-based navigation of robots involves a variety of different aspects. For example, Efrat et al. [4] study the task of developing strategies for tracking and capturing a visible target with known trajectory, while maintaining line-of-sight among obstacles. Kutulakos et al. [13] consider the task of vision-guided exploration, where the robot is assumed to move about freely in three dimensions, among various obstacles.

Our Results. The main objective of this paper is to demonstrate that technology has reached the stage of actually applying previous theoretical studies, at the same time triggering new algorithmic research. We hope that this will highlight the need for and the opportunities of closer interaction between theoreticians and practitioners. In particular, we describe the problem of online searching by a real autonomous robot, for an object (a chair) hidden behind a corner, which is at distance $ d$ from the robot's starting position. Our mathematical results are as follows:


Further documentation of our work is provided by a video [6] that is also available at the authors' web addresses.

The rest of this paper is organized as follows. In Section 2, we describe the technical details, properties, and capabilities of Kurt3D, an autonomous mobile robot that was used in our experiments. Section 3 provides mathematical results on the problem arising from Kurt searching for a hidden object. Section 4 gives a description of how our results are used in practice. The final Section 5 provides some directions for future research.



next up previous
Next: The Autonomous Mobile Robot Up: wafr2004 Previous: wafr2004
root 2004-06-02