Global Vision Based Path Planning for AVGs Using A* Algorithm

Abstract

One of the most studied problems in robotics is robot path planning. Many strategies have been invented. Image processing and machine vision technology also have been utilized in this regard. Studies are still underway to improve path planning methods. This paper proposes an implementing visual servoing-based technique using the A* algorithm to achieve efficient searching capabilities of path planning in complicated maps with a combination of LabVIEW and MATLAB software. The proposed algorithm is divided into three parts. Firstly, the environment model or robot motion environment is conducted. In this stage, the visual information extracted from a single ceiled camera. Secondly, the position and orientation of the objects (robot, obstacles etc.) under the visibility of the camera are generated from visual information. Thirdly, the A* algorithm is used as a path planning method. This algorithm is not guaranteed the generated path to be safe and desirable with obstacle-free. To solve this problem image processing techniques are utilized. This gives an effective improvement and high performance to A* in a complex environment and gives a safe path as a comparison to the traditional version of A*. The experimental results, considering the optimal path lengths and execution time, show that the proposed design is more effective and faster to generate the shortest path.

Keywords

• A* Algorithm
• AVGs
• Image Processing
• Path Planning
• Visual Servoing

References

1. X. Dai, S. Long, Z. Zhang, and D. Gong, “Mobile robot path planning based on ant colony algorithm with a∗ heuristic method,” Front. Neurorobot., 2019, doi: 10.3389/fnbot.2019.00015.
2. A. Cherubini, F. Chaumette, and G. Oriolo, “A position-based visual servoing scheme for following paths with nonholonomic mobile robots,” in IEEE/RSJ International Conference on Intelligent Robots and Systems, Sep. 2008, pp. 1648–1654, doi: 10.1109/IROS.2008.4650679.
3. E. A. Elsheikh, M. A. El-Bardini, and M. A. Fkirin, “Practical Design of a Path Following for a Non-holonomic Mobile Robot Based on a Decentralized Fuzzy Logic Controller and Multiple Cameras,” Arab. J. Sci. Eng., vol. 41, no. 8, pp. 3215–3229, Aug. 2016, doi: 10.1007/s13369-016-2147-x.
4. T. T. Mac, C. Copot, T. Tran, and R. De Keyser, “Heuristic approaches in robot path planning: A survey,” Rob. Auton. Syst., vol. 86, pp. 13–28, 2016, doi: 10.1016/j.robot.2016.08.001.
5. R. Kala, A. Shukla, R. Tiwari, S. Rungta, and R. R. Janghel, “Mobile robot navigation control in moving obstacle environment using genetic algorithm, artificial neural networks and A* algorithm,” in 2009 WRI World Congress on Computer Science and Information Engineering, CSIE 2009, 2009, doi: 10.1109/CSIE.2009.854.
6. R. Lagisetty, N. K. Philip, R. Padhi, and M. S. Bhat, “Object detection and obstacle avoidance for mobile robot using stereo camera,” in Proceedings of the IEEE International Conference on Control Applications, 2013, doi: 10.1109/CCA.2013.6662816.
7. K. Zheng, D. F. Glas, T. Kanda, H. Ishiguro, and N. Hagita, “Supervisory control of multiple social robots for navigation,” in ACM/IEEE International Conference on Human-Robot Interaction, 2013, doi: 10.1109/HRI.2013.6483497.
8. J. Han and Y. Seo, “Mobile robot path planning with surrounding point set and path improvement,” Appl. Soft Comput., vol. 57, pp. 35–47, Aug. 2017, doi: 10.1016/j.asoc.2017.03.035.

