Abstract
Consider the problem of an agent or robot searching for the centre of a circle. The robot has only a limited number of capabilities. It can detect whether it is inside the circle or not. It can mark the point which it occupies. It can move in a straight line, possibly towards a mark which it made previously. It can make 90 and 180 degree turns. It can move to the middle of a line segment determined by two marked points, if it is on the line segment. The searcher starts at the edge of the circle. The objective is for the searcher to move to the centre of the circle as quickly as possible. This problem is inspired by the problem of finding a lost skier buried in an avalanche. The members of a ski party in the backcountry carry transceivers which are used for search and rescue in case of burial in an avalanche. A transceiver is a piece of equipment similar to a walkie-talkie that can either transmit or receive a radio signal. When a transceiver in receiver mode is within range of a transceiver in transmit mode, the receiver emits an audible signal. All transceivers are equipped with a volume knob. At the highest setting transceivers have a reception range of 10-35 meters.
Bibtex Entry
