An Interpolated Dynamic Navigation Function

The E* algorithm is a path planning method capable of dynamic replanning and user-configurable path cost interpolation. It calculates a navigation function as a sampling of an underlying smooth goal distance that takes into account a continuous notion of risk that can be controlled in a fine-grained manner. E* results in more appropriate paths during gradient descent. Dynamic replanning means that changes in the environment model can be repaired to avoid the expenses of complete replanning. This helps compensating for the increased computational effort required for interpolation. We present the theoretical basis and a working implementation, as well as measurements of the algorithm’s precision, topological correctness, and computational effort.