9. B. K. Patle, D. R. K. Parhi, A. Jagadeesh, and S. K. Kashyap, “Application of probability to enhance the performance of fuzzy based mobile robot navigation,” Appl. Soft Comput., vol. 75, pp. 265–283, Feb. 2019, doi: 10.1016/j.asoc.2018.11.026.
10. R. Kala, A. Shukla, and R. Tiwari, “Robotic path planning in static environment using hierarchical multi-neuron heuristic search and probability based fitness,” Neurocomputing, vol. 74, no. 14–15, pp. 2314–2335, Jul. 2011, doi: 10.1016/j.neucom.2011.03.006.
11. M. Dirik, O. Castillo, and A. Kocamaz, “Visual-Servoing Based Global Path Planning Using Interval Type-2 Fuzzy Logic Control,” Axioms 2019, Vol. 8, Page 58, vol. 8, no. 2, p. 58, May 2019, doi: 10.3390/AXIOMS8020058.
12. G. Antonelli, S. Chiaverini, and G. Fusco, “A Fuzzy-Logic-Based Approach for Mobile Robot Path Tracking,” IEEE Trans. Fuzzy Syst., vol. 15, no. 2, pp. 211–221, Apr. 2007, doi: 10.1109/TFUZZ.2006.879998.
13. F. Duchoň et al., “Path Planning with Modified a Star Algorithm for a Mobile Robot,” Procedia Eng., vol. 96, pp. 59–69, 2014, doi: 10.1016/j.proeng.2014.12.098.
14. G. Klančar, A. Zdešar, S. Blažič, and I. Škrjanc, Wheeled Mobile Robotics, From Fundamentals Towards Autonomous Systems. Butterworth-Heinemann, © 2017 Elsevier Inc., 2017.
15. S. A. Fadzli, S. I. Abdulkadir, M. Makhtar, and A. A. Jamal, “Robotic Indoor Path Planning using Dijkstra ’ s Algorithm with Multi-Layer Dictionaries,” pp. 1–4, 2015.
16. P. Hart, N. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Trans. Syst. Sci. Cybern., vol. 4, no. 2, pp. 100–107, 1968, doi: 10.1109/TSSC.1968.300136.
17. S. Salmanpour, H. Monfared, and H. Omranpour, “Solving robot path planning problem by using a new elitist multi-objective IWD algorithm based on coefficient of variation,” Soft Comput., vol. 21, no. 11, pp. 3063–3079, 2017, doi: 10.1007/s00500-015-1991-z.
18. P. Sudhakara, V. Ganapathy, and K. Sundaran, “Genetic algorithm based optimization technique for route planning of wheeled mobile robot,” in Proceedings of the 4th IEEE International Conference on Advances in Electrical and Electronics, Information, Communication and Bio-Informatics, AEEICB 2018, 2018, doi: 10.1109/AEEICB.2018.8480937.
19. A. Elshamli, H. A. Abdullah, and S. Areibi, “Genetic algorithm for dynamic path planning,” in Canadian Conference on Electrical and Computer Engineering, 2004.
20. AL-Taharwa, “A Mobile Robot Path Planning Using Genetic Algorithm in Static Environment,” J. Comput. Sci., vol. 4, no. 4, pp. 341–344, Apr. 2008, doi: 10.3844/jcssp.2008.341.344.
21. C. Lamini, S. Benhlima, and A. Elbekri, “Genetic Algorithm Based Approach for Autonomous Mobile Robot Path Planning,” Procedia Comput. Sci., vol. 127, pp. 180–189, 2018, doi: 10.1016/j.procs.2018.01.113.
22. Jianping Tu and S. X. Yang, “Genetic algorithm based path planning for a mobile robot,” in International Conference on Robotics and Automation (Cat. No.03CH37422), 2003, vol. 1, pp. 1221–1226, doi: 10.1109/ROBOT.2003.1241759.
23. L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Trans. Robot. Autom., vol. 12, no. 4, pp. 566–580, 1996, doi: 10.1109/70.508439.
24. J. Bruce and M. Veloso, “Real-time randomized path planning for robot navigation,” in IEEE/RSJ International Conference on Intelligent Robots and System, 2002, vol. 3, pp. 2383–2388, doi: 10.1109/IRDS.2002.1041624.
25. E. Dönmez, A. F. Kocamaz, and M. Dirik, “Bi-RRT path extraction and curve fitting smooth with visual based configuration space mapping,” in IDAP 2017 - International Artificial Intelligence and Data Processing Symposium, 2017, doi: 10.1109/IDAP.2017.8090214.
26. R. Sadeghian, S. Shahin, and M. T. Masouleh, “An experimental study on vision based controlling of a spherical rolling robot,” in Iranian Conference on Intelligent Systems and Signal Processing (ICSPIS), Dec. 2017, pp. 23–27, doi: 10.1109/ICSPIS.2017.8311583.
27. T. Weerakoon, K. Ishii, and A. A. F. Nassiraei, “An Artificial Potential Field Based Mobile Robot Navigation Method To Prevent From Deadlock,” J. Artif. Intell. Soft Comput. Res., vol. 5, no. 3, pp. 189–203, Jul. 2015, doi: 10.1515/jaiscr-2015-0028.
28. E. Rimon and D. E. Koditschek, “Exact robot navigation using artificial potential functions,” IEEE Trans. Robot. Autom., vol. 8, no. 5, pp. 501–518, Oct. 1992, doi: 10.1109/70.163777.
29. J.-Y. Jhang, C.-J. Lin, C.-T. Lin, and K.-Y. Young, “Navigation Control of Mobile Robots Using an Interval Type-2 Fuzzy Controller Based on Dynamic-group Particle Swarm Optimization,” Int. J. Control. Autom. Syst., vol. 16, no. 5, pp. 2446–2457, Oct. 2018, doi: 10.1007/s12555-017-0156-5.
30. J.-Y. Jhang, C.-J. Lin, C.-T. Lin, and K.-Y. Young, “Navigation Control of Mobile Robots Using an Interval Type-2 Fuzzy Controller Based on Dynamic-group Particle Swarm Optimization,” Int. J. Control. Autom. Syst., vol. 16, no. 5, pp. 2446–2457, Oct. 2018, doi: 10.1007/s12555-017-0156-5.
31. T. W. Liao, “A procedure for the generation of interval type-2 membership functions from data,” Appl. Soft Comput., vol. 52, pp. 925–936, Mar. 2017, doi: 10.1016/j.asoc.2016.09.034.
32. A. Pandey, R. K. Sonkar, K. K. Pandey, and D. R. Parhi, “Path planning navigation of mobile robot with obstacles avoidance using fuzzy logic controller,” 2014 IEEE 8th Int. Conf. Intell. Syst. Control, pp. 39–41, 2014, doi: 10.1109/ISCO.2014.7103914.
33. A. Pandey, “Multiple Mobile Robots Navigation and Obstacle Avoidance Using Minimum Rule Based ANFIS Network Controller in the Cluttered Environment,” Int. J. Adv. Robot. Autom., vol. 1, no. 1, pp. 1–11, 2016, doi: 10.15226/2473-3032/1/1/00102.
34. K. Srinivasan and J. Gu, “Multiple Sensor Fusion in Mobile Robot Localization,” in Canadian Conference on Electrical and Computer Engineering, 2007, pp. 1207–1210, doi: 10.1109/CCECE.2007.308.
35. A. Shitsukane, W. Cheruiyot, C. Otieno, and M. Mvurya, “Fuzzy Logic Sensor Fusion for Obstacle Avoidance Mobile Robot,” IST-Africa Week Conf., no. May, pp. 1–8, 2018.
36. S. R. Bista, P. R. Giordano, and F. Chaumette, “Combining line segments and points for appearance-based indoor navigation by image based visual servoing,” in IEEE International Conference on Intelligent Robots and Systems, 2017, doi: 10.1109/IROS.2017.8206131.
37. F. Bonin-Font, A. Ortiz, and G. Oliver, “Visual Navigation for Mobile Robots: A Survey,” J. Intell. Robot. Syst., vol. 53, no. 3, pp. 263–296, Nov. 2008, doi: 10.1007/s10846-008-9235-4.
38. E. Dönmez, A. F. Kocamaz, and M. Dirik, “A Vision-Based Real-Time Mobile Robot Controller Design Based on Gaussian Function for Indoor Environment,” Arab. J. Sci. Eng., vol. 43, no. 12, pp. 7127–7142, Dec. 2018, doi: 10.1007/s13369-017-2917-0.
39. Y. Yoon, G. N. DeSouza, and A. C. Kak, “Real-time tracking and pose estimation for industrial objects using geometric features,” in Proceedings - IEEE International Conference on Robotics and Automation, 2003, doi: 10.1109/robot.2003.1242127.
40. A. Elgammal, D. Harwood, and L. Davis, “Non-parametric model for background subtraction,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2000, doi: 10.1007/3-540-45053-x_48.
41. M. Dirik, “Development of vision-based mobile robot control and path planning algorithms in obstacled environments,” Inonu University, 2020.
42. L. M. S. Bento, D. R. Boccardo, R. C. S. Machado, F. K. Miyazawa, V. G. Pereira de Sá, and J. L. Szwarcfiter, “Dijkstra graphs,” Discret. Appl. Math., vol. 261, pp. 52–62, May 2019, doi: 10.1016/j.dam.2017.07.033.
43. R. Kala, A. Shukla, and R. Tiwari, “Fusion of probabilistic A* algorithm and fuzzy inference system for robotic path planning,” Artif. Intell. Rev., vol. 33, no. 4, pp. 307–327, Apr. 2010, doi: 10.1007/s10462-010-9157-y.