Structuring Free Space as a Hypergraph for Roving Robot Path Planning and Navigation
- 1 March 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. PAMI-9 (2), 263-273
- https://doi.org/10.1109/TPAMI.1987.4767900
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.Keywords
This publication has 7 references indexed in Scilit:
- An Integrated Navigation and Motion Control System for Autonomous Multisensory Mobile RobotsPublished by Springer Nature ,1990
- Entropy and Distance of Random Graphs with Application to Structural Pattern RecognitionIEEE Transactions on Pattern Analysis and Machine Intelligence, 1985
- Computational Geometry—A SurveyIEEE Transactions on Computers, 1984
- Solving the find-path problem by good representation of free spaceIEEE Transactions on Systems, Man, and Cybernetics, 1983
- An algorithm for planning collision-free paths among polyhedral obstaclesCommunications of the ACM, 1979
- Decomposition of Polygons into Convex SetsIEEE Transactions on Computers, 1978
- Structural Pattern RecognitionPublished by Springer Nature ,1977