Robot path planning based on concept lattice. (English) Zbl 1524.68384
Summary: Path planning is a popular topic in research on mobile robots. In this paper, we apply the concept lattice to the path planning problem for the first time in the literature to propose a static path planning algorithm. The given grid map is first transformed into the formal context of the grid, and locational relations between rectangular regions are mapped into partial-order relations in the graph of rectangular regions based on a lattice of region concepts. Following this, the path planning problem on the original grid map is transformed into a path searching problem in the graph of rectangular regions. The graph derived from the sublattice of region concepts is used to avoid the high time complexity of applying the complete concept lattice. Finally, a novel path planning algorithm that can generate a path consisting of rectangular regions is constructed. This path can also be converted into the path consisting of inflection points. The results of simulations verified the effectiveness of the proposed method. It can generate a path with significantly fewer inflection points than the \(\mathrm{A}^*\) algorithm for a four-direction (left, right, front, back) mobile robot.
References:
| [1] | Ma, X.; Zhao, Y.; Lin, W., Application of improved A* algorithm in bridge crane, Process Automat. Instr., 42, 4, 102-106 (2020) |
| [2] | Tang, Gang; Tang, Congqiang; Claramunt, Christophe; Hu, Xiong; Zhou, Peipei, Geometric A-Star algorithm: an improved A-Star algorithm for AGV path planning in a port environment, IEEE Access, 9, 59196-59210 (2021) |
| [3] | Tsardoulias, E. G.; Iliakopoulou, A.; Kargakos, A.; Petrou, L., A review of global path planning methods for occupancy grid maps regardless of obstacle density, J. Intell. Robot. Syst., 84, 1-4, 829-858 (2016) |
| [4] | Xu, Y.; Liu, R., Path planning for mobile articulated robots based on the improved A* algorithm, Int. J. Adv. Robot. Syst., 14, 4, 1-10 (2017) |
| [5] | Guo, W.; Qin, G.; Wang, L., Robot path planning based on improved artificial fish swarm algorithm and MAKLINK graph, Control Decis., 45, 9, 2145-2152 (2020) |
| [6] | Xu, L.; Fu, W.; Jiang, W., Mobile robots path planning based on 16 directions 24-neighborhoods improved ant colony algorithm, Control Decis., 36, 5, 1137-1146 (2021) |
| [7] | Lee, J., Heterogeneous-ants-based path planner for global path planning of mobile robot applications, Int. J. Control. Autom. Syst., 15, X, 1-16 (2017) |
| [8] | Contreras-Cruz, M. A.; Ayala-Ramirez, V.; Hernandez-Belmonte, U. H., Mobile robot path planning using artificial bee colony and evolutionary programming, Appl. Soft Comput., 30, 319-328 (2015) |
| [9] | Ruan, J.; Zhang, X.; Huang, J., An environment cognition model combined with intrinsic motivation for mobile robots, Control Decis., 36, 9, 2211-2217 (2021) |
| [10] | Sun, H.; Hu, C.; Zhang, J., Deep reinforcement learning for motion planning of mobile robots, Control Decis., 36, 6, 1281-1292 (2021) |
| [11] | Stentz, A., Optimal and efficient path planning for partially-known environments, Proc. - IEEE Int. Conf. Robot. Autom., 4, 3310-3317 (1994) |
| [12] | Koenig, S.; Likhachev, M.; Furcy, D., Lifelong planning A*, Artif. Intell., 155, 1-2, 93-146 (2004) · Zbl 1085.68674 |
| [13] | Qi, J.; Yang, H.; Sun, H., MOD-RRT*: A sampling-based algorithm for robot path planning in dynamic environment, IEEE Trans. Ind. Electron., 68, 8, 7244-7251 (2020) |
| [14] | Wu, C.; Zhou, S.; Xiao, L., Dynamic path planning based on improved ant colony algorithm in traffic congestion, IEEE Access, 8, 180773-180783 (2020) |
| [15] | Khatib, O., Real-time obstacle avoidance for manipulators and mobile robots, (Proceedings. 1985 IEEE International Conference on Robotics and Automation, vol. 2 (1985)), 500-505 |
| [16] | Ayawli, B. B.K.; Mei, X.; Shen, M.; Appiah, A. Y.; Kyeremeh, F., Mobile robot path planning in dynamic environment using voronoi diagram and computation geometry technique, IEEE Access, 7, 86026-86040 (2019) |
| [17] | Guo, X.; Ji, M.; Zhang, W., AGV global path planning integrating with the control of multi-objectives and speed, Control Decis., 35, 6, 1369-1376 (2020) |
| [18] | Li, B.; Lu, D.; Zhang, Q., A path planner based on multivariant optimization algorithm, Acta Electron. Sin., 44, 9, 2242-2247 (2016) |
| [19] | Liu, C.; Han, J.; An, K., Dynamic path planning based on an improved RRT algorithm for robocup robot, ROBOT, 39, 1, 8-15 (2017) |
| [20] | Wille, R., Restructuring lattice theory: an approach based on hierarchies of concepts, (Rival, I., Ordered Sets. Ordered Sets, NATO Advanced Study Institutes Series, vol. 83 (1982), Springer: Springer Dordrecht), 445-470 · Zbl 0491.06008 |
| [21] | Li, J.; Wei, L.; Zhang, Z., Concept lattice theory and method and their research prospect, Int. J. Pattern Recognit. Artif. Intell., 33, 7, 619-642 (2020) |
| [22] | Zhang, Z.; Du, J.; Wang, L., Formal concept analysis approach for data extraction from a limited deep web database, J. Intell. Inf. Syst., 41, 2, 211-234 (2013) |
| [23] | Cimiano, P.; Hotho, A.; Staab, S., Learning concept hierarchies from text corpora using formal concept analysis, J. Artif. Intell. Res., 24, 305-339 (2005) · Zbl 1080.68700 |
| [24] | Makhalova, T., Introducing the closure structure and the GDPM algorithm for mining and understanding a tabular dataset, Int. J. Approx. Reason., 145, 75-90 (2022) · Zbl 1529.68262 |
| [25] | Dijkstra, E. W., A note on two problems in connexion with graphs, Numer. Math., 1, 1, 139-142 (1959) · Zbl 0092.16002 |
| [26] | Hart, P. E.; Nilsson, N. J.; Raphael, B., A formal basis for the heuristic determination of minimum cost paths, IEEE Trans. Syst. Sci. Cybern., 4, 2, 100-107 (1968) |
| [27] | Korf, R. E., Depth-first iterative-deepening: an optimal admissible tree search, Artif. Intell., 27, 1, 97-109 (1985) · Zbl 0573.68030 |
| [28] | Kavraki, L. E.; Svestka, P.; Latombe, J. C.; Overmars, M. H., Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE Trans. Robot. Autom., 12, 4, 566-580 (1996) |
| [29] | LaValle, S. M., Rapidly-exploring random trees: a new tool for path planning (1998), Research Report |
| [30] | Nazarahari, M.; Khanmirza, E.; Doostie, S., Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm, Expert Syst. Appl., 115, 106-120 (2019) |
| [31] | Chen, W.; Wu, X.; Lu others, Y., An improved path planning method based on artificial potential field for a mobile robot, Cybern. Inf. Technol., 15, 2, 181-191 (2015) |
| [32] | Guo, N.; Li, C.; Gao, T.; Liu, G.; Li, Y.; Wang, D., A fusion method of local path planning for mobile robots based on lstm neural network and reinforcement learning, Math. Probl. Eng., 2021 (2021) |
| [33] | Wu, K.; Esfahani, M. A.; Yuan, S.; Wang, H., TDPP-net: achieving threedimensional path planning via a deep neural network architecture, Neurocomputing, 357, 151-162 (2019) |
| [34] | Guo, L.; Jia, Z.; Li, Q., Steadiness analysis of means-end conceptual paths and problem-chains based on concept lattices and similarity measuring, Int. J. Mach. Learn. Cybern., 13, 3, 691-719 (2022) |
| [35] | Li, J. H., Concept learning via granular computing: a cognitive viewpoint, Inf. Sci., 298, 447-467 (2015) · Zbl 1360.68688 |
| [36] | Li, J. H.; Mi, Y. L.; Liu, W. Q., Incremental cognition of concepts: theories and methods, Chinese J. Comput., 42, 10, 2233-2250 (2019) |
| [37] | Zhang, J.; Wu, J.; Shen, X.; Li, Y., Autonomous land vehicle path planning algorithm based on improved heuristic function of A-Star, Int. J. Adv. Robot. Syst., 18, 5, 1-10 (2021) |
| [38] | Liu, Z.; Liu, H.; Lu, Z.; Zeng, Q., A dynamic fusion path finding algorithm using delaunay triangulation and improved a-star for mobile robots, IEEE Access, 9, 20602-20621 (2021) |
| [39] | Ganter, B.; Wille, R., Formal Concept Analysis: Mathematical Foundations (1999), Springer Verlag: Springer Verlag New York · Zbl 0909.06001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
