Paper Info
Title
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 a priori 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.
Year
DOI
Venue
2010
10.1142/S0218195910003293
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS
Keywords
DocType
Volume
Mobile robot, on-line motion planning, competitive complexity
Journal
20
Issue
ISSN
Citations 
3
0218-1959
12
PageRank 
References 
Authors
0.65
17
2
Name
Order
Citations
PageRank
Yoav Gabriely117812.13
Elon Rimon21128157.34