Smoothly blending vector fields for global robot navigation

We introduce a new algorithm for constructing smooth vector fields for global robot navigation. Given a d-dimensional cell complex with each cell a convex polygon, our algorithm defines a number of local vector fields: one for each cell, and one for each face connecting two cells together. We smoothly blend these component vector fields together using bump functions; the precomputation of the component vector field and all queries can be done in linear time. The integral curves of the resulting globally-defined vector field are guaranteed to arrive at a neighborhood of the goal state in finite time. Except for a set of measure zero, the vector field is smooth. The resulting vector field can be used directly to control kinematic systems or can be used to develop dynamic control policies. We prove convergence for the integral curves of the vector fields produced by our algorithm and give examples illustrating the practical advantages of our technique.