COMPETITIVE COMPLEXITY OF MOBILE ROBOT ON-LINE MOTION PLANNING PROBLEMS

Abstract

This paper classifies common mobile robot on-line motion planning problems according to their competitive complexity. The competitiveness of an on-line algorithm measures its worst case performance relative to the optimal off-line solution to the problem. Competitiveness usually means constant relative performance. This paper generalizes competitiveness to any functional relationship between on-line performance and optimal off-line solution. The constants in the functional relationship must be scalable and may depend only upon on-line information. Given an on-line task, its competitive complexity class is a pair of lower and upper bounds on the competitive performance of all on-line algorithms for the task, such that the two bounds satisfy the same functional relationship. The paper classifies the following on-line motion planning problems into competitive classes: area coverage, navigation to a target, and on-line search for an optimal path. In particular, it is shown that navigation to a target whose position is either apriori known or recognized upon arrival belongs to a quadratic competitive complexity class. The hardest on-line problem involves navigation in unknown variable traversibility environments. Under certain restriction on traversibility, this last problem belongs to an exponential competitive complexity class.