A Novel Path Planning System for Guidance of Blind People using Integration of GA and A* Techniques

Mohamed M. Ghoniem; A. E. El-Alfi; A. F. Elgamal

Research Article

A Novel Path Planning System for Guidance of Blind People using Integration of GA and A* Techniques

by Mohamed M. Ghoniem, A. E. El-Alfi, A. F. Elgamal

International Journal of Computer Applications

Foundation of Computer Science (FCS), NY, USA

Volume 178 - Issue 29

Published: Jul 2019

Authors: Mohamed M. Ghoniem, A. E. El-Alfi, A. F. Elgamal

10.5120/ijca2019919138

PDF

Mohamed M. Ghoniem, A. E. El-Alfi, A. F. Elgamal . A Novel Path Planning System for Guidance of Blind People using Integration of GA and A* Techniques. International Journal of Computer Applications. 178, 29 (Jul 2019), 26-34. DOI=10.5120/ijca2019919138

                        @article{ 10.5120/ijca2019919138,
                        author  = { Mohamed M. Ghoniem,A. E. El-Alfi,A. F. Elgamal },
                        title   = { A Novel Path Planning System for Guidance of Blind People using Integration of GA and A* Techniques },
                        journal = { International Journal of Computer Applications },
                        year    = { 2019 },
                        volume  = { 178 },
                        number  = { 29 },
                        pages   = { 26-34 },
                        doi     = { 10.5120/ijca2019919138 },
                        publisher = { Foundation of Computer Science (FCS), NY, USA }
                        }

                        %0 Journal Article
                        %D 2019
                        %A Mohamed M. Ghoniem
                        %A A. E. El-Alfi
                        %A A. F. Elgamal
                        %T A Novel Path Planning System for Guidance of Blind People using Integration of GA and A* Techniques%T 
                        %J International Journal of Computer Applications
                        %V 178
                        %N 29
                        %P 26-34
                        %R 10.5120/ijca2019919138
                        %I Foundation of Computer Science (FCS), NY, USA

Abstract

It is a challenging task for the blind people to perceive indoor environment information and walk independently. Path planning is a crucial requirement to provide constant assistance for blind people to navigate from one location to another. This paper presents a novel system for path planning to assist blind people for walking through the indoor environment and avoiding the obstacles. The algorithm is based on genetic algorithm and A* algorithm to select the shortest path that achieves the lowest computational time. A comparison a mong the GA, A* and the new algorithm shows that is faster and shorter than the previous algorithms.

References

