Algorithms for Mobile Agents with Limited Capabilities (PDF)

This work deals with geometric problems and the use of limited capability agents for these problems. Exploration and guarding problems have been extensively studied in computational geometry. The basic task is to monitor an environment (a polygon) either with a mobile guard or with a number of sta¬tionary guards (or guards with hard restrictions on the allowed movements). Though all these problems are easy to formulate—and have real-world interpretations that vividly illustrate them—some of these problems (as the classical art gallery problem) are hard to solve. The task of exploring an environment becomes more challenging if the environment is not known in advance, that is, there is no given ground plan and only areas that have already been visibly encountered by the explorer are known. Problems with this kind of uncertainty are called online problems. For offline problems the ground plan of the environment is known in advance. In this work we study one offline exploration problem and one exploration and guarding problem in the offline and online version, where the focus is on the latter. For our problems we do not deal with “almighty” explorers, but face limits on their perceptive capabilities. Other types of geometric problems can exploit this kind of limited agents: We present an exact and fast algorithm for an image analysis task with polyomino-shaped objects on a grid.
Distributed Vision with Smart Pixels. An important image analysis task is the identification of objects present in a given image. If these objects are to be processed automatically, not only the identification of the objects themselves, but also of certain attributes is of interest. The images we treat are pixel (grid) images, with a possibly huge number of intertwined objects. We make an assumption on the pixels: Besides light detection, they can perform simple computations and communicate with their grid neighbors (smart pixels). Our goal is to extract attributes, such as the center of gravity or orientation, for each object in the image. In particular, we want to give a fast algorithm for this task. We show how the use of mobile agents, mimicked by messages sent by the pixels, allows for an exact algorithm—an agent sweep—that can cope with intertwined objects. We present how the attributes can be expressed as moments (of a random variable, considering the pixels as a point set in R2) and how the sweep accumulates the necessary information. For the algorithm we prove a runtime of only O(W + H), with W and H being the width and height of the smallest bounding box for an object, respectively.
Exploration with a Myopic Watchman with Discrete Vision. In the classical watchman route problem the task is to find a shortest tour for an explorer such that each point of a given polygon is visible from at least one point of the tour. For this problem exact algorithms for a variety of polygon classes exist. We study this problem with two restrictions on the watchman’s capabilities: The scan range is limited and visibility information can only be acquired at discrete points, “scanpoints”. A scanpoint in combination with all points of the polygon that can be seen from the point and lie within its scan range form a scan. The scans must fully cover the given polygon. The cost for a tour of this watchman is a linear combination of tour length and number of scan points used along this tour. We show that this problem is NP-hard and present approximation algorithms for different variants: A 2.5-approximation for rectilinear grid polygons and unit L∞ scan range, a 4-approximation for rectilinear grid polygons and unit L2 scan range and a
πr πr π
max(21 , + + )-approximation for the case of general polygons, an L2
4 a 22
scan range and a bounded ratio r/a between visibility range r and minimum side length a. All these approximation algorithms can also be applied for the bicriteria version, that is, approximating the scan number and the tour length separately.
Exploration and Triangulation with a Swarm of Robots. The art gallery problem asks for a minimum number of (stationary) guards that al¬low for visibility coverage of a given polygon. Another classical problem in computational geometry is triangulation: The partition of a given polygon into triangles. We study a guarding problem linked to both of these problems: A swarm of agents with limited communication range has to establish a triangulated network in a given polygon. The edge lengths are limited to the communication range. The task is not only to give the positions, but to move to these locations in a connected fashion. Our goal is to minimize the number of robots used for this task, or, if the number of robots is limited, to cover as much area as possible with the triangulation established by these robots. We present NP-hardness results for both problems. Our focus is on the online variants, we give a lower bound of 6/5 for the competitive ratio for any strategy for the first problem, as well as a 3-competitive strategy. We prove that the second problem does not allow for a constant competitive ratio.