Treasure hunt is the task of finding an inert target by a mobile agent in an unknown environment. We consider treasure hunt in geometric terrains with obstacles. Both the terrain and the obstacles are modeled as polygons and both the agent and the treasure are modeled as points. The agent navigates in the terrain, avoiding obstacles, and finds the treasure when there is a segment of length at most 1 between them, unobstructed by the boundary of the terrain or by the obstacles. The cost of finding the treasure is the length of the trajectory of the agent. We investigate the amount of information that the agent needs a priori in order to find the treasure at cost @math , where @math is the length of the shortest path in the terrain from the initial position of the agent to the treasure, avoiding obstacles. Following the paradigm of algorithms with advice, this information is given to the agent in advance as a binary string, by an oracle cooperating with the agent and knowing the whole environment: the terrain, the position of the treasure and the initial position of the agent. Information complexity of treasure hunt is the minimum length of the advice string (up to multiplicative constants) that enables the agent to find the treasure at cost @math . We first consider treasure hunt in regular terrains which are defined as convex polygons with convex @math -fat obstacles, for some constant @math . A polygon is @math -fat if the ratio of the radius of the smallest disc containing it to the radius of the largest disc contained in it is at most @math . For the class of regular terrains, we establish the exact information complexity of treasure hunt. We then show that information complexity of treasure hunt for the class of arbitrary terrains (even for non-convex polygons without obstacles, and even for those with only horizontal or vertical sides) is exponentially larger than for regular terrains.
Exploration of polygons by a robot with limited vision has been studied, e.g., in @cite_27 @cite_7 @cite_0 . In @cite_27 the authors described an on-line algorithm with competitive ratio @math , where @math is a quantity depending on the perimeter of the polygon, @math is the area seen by the robot, and @math is the area of the polygon. In @cite_0 the author studied exploration of the boundary of a terrain with limited vision. The cost of exploration of arbitrary terrains with obstacles, both for limited and unlimited vision, was studied in @cite_30 .
@cite_0 @cite_27 @cite_30 @cite_7
2044973122 2050037634 1970845672 1980745281
A mobile robot represented by a point moving in the plane has to explore an unknown flat terrain with impassable obstacles. Both the terrain and the obstacles are modeled as arbitrary polygons. We consider two scenarios: the unlimited vision, when the robot situated at a point p of the terrain explores (sees) all points q of the terrain for which the segment pq belongs to the terrain, and the limited vision, when we require additionally that the distance between p and q is at most 1. All points of the terrain (except obstacles) have to be explored and the performance of an exploration algorithm, called its complexity, is measured by the length of the trajectory of the robot. For unlimited vision we show an exploration algorithm with complexity O(P+Dk), where P is the total perimeter of the terrain (including perimeters of obstacles), D is the diameter of the convex hull of the terrain, and k is the number of obstacles. We do not assume knowledge of these parameters. We also prove a matching lower bound showing that the above complexity is optimal, even if the terrain is known to the robot. For limited vision we show exploration algorithms with complexity O(P+A+Ak), where A is the area of the terrain (excluding obstacles). Our algorithms work either for arbitrary terrains (if one of the parameters A or k is known) or for c-fat terrains, where c is any constant (unknown to the robot) and no additional knowledge is assumed. (A terrain T with obstacles is c-fat if R r= 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. 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. We consider the problem of localizing a robot in a known environment modeled by a simple polygon P. We assume that the robot has a map of P but is placed at an unknown location inside P. From its initial location, the robot sees a set of points called the visibility polygon V of its location. In general, sensing at a single point will not suffice to uniquely localize the robot, since the set H of points in P with visibility polygon V may have more than one element. Hence, the robot must move around and use range sensing and a compass to determine its position (i.e., localize itself). We seek a strategy that minimizes the distance the robot travels to determine its exact location. We show that the problem of localizing a robot with minimum travel is NP-hard. We then give a polynomial time approximation scheme that causes the robot to travel a distance of at most (k - 1)d, where k = |H|, which is no greater than the number of reflex vertices of P, and d is the length of a minimum length tour that would allow the robot to verify its true initial location by sensing. We also show that this bound is the best possible.