The essential visibility graph: an approach to global motion planning for autonomous mobile robots

Abstract

An approach to global motion planning for autonomous mobile robots has been developed on the basis of traversability vectors (t-vectors). Through the overall course of this research it was found that t-vectors provide a utility, efficiency and mathematical stability for collision detection and visibility that cannot be matched by commonly used algebraic approaches in static and dynamic environments. This paper will show that t-vectors also impact global motion planning by identifying redundancies in visibility graphs (V-graphs) and expediting their construction. The result of eliminating redundant path segments is a streamlined version of the V-graph called the essential visibility graph (EVG). This paper will also show that the EVG offers a significant reduction in data storage requirements and complexity.