Gap Navigation Trees for Discovering Unknown Environments

Ashraf  Elnagar; Reem  Nasir

doi:10.4236/ica.2015.64022

Reem Nasir, Ashraf Elnagar

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.

Keywords: Motion Planning, Gap-Navigation Trees, Roadmap, Robotics, Local Environments

Cite this paper: Nasir, R. and Elnagar, A. (2015) Gap Navigation Trees for Discovering Unknown Environments. Intelligent Control and Automation, 6, 229-240. doi: 10.4236/ica.2015.64022.

References

[1] Canny, J. and Reif, J. (1987) New Lower Bound Techniques for Robot Motion Planning Problems. Proceedings IEEE Symposium on Foundations of Computer Science, Los Angeles, 12-14 October 1987, 49-60. http://dx.doi.org/10.1109/sfcs.1987.42

[2] Murphy, L. and Newman, P (2008) Using Incomplete Online Metric Maps for Topological Exploration with the Gap Navigation Tree. IEEE International Conference on Robotics and Automation, Pasadena, 19-23 May 2008, 2792-2797. http://dx.doi.org/10.1109/robot.2008.4543633

[3] Craig, J. (2004) Introduction to Robotics: Mechanics and Control. 3rd Edition, Prentice Hall, Upper Saddle River.

[4] LaValle, S.M. and Hinrichsen, J. (2001) Visibility-Based Pursuit-Evasion: The Case of Curved Environments. IEEE Transactions on Robotics and Automation, 17, 196-201. http://dx.doi.org/10.1109/70.928565

[5] Thrun, S., Burgard, W. and Fox, D. (2005) Probabilistic Robotics. MIT Press, Cambridge.

[6] Thrun, S., Burgard, W. and Fox, D. (1998) Probabilistic Mapping of an Environment by a Mobile Robot. IEEE International Conference on Robotics and Automation, Levene, 16-20 May 1998, 1546-1551.

[7] Elnagar, A. and Lulu, L. (2005) An Art Gallery-Based Approach to Autonomous Robot Motion Planning in Global Environments. IEEE/RSJ International Conference on Intelligent Robots and Systems, 2-6 August 2005, 2079-2084. http://dx.doi.org/10.1109/iros.2005.1545170

[8] Tovar, B., Murrieta-Cid, R. and LaValle, S.M. (2007) Distance-Optimal Navigation in an Unknown Environment without Sensing Distances. IEEE Transactions on Robotics, 23, 506-518. http://dx.doi.org/10.1109/TRO.2007.898962

[9] Nasir, R. and Elnagar, A. (2014) Exploration of Unknown Multiply Connected Environments Using Minimal Sensory Data. In: Zhang, X., et al., Eds., ICIRA 2014, Part I, LNAI 8917, 479-490. http://dx.doi.org/10.1007/978-3-319-13966-1_47

[10] Erdmann, M. (1995) Understanding Action and Sensing by Designing Action-Based Sensors. The International Journal of Robotics Research, 14, 483-509. http://dx.doi.org/10.1177/027836499501400506

[11] Tovar, B., LaValle, S.M. and Murrieta, R. (2003) Optimal Navigation and Object Finding without Geometric Maps or Localization. IEEE International Conference on Robotics and Automation, 1, 464-470.

[12] Tovar, B., LaValle, S.M. and Murrieta, R. (2003) Locally-Optimal Navigation in Multiply-Connected Environments without Geometric Maps. IEEE/RSJ International Conference on Intelligent Robots and Systems, 4, 3491-3497. http://dx.doi.org/10.1109/iros.2003.1249696

[13] Tovar, B., Guilamo, L. and LaValle, S.M. (2005) Gap Navigation Trees: Minimal Representation for Visibility-Based Tasks. Algorithmic Foundations of Robotics VI, Springer Berlin Heidelberg, 425-440.

[14] Yoon, K-J. and Kweon, I. (2002) Landmark Design and Real-Time Landmark Tracking for Mobile Robot Localization. Electrical Engineering, 4573, 219-226.

[15] Bais, A. and Sablatnig, R. (2006) Landmark Based Global Self-Localization of Mobile Soccer Robots. Computer Vision-ACCV, 3852, 842-851. http://dx.doi.org/10.1007/11612704_84

[16] Se, S., Lowe, D. and Little, J. (2002) Mobile Robot Localization and Mapping with Uncertainty Using Scale-Invariant Visual Landmarks. The International Journal of Robotics Research, 21, 735-758. http://dx.doi.org/10.1177/027836402761412467

[17] Zhao, L., Li, R., Zang, T., Sun, L. and Fan, X. (2008) A Method of Landmark Visual Tracking for Mobile Robot. Lecture Notes in Computer Science, 5314, 901-910. http://dx.doi.org/10.1007/978-3-540-88513-9_97