Dynamical Systems-based Navigation: Modeling and Verification

Autonomous navigation modeling and verification are valuable parts of the design of situated autonomous agents. Navigation modeling is necessary to create mobile agents, such as robots, while verification makes it possible to analyze such models to identify flaws or prove correctness. This paper explores modeling and verification in the context of the dynamical systems approach to navigation (dynamical navigation, for short), in which autonomous navigation arises from the evolution of differential equations governing agent behavior. While dynamical navigation has considerable desirable qualities, like robustness in unpredictable environments and obstacle avoidance at constant speed, its underlying mathematics has the restricting limitation that obstacles must be represented by circles. Representing elongated obstacles, such as walls, is therefore a challenging problem that this paper addresses by presenting a dynamic tangent (DT) model for wall representation: an agent represents each wall by a circular obstacle, tangent to the wall, that resizes and moves with the agent to support effective dynamical navigation. Simulations show that the DT model supports more successful navigation than previously employed wall representations, and it is comparable in efficiency to the fastest previous representations. This paper also describes a heuristic reachability model for analyzing dynamical navigation. This model, based on reachability analysis, examines the overall behavior of a system by analyzing approximations of its behavior locally in subregions of the world. Heuristic reachability is applied to estimate relative difficulty of different navigation environments.