Using hypergraph knowledge representation for natural terrain robot navigation and path planning

Abstract

Rapidly changing requirements in manufacturing and robotics require efficient automated planning systems. In this paper, we present a method to acquire and exploit domain-knowledge. We use two examples of knowledge-extensive contexts; outdoor terrain robot navigation and mission planning. We represent the acquired sensory 3D data by triangular terrain meshes. Application independent features are automatically extracted from these and converted into symbolic entities suitable for reasoning. Their topological relations are then organized into attributed graphs. Higher-order, application dependent relations are captured by hyper-edges in attributed hypergraphs. The symbolic relations inducing hyperedges are used as the basis of symbolic reasoning operations. The resulting compact hypergraph representation of the raw data facilitates complex navigation and mission planning tasks. Domain-knowledge is thus captured in a flexible form and used to reduce the search for feasible paths.