[1]CAI Jun,ZHONG Zhiyuan.Path planning of a meal delivery robot based on an improved ant colony algorithm[J].CAAI Transactions on Intelligent Systems,2024,19(2):370-380.[doi:10.11992/tis.202205056]
Copy
Path planning of a meal delivery robot based on an improved ant colony algorithm
CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume:
19
Number of periods:
2024 2
Page number:
370-380
Column:
学术论文—智能系统
Public date:
2024-03-05
- Title:
- Path planning of a meal delivery robot based on an improved ant colony algorithm
- Keywords:
- ant colony algorithm; genetic algorithm; state transition formula; fitness function; guiding element; local optimum; initial population; time window constraint; path planning
- CLC:
- TP273
- DOI:
- 10.11992/tis.202205056
- Abstract:
- The ant colony algorithm has advantages, such as good global ability, self-organization, and robustness, but the conventional ant colony algorithm has several drawbacks. Herein, with the goal of addressing these drawbacks, in the path planning problem, according to the conventional ant colony algorithm, the distance factor of the target point and the guide element are added to the state transition formula to optimize the convergence of the ant colony algorithm in the path planning and enhance the defect of local optimal point. On the vehicle routing problem with time window (VRPTW), the ant colony algorithm and genetic algorithm are combined, and the customer time window width and robot waiting time are added to the state transition formula of the ant colony algorithm. The solution of the ant colony algorithm is taken as the initial population of the genetic algorithm to enhance the quality of the initial solution of the genetic algorithm, and subsequently, coding is conducted. The penalty function and fitness function violating the time window constraint and load are set. After the mutation and crossover operation of the conventional genetic algorithm, the damage and repair gene operation is added to optimize the quality of each generation of new solutions. Simulations are performed on the Solomon benchmark example, and the optimal solutions before and after enhancement of the algorithm are compared to confirm the feasibility of the algorithm. To apply this to a real-world problem, the path planning problem in a simulative environment with obstacles and the VRPTW problem are joined using the enhanced algorithm to solve the customer service delivery problem of the restaurant delivery robot.
- References:
-
[1] 陶永, 王田苗, 刘辉, 等. 智能机器人研究现状及发展趋势的思考与建议[J]. 高技术通讯, 2019, 29(2): 149–163
TAO Yong, WANG Tianmiao, LIU Hui, et al. Insights and suggestions on the current situation and development trend of intelligent robots[J]. Chinese high technology letters, 2019, 29(2): 149–163
[2] KUANG Hua, XU Zhipeng, LI Xingli, et al. An extended car-following model accounting for the average headway effect in intelligent transportation system[J]. Physica A:statistical mechanics and its applications, 2017, 471: 778–787.
[3] POOLE A, KOTSIALOS A. Swarm intelligence algorithms for macroscopic traffic flow model validation with automatic assignment of fundamental diagrams[J]. Applied soft computing, 2016, 38: 134–150.
[4] CHMIEL W, DA?DA J, DZIECH A, et al. INSIGMA: an intelligent transportation system for urban mobility enhancement[J]. Multimedia tools and applications, 2016, 75(17): 10529–10560.
[5] 程志, 张志安, 李金芝, 等. 改进人工势场法的移动机器人路径规划[J]. 计算机工程与应用, 2019, 55(23): 29–34
CHENG Zhi, ZHANG Zhian, LI Jinzhi, et al. Mobile robots path planning based on improved artificial potential field[J]. Computer engineering and applications, 2019, 55(23): 29–34
[6] WANG Xiuhong, LIU Xuehao, WANG Yongcheng, et al. Research on path planning of mobile robot based on improved A* algorithm[C]//IE&EM 2019. Singapore: Springer, 2020: 153-161.
[7] WANG Huijuan, YU Yuan, YUAN Quanbo. Application of Dijkstra algorithm in robot path-planning[C]//2011 Second International Conference on Mechanic Automation and Control Engineering. Hohhot. IEEE, 2011: 1067-1069.
[8] ELHOSENY M, THARWAT A, HASSANIEN A E. Bezier curve based path planning in a dynamic field using modified genetic algorithm[J]. Journal of computational science, 2018, 25: 339–350.
[9] SONG Baoye, WANG Zidong, SHENG Ligang. A new genetic algorithm approach to smooth path planning for mobile robots[J]. Assembly automation, 2016, 36: 138–145.
[10] FERNANDES C M, MORA A M, MERELO J J, et al. KANTS: a stigmergic ant algorithm for cluster analysis and swarm art[J]. IEEE transactions on cybernetics, 2014, 44(6): 843–856.
[11] 陈嘉林, 魏国亮, 田昕. 改进粒子群算法的移动机器人平滑路径规划[J]. 小型微型计算机系统, 2019, 40(12): 2550–2555
CHEN Jialin, WEI Guoliang, TIAN Xin. Smooth path planning for mobile robots based on improved particle swarm optimization algorithm[J]. Journal of Chinese computer systems, 2019, 40(12): 2550–2555
[12] ALAM M S, RAFIQUE M U, KHAN M U. Mobile robot path planning in static environments using particle swarm optimization[EB/OL]. (2020-08-23)[2021-01-01].https://arxiv.org/abs/2008.10000.pdf.
[13] PATLE B K, PANDEY A, JAGADEESH A, et al. Path planning in uncertain environment by using firefly algorithm[J]. Defence technology, 2018, 14(6): 691–701.
[14] JIANG Tao, WANG Jianzhong. Study on path planning method for mobile robot based on fruit fly optimization algorithm[J]. Applied mechanics and materials, 2014, 536/537: 970–973.
[15] PANDA M, DAS B, PATI B B. Grey wolf optimization for global path planning of autonomous underwater vehicle[C]//Proceedings of the Third International Conference on Advanced Informatics for Computing Research. New York: ACM, 2019: 1-6.
[16] 楼传炜, 葛泉波, 刘华平, 等. 无人机群目标搜索的主动感知方法[J]. 智能系统学报, 2021, 16(3): 575–583
LOU Chuanwei, GE Quanbo, LIU Huaping, et al. Active perception method for UAV group target search[J]. CAAI transactions on intelligent systems, 2021, 16(3): 575–583
[17] 徐玉琼, 娄柯, 李志锟. 基于变步长蚁群算法的移动机器人路径规划[J]. 智能系统学报, 2021, 16(2): 330–337
XU Yuqiong, LOU Ke, LI Zhikun. Mobile robot path planning based on variable-step ant colony algorithm[J]. CAAI transactions on intelligent systems, 2021, 16(2): 330–337
[18] 夏小云, 周育人. 蚁群优化算法的理论研究进展[J]. 智能系统学报, 2016, 11(1): 27–36
XIA Xiaoyun, ZHOU Yuren. Advances in theoretical research of ant colony optimization[J]. CAAI transactions on intelligent systems, 2016, 11(1): 27–36
[19] CAO Jingang. Robot global path planning based on an improved ant colony algorithm[J]. Journal of computer and communications, 2016, 4(2): 11–19.
[20] TSAI P W, NGUYEN T T, DAO T K. Robot path planning optimization based on multiobjective grey wolf optimizer[C]// International Conference on Genetic and Evolutionary Computing. Cham: Springer, 2017: 166-173.
[21] 张毅, 杨光辉, 花远红. 基于改进人工鱼群算法的机器人路径规划[J]. 控制工程, 2020, 27(7): 1157–1163
ZHANG Yi, YANG Guanghui, HUA Yuanhong. Robot path planning based on improved artificial fish swarm algorithm[J]. Control engineering of China, 2020, 27(7): 1157–1163
[22] BRAND M, YU Xiaohua. Autonomous robot path optimization using firefly algorithm[C]//2013 International Conference on Machine Learning and Cybernetics. Tianjin: IEEE, 2014: 1028-1032.
[23] DORIGO M, MANIEZZO V, COLORNI A. The ant system: an autocatalytic optimizing process Technical Report91-O16[R]. Milan: Dipartimento di Elettronica, Politecnicl di Milano, 1991.
[24] DORIGO M, MANIEZZO V, COLORNI A. Ant system: optimization by a colony of cooperating agents[C]//IEEE Transactions on Systems, Man, and Cybernetics, Part B. Cybernetics: IEEE, 2002: 29-41.
[25] 董炫良, 赵桂清. 人工势场引导蚁群算法的机器人导航路径规划[J]. 机械设计与制造, 2021(6): 169–173
DONG Xuanliang, ZHAO Guiqing. Robot navigation path planning based on ant colony algorithm guided by artificial potential field[J]. Machinery design & manufacture, 2021(6): 169–173
[26] 李琳, 刘士新, 唐加福. 改进的蚁群算法求解带时间窗的车辆路径问题[J]. 控制与决策, 2010, 25(9): 1379–1383
LI Lin, LIU Shixin, TANG Jiafu. Improved ant colony algorithm for solving vehicle routing problem with time windows[J]. Control and decision, 2010, 25(9): 1379–1383
- Similar References:
Memo
-
Last Update:
1900-01-01