Structuring Free Space as a Hypergraph for Roving Robot Path Planning and Navigation

This paper presents a method of structuring the free space of a roving robot's environment into a set of overlapping convex regions ideally suited to path planning and navigation tasks. The structure of the free space environment is maintained as a hypergraph with each convex region represented by a hyperedge identifying the boundary walls of the region. A new methodology reveals the structure of free space and constructs the hypergraph representation through a directed search for a set of fundamental circits in an abstract graphical representation of the environment geometry.