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
1971116024 1983655539 1992876208 2095383780
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. We study several versions of the shortest-path problem when the map is not known in advanced, but is specified dynamically. We are seeking dynamic decision rules that optimize the worst-case ratio of the distance covered to the length of the (statically) optimal path. We describe optimal decision rules for two cases: Layered graphs of bounded width, and two-dimensional scenes with unit square obstacles. The optimal rules turn out to be intuitive, common-sense heuristics. For slightly more general graphs and scenes, we show that no bounded ratio is possible. We also show that the computational problem of devising a strategy that achieves a given worst-case ratio to the optimum path in a graph is a universal two-person game, and thus PSPACE-complete, whereas optimizing the expected ratio is #P-hard. 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.