<< Kod*lab Publications

# Exact Robot Navigation in Geometrically Complicated but Topologically Simple Spaces

#### *Proceedings of the IEEE International Conference on Robotics and Automation*, May 1990

Elon Rimon and D. E. Koditschek

Yale University

Full PDF | Penn ScholarlyCommons | Web Link

Abstract |

A navigation function is an artificial potential energy function on a robot configuration space (C-space) which encodes the task of moving to an arbitrary destination without hitting any obstacle. In particular, such a function possesses no spurious local minima. In this paper we construct navigation functions on forests of stars: geometrically complicated C-spaces that are topologically indistinguishable from a simple disc punctured by disjoint smaller discs, representing “model” obstacles. For reasons of mathematical tractability we approximate each C-space obstacle by a Boolean combination of linear and quadratic polynomial inequalities (with “sharp corners” allowed), and use a “calculus” of implicit representations to effectively represent such obstacles. We provide evidence of the effectiveness of this “technology” of implicit representations in the form of several simulation studies illustrated at the end of the paper. |

BibTeX entry |

@inproceedings{rimon-icra-1990,
title = {Exact Robot Navigation in Geometrically Complicated but Topologically Simple Spaces},
author = {E. Rimon and D.E. Koditschek},
booktitle = {Robotics and Automation, 1990. Proceedings., 1990 IEEE International Conference on},
year = {1990},
month = {May},
pages = {1937-1942 vol.3},
doi = {10.1109/ROBOT.1990.126291}
} |