Navigating: Reshaping Maps for Mobile Robots with Shortest Path Analysis

Full Length Article

•

Navigating: Reshaping Maps for Mobile Robots with Shortest Path Analysis

DOI

format_quote Cite this article

View PDF open_in_new

Abstract

Efficient path planning is needed by robotics to be deployed in daily applications so as to move around safely and effectively. In this research, novel algorithms for map adaptation and path optimization of robot navigation between given points are examined. The first step in the study involves the use of the Voronoi algorithm to determine safe zones and identify barriers in an environment for a safe passage of robots. After that, Dijkstra’s algorithm is used to generate a graph from the above data that can determine the shortest path between meaningful locations on it. Where there are many possible directions, it prefers the shortest one allowing for safety criteria between any two points and obstacles along it. Also, augmented development of security enhanced paths helps expand out original trajectory to prevent obstructing objects from causing collisions half a radius beyond safety distance traveled by their carriers. This study therefore makes its main innovation in providing new maps having secure pathways that let algorithms be employed for optimization of path planning procedures enhancing navigational efficiency within unfamiliar terrains. As regards experiments, these new maps have been found to give accurate results especially when used in complex terrains like maze layouts.

Keywords

Mobile robot Path planning Reshaping Navigation Map Reconstruction Safety.

References

