Modified Q-Learning Algorithm for Mobile Robot Path Planning Variation using Motivation Model
Abstract
Path planning is an essential algorithm in autonomous mobile robots, including agricultural robots, to find the shortest path and to avoid collisions with obstacles. Q-Learning algorithm is one of the reinforcement learning methods used for path planning. However, for multi-robot system, this algorithm tends to produce the same path for each robot. This research modifies the Q-Learning algorithm in order to produce path variations by utilizing the motivation model, i.e. achievement motivation, in which different motivation parameters will result in different optimum paths. The Motivated Q-Learning (MQL) algorithm proposed in this study was simulated in an area with three scenarios, i.e. without obstacles, uniform obstacles, and random obstacles. The results showed that, in the determined scenario, the MQL can produce 2 to 4 variations of optimum path without any potential of collisions (Jaccard similarity = 0%), in contrast to the Q-Learning algorithm that can only produce one optimum path variation. This result indicates that MQL can solve multi-robots path planning problems, especially when the number of robots is large, by reducing the possibility of collisions as well as decreasing the problem of queues. However, the average computational time of the MQL is slightly longer than that of the Q-Learning.
Keywords
Full Text:
PDFReferences
S. S. Valle and J. Kienzle, “Agriculture 4.0 - Agricultural robotics and automated equipment for sustainable crop production,” in Integrated Crop Management, vol. 24, no. 24, p. 40, 2020.
M. Javaid, A. Haleem, R. P. Singh, and R. Suman, “Enhancing smart farming through the applications of Agriculture 4.0 technologies,” Int. J. Intell. Networks, vol. 3, pp. 150–164, 2022, doi: 10.1016/j.ijin.2022.09.004.
M. B. Ahsan, G. Leifeng, F. Mohammad, S. Azam, B. Xu, and S. J. Rayhan, “Barriers, Challenges, and Requirements for ICT Usage among Sub-Assistant Agricultural Officers in Bangladesh : Toward Sustainability in Agriculture,” Sustainability, vol. 15, no. 782, pp. 1–29, 2023, doi: 10.3390/su15010782.
S. Ruzzante, R. Labarta, and A. Bilton, “Adoption of agricultural technology in the developing world: A meta-analysis of the empirical literature,” World Development, vol. 146, p. 105599, 2021, doi: 10.1016/j.worlddev.2021.105599.
L. F. P. Oliveira, A. P. Moreira, and M. F. Silva, “Advances in agriculture robotics: A state-of-the-art review and challenges ahead,” Robotics, vol. 10, no. 2, pp. 1–31, 2021, doi: 10.3390/robotics10020052.
L. C. Santos, F. N. Santos, E. J. Solteiro Pires, A. Valente, P. Costa and S. Magalhães, "Path Planning for ground robots in agriculture: a short review," 2020 IEEE International Conference on Autonomous Robot Systems and Competitions (ICARSC), pp. 61-66, 2020, doi: 10.1109/ICARSC49921.2020.9096177.
S. Chakraborty, D. Elangovan, P. L. Govindarajan, M. F. ELnaggar, M. M. Alrashed, and S. Kamel, “A Comprehensive Review of Path Planning for Agricultural Ground Robots,” Sustain., vol. 14, no. 15, pp. 1–19, 2022, doi: 10.3390/su14159156.
C. Cheng, J. Fu, H. Su, and L. Ren, “Recent Advancements in Agriculture Robots: Benefits and Challenge,” Machines, vol. 11, no. 48, pp. 1–24, 2023, doi: https://doi.org/10.3390/machines11010048.
Q. Yang, X. Du, Z. Wang, Z. Meng, Z. Ma, and Q. Zhang, “A review of core agricultural robot technologies for crop productions,” Comput. Electron. Agric., vol. 206, p. 107701, 2023, doi: 10.1016/j.compag.2023.107701.
P. Gonzalez-de-Santos, R. Fernández, D. Sepúlveda, E. Navas, L. Emmi, and M. Armada, “Field Robots for Intelligent Farms—Inhering Features from Industry,” Agronomy, vol. 10, no. 11, p. 1638, 2020, doi: 10.3390/agronomy10111638.
V. Marinoudi, C. G. Sørensen, S. Pearson, and D. Bochtis, “Robotics and labour in agriculture. A context consideration,” Biosyst. Eng., vol. 184, pp. 111–121, 2019, doi: 10.1016/j.biosystemseng.2019.06.013.
X. Gao et al., “Review of wheeled mobile robots’ navigation problems and application prospects in agriculture,” IEEE Access, vol. 6, pp. 49248–49268, 2018, doi: 10.1109/ACCESS.2018.2868848.
J. Chen, H. Qiang, J. Wu, G. Xu, and Z. Wang, “Navigation path extraction for greenhouse cucumber-picking robots using the prediction-point Hough transform,” Comput. Electron. Agric., vol. 180, p. 105911, 2021, doi: 10.1016/j.compag.2020.105911.
A. Loganathan and N. S. Ahmad, “A systematic review on recent advances in autonomous mobile robot navigation,” Eng. Sci. Technol. an Int. J., vol. 40, p. 101343, 2023, doi: 10.1016/j.jestch.2023.101343.
I. Nizar and M. Mestari, “Mobile Robot Autonomous Navigation: A Path Planning Approach,” IFAC-PapersOnLine, vol. 55, no. 12, pp. 610–615, 2022, doi: 10.1016/j.ifacol.2022.07.379.
Y. Bai, B. Zhang, N. Xu, J. Zhou, J. Shi, and Z. Diao, “Vision-based navigation and guidance for agricultural autonomous vehicles and robots: A review,” Comput. Electron. Agric., vol. 205, p. 107584, 2023, doi: 10.1016/j.compag.2022.107584.
T. T. Mac, C. Copot, D. 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.
M. S. Abed, O. F. Lutfy, and Q. F. Al-Doori, “A Review on Path Planning Algorithms for Mobile Robots,” Eng. Technol. J., vol. 39, no. 5, pp. 804–820, 2021, doi: 10.30684/etj.v39i5A.1941.
H. Tian, “Research on Robot Path Planning Based on Improved Ant Colony Algorithm,” Int. J. Comput. Sci. Math., vol. 13, no. 1, pp. 80–92, 2021, doi: 10.1088/1742-6596/1992/3/032050.
L. Wu, X. Huang, J. Cui, C. Liu, and W. Xiao, “Modified adaptive ant colony optimization algorithm and its application for solving path planning of mobile robot,” Expert Syst. Appl., vol. 215, p. 119410, 2023, doi: 10.1016/j.eswa.2022.119410.
C. Liu et al., “An improved heuristic mechanism ant colony optimization algorithm for solving path planning,” Knowledge-Based Syst., vol. 271, p. 110540, 2023, doi: 10.1016/j.knosys.2023.110540.
M. Morin, I. Abi-Zeid, and C.-G. Quimper, “Ant colony optimization for path planning in search and rescue operations,” Eur. J. Oper. Res., vol. 305, no. 1, pp. 53–63, 2023, doi: 10.1016/j.ejor.2022.06.019.
C. Miao, G. Chen, C. Yan, and Y. Wu, “Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm,” Comput. Ind. Eng., vol. 156, p. 107230, 2021.
D. Di Caprio, A. Ebrahimnejad, H. Alrezaamiri, and F. J. Santos-Arteaga, “A novel ant colony algorithm for solving shortest path problems with fuzzy arc weights,” Alexandria Eng. J., vol. 61, no. 5, pp. 3403–3415, 2022, doi: 10.1016/j.aej.2021.08.058.
H.-J. Wang, Y. Fu, Z.-Q. Zhao, and Y.-J. Yue, “An Improved Ant Colony Algorithm of Robot Path Planning for Obstacle Avoidance,” J. Robot., vol. 2019, pp. 1–8, 2019, doi: 10.1155/2019/6097591.
X. Pu, C. Xiong, L. Ji, and L. Zhao, “3D path planning for a robot based on improved ant colony algorithm,” Evol. Intell., pp. 1-11, 2020, doi: 10.1007/s12065-020-00397-6.
Y. Xue, Y. Chen, Z. Ding, X. Huang, and D. Xi, "Robot path planning based on improved ant colony algorithm," 2021 Power System and Green Energy Conference (PSGEC), pp. 129-133, 2021, doi: 10.1109/PSGEC51302.2021.9541872.
T. Wang, L. Zhao, Y. Jia, and J. Wang, “Robot Path Planning Based on Improved Ant Colony Algorithm,” 2018 WRC Symposium on Advanced Robotics and Automation (WRC SARA), pp. 70–76, 2018, doi: 10.1109/WRC-SARA.2018.8584217.
R. Sarkar, D. Barman, and N. Chowdhury, “Domain knowledge based genetic algorithms for mobile robot path planning having single and multiple targets,” J. King Saud Univ. - Comput. Inf. Sci., vol. 34, no. 7, pp. 4269–4283, 2022, doi: 10.1016/j.jksuci.2020.10.010.
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.
K. Hao, J. Zhao, Z. Li, Y. Liu, and L. Zhao, “Dynamic path planning of a three-dimensional underwater AUV based on an adaptive genetic algorithm,” Ocean Eng., vol. 263, p. 112421, 2022, doi: 10.1016/j.oceaneng.2022.112421.
W. Rahmaniar and A. E. Rakhmania, “Mobile Robot Path Planning in a Trajectory with Multiple Obstacles Using Genetic Algorithms,” J. Robot. Control, vol. 3, no. 1, pp. 1–7, 2022, doi: 10.18196/jrc.v3i1.11024.
M. Fan, J. He, S. Ding, Y. Ding, M. Li, and L. Jiang, “Research and implementation of multi-robot path planning based on genetic algorithm,” 2021 5th International Conference on Automation, Control and Robots (ICACR), pp. 140–144, 2021, doi: 10.1109/ICACR53472.2021.9605194.
A. López-González, J. A. Meda Campaña, E. G. Hernández Martínez, and P. P. Contro, “Multi robot distance based formation using Parallel Genetic Algorithm,” Appl. Soft Comput., vol. 86, p. 105929, 2020, doi: 10.1016/j.asoc.2019.105929.
A. Al Hilli, M. Al-Ibadi, A. M. Alfadhel, S. H. Abdulshaheed, and A. H. Hadi, “Optimal path finding in stochastic quasi-dynamic environments using particle swarm optimization,” Expert Syst. Appl., vol. 186, p. 115706, 2021, doi: 10.1016/j.eswa.2021.115706.
H. S. Dewang, P. K. Mohanty, and S. Kundu, “A Robust Path Planning for Mobile Robot Using Smart Particle Swarm Optimization,” Procedia Comput. Sci., vol. 133, pp. 290–297, 2018, doi: 10.1016/j.procs.2018.07.036.
P. B. Fernandes, R. C. L. Oliveira, and J. V. Fonseca Neto, “Trajectory planning of autonomous mobile robots applying a particle swarm optimization algorithm with peaks of diversity,” Appl. Soft Comput., vol. 116, p. 108108, 2022, doi: 10.1016/j.asoc.2021.108108.
S. Lin, A. Liu, J. Wang, and X. Kong, “An intelligence-based hybrid PSO-SA for mobile robot path planning in warehouse,” J. Comput. Sci., vol. 67, p. 101938, 2023, doi: 10.1016/j.jocs.2022.101938.
B. Alkhlidi, A. T. Abdulsadda, and A. Al Bakri, “Optimal robotic path planning using intelligent search algorithms,” J. Robot. Control, vol. 2, no. 6, pp. 519–526, 2021, doi: 10.18196/jrc.26132.
P. K. Das and P. K. Jena, “Multi-robot path planning using improved particle swarm optimization algorithm through novel evolutionary operators,” Appl. Soft Comput. J., vol. 92, p. 106312, 2020, doi: 10.1016/j.asoc.2020.106312.
M. Samadi Gharajeh and H. B. Jond, “An intelligent approach for autonomous mobile robots path planning based on adaptive neuro-fuzzy inference system,” Ain Shams Eng. J., vol. 13, no. 1, p. 101491, 2022, doi: 10.1016/j.asej.2021.05.005.
C. Ntakolia, S. Moustakidis, and A. Siouras, “Autonomous path planning with obstacle avoidance for smart assistive systems,” Expert Syst. Appl., vol. 213, p. 119049, 2023, doi: 10.1016/j.eswa.2022.119049.
R. Zhen, P. Lv, Z. Shi, and G. Chen, “A novel fuzzy multi-factor navigational risk assessment method for ship route optimization in costal offshore wind farm waters,” Ocean Coast. Manag., vol. 232, p. 106428, 2023, doi: 10.1016/j.ocecoaman.2022.106428.
T. Shen and J. Zhai, "Reactive Obstacle Avoidance Strategy Based on Fuzzy Neural Network and Arc Trajectory," 2019 Chinese Automation Congress (CAC), pp. 4792-4796, 2019, doi: 10.1109/CAC48633.2019.8996374.
N. Awad, A. Lasheen, M. Elnaggar, and A. Kamel, “Model predictive control with fuzzy logic switching for path tracking of autonomous vehicles,” ISA Trans., vol. 129, pp. 193–205, 2022, doi: 10.1016/j.isatra.2021.12.022.
N. Rinanto, I. Marzuqi, A. Khumaidi, and S. T. Sarena, “Obstacle Avoidance using Fuzzy Logic Controller on Wheeled Soccer Robot,” J. Ilm. Tek. Elektro Komput. dan Inform., vol. 5, no. 1, pp. 26–35, 2019, doi: 10.26555/jiteki.v5i1.13298.
O. O. Martins, A. A. Adekunle, O. M. Olaniyan, and B. O. Bolaji, “An Improved multi-objective a-star algorithm for path planning in a large workspace: Design, Implementation, and Evaluation,” Sci. African, vol. 15, p. e01068, 2022, doi: 10.1016/j.sciaf.2021.e01068.
L. Pasandi, M. Hooshmand, and M. Rahbar, “Modified A* Algorithm integrated with ant colony optimization for multi-objective route-finding; case study: Yazd,” Appl. Soft Comput., vol. 113, p. 107877, 2021, doi: 10.1016/j.asoc.2021.107877.
J. P. Vasconez et al., “Comparison of path planning methods for robot robot navigation in simulated agricultural environments,” The 1st International Workshop on Human-Centric Innovation and Computational Intelligence (IWHICI 2023), vol. 220, pp. 898–903, 2023, doi: 10.1016/j.procs.2023.03.122.
X. Zhong, J. Tian, H. Hu, and X. Peng, “Hybrid path planning based on safe A* algorithm and adaptive window approach for mobile robot in large-scale dynamic environment,” J. Intell. Robot. Syst. Theory Appl., vol. 99, no. 1, pp. 65–77, 2020, doi: 10.1007/s10846-019-01112-z.
S. Hosseininejad and C. Dadkhah, “Mobile robot path planning in dynamic environment based on cuckoo optimization algorithm,” Int. J. Adv. Robot. Syst., vol. 16, no. 2, pp. 1–13, 2019, doi: 10.1177/1729881419839575.
J. Yu, Y. Wang, X. Ruan, G. Zuo, and C. Li, “AGV multi-objective path planning method based on improved cuckoo algorithm,” 2019 IEEE 4th Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), pp. 556–561, 2019, doi: 10.1109/IAEAC47372.2019.8997687.
J. Wang, X. Shang, T. Guo, J. Zhou, S. Jia and C. Wang, "Optimal Path Planning Based on Hybrid Genetic-Cuckoo Search Algorithm," 2019 6th International Conference on Systems and Informatics (ICSAI), pp. 165-169, 2019, doi: 10.1109/ICSAI48974.2019.9010519.
L. Zhao, F. Wang, and Y. Bai, “Route planning for autonomous vessels based on improved artificial fish swarm algorithm,” Ships Offshore Struct., vol. 18, no. 6, pp. 897-906, 2022, doi: 10.1080/17445302.2022.2081423.
S. Kumar and A. Sikander, “A modified probabilistic roadmap algorithm for efficient mobile robot path planning,” Eng. Optim., vol. 55, no. 9, pp. 1616-1634, 2022, doi: 10.1080/0305215X.2022.2104840.
J. C. Mohanta and A. Keshari, “A knowledge based fuzzy-probabilistic roadmap method for mobile robot navigation,” Appl. Soft Comput., vol. 79, pp. 391–409, 2019, doi: 10.1016/j.asoc.2019.03.055.
M. S. Das, S. Sanyal, and S. Mandal, “Navigation of Multiple Robots in Formative Manner in an Unknown Environment using Artificial Potential Field Based Path Planning Algorithm,” Ain Shams Eng. J., vol. 13, no. 5, p. 101675, 2022, doi: 10.1016/j.asej.2021.101675.
Z. Wu, J. Dai, B. Jiang, and H. R. Karimi, “Robot path planning based on artificial potential field with deterministic annealing,” ISA Trans., vol. 112, p. 106640, 2023, doi: 10.1016/j.ast.2021.106640.
A. Lazarowska, “Discrete Artificial Potential Field Approach to Mobile Robot Path Planning,” IFAC-PapersOnLine, vol. 52, no. 8, pp. 334–337, 2019, doi: 10.1016/j.ifacol.2019.08.083.
F. Sui, X. Tang, Z. Dong, X. Gan, P. Luo, and J. Sun, “ACO+PSO+A*: A bi-layer hybrid algorithm for multi-task path planning of an AUV,” Comput. Ind. Eng., vol. 175, p. 108905, 2023, doi: 10.1016/j.cie.2022.108905.
B. Sahu, P. Kumar Das, and R. Kumar, “A Modified Cuckoo Search Algorithm implemented with SCA and PSO for Multi-robot Cooperation and Path Planning,” Cogn. Syst. Res., vol. 79, pp. 24-42, 2023, doi: 10.1016/j.cogsys.2023.01.005.
F. Gul, I. Mir, D. Alarabiat, H. M. Alabool, L. Abualigah, and S. Mir, “Implementation of bio-inspired hybrid algorithm with mutation operator for robotic path planning,” J. Parallel Distrib. Comput., vol. 169, pp. 171–184, 2022, doi: 10.1016/j.jpdc.2022.06.014.
D. Zhang, Y. Yin, R. Luo, and S. Zou, “Hybrid IACO-A*-PSO optimization algorithm for solving multiobjective path planning problem of mobile robot in radioactive environment,” Prog. Nucl. Energy, vol. 159, p. 104651, 2023, doi: 10.1016/j.pnucene.2023.104651.
X. Pu, C. Xiong and L. Zhao, "Path Planning for Robot Based on IACO-SFLA Hybrid Algorithm," 2020 Chinese Control And Decision Conference (CCDC), pp. 4886-4893, 2020, doi: 10.1109/CCDC49329.2020.9164671.
G. Kulathunga, “A Reinforcement Learning based Path Planning Approach in 3D Environment,” Procedia Comput. Sci., vol. 212, pp. 152–160, 2021, doi: 10.1016/j.procs.2022.10.217.
F. Gismondi, C. Possieri, and A. Tornambe, “A solution to the path planning problem via algebraic geometry and reinforcement learning,” J. Franklin Inst., vol. 359, no. 2, pp. 1732–1754, 2022, doi: 10.1016/j.jfranklin.2021.12.003.
X. Zhang, S. Xia, X. Li, and T. Zhang, “Multi-objective particle swarm optimization with multi-mode collaboration based on reinforcement learning for path planning of unmanned air vehicles,” Knowledge-Based Syst., vol. 250, p. 109075, 2022, doi: 10.1016/j.knosys.2022.109075.
E. S. Low, P. Ong, C. Y. Low, and R. Omar, “Modified Q-learning with distance metric and virtual target on path planning of mobile robot,” Expert Syst. Appl., vol. 199, p. 117191, 2022, doi: 10.1016/j.eswa.2022.117191.
L. D. Hanh and V. D. Cong, “Path following and avoiding obstacle for mobile robot under dynamic environments using reinforcement learning,” J. Robot. Control, vol. 4, no. 2, pp. 157–164, 2023, doi: 10.18196/jrc.v4i2.17368.
E. S. Low, P. Ong, and K. C. Cheah, “Solving the optimal path planning of a mobile robot using improved Q-Learning,” Rob. Auton. Syst., vol. 115, pp. 143–161, 2019, doi: 10.1016/j.robot.2019.02.013.
S. Gu, “An algorithm for path planning based on improved Q-Learning,” in The Genetic and Evolutionary Computing, pp. 20–29, 2019, doi: 10.1007/978-981-15-3308-2_3.
S. Gu and G. Mao, “An improved Q-Learning algorithm for path planning in maze environments,” Intelligent Systems and Applications, vol. 1251, no. 2, pp. 545–557, 2020, doi: 10.1007/978-3-030-55187-2_40.
M. Zhao, H. Lu, S. Yang, and F. Guo, “The experience-memory Q-Learning algorithm for robot path planning in unknown environment,” IEEE Access, vol. 8, pp. 47824–47844, 2020, doi: 10.1109/ACCESS.2020.2978077.
C. Yan and X. Xiang, “A Path Planning Algorithm for UAV Based on Improved Q-Learning,” in 2nd International Conference on Robotics and Automation Sciences (ICRAS), pp. 46–50, 2018, doi: 10.1109/ICRAS.2018.8443226.
T. Zhang, X. Huo, S. Chen, B. Yang and G. Zhang, "Hybrid Path Planning of A Quadrotor UAV Based on Q-Learning Algorithm," 2018 37th Chinese Control Conference (CCC), pp. 5415-5419, 2018, doi: 10.23919/ChiCC.2018.8482604.
H. Hidayat, A. Buono, K. Priandana, and S. Wahjuni, “Modified Q-Learning algorithm for mobile robot real-time path planning using reduced states,” RESTI (Rekayasa Sist. dan Teknol. Informasi), vol. 7, no. 3, pp. 628–636, 2023, doi: 10.29207/resti.v7i3.4949.
K. E. Merrick and K. Shafi, “Achievement, affiliation, and power: Motive profiles for artificial agents,” Adapt. Behav., vol. 19, no. 1, pp. 40–62, 2011, doi: 10.1177/1059712310395953.
M. K. D. Hardhienata, V. Ugrinovskii, and K. E. Merrick, “Task allocation under communication constraints using motivated Particle Swarm Optimization,” in IEEE Congress on Evolutionary Computation (CEC), pp. 3135–3142, 2014, doi: 10.1109/CEC.2014.6900560.
M. K. D. Hardhienata, K. E. Merrick and V. Ugrinovskii, "Task allocation in multi-agent systems using models of motivation and leadership," 2012 IEEE Congress on Evolutionary Computation, pp. 1-8, 2012, doi: 10.1109/CEC.2012.6256114.
R. S. Sutton and A. G. Barto, Reinforcement Learning: An introduction. MIT Press, 2018.
C. J. C. H. Watkins, “Technical Note Q-Learning,” Mach. Learn., vol. 8, pp. 279–292, 1992, doi: 10.1109/ICCC49849.2020.9238991.
P. Jaccard, “The distribution of the flora in the Alpine Zone,” New Phytol., vol. 11, no. 2, pp. 37–50, 1912, doi: 10.1111/j.1469-8137.1912.tb05611.x.
H. Seifoddini and M. Djassemi, “The production data-based similarity coefficient versus Jaccard’s similarity coefficient,” Comput. Ind. Eng., vol. 21, no. 1–4, pp. 263–266, 1991, doi: 10.1016/0360-8352(91)90099-R.
DOI: https://doi.org/10.18196/jrc.v4i5.18777
Refbacks
- There are currently no refbacks.
Copyright (c) 2023 Hidayat Hidayat, Agus Buono, Karlisa Priandana, Sri Wahjuni
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Journal of Robotics and Control (JRC)
P-ISSN: 2715-5056 || E-ISSN: 2715-5072
Organized by Peneliti Teknologi Teknik Indonesia
Published by Universitas Muhammadiyah Yogyakarta in collaboration with Peneliti Teknologi Teknik Indonesia, Indonesia and the Department of Electrical Engineering
Website: http://journal.umy.ac.id/index.php/jrc
Email: jrcofumy@gmail.com