A popular way to evaluate algorithms that utilize different information has emerged from the algorithms community. The idea is to compute a competitive ratio, which places an on-line algorithm in competition with an algorithm that receives more information [674,892]. The idea can generally be applied to plans. First a cost is formulated, such as the total distance that the robot travels to solve a navigation task. A competitive ratio can then be defined as
A nice illustration of competitive ratio analysis and issues is provided by the lost-cow problem [60]. As shown in Figure 12.26a, a short-sighted cow is following along an infinite fence and wants to find the gate. This makes a convenient one-dimensional planning problem. If the location of the gate is given, then the cow can reach it by traveling directly. If the cow is told that the gate is exactly distance away, then it can move one unit in one direction and return to try the other direction if the gate has not been found. The competitive ratio in this case (the set of environments corresponds to all gate placements) is . What if the cow is told only that the gate is at least distance 1 away? In this case, the best strategy is a spiral search, which is to zig-zag back and forth while iteratively doubling the distance traveled in each direction, as shown in Figure 12.26b. In other words: left one unit, right one unit, left two units, right two units, left four units, and so on. The competitive ratio for this strategy turns out to be , which is optimal. This approach resembles iterative deepening, which was covered in Section 2.2.2.
Steven M LaValle 2020-08-14