CautiousBug- a Competitive Algorithm for Sensory-based Robot Navigation
.
CautiousBug- a competitive algorithm for sensory-based robot navigation.
In IEEE/RSJ/GI International Conference on Intelligent Robots and Systems., 3:2757--2762, 2004
Online Version
A pdf version is available for download.
Abstract
Bug algorithms are a class of popular algorithms for autonomous robot navigation in unknown environments with local information. Very natural, with low memory requirements, Bug strategies do not yet allow any competitive analysis. The bound on the robot's path changes from scene to scene depending an the obstacles, even though a new obstacle may not alter the length of the shortest path. We propose a new competitive algorithm, CautiousBug, whose competitive factor has an order of O(dm-1), where d is the length of the optimal path from starting point S to a target point T. m = 2#Min-1 and #Min denote the number of the distance function isolated local minima points in the given environment. Simulations were performed to study the average competitive factor of the algorithm.
Co-authors
Bibtex Entry
@inproceedings{MagidR04i,
title = {CautiousBug- a competitive algorithm for sensory-based robot navigation},
author = {Evgeni Magid and Ehud Rivlin},
year = {2004},
booktitle = {IEEE/RSJ/GI International Conference on Intelligent Robots and Systems.},
volume = {3},
pages = {2757--2762},
abstract = {Bug algorithms are a class of popular algorithms for autonomous robot navigation in unknown environments with local information. Very natural, with low memory requirements, Bug strategies do not yet allow any competitive analysis. The bound on the robot's path changes from scene to scene depending an the obstacles, even though a new obstacle may not alter the length of the shortest path. We propose a new competitive algorithm, CautiousBug, whose competitive factor has an order of O(dm-1), where d is the length of the optimal path from starting point S to a target point T. m = 2#Min-1 and #Min denote the number of the distance function isolated local minima points in the given environment. Simulations were performed to study the average competitive factor of the algorithm.}
}