Fuzzy A* for optimum Path Planning in a Large Maze
DOI:
https://doi.org/10.12928/biste.v5i4.9394Keywords:
Fuzzy, A*, Path Planning, Maze, OptimizationAbstract
Traditional A* path planning, while guaranteeing the shortest path with an admissible heuristic, often employs conservative heuristic functions that neglect potential obstacles and map inaccuracies. This can lead to inefficient searches and increased memory usage in complex environments. To address this, machine learning methods have been explored to predict cost functions, reducing memory load while maintaining optimal solutions. However, these require extensive data collection and struggle in novel, intricate environments. We propose the Fuzzy A* algorithm, an enhancement of the classic A* method, incorporating a new determinant variable to adjust heuristic cost calculations. This adjustment modulates the scope of scanned vertices during searches, optimizing memory usage and computational efficiency. In our approach, unlike traditional A* heuristics that overlook environmental complexities, the Fuzzy A* employs a dynamic heuristic function. This function, leveraging fuzzy logic principles, adapts to varying levels of environmental complexity, allowing a more nuanced estimation of the path cost that considers potential obstructions and route feasibility. This adaptability contrasts with standard machine learning-based solutions, which, while effective in known environments, often falter in unfamiliar or highly complex settings due to their reliance on pre-existing datasets. Our experimental framework involved 100 maze-solving trials in diverse maze configurations, ranging from simple to highly intricate layouts, to evaluate the effectiveness of Fuzzy A*. We employed specific metrics such as path length, computational time, and memory usage for a comprehensive assessment. The results showcased that Fuzzy A* consistently found the shortest paths (99.96% success rate) and significantly reduced memory usage by 67% and 59% compared to Breadth-First-Search (BFS) and traditional A*, respectively. These findings underline the effectiveness of our modified heuristic approach in diverse and challenging environments, highlighting its potential for real-world pathfinding applications.
References
B. K. Oleiwi, A. Mahfuz and H. Roth, "Application of Fuzzy Logic for Collision Avoidance of Mobile Robots in Dynamic-Indoor Environments," 2021 2nd International Conference on Robotics, Electrical and Signal Processing Techniques (ICREST), pp. 131-136, 2021, https://doi.org/10.1109/ICREST51555.2021.9331072.
C. S. Tan, R. Mohd-Mokhtar and M. R. Arshad, "A Comprehensive Review of Coverage Path Planning in Robotics Using Classical and Heuristic Algorithms," in IEEE Access, vol. 9, pp. 119310-119342, 2021, https://doi.org/10.1109/ACCESS.2021.3108177.
K. He, L. He, L. Fan, X. Lei, Y. Deng and G. K. Karagiannidis, "Efficient Memory-Bounded Optimal Detection for GSM-MIMO Systems," in IEEE Transactions on Communications, vol. 70, no. 7, pp. 4359-4372, 2022, https://doi.org/10.1109/TCOMM.2022.3176649.
A. A. Z. Ibrahim, F. Hashim, A. Sali, N. K. Noordin and S. M. E. Fadul, "A Multi-Objective Routing Mechanism for Energy Management Optimization in SDN Multi-Control Architecture," in IEEE Access, vol. 10, pp. 20312-20327, 2022, https://doi.org/10.1109/ACCESS.2022.3149795.
K. L. Keung, L. Xia, C. K. M. Lee and C. Y. Leung, "A Shortest Path Graph Attention Network and Non-traditional Multi-deep Layouts in Robotic Mobile Fulfillment System," 2022 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), pp. 0655-0659, 2022, https://doi.org/10.1109/IEEM55944.2022.9989607.
L. Zhe, L. Yibin, R. Xuewen, and Z. Hui, “Path Planning Based on ADFA∗ Algorithm for Quadruped Robot,” IEEE Access, vol. 7, pp. 111 095–111 101, 2019, https://doi.org/10.1109/ACCESS.2019.2920420.
J. Yang, J. Ni, M. Xi, J. Wen and Y. Li, "Intelligent Path Planning of Underwater Robot Based on Reinforcement Learning," in IEEE Transactions on Automation Science and Engineering, vol. 20, no. 3, pp. 1983-1996, 2023, https://doi.org/10.1109/TASE.2022.3190901.
J. Yang, J. Huo, M. Xi, J. He, Z. Li and H. H. Song, "A Time-Saving Path Planning Scheme for Autonomous Underwater Vehicles With Complex Underwater Conditions," in IEEE Internet of Things Journal, vol. 10, no. 2, pp. 1001-1013, 2023, https://doi.org/10.1109/JIOT.2022.3205685.
T. T. Cam Giang, N. T. Dung, H. T. Thanh Binh, D. Q. Huy and M. T. Thoa, "Wave Environment Decomposition with Adaptive Tri-Objective Particle Swarm Optimization for Mobile Robot Path Planning," 2022 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 990-997, 2022, https://doi.org/10.1109/SSCI51031.2022.10022243.
J. Liu, C. -W. Pui, F. Wang and E. F. Y. Young, "CUGR: Detailed-Routability-Driven 3D Global Routing with Probabilistic Resource Model," 2020 57th ACM/IEEE Design Automation Conference (DAC), pp. 1-6, 2020, https://doi.org/10.1109/DAC18072.2020.9218646.
T. A. Ayall et al., "Graph Computing Systems and Partitioning Techniques: A Survey," in IEEE Access, vol. 10, pp. 118523-118550, 2022, https://doi.org/10.1109/ACCESS.2022.3219422.
Z. Yao, W. Wang, J. Zhang, Y. Wang and J. Li, "Jump Over Block (JOB): An Efficient Line-of-Sight Checker for Grid/Voxel Maps With Sparse Obstacles," in IEEE Robotics and Automation Letters, vol. 8, no. 11, pp. 7575-7582, 2023, https://doi.org/10.1109/LRA.2023.3320435.
E. P. Herrera-Alarcón, M. Satler, M. Vannucci and C. A. Avizzano, "GNGraph: Self-Organizing Maps for Autonomous Aerial Vehicle Planning," in IEEE Robotics and Automation Letters, vol. 7, no. 4, pp. 10721-10728, 2022, https://doi.org/10.1109/LRA.2022.3195192.
S. Franco, J. Sustarevas and S. Bernardini, "Hybrid Discrete-Continuous Path Planning for Lattice Traversal," 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 8971-8978, 2022, https://doi.org/10.1109/IROS47612.2022.9981801.
Z. Husain, A. Al Zaabi, H. Hildmann, F. Saffre, D. Ruta, and A. F. Isakovic, "Search and Rescue in a Maze-like Environment with Ant and Dijkstra Algorithms," in Drones, vol. 6, no. 10, Art. no. 273, 2022, https://doi.org/10.3390/drones6100273.
S. Zhang, Y. Li, F. Ye, X. Geng, Z. Zhou, and T. Shi, "A Hybrid Human-in-the-Loop Deep Reinforcement Learning Method for UAV Motion Planning for Long Trajectories with Unpredictable Obstacles," in Drones, vol. 7, no. 5, Art. no. 311, 2023, https://doi.org/10.3390/drones7050311.
W. He, Z. Cao, and H. Ye, "Path Planning Algorithms for Mobile Robots in Hospital Environment during Covid-19," in Proceedings of the 3rd International Symposium on Artificial Intelligence for Medicine Sciences (ISAIMS '22), pp. 522-530, 2022, https://doi.org/10.1145/3570773.3570853.
S. Kim and B. An, "Learning Heuristic A: Efficient Graph Search using Neural Network," 2020 IEEE International Conference on Robotics and Automation (ICRA), pp. 9542-9547, 2020, https://doi.org/10.1109/ICRA40945.2020.9197015.
M. P. Strub and J. D. Gammell, "Adaptively Informed Trees (AIT*) and Effort Informed Trees (EIT*): Asymmetric bidirectional sampling-based path planning," in Int. J. Rob. Res., vol. 41, no. 4, pp. 390-417, 2022, https://doi.org/10.1177/02783649211069572.
J. Li and X. Wu, "Constrained Shortest Path by Parameter Searching," 2019 2nd International Conference on Safety Produce Informatization (IICSPI), pp. 26-29, 2019, https://doi.org/10.1109/IICSPI48186.2019.9095897.
J. Persis, “A novel routing protocol for underwater wireless sensor network using pareto uninformed and heuristic search techniques,” Wireless Personal Communications, vol. 121, no. 3, pp. 1917-1944, 2021, https://doi.org/10.1007/s11277-021-08747-y.
M. Chen and D. Zhu, "Optimal Time-Consuming Path Planning for Autonomous Underwater Vehicles Based on a Dynamic Neural Network Model in Ocean Current Environments," in IEEE Transactions on Vehicular Technology, vol. 69, no. 12, pp. 14401-14412, 2020, https://doi.org/10.1109/TVT.2020.3034628.
P. Lehner and A. A.-S. affer, “The Repetition Roadmap for Repetitive Constrained Motion Planning,” IEEE Robotics and Automation Letters, vol. 3, no. 4, pp. 3884–3891, 2018, https://doi.org/10.1109/LRA.2018.2856925.
R. Kong and X. Tong, "Anytime Dynamic Heuristic Search for Suboptimal Solution on Path Search," 2020 13th International Congress on Image and Signal Processing, BioMedical Engineering and Informatics (CISP-BMEI), Chengdu, China, 2020, pp. 1070-1074, https://doi.org/10.1109/CISP-BMEI51763.2020.9263589.
J. Wang, N. Wu, W. X. Zhao, F. Peng, and X. Lin , “Empowering A∗ Search Algorithms with Neural Networks for Personalized Route Recommendation,” in Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 539-547, 2019, https://doi.org/10.1145/3292500.3330824.
Y. Wang, S. Wang, Y. Xie, Y. Hu and H. Li, "Q-learning-based Collision-free Path Planning for Mobile Robot in Unknown Environment," 2022 IEEE 17th Conference on Industrial Electronics and Applications (ICIEA), pp. 1104-1109, 2022, https://doi.org/10.1109/ICIEA54703.2022.10006304.
X. Wang, Z. Ning, S. Guo and L. Wang, "Imitation Learning Enabled Task Scheduling for Online Vehicular Edge Computing," in IEEE Transactions on Mobile Computing, vol. 21, no. 2, pp. 598-611, 1 Feb. 2022, https://doi.org/10.1109/TMC.2020.3012509.
S. Choudhury, D. Dey, M. Bhardwaj, S. Arora, A. Kapoor, G. Ranade, and S. Scherer, “Data-driven planning via imitation learning,” The International Journal of Robotics Research, vol. 37, no. 13-14, pp. 1632–1672, 2018, https://doi.org/10.1177/0278364918781001.
P. Cai, S. Wang, Y. Sun and M. Liu, "Probabilistic End-to-End Vehicle Navigation in Complex Dynamic Environments With Multimodal Sensor Fusion," in IEEE Robotics and Automation Letters, vol. 5, no. 3, pp. 4218-4224, 2020, https://doi.org/10.1109/LRA.2020.2994027.
M. Mia et al., “Identifying factors affecting irrigation metrics in the Haor basin using integrated Shannon's entropy, fuzzy logic and automatic linear model,” Environmental Research, vol. 226, p. 115688, 2023, https://doi.org/10.1016/j.envres.2023.115688.
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Gregorius Airlangga
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
This journal is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
