Search Analysis

This analysis looks at the issue in finding the samples. It assumes that cameras on the robot can see a sample that is within 3 meters of each side of the robot and, hopefully, up to twice that distance. This was discussed in the Area Analysis.

To keep this analysis simple assume the search area is a rectangle that is 18 meters tall and as many meters wide as to make it 80,000 m2. I'll use compass directions (north, south, east, west) to describe the motion of the robot to avoid confusion with positions relative to the robot (left, right, front back).

Start the robot on the west and south corner moving toward the east. The right search area (the right 'wing') of the robot keeps just in contact with the south boundary. When the robot reaches the east boundary it has to turn north, move twice the wing length, i.e 2 x 3m, and make a turn toward the west to resume the search. Similarly, when it then reaches the west boundary it turns north and then to the east. At the east boundary, it is finished. There are few inefficiencies in this search.

When the robot turns to head north its right wing is searching an area that is outside the search area. Its left wing is searching an area already examined during the eastward movement. The left wing searches a new area once it leaves the already examined area, but that area will be searched again once the robot moves to the west. The same duplication occurs at the west boundary turn.

This inefficiency isn't bad with only three search stripes, but if the search area is a square [ sqrt(80,000) = 283m) there are (283m / 6m) 47 stripes. That is a big waste of time. (If the search area is taller than wide you search north/south instead of east/west.)

A first thought is to stop before reaching the boundary and turn so the right wing, as described above, is just contacting the boundary. This saves time but it also will miss a tiny bit of the search area in the corner of the two boundaries. There is likely to be a maneuver that turns the robot slightly toward the south boundary so the circular swing of the right wing catches the corner. The slight area missed on the left wing in this maneuver will be caught as the robot moves north.

The above highlights one of the issues with searching.

In the competition, the robot starts from a platform somewhere within the search area, not at a boundary. Let's consider that example.

Assume the starting platform is in the center of the rectangle described above. The robot leaves the platform again heading east. It reaches the east boundary and again heads north and then west. It passes the starting platform, encounters the west boundary, and turns south. It has two possible approaches. It can continue south until it reaches the south boundary and then turn east until it reaches the east boundary. This leaves the area to the west of the starting platform unexamined and no way to reach there without covering an already searched area.

The second option is the robot immediately turns east until it reaches the platform where it turns south. Regardless of how it proceeds it is going to leave an area unsearched with the need to traverse a searched area to reach it.

Right now (11 Sept 2012) I don't have a good analysis of search that indicates how it should be done. There are many other possible approaches (spiral out from the platform, spiral in from boundaries) but they all encounter the same issues of duplicate coverage in turns or leaving holes that can only be reached by traversing already covered areas. I'll be doing some research on this.