text: We study a new search problem on the plane involving a robot and an immobile treasure, initially placed at distance @math from each other. The length @math of an arc (a fence) within the perimeter of the corresponding circle, as well as the promise that the treasure is outside the fence, is given as part of the input. The goal is to device movement trajectories so that the robot locates the treasure in minimum time. Notably, although the presence of the fence limits searching uncertainty, the location of the fence is unknown, and in the worst case analysis is determined adversarially. Nevertheless, the robot has the ability to move in the interior of the circle. In particular the robot can attempt a number of chord-jump moves if it happens to be within the fence or if an endpoint of the fence is discovered. The optimal solution to our question can be obtained as a solution to a complicated optimization problem, which involves trigonometric functions, and trigonometric equations that do not admit closed form solutions. For the 1-Jump Algorithm, we fully describe the optimal trajectory, and provide an analysis of the associated cost as a function of @math . Our analysis indicates that the optimal k-Jump Algorithm requires that the robot has enough memory and computation power to compute the optimal chord-jumps. Motivated by this, we give an abstract performance analysis for every k-Jump Algorithm. Subsequently, we present a highly efficient Halving Heuristic k-Jump Algorithm that can effectively approximate the optimal k-Jump Algorithm, with very limited memory and computation requirements.
  @cite_14: We address the problem of mobile agents searching a ring network for a highly harmful item, a black hole, a stationary process destroying visiting agents upon their arrival. No observable trace of such a destruction will be evident. The location of the black hole is not known; the task is to unambiguously determine and report the location of the black hole. We answer some natural computational questions: How many agents are needed to locate the black hole in the ring ? How many suffice? What a-priori knowledge is required? as well as complexity questions, such as: With how many moves can the agents do it ? How long does it take ?
  @cite_8: We present an on-line strategy that enables a mobile robot with vision to explore an unknown simple polygon. We prove that the resulting tour is less than 26.5 times as long as the shortest watchman tour that could be computed off-line. Our analysis is doubly founded on a novel geometric structure called angle hull. Let D be a connected region inside a simple polygon, P. We define the angle hull of D, @math , to be the set of all points in P that can see two points of D at a right angle. We show that the perimeter of @math cannot exceed in length the perimeter of D by more than a factor of 2. This upper bound is tight.
  @cite_1: Assume that two robots are located at the centre of a unit disk. Their goal is to evacuate from the disk through an exit at an unknown location on the boundary of the disk. At any time the robots can move anywhere they choose on the disk, independently of each other, with maximum speed @math . The robots can cooperate by exchanging information whenever they meet. We study algorithms for the two robots to minimize the evacuation time: the time when both robots reach the exit. In [9] the authors gave an algorithm defining trajectories for the two robots yielding evacuation time at most @math and also proved that any algorithm has evacuation time at least @math . We improve both the upper and lower bounds on the evacuation time of a unit disk. Namely, we present a new non-trivial algorithm whose evacuation time is at most @math and show that any algorithm has evacuation time at least @math . To achieve the upper bound, we designed an algorithm which non-intuitively proposes a forced meeting between the two robots, even if the exit has not been found by either of them.
  @cite_3: 
  @cite_5: Consider k mobile robots inside a circular disk of unit radius. The robots are required to evacuate the disk through an unknown exit point situated on its boundary. We assume all robots having the same (unit) maximal speed and starting at the centre of the disk. The robots may communicate in order to inform themselves about the presence (and its position) or the absence of an exit. The goal is for all the robots to evacuate through the exit in minimum time.
  @cite_15: The paper suggests a new mathematical construction for the potential field used in the design of obstacle avoiding trajectories. The main benefits of the proposed construction are the quickness of minimum computation and the compensation for the main drawbacks specific to the ''traditional approaches'' belonging to the potential field method in general. The potential field definition and its minimum computation concept are presented. Next the concept is included in a design method for obstacle avoiding trajectories. The method is expressed in the form of an algorithm for obstacle avoidance. In the following step a state-space controller is designed in order to control the car along that trajectory. Digital simulation results obtained for the complete dynamic model of a car well validate the method.
  @cite_13: A practical real-time system for passive obstacle detection and avoidance is presented. Range information is obtained from stereo images by first computing a disparity picture from the image pair and extracting points above the ground plane. Then these points are projected onto the ground plane and an Instantaneous Obstacle Map (IOM) is obtained. The IOM is transformed into a one dimensional steering vector that represents the hindrance associated with steering in a particular direction and then a one dimensional search is performed on the steering vector for an angle with least hindrance. The steering direction and hindrance value are used to set the speed of the vehicle. This system has been implemented on the Mobile Perception Lab (MPL) at University of Massachusetts at Amherst with considerable success, running at 2 Hz for 256 spl times 240 sized images. >
summary: Search by multiple robots with communication capabilities has been considered in @cite_14 @cite_8 , while @cite_5 @cite_1 study the evacuation of @math robots searching for an exit located on the perimeter of a disk. The problem of finding trajectories for obstacle avoidance in both known and unknown terrains has been considered in several papers including @cite_13 @cite_3 @cite_15 .