[1] Mohammed R. Hashim Al-Dahhan, Mahmood Abdulrazzaq Alsaadi, Ruqayah R. Al-Dahhan, Salah A. Aliesawi, The Art of Navigation: Pure Pursuit Controller Strategies for Four-Wheeled Mobile Robots, Journal of Fusion: Practice and Applications, Vol. 15 , No. 2 , (2024) : 80-88 (Doi : https://doi.org/10.54216/FPA.150207)

[2] Mohammed R. Hashim Al-Dahhan, Mahmood Abdulrazzaq Alsaadi, Ruqayah R. Al-Dahhan, Salah A. Aliesawi, The Art of Navigation: Pure Pursuit Controller Strategies for Four-Wheeled Mobile Robots, Journal of Fusion: Practice and Applications, Vol. 15 , No. 2 , (2024) : 80-88 (Doi : https://doi.org/10.54216/FPA.150207)

[3] M. R. H. Al-Dahhan, K. W. Schmidt, Voronoi Boundary Visibility for Efficient Path Planning, IEEE Access, 2020, 8, pp. 134764–134781, 9145546.

[4] M. R. H. Al-Dahhan, R.R. Al-Dahhan, A. T. Radeef, Multi-layer perceptron neural network mobile robot navigator in unknown environment, In Indonesian Journal of Electrical Engineering and Computer Science, 2023, 31(2), pp. 725–733.

[5] R.R. Al-Dahhan, M. R. H Al-Dahhan, M. H. Jabur, Target Seeking and Obstacle Avoidance of Omni Robot in an Unknown Environment, In HORA 2020 - 2nd International Congress on Human-Computer Interaction, Optimization and Robotic Applications, Proceedings, 2020, 9152864 .

[6] P. Corke, Robotics, vision and control: fundamental algorithms in MATLAB 2nd ed, Springer, (118), (2017).

[7] H. M.Choset, S.Hutchinson, K. M.Lynch, G.Kantor, W. Burgard, Kavraki, L. E., S. Thrun, Principles of robot motion: theory, algorithms, and implementation. MIT press, (2005).

[8] P. Bhattacharya, M. L.Gavrilova, Roadmap-Based Path Planning Using the Voronoi Diagram for a Clearance- Based Shortest Path, IEEE Robotics & Automation Magazine, 15(2), (2008), 58–66.

[9] N. Y, D. Kim, W. I. Ko, H. Suh, Confidence random tree-based algorithm for mobile robot path planning considering the path length and safety, International Journal of Advanced Robotic Systems, 16(2), (2019), 1–10.

[10]L. E. Kavraki, P. Svestka, J. C. Latombe, M. H. Overmars, Probabilistic roadmaps for path planning in highdimensional configuration spaces, IEEE Transactions on Robotics and Automation, 12(4), (1996), 566-–580.

[11]L. Kavraki, J.Latombe, Randomized preprocessing of configuration for fast path planning, IEEE International Conference on Robotics and Automation, 3, (1994), 2138–2145.

[12]S. Karaman, E.Frazzoli, Sampling-based algorithms for optimal motion planning, The International Journal of Robotics Research, 30(7), (2011), 846-–894.

[13]S. M. LaValle, J. J. Kuffner, Randomized Kinodynamic Planning, The International Journal of Robotics Research, 20(5), (2001), 378–400.

[14]L. Janson, M. Pavone, Fast Marching Trees: A Fast Marching Sampling-Based Method for Optimal Motion.

[15]B. K. Patle, G. Babu L, A. Pandey, D. R. K. Parhi, A. Jagadeesh, A review: On path planning strategies for navigation of mobile robot, Defence Technology, 15(4), (2019), 582–606.

[16]D. A. L. Garcla, F. Gomez-Bravo, Vodec: A fast Voronoi algorithm for car-like robot path planning in dynamic scenarios, Robotica, 30(7), (2012), 1189-1201.

[17]B. B. K. Ayawli, X. Mei, M. Shen, A. Y. Appiah, F. Kyeremeh, Mobile Robot Path Planning in Dynamic Environment using Voronoi Diagram and Computation Geometry Technique, IEEE Access,(2019), 86026-86040.

[18]M. R. H. Al-Dahhan, M. M. Ali, Path tracking control of a mobile robot using fuzzy logic, In 2016 13th International Multi-Conference on Systems, Signals and Devices (SSD), (2016), 82–88.

[19]L. Gang, J. Wang, PRM path planning optimization algorithm research, Wseas Transactions on Systems and control, (2016), (11), 81-86.

[20]I. B. Jeong, S. J. Lee, J. H. Kim, Quick-RRT*: Triangular inequality-based implementation of RRT* with improved initial solution and convergence rate, Expert Systems with Applications, (2019), 82-90.

[21]T. Bai, Z. Fan, M. Liu, S. Zhang, R. Zheng, Multiple Waypoints Path Planning for a Home Mobile Robot, In 2018 Ninth International Conference on Intelligent Control and Information Processing (ICICIP) IEEE, (2018), 53–58).

[22]K. Yang, Anytime synchronized-biased-greedy rapidly-exploring random tree path planning in two dimensional complex environments, International Journal of Control, Automation and Systems, (2011), 9(4), 750.

[23]H. Dong, W. Li, J. Zhu, S. Duan, The path planning for mobile robot based on Voronoi diagram, In 2010 Third International Conference on Intelligent Networks and Intelligent Systems, (2010), 446–449.

[24]M. Foskey, M. Garber, M. C. Lin, D. Manocha, A Voronoi-based hybrid motion planner, IEEE/RSJ International Conference on Intelligent Robots and Systems. Expanding the Societal Role of Robotics in the the Next Millennium, (2001), 55–60.

[25]E. Masehian, M. R. Amin-Naseri, A voronoi diagram-visibility graph-potential field compound algorithm for robot path planning. Journal of Robotic Systems, fbf 21g(6). (2004), 275–300.

[26]Q. Wang, M. Wulfmeier, B. Wagner, Voronoi-Based Heuristic for Nonholonomic Search-Based Path Planning, Intelligent Autonomous Systems 13. Advances in Intelligent Systems and Computing, 302. (2016), 445–458.

[27]E.W. Dijkstra, A Note on Two Problems in Connection with Graphs.Numerische Mathematik. 1, (1959), 269–271.

[28]N. Alpkiray, Y. Torun, et al. “Probabilistic Roadmap and Artificial Bee Colony Algorithm Cooperation for Path Planning', International Conference on Artificial Intelligence and Data Processing (IDAP), pp. 1-6, Turkey, 2018.

[29]R. Santiago, A. Ocampo, et al. "Path planning for mobile robots using genetic algorithm and probabilistic roadmap", 9th International Conference on Humanoid, Nanotechnology, Information Technology, Communication and Control, Environment and Management, pp. 1-5 , Philippines, 2017.

[30]E. Magid, R. Lavrenov, "Voronoi-based trajectory optimization for UGV path planning", International Conference on Mechanical, System and Control Engineering, pp. 383-387, Russia, 2017.

[31]Z. Baoyan, L. Caihong et al. "A* algorithm of global path planning based on the grid map and V-graph environmental model for the mobile robot", Chinese Automation Congress (CAC,) pp. 4973-4977. China, 2017.

[32]D. Connell and H. Manh, "Dynamic path planning and replanning for mobile robots using RRT". International Conference on Systems, Man, and Cybernetics, pp. 1429-1434, China, 2017.

[33]Sudhakara, P., Ganapathy, V., & Sundaran, K. "Probabilistic roadmaps-spline based trajectory planning for wheeled mobile robot. International Conference on Energy, Communication, Data Analytics and Soft Computing (ICECDS), pp. 3579-3583, India, 2017.

[34]Garip, Z. B., Atali, G., Karayel, D., & Ozkan, S. S. "Path Planning for Multiple Mobile Robots in Static Environment using Hybrid Algorithm". 2nd International Symposium on Multidisciplinary Studies and Innovative Technologies (ISMSIT), pp. 1-4, Turkey, 2018.

[35] Mo, H., & Xu, L. "Research of biogeography particle swarm optimization for robot path planning". Neurocomputing, pp. 91-99, 2015

[36] Sugihara, K. "Approximation of generalized Voronoi diagrams by ordinary Voronoi diagrams". CVGIP: Graphical Models and Image Processing, pp. 55(6), 522-5, 1993.

Cite This Article

Choose your preferred format

format_quote

. "Navigating: Reshaping Maps for Mobile Robots with Shortest Path Analysis." International Journal of Neutrosophic Science, vol. , no. , , pp. . DOI:

(). Navigating: Reshaping Maps for Mobile Robots with Shortest Path Analysis. International Journal of Neutrosophic Science, (), . DOI:

. "Navigating: Reshaping Maps for Mobile Robots with Shortest Path Analysis." International Journal of Neutrosophic Science , no. (): . DOI:

() 'Navigating: Reshaping Maps for Mobile Robots with Shortest Path Analysis', International Journal of Neutrosophic Science, (), pp. . DOI:

. Navigating: Reshaping Maps for Mobile Robots with Shortest Path Analysis. International Journal of Neutrosophic Science. ;():. DOI:

, "Navigating: Reshaping Maps for Mobile Robots with Shortest Path Analysis," International Journal of Neutrosophic Science, vol. , no. , pp. , . DOI:

Digital Archive Ready