A Formal Concept Analysis Method for Path Planning Based on Formal Contexts
DOI:
https://doi.org/10.54097/k08npz81Keywords:
Path planning, Formal concept analysis, Q-learning algorithmAbstract
Path planning is widely applied in various fields, including robotic movement and 3D printing. In this paper, we propose a path planning method by combining formal concept analysis and the Q-learning algorithm to study grid map path planning. First, a grid map is represented as a formal context, and based on formal concept analysis theory, the necessary region concepts are defined and introduced into the Q-learning algorithm to obtain the optimal path. Finally, through system experiments, it has been proven that using the necessary region concept can reduce redundant information and the effectiveness of this method. The experimental results demonstrate that this method can identify an optimal path with fewer inflection points. This study may provide a new way to achieve optimal path planning based on formal concept analysis.
Downloads
References
[1] Li B, Hui M, Zhu Y, et al. A path planner based on multivariant optimization algorithm with absorption [J]. International Journal of Machine Learning and Cybernetics, 2017, 8: 1743-1750.
[2] Nazarahari M, Khanmirza E, Doostie S. Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm [J]. Expert Systems with Applications, 2019, 115: 106-120.
[3] Tuncer A, Yildirim M. Dynamic path planning of mobile robots with improved genetic algorithm [J]. Computers & Electrical Engineering, 2012, 38(6): 1564-1572.
[4] Xu W, Xu H, Li Q, et al. Stress-based continuous planar path planning for additive manufacturing [J]. Advances in Engineering Software, 2024, 188: 103544.
[5] Tang G, Tang C, Claramunt C, et al. Geometric A-star algorithm: An improved A-star algorithm for AGV path planning in a port environment [J]. IEEE access, 2021, 9: 59196-59210.
[6] Fransen K, van Eekelen J. Efficient path planning for automated guided vehicles using A*(Astar) algorithm incorporating turning costs in search heuristic [J]. International Journal of Production Research, 2023, 61(3): 707-725.
[7] Contreras-Cruz M A, Ayala-Ramirez V, Hernandez-Belmonte U H. Mobile robot path planning using artificial bee colony and evolutionary programming [J]. Applied Soft Computing, 2015, 30: 319-328.
[8] Ayawli B B K, Mei X, Shen M, et al. Mobile robot path planning in dynamic environment using Voronoi diagram and computation geometry technique [J]. Ieee Access, 2019, 7: 86026-86040.
[9] Wu B, Chi X, Zhao C, et al. Dynamic path planning for forklift AGV based on smoothing A* and improved DWA hybrid algorithm [J]. Sensors, 2022, 22(18): 7079.
[10] Zhao J, Liu S, Li J. Research and implementation of autonomous navigation for mobile robots based on SLAM algorithm under ROS [J]. Sensors, 2022, 22(11): 4172.
[11] Yu H, Dai Q. DWE-IL: a new incremental learning algorithm for non-stationary time series prediction via dynamically weighting ensemble learning [J]. Applied Intelligence, 2022, 52(1): 174-194.
[12] Wu J, Ma X, Peng T, et al. An improved timed elastic band (TEB) algorithm of autonomous ground vehicle (AGV) in complex environment [J]. Sensors, 2021, 21(24): 8312.
[13] Semnani S H, Liu H, Everett M, et al. Multi-agent motion planning for dense and dynamic environments via deep reinforcement learning [J]. IEEE Robotics and Automation Letters, 2020, 5(2): 3221-3226.
[14] Fan J, Wang Z, Xie Y, et al. A theoretical analysis of deep Q-learning. InLearning for dynamics and control [J]. 2020.
[15] Fransen K, van Eekelen J. Efficient path planning for automated guided vehicles using A*(Astar) algorithm incorporating turning costs in search heuristic [J]. International Journal of Production Research, 2023, 61(3): 707-725.
[16] Zhang Z, Jiang J, Wu J, et al. Efficient and optimal penetration path planning for stealth unmanned aerial vehicle using minimal radar cross-section tactics and modified A-Star algorithm [J]. ISA transactions, 2023, 134: 42-57.
[17] Yan C, Xiang X, Wang C. Towards real-time path planning through deep reinforcement learning for a UAV in dynamic environments [J]. Journal of Intelligent & Robotic Systems, 2020, 98: 297-309.
[18] Wille R. Restructuring lattice theory: an approach based on hierarchies of concepts[C]//Formal Concept Analysis: 7th International Conference, ICFCA 2009 Darmstadt, Germany, May 21-24, 2009 Proceedings 7. Springer Berlin Heidelberg, 2009: 314-339.
[19] Wu W Z, Leung Y, Mi J S. Granular computing and knowledge reduction in formal contexts [J]. IEEE transactions on knowledge and data engineering, 2008, 21(10): 1461-1474.
[20] Hao F, Pei Z, Yang L T. Diversified top-k maximal clique detection in social internet of things [J]. Future Generation Computer Systems, 2020, 107: 408-417.
[21] Qi J, Wei L, Yao Y. Three-way formal concept analysis[C]//Rough Sets and Knowledge Technology: 9th International Conference, RSKT 2014, Shanghai, China, October 24-26, 2014, Proceedings 9. Springer International Publishing, 2014: 732-741.
[22] Yao Y. The geometry of three-way decision [J]. Applied Intelligence, 2021, 51(9): 6298-6325.
[23] Kent R E. Rough concept analysis: a synthesis of rough sets and formal concept analysis [J]. Fundamenta informaticae, 1996, 27(2-3): 169-181.
[24] Zhi H, Li J. Granule description based knowledge discovery from incomplete formal contexts via necessary attribute analysis [J]. Information Sciences, 2019, 485: 347-361.
[25] Zhi H, Ma Y, Li Y, et al. Granule description with undetermined values in a three-way epistemic perspective [J]. Information Sciences, 2024, 655: 119863.
[26] Zhi H, Qi Z, Li Y. An efficient conflict analysis method based on splitting and merging of formal contexts [J]. Information Sciences, 2024, 661: 120154.
[27] Zhi H, Li J, Li Y. Multilevel conflict analysis based on fuzzy formal contexts [J]. IEEE Transactions on Fuzzy Systems, 2022, 30(12): 5128-5142.
[28] Wei L, Qian T. The three-way object oriented concept lattice and the three-way property oriented concept lattice[C]//2015 International Conference on Machine Learning and Cybernetics (ICMLC). IEEE, 2015, 2: 854-859.
[29] Xu W, Guo D, Qian Y, et al. Two-way concept-cognitive learning method: a fuzzy-based progressive learning [J]. IEEE Transactions on Fuzzy Systems, 2022, 31(6): 1885-1899.
[30] Zhang Z, Xu X, Yue F, et al. Robot path planning based on concept lattice [J]. International Journal of Approximate Reasoning, 2023, 153: 87-103.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Journal of Computer Science and Artificial Intelligence
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
