CBUG: A Quadratically Competitive Mobile Robot Navigation Algorithm

This paper is concerned with online navigation of a size D mobile robot in an unknown planar environment. A formal means for assessing algorithms for online tasks is competitiveness. For the navigation task, competitiveness measures the algorithm's path length relative to the optimal offline path length. While competitiveness usually means constant relative performance, it is measured in this paper in terms of a quadratic relationship between online performance and optimal offline solution. An online navigation algorithm for a size D robot called CBUG is described. The competitiveness of CBUG is analyzed and shown to be quadratic in the length of the shortest offline path. Moreover, it is shown that, in general, quadratic competitiveness is the best achievable performance over all online navigation algorithms. Thus, up to constants, CBUG achieves optimal competitiveness. The algorithm is improved with some practical speedups, and the usefulness of its competitiveness in terms of path stability is illustrated in office-like environments.

I. Introduction

This paper is concerned with the task where a mobile robot of size has to navigate to various prespecified targets in a planar environment populated by unknown obstacles. The robot has no a priori information about the environment but may locally acquire this information using its onboard sensors. This class of online problems has a wide range of applications in unstructured environments where the robot must detect obstacles during task execution. Examples are navigation to various targets for material and mail delivery in factories and offices [3], medicine distribution in hospitals [10], horticulture duty in greenhouses [1], and planetary exploration and sample acquisition [16], [21]. The most critical parameter in such tasks is physical travel time, and under a uniform velocity assumption, travel time corresponds to path length.