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.
Navigation in a @math square room filled with rectangle obstacles aligned with sides of the square was considered in @cite_15 @cite_36 @cite_3 @cite_25 . It was shown in @cite_15 that the navigation from a corner to the center of a room can be performed with a competitive ratio @math , only using tactile information (i.e., the robot modeled as a point sees an obstacle only when it touches it). No deterministic algorithm can achieve better competitive ratio, even with unlimited vision @cite_15 . For navigation between any pair of points, there is a deterministic algorithm achieving a competitive ratio of @math @cite_3 . No deterministic algorithm can achieve a better competitive ratio @cite_25 . However, there is a randomized approach performing navigation with a competitive ratio of @math @cite_36 .
@cite_36 @cite_15 @cite_25 @cite_3
2050037634 1983655539 2095383780 2100098951
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 problem of navigating through an unknownenvironment in which the obstacles are disjoint oriented rectanglesenclosed in an n x n square room. The task of navigatingalgorithm is to reach the center of the room starting from one of thecorners. While there always exists a path of length n , the best previously knownnavigating algorithm finds paths of length n 20 1nn . We give an efficient deterministicalgorithm which finds a path of length O ( n ln n ); this algorithm uses tactileinformation only. Moreover, we prove that any deterministic algorithmcan be forced to traverse a distance ofO( n ln n ), even if it uses visualinformation. Consider a robot that has to travel from a start location @math to a target @math 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 @math to @math to the length of the shortest (obstacle-free) path between @math and @math 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. We consider the problem of on-line searching on m rays. A point robot is assumed to stand at the origin of m concurrent rays one of which contains a goal g that the point robot has to find. Neither the ray containing g nor the distance to g are known to the robot. The only way the robot can detect g is by reaching its location. We use the competitive ratio as a measure of the performance of a search strategy, that is, the worst case ratio of the total distance DR traveled by the robot to find g to the distance D from the origin to g.We present a new proof of a tight lower bound of the competitive ratio for randomized strategies to search on m rays. Our proof allows us to obtain a lower bound on the optimal competitive ratio for a fixed m even if the distance of the goal to the origin is bounded from above.Finally, we show that the optimal competitive ratio converges to 1 +2(eα- 1) α2 m ∼ 1 + 2.1.544 m, for large m where α minimizes the function(ex- 1) x2.