The Meeting problem for @math searchers in a polygon @math (possibly with holes) consists in making the searchers move within @math , according to a distributed algorithm, in such a way that at least two of them eventually come to see each other, regardless of their initial positions. The polygon is initially unknown to the searchers, and its edges obstruct both movement and vision. Depending on the shape of @math , we minimize the number of searchers @math for which the Meeting problem is solvable. Specifically, if @math has a rotational symmetry of order @math (where @math corresponds to no rotational symmetry), we prove that @math searchers are sufficient, and the bound is tight. Furthermore, we give an improved algorithm that optimally solves the Meeting problem with @math searchers in all polygons whose barycenter is not in a hole (which includes the polygons with no holes). Our algorithms can be implemented in a variety of standard models of mobile robots operating in Look-Compute-Move cycles. For instance, if the searchers have memory but are anonymous, asynchronous, and have no agreement on a coordinate system or a notion of clockwise direction, then our algorithms work even if the initial memory contents of the searchers are arbitrary and possibly misleading. Moreover, oblivious searchers can execute our algorithms as well, encoding information by carefully positioning themselves within the polygon. This code is computable with basic arithmetic operations, and each searcher can geometrically construct its own destination point at each cycle using only a compass. We stress that such memoryless searchers may be located anywhere in the polygon when the execution begins, and hence the information they initially encode is arbitrary. Our algorithms use a self-stabilizing map construction subroutine which is of independent interest.
Another problem for robots in polygons is the search for an intruder, e.g., @cite_17 @cite_26 , where one robot tries to escape while others have to locate it. This setting is clearly quite different, as in the Meeting problem we consider robots that cooperate to achieve a common goal.
@cite_26 @cite_17
2048209083 2050037634 2099745962 1970845672
We consider the problem of mapping an initially unknown polygon of size n with a simple robot that moves inside the polygon along straight lines between the vertices. The robot sees distant vertices in counter-clockwise order and is able to recognize the vertex among them which it came from in its last move, i.e. the robot can look back. Other than that the robot has no means of distinguishing distant vertices. We assume that an upper bound on n is known to the robot beforehand and show that it can always uniquely reconstruct the visibility graph of the polygon. Additionally, we show that multiple identical and deterministic robots can always solve the weak rendezvous problem in which the robots need to position themselves such that all of them are mutually visible to each other. 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 L 1 metric) in polynomial time, in the case where the entry and the exit are different points. Two mobile agents (robots) have to meet in an a priori unknown bounded terrain modeled as a polygon, possibly with polygonal obstacles. Robots are modeled as points, and each of them is equipped with a compass. Compasses of robots may be incoherent. Robots construct their routes, but the actual walk of each robot is decided by the adversary that may, e.g., speed up or slow down the robot. We consider several scenarios, depending on three factors: (1) obstacles in the terrain are present, or not, (2) compasses of both robots agree, or not, (3) robots have or do not have a map of the terrain with their positions marked. The cost of a rendezvous algorithm is the worst-case sum of lengths of the robots' trajectories until they meet. For each scenario, we design a deterministic rendezvous algorithm and analyze its cost. We also prove lower bounds on the cost of any deterministic rendezvous algorithm in each case. For all scenarios these bounds are tight. We consider the exploration of a simple polygon P by a robot that moves from vertex to vertex along edges of the visibility graph of P. The visibility graph has a vertex for every vertex of P and an edge between two vertices if they see each other—that is, if the line segment connecting them lies inside P entirely. While located at a vertex, the robot is capable of ordering the vertices it sees in counterclockwise order as they appear on the boundary, and for every two such vertices, it can distinguish whether the angle between them is convex (l π) or reflex ( > π). Other than that, distant vertices are indistinguishable to the robot. We assume that an upper bound on the number of vertices is known. We obtain the general result that a robot exploring any locally oriented, arc-labeled graph G can always determine the base graph of G. Roughly speaking, this is the smallest graph that cannot be distinguished by a robot from G by its observations alone, no matter how it moves. Combining this result with various other techniques allows the ability to show that a robot exploring a polygon P with the preceding capabilities is always capable of reconstructing the visibility graph of P. We also show that multiple identical, indistinguishable, and deterministic robots of this kind can always solve the weak rendezvous problem in which they need to position themselves such that they mutually see each other—for instance, such that they form a clique in the visibility graph.