1. Search Analysis

The search analysis asks the basic question: Can the area be searched with existing technology within the constraints given in the rules? Presumably it can be done because NASA would not want to pose a problem that is totally impossible. But the related question is: Can I, or a team I put together, do this within the constraints given the resources I have available? 

The basic information and constraints for the search are:
  • 80,000 square meters
  • 2 hours or (60 sec / min * 60 min / hr * 2 hr) 7200 seconds
  • 2 meter / second speed limit
Say you drop something on the floor and don't see it right away. You start to bend over or maybe get on your hands and knees to start searching carefully. You might start scanning back and forth in the search area. To get a feel for the sample search lets try that approach. To do that we'll assume we can see a 2 m2 area - because the 2 meter area makes the math really easy.

With that assumption we have (80,000 m2 / 2 m2) or 40,000 search units. (See the easy math!) The speed limit says we can search one 2 m2 section in a second so we can search the entire area in 40,000 seconds. That is a bit more than the 7200 secs allowed. A detailed search of the area is not possible.

Now turn the question around: how much area must be searched each second?

We have 80,000 mand 7,200 seconds so the area to examine is (80,000 m2 / 7,200 secs) 11.11  m2/ sec. (If you aren't easily visualizing this in meters, which I am not - that is  an area slightly larger than 33 ft x 3 ft, or, lets say, 100 ft2, using the very rough approximation that 1 m is 3 ft and 99 is close enough to 100 to not worry about the difference. Again, we're just trying to get a feel for the size of the project.) 

At this point you may be thinking, as I did, that this isn't bad. Surely a camera or two can see that area around the robot and see a sample. I went down that path for awhile before I realized: You have to search a new area every second!

Aren't we? Nope! If the cameras are looking at the circle around the robot than the new area is toward the front. Any area toward the rear has already been examined. In fact, when looking at a circular area only the area immediately inside the front of the scan circle is new area. In other words, only an area of 11.11  m2 in front of the robot is newly scanned every 2 seconds. With the robot moving at the maximum speed of 2 m / sec then a new 2 m deep area is scanned every second. Therefore, given a 2 m deep scanning area, that is how far the rover travels in 2 seconds, the necessary width is (11.1 m2 / 2 m) 5.6 m, or about 24 ft.

You can visualize this as 6 twin size mattresses setup as 3 end-to-end and two deep. That is slightly small but close enough. The problem is a camera needs to be pretty far away to capture that area which means the image of a sample is going to be very small and probably not detectable.

Up to this point the analysis parallels my original thinking in 2011, although back then the analysis was based on two cameras looking toward the side of the robot. I concluded the approach was feasible with a single robot bearing two cameras with each camera seeing 3 meters, or 6 meters with the adjustments mentioned later, to the side. I believe I was optimistic that a camera would see a sample at that range but, in my defense, I also did not know that the hard samples would be, apparently, small medallions. (I still have not seen an actual hard sample but the detailed descriptions suggests they are medallions.)

Today, I see the analysis as indicating a big problem based on using one camera. Why limit this to one? Because my operating system, Windows XP, only readily supports one camera and, also, the processing time required for vision processing makes using multiple cameras is not feasible with the single computer onboard the rovers.

Now we are going to cheat. I chatted with a 2012 entrant to determine how much of the park was used for the challenge and then examined satellite photos from Google to determine a rough estimate of the roving area. My estimate is an area around 22,000 m2. The 2012 entrant agreed based on his own estimates. Let's cheat by using that as the total search area.

From 30,000 feet, let's say the area is 1/4 of the original area (80,0000 / 4 or 20,0000) so we can divide the search area by 4. The width is now (5.6 m / 4) 1.4 m, or an area roughly the size of a twin bed. That looks really good. 

Unfortunately, there are additional issues to consider. 

How long is it going to take to pick up a sample once it is found? My original estimate was 5 minutes and that seemed to be reasonable watching the 2013 entrants acquire samples. There are 10 samples so it takes (10 x 5) 50 minutes to pick up samples. That effectively cuts the search time in half which increase the camera viewing area width to (1.4 m * 2) 2.8 m. 

Another factor is the time it takes to reach the starting platform once the last sample is acquired. Again, a 30,000 foot estimate is obtained by assuming the challenge area is a square (we know it is not but we are at 30,000 ft and trying to get a feel for the number) and the starting platform is in the center. How long does it take to get from a corner to the center? A 22,000 m square has a side of (22,000 m2 ^ 1/2) 148 m so the diagonal is ([2 * (148 m ^ 2)] ^ 1/2) 210 m. At 2 m / sec the rover takes (210 m /  2 m / sec) 105 seconds. Let's say that is 2 minutes but add some additional time for the rover to sight and align itself with the platform. Based on this we will just round our previous estimate for collecting samples to an hour. The leaves the search time also at an hour so we'll stay with a camera viewing area of  2 m / 2.8 m. 

Actual experiments on my driveway with a webcam show that the larger samples can be seen at the distance required to see that area.

Now that we worked some rough numbers lets refine them a bit by starting with the 22,000 m2 area and the revised time. These are still 30,000 foot numbers, just revised by the better understanding we have now.

We now recalculate the camera viewing area based on the new area and time. This new area is (22,000 m2 / 3600 s) 6.1 m2 which is an area 2 m x 3 m which closely matches our rougher estimate of 2 m / 2.8 m. Visualize this as three twin mattresses side-by-side.

Have we answered the feasibility question? A team with a fast robot and multiple cameras might be able to solve the challenge if everything works flawlessly. I have no confidence I could do this.

I do think that it is worth pursuing by myself by using multiple rovers.