TITLE:
Gap Navigation Trees for Discovering Unknown Environments
AUTHORS:
Reem Nasir, Ashraf Elnagar
KEYWORDS:
Motion Planning, Gap-Navigation Trees, Roadmap, Robotics, Local Environments
JOURNAL NAME:
Intelligent Control and Automation,
Vol.6 No.4,
November
9,
2015
ABSTRACT: We propose a motion
planning gap-based algorithms for mobile robots in an unknown environment for
exploration purposes. The results are locally optimal and sufficient to
navigate and explore the environment. In contrast with the traditional
roadmap-based algorithms, our proposed algorithm is designed to use minimal
sensory data instead of costly ones. Therefore, we adopt a dynamic data
structure called Gap Navigation Trees (GNT), which keeps track of the depth
discontinuities (gaps) of the local environment. It is incrementally
constructed as the robot which navigates the environment. Upon exploring the
whole environment, the resulting final data structure exemplifies the roadmap
required for further processing. To avoid infinite cycles, we propose to use
landmarks. Similar to traditional roadmap techniques, the resulting algorithm
can serve key applications such as exploration and target finding. The
simulation results endorse this conclusion. However, our solution is cost
effective, when compared to traditional roadmap systems, which makes it more
attractive to use in some applications such as search and rescue in hazardous
environments.