Exact robot navigation in geometrically complicated but topologically simple spaces

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.