next up previous
Next: Bounded Distances Up: Semi-Planar Performance Analysis and Previous: Rendezvous Search in the

A Competitive Ratio Examination

Assuming that we know the distance to the target for multiple (2) agent search it is easy enough to concoct the formula for the distance traveled according to each search strategy employed. If the distance is known to be d, the sensor radius r, then number of rendezvous attempts made will have to be tex2html_wrap_inline281 for strategy tex2html_wrap_inline265 , where tex2html_wrap_inline285 is the integer ceiling operator, the smallest integer not less than the operand. Then the distance traveled by each strategy, tex2html_wrap_inline287 is given by

align129

and the resulting curve is plotted, for example d=10, in figure 3.

   figure139
Figure 3: A plot of distances walked by the different strategies for a target at distance, d=10. Here r=1 WLOG. Note: the curve is monotonically increasing to the right after tex2html_wrap_inline295

Of course the competitive ratio that we are examining here is in comparison to the distance traveled by an omniscient agent that simply walks to the target and back to the rendezvous location, for distance of 2d.

displaymath275



M. Scott Burlington
Wed Apr 8 12:02:33 EDT 1998