CBUG: A Quadratically Competitive Mobile Robot Navigation Algorithm

This paper is concerned with on-line navigation of a size D mobile robot in an unknown planar environment. The competitiveness of an on-line navigation algorithm measures its path length relative to the length of the optimal off-line path. While competitiveness usually means constant relative performance, it is generalized here to any functional relationship between on-line performance and optimal off-line solution. This paper describes a new on-line navigation algorithm, called CBUG, which requires constant memory and has a quadratic competitive performance. Moreover, it is shown that in general any online navigation algorithm must have at least a quadratic competitive performance. The CBUG algorithm achieves the quadratic lower bound and thus has optimal competitiveness.