K. Hasan, Abdullah-Al-Nahid and K. Reza, "Path planning algorithm development for autonomous vacuum cleaner robots", 2014 International Conference on Informatics, Electronics & Vision (ICIEV), pp. 1-6, 2014.
S. Mahmoudzadeh, D. Powers, K. Sammut, A. Lammas and A. Yazdani, "Optimal route planning with prioritized task scheduling for AUV missions", 2015 IEEE International Symposium on Robotics and Intelligent Sensors (IRIS), 2015.
R. Galvez, E. Dadios and A. Bandala, "Path planning for quadrotor UAV using genetic algorithm", 2014 International Conference on Humanoid, Nanotechnology, Information Technology, Communication and Control, Environment and Management (HNICEM), 2014.
Y. Lee and G. Medioni, "Wearable RGBD Indoor Navigation System for the Blind", Computer Vision - ECCV 2014 Workshops, pp. 493-508, 2015.
U. Orozco-Rosas, O. Montiel and R. Sepúlveda, "Mobile robot path planning using membrane evolutionary artificial potential field", Applied Soft Computing, vol. 77, pp. 236-251, 2019.
J. Han and Y. Seo, "Mobile robot path planning with surrounding point set and path improvement", Applied Soft Computing, vol. 57, pp. 35-47, 2017.
Y. Wang, D. Mulvaney, I. Sillitoe and E. Swere, "Robot Navigation by Waypoints", Journal of Intelligent and Robotic Systems, vol. 52, no. 2, pp. 175-207, 2008.
"Vision impairment and blindness", Who.int, 2019. [Online]. Available: https://www.who.int/news-room/fact-sheets/detail/blindness-and-visual-impairment. [Accessed: 09- Mar- 2019].
D. Ni, A. Song, L. Tian, X. Xu and D. Chen, "A Walking Assistant Robotic System for the Visually Impaired Based on Computer Vision and Tactile Perception", International Journal of Social Robotics, vol. 7, no. 5, pp. 617-628, 2015.
M. Yakoubi and M. Laskri, "The path planning of cleaner robot for coverage region using Genetic Algorithms", Journal of Innovation in Digital Ecosystems, vol. 3, no. 1, pp. 37-43, 2016.
G. Kumar, U. Painumgal, M. Kumar and K. Rajesh, "Autonomous Underwater Vehicle for Vision Based Tracking", Procedia Computer Science, vol. 133, pp. 169-180, 2018.
J. Tao, C. Zhong, L. Gao and H. Deng, "A Study on Path Planning of Unmanned Aerial Vehicle Based on Improved Genetic Algorithm", 2016 8th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC), 2016.
M. Zafar and J. Mohanta, "Methodology for Path Planning and Optimization of Mobile Robots: A Review", Procedia Computer Science, vol. 133, pp. 141-152, 2018.
F. Matoui, B. Boussaid, B. Metoui, G. Frej and M. Abdelkrim, "Path planning of a group of robots with potential field approach: decentralized architecture", IFAC-PapersOnLine, vol. 50, no. 1, pp. 11473-11478, 2017.
Z. Wang and J. Cai, "Probabilistic roadmap method for path-planning in radioactive environment of nuclear facilities", Progress in Nuclear Energy, vol. 109, pp. 113-120, 2018.
A. Panov, K. Yakovlev and R. Suvorov, "Grid Path Planning with Deep Reinforcement Learning: Preliminary Results", Procedia Computer Science, vol. 123, pp. 347-353, 2018.
W. Wang, H. Deng and X. Wu, "Path planning of loaded pin-jointed bar mechanisms using Rapidly-exploring Random Tree method", Computers & Structures, vol. 209, pp. 65-73, 2018.
S. Mohammad, M. Jeffril and N. Sariff, "Mobile robot obstacle avoidance by using Fuzzy Logic technique", 2013 IEEE 3rd International Conference on System Engineering and Technology, 2013.
H. Li, S. Yang and M. Seto, "Neural-Network-Based Path Planning for a Multirobot System With Moving Obstacles", IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), vol. 39, no. 4, pp. 410-419, 2009.
X. Chen, Y. Kong, X. Fang and Q. Wu, "A fast two-stage ACO algorithm for robotic path planning", Neural Computing and Applications, vol. 22, no. 2, pp. 313-319, 2011.
B. Patle, D. Parhi, A. Jagadeesh and S. Kashyap, "Matrix-Binary Codes based Genetic Algorithm for path planning of mobile robot", Computers & Electrical Engineering, vol. 67, pp. 708-728, 2018.
Y. Zhang, D. Gong and J. Zhang, "Robot path planning in uncertain environment using multi-objective particle swarm optimization", Neurocomputing, vol. 103, pp. 172-185, 2013.
N. Fallah, I. Apostolopoulos, K. Bekris and E. Folmer, "Indoor Human Navigation Systems: A Survey", Interacting with Computers, vol. 25, no. 1, pp. 21 - 33, 2013.
M. Hosny, R. Alsarrani and A. Najjar, "Indoor Wheelchair Navigation for the Visually Impaired", Communications in Computer and Information Science, pp. 411-417, 2015.
J. Bai, S. Lian, Z. Liu, K. Wang and D. Liu, "Virtual-Blind-Road Following-Based Wearable Navigation Device for Blind People", IEEE Transactions on Consumer Electronics, vol. 64, no. 1, pp. 136-143, 2018.
T. Gao Smith, C. Rose, J. Nolen, D. Pierce and A. Sherman, "Interactive Navigation System for the Visually Impaired with Auditory and Haptic Cues in Crosswalks, Indoors and Urban Areas", Communications in Computer and Information Science, pp. 539-545, 2015.
D. Nandini and K. Seeja, "A novel path planning algorithm for visually impaired people", Journal of King Saud University - Computer and Information Sciences, 2017.
M. Eichhorn, "Optimal routing strategies for autonomous underwater vehicles in time-varying environment", Robotics and Autonomous Systems, vol. 67, pp. 33-43, 2015.
S. Choi, S. Lee, H. Viet and T. Chung, "B-Theta*: an Efficient Online Coverage Algorithm for Autonomous Cleaning Robots", Journal of Intelligent & Robotic Systems, vol. 87, no. 2, pp. 265-290, 2017.
M. Yakoubi and M. Laskri, "The path planning of cleaner robot for coverage region using Genetic Algorithms", Journal of Innovation in Digital Ecosystems, vol. 3, no. 1, pp. 37-43, 2016.
M. Alajlan, A. Koubaa, I. Chaari, H. Bennaceur and A. Ammar, "Global path planning for mobile robots in large-scale grid environments using genetic algorithms", 2013 International Conference on Individual and Collective Behaviors in Robotics (ICBR), 2013.
Pu Shi and Yujie Cui, "Dynamic path planning for mobile robot based on genetic algorithm in unknown environment", 2010 Chinese Control and Decision Conference, 2010.
T. Yusof, S. Toha and H. Yusof, "Path Planning for Visually Impaired People in an Unfamiliar Environment Using Particle Swarm Optimization", Procedia Computer Science, vol. 76, pp. 80-86, 2015.
Y. Zhang, D. Gong and J. Zhang, "Robot path planning in uncertain environment using multi-objective particle swarm optimization", Neurocomputing, vol. 103, pp. 172-185, 2013.
S. Mahmoudzadeh, D. Powers, K. Sammut, A. Lammas and A. Yazdani, "Optimal route planning with prioritized task scheduling for AUV missions", 2015 IEEE International Symposium on Robotics and Intelligent Sensors (IRIS), 2015.
Y. Zhuang, S. Sharma, B. Subudhi, H. Huang and J. Wan, "Efficient collision-free path planning for autonomous underwater vehicles in dynamic environments with a hybrid optimization algorithm", Ocean Engineering, vol. 127, pp. 190-199, 2016.
S. Primatesta, L. Cuomo, G. Guglieri and A. Rizzo, "An Innovative Algorithm to Estimate Risk Optimum Path for Unmanned Aerial Vehicles in Urban Environments", Transportation Research Procedia, vol. 35, pp. 44-53, 2018.
L. Yu, Z. Wei, Z. Wang, Y. Hu and H. Wang, "Path optimization of AUV based on smooth-RRT algorithm", 2017 IEEE International Conference on Mechatronics and Automation (ICMA), 2017.
P. Yao and H. Wang, "Dynamic Adaptive Ant Lion Optimizer applied to route planning for unmanned aerial vehicle", Soft Computing, vol. 21, no. 18, pp. 5475-5488, 2016.
J. Velagic, D. Delimustafic and D. Osmankovic, "Mobile robot navigation system based on Probabilistic Road Map (PRM) with Halton sampling of configuration space", 2014 IEEE 23rd International Symposium on Industrial Electronics (ISIE), 2014.
E. Yanmaz, R. Kuschnig, M. Quaritsch, C. Bettstetter and B. Rinner, "On path planning strategies for networked unmanned aerial vehicles", 2011 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), 2011.
R. M., Ghoniem. “Deep Genetic Algorithm-based Voice Pathology Diagnostic System”, Natural Language Processing and Information Systems Lecture Notes in Computer Science. (2019).
A. Jayaprakash and C. Keziselvavijila. 2019. Feature Selection using Ant Colony Optimization (ACO) and Road Sign Detection and Recognition (RSDR) System. Cognitive Systems Research(2019). DOI:http://dx.doi.org/10.1016/j.cogsys.2019.04.002.
R. M., Ghoniem & K. Shaalan, (2017). “FCSR - Fuzzy Continuous Speech Recognition Approach for Identifying Laryngeal Pathologies Using New Weighted Spectrum Features”. Proceedings of the International Conference on Advanced Intelligent Systems and Informatics 2017 Advances in Intelligent Systems and Computing, 384–395. http://doi.org/10.1007/978-3-319-64861-3_36.
T. Mac, C. Copot, D. Tran and R. De Keyser, "Heuristic approaches in robot path planning: A survey", Robotics and Autonomous Systems, vol. 86, pp. 13-28, 2016.
C. Lamini, S. Benhlima and A. Elbekri, "Genetic Algorithm Based Approach for Autonomous Mobile Robot Path Planning", Procedia Computer Science, vol. 127, pp. 180-189, 2018.
J. Yao, C. Lin, X. Xie, A. Wang and C. Hung, "Path Planning for Virtual Human Motion Using Improved A* Star Algorithm", 2010 Seventh International Conference on Information Technology: New Generations, 2010.
F. Duchoň et al., "Path Planning with Modified a Star Algorithm for a Mobile Robot", Procedia Engineering, vol. 96, pp. 59-69, 2014.
I. Wojnicki, S. Ernst and W. Turek, "A Robust Heuristic for the Multidimensional A-star/Wavefront Hybrid Planning Algorithm", Artificial Intelligence and Soft Computing, pp. 282-291, 2015.
K. Da, L. Xiaoyu and Z. Bi, "Variable-step-length A∗ algorithm for path planning of mobile robot", 2017 29th Chinese Control And Decision Conference (CCDC), 2017.
G. Klančar, A. Zdešar, S. Blažič and I. Škrjanc, "Path Planning", Wheeled Mobile Robotics, pp. 161-206, 2017.
A. Tuncer and M. Yildirim, "Dynamic path planning of mobile robots with improved genetic algorithm", Computers & Electrical Engineering, vol. 38, no. 6, pp. 1564-1572, 2012.
M. Alajlan, A. Koubaa, I. Chaari, H. Bennaceur and A. Ammar, "Global path planning for mobile robots in large-scale grid environments using genetic algorithms", 2013 International Conference on Individual and Collective Behaviors in Robotics (ICBR), 2013.
Shenlu Jiang, Zhonghua Hong, Yun Zhang, Yanling Han, Ruyan Zhou and Bo Shen, "Automatic path planning and navigation with stereo cameras", 2014 Third International Workshop on Earth Observation and Remote Sensing Applications (EORSA), 2014.
I. Châari et al., "On the Adequacy of Tabu Search for Global Robot Path Planning Problem in Grid Environments", Procedia Computer Science, vol. 32, pp. 604-613, 2014.
N. Eraghi, F. Lopez-Colino, A. de Castro and J. Garrido, "Path length comparison in grid maps of planning algorithms: HCTNav and Dijkstra", Design of Circuits and Integrated Systems, 2014.
Y. Miao, A. Khamis, F. Karray and M. Kamel, "A NOVEL APPROACH TO PATH PLANNING FOR AUTONOMOUS MOBILE ROBOTS", Control and Intelligent Systems, vol. 39, no. 4, 2011.
Haiming Shen, "A study of welding robot path planning application based on Genetic Ant Colony Hybrid Algorithm", 2016 IEEE Advanced Information Management, Communicates, Electronic and Automation Control Conference (IMCEC), 2016.
M. Gao, G. Shi, W. Li, Y. Wang and D. Liu, "An Improved Genetic Algorithm for Island Route Planning", Procedia Engineering, vol. 174, pp. 433-441, 2017.
H. Kim, D. Kim, H. Kim, J. Shin and H. Myung, "An extended any-angle path planning algorithm for maintaining formation of multi-agent jellyfish elimination robot system", International Journal of Control, Automation and Systems, vol. 14, no. 2, pp. 598-607, 2016.

Index Terms

Computer Science

Information Sciences

No index terms available.

Keywords

Path planning grid map Genetic Algorithm A Star algorithm Path guidance.