title: Structuring free space as a hypergraph for roving robot path planning and navigation.
abstract: 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.
authors.affiliation: Department of Systems Design Engineering, University of Waterloo, Waterloo, Ont. N2L. 3G1, Canada.
authors.forename: K D
authors.initials: KD
authors.lastname: Rueb
authors.forename: A K
authors.initials: AK
authors.lastname: Wong