Robot Fence-Jumping Search

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.


Steau, Ioana Alexandra




We study a new search problem on the plane involving a robot and an immobile treasure, initially placed at distance 1 from each other. The length 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 devise movement trajectories so that the robot locates the treasure in minimum time. Although the presence of the fence limits searching uncertainty, the location of the fence is unknown, and 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. We study optimization and randomization algorithms using fence-jumping techniques.


Computer science




Carleton University

Thesis Degree Name: 

Master of Computer Science: 

Thesis Degree Level: 


Thesis Degree Discipline: 

Computer Science

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).