Optimization Method for Multi Agricultural Machinery Collaborative Operation Based on Genetic Algorithm and A * Algorithm

doi:10.16182/j.issn1004731x.joss.24-0453

Abstract

Abstract:

To address the uneven task distribution among multiple agricultural machines (referred to as farm machinery) and the high time cost due to numerous turning points at intersections, this paper proposes a task planning method that combines a pre-heat multi grouped genetic algorithm (PHMGA) with the turn A* algorithm (tA*). PHMGA allocates tasks to each piece of farm machinery based on the known environment, ensuring balanced workload through a cost objective function that considers travel, operation, and turning distances. It also designs various operators and strategies to search for near-optimal solutions. The tA* algorithm is used to select paths in the fields, avoiding complex areas with many turning points through turning penalties, thereby further reducing operation time. Simulation results show that our proposed method effectively balances the workload among the farm machinery and significantly reduces operation and waiting times, achieving a reduction of 5% and 56%~67% respectively compared to traditional methods.

Key words: agricultural machines, improved multi-group genetic algorithm, improved A* algorithm, multi-machine collaborative operation planning, task assignment, path planning

CLC Number:

TP391.9

Yu Yiran, Lai Huicheng, Gao Guxue, Zhang Guo, Peng Wangyinan, Yang Longfei, Huang Junhao. Optimization Method for Multi Agricultural Machinery Collaborative Operation Based on Genetic Algorithm and A * Algorithm[J]. Journal of System Simulation, 2025, 37(9): 2397-2408.

Figures/Tables 17

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Table 1

Table 2

Fig. 9

Table 3

Experimental results with different weights

权重	任务分配结果				$∑ j = 1 M S j$ /km	R	G
权重	农机1	农机2	农机3	农机4	$∑ j = 1 M S j$ /km	R	G
α=1，β=0，γ=0	0→7→8→0	0→5→9→0	0→2→4→6→ 10→11→12→0	0→1→3→0	22.08	384.291	134.180
α=0，β=1，γ=0	0→12→3→2→0	0→11→5→0	0→10→4→ 7→9→0	0→8→6→1→0	37.255	0.011	8.514
α=0，β=0，γ=1	0→7→10→3→0	0→2→5→9→0	0→1→4→8→0	0→11→6→12→0	34.219	32.813	0.003
α=0.6，β=0.2，γ=0.2	0→12→2→3→0	0→1→4→8→0	0→5→6→ 10→9→0	0→7→11→0	30.977	1.911	0.065
α=0.2，β=0.6，γ=0.2	0→7→5→3→0	0→6→10→ 9→8→0	0→11→4→0	0→12→2→1→0	30.253	0.459	1.703
α=0.2，β=0.2，γ=0.6	0→5→11→0	0→9→10→ 6→4→0	0→1→8→7→0	0→12→2→3→0	29.403	0.015	4.786
α=0.33，β=0.33，γ=0.33	0→5→6→ 10→9→0	0→3→2→12→0	0→8→4→1→0	0→7→11→0	30.977	1.911	0.065

Table 3

Fig. 10

Fig. 11

Table 4

Table 5

Fig. 12

References 25

[1]	国家统计局. 中国统计年鉴——2023[EB/OL]. [2024-04-15]. .
[2]	习近平. 加快建设农业强国推进农业农村现代化[J]. 求是, 2023(6): 4-17.
[3]	刘成良, 贡亮, 苑进, 等. 农业机器人关键技术研究现状与发展趋势[J]. 农业机械学报, 2022, 53(7): 1-22, 55.
	Liu Chengliang, Gong Liang, Yuan Jin, et al. Current Status and Development Trends of Agricultural Robots[J]. Transactions of the Chinese Society for Agricultural Machinery, 2022, 53(7): 1-22, 55.
[4]	韩冷, 何雄奎, 王昌陵, 等. 智慧果园构建关键技术装备及展望[J]. 智慧农业(中英文), 2022, 4(3): 1-11.
	Han Leng, He Xiongkui, Wang Changling, et al. Key Technologies and Equipment for Smart Orchard Construction and Prospects[J]. Smart Agriculture, 2022, 4(3): 1-11.
[5]	张振国, 毛建旭, 谭浩然, 等. 重大装备制造多机器人任务分配与运动规划技术研究综述[J]. 自动化学报, 2024, 50(1): 21-41.
	Zhang Zhenguo, Mao Jianxu, Tan Haoran, et al. A Review of Task Allocation and Motion Planning for Multi-robot in Major Equipment Manufacturing[J]. Acta Automatica Sinica, 2024, 50(1): 21-41.
[6]	陈宝童, 王丽清, 蒋晓敏, 等. 群智协同任务分配研究综述[J]. 计算机工程与应用, 2021, 57(20): 1-12.
	Chen Baotong, Wang Liqing, Jiang Xiaomin, et al. Survey of Task Assignment for Crowd-based Cooperative Computing[J]. Computer Engineering and Applications, 2021, 57(20): 1-12.
[7]	Tang Jun, Liu Gang, Pan Qingtao. A Review on Representative Swarm Intelligence Algorithms for Solving Optimization Problems: Applications and Trends[J]. IEEE/CAA Journal of Automatica Sinica, 2021, 8(10): 1627-1643.
[8]	Chakraa Hamza, Guérin François, Leclercq Edouard, et al. Optimization Techniques for Multi-robot Task Allocation Problems: Review on the State-of-the-art[J]. Robotics and Autonomous Systems, 2023, 168: 104492.
[9]	崔炜, 朱发证. 机器人导航的路径规划算法研究综述[J]. 计算机工程与应用, 2023, 59(19): 10-20.
	Cui Wei, Zhu Fazheng. Review of Path Planning Algorithms for Robot Navigation[J]. Computer Engineering and Applications, 2023, 59(19): 10-20.
[10]	Yao Linhui, Sun Zhongyi. Research Progress of Robot Path Planning Algorithm[J]. Current Journal of Applied Science and Technology, 2023, 42(23): 27-41.
[11]	Chakraborty Suprava, Elangovan Devaraj, Padma Lakshmi Govindarajan, et al. A Comprehensive Review of Path Planning for Agricultural Ground Robots[J]. Sustainability, 2022, 14(15): 9156.
[12]	唐昀超, 祁少军, 朱立学, 等. 移动机器人避障运动研究[J]. 系统仿真学报, 2024, 36(1): 1-26.
	Tang Yunchao, Qi Shaojun, Zhu Lixue, et al. Obstacle Avoidance Motion in Mobile Robotics[J]. Journal of System Simulation, 2024, 36(1): 1-26.
[13]	Hu Kewei, Chen Zheng, Kang Hanwen, et al. 3D Vision Technologies for a Self-developed Structural External Crack Damage Recognition Robot[J]. Automation in Construction, 2024, 159: 105262.
[14]	余翔, 姜陈, 段思睿, 等. 改进A^*算法和人工势场法的路径规划[J]. 系统仿真学报, 2024, 36(3): 782-794.
	Yu Xiang, Jiang Chen, Duan Sirui, et al. Path Planning for Improvement of A^* Algorithm and Artificial Potential Field Method[J]. Journal of System Simulation, 2024, 36(3): 782-794.
[15]	Dam Tuan, Chalvatzaki Georgia, Peters Jan, et al. Monte-Carlo Robot Path Planning[J]. IEEE Robotics and Automation Letters, 2022, 7(4): 11213-11220.
[16]	余翔, 邓千锐, 段思睿, 等. 一种多无人机协同优先覆盖搜索算法[J]. 系统仿真学报, 2024, 36(4): 991-1000.
	Yu Xiang, Deng Qianrui, Duan Sirui, et al. A Multi-UAV Collaborative Priority Coverage Search Algorithm[J]. Journal of System Simulation, 2024, 36(4): 991-1000.
[17]	王伟权, 丁鼎, 曹淑艳. 混合变邻域搜索算法求解大规模电动车辆路径优化问题[J]. 系统仿真学报, 2022, 34(4): 910-919.
	Wang Weiquan, Ding Ding, Cao Shuyan. Hybrid Variable Neighborhood Search algorithm for the Multi-trip and Heterogeneous-fleet Electric Vehicle Routing Problem[J]. Journal of System Simulation, 2022, 34(4): 910-919.
[18]	Zhang Yajia, Sun Hongyi, Zhou Jinyun, et al. Optimal Vehicle Path Planning Using Quadratic Optimization for Baidu Apollo Open Platform[C]//2020 IEEE Intelligent Vehicles Symposium (IV). Piscataway: IEEE, 2020: 978-984.
[19]	张莉, 张惠珍, 刘冬, 等. 考虑紧迫度的应急物资调度及粒子群算法求解[J]. 系统仿真学报, 2022, 34(9): 1988-1998.
	Zhang Li, Zhang Huizhen, Liu Dong, et al. Particle Swarm Algorithm for Solving Emergency Material Dispatch Considering Urgency[J]. Journal of System Simulation, 2022, 34(9): 1988-1998.
[20]	Evans J T IV, Pitla S K, Luck J D, et al. Row Crop Grain Harvester Path Optimization in Headland Patterns[J]. Computers and Electronics in Agriculture, 2020, 171: 105295.
[21]	Zhao Xin, Wang Ke, Wu Sixian, et al. An Obstacle Avoidance Path Planner for an Autonomous Tractor Using the Minimum Snap Algorithm[J]. Computers and Electronics in Agriculture, 2023, 207: 107738.
[22]	Worasan Kongkidakhon, Sethanan Kanchana, Pitakaso Rapeepan, et al. Hybrid Particle Swarm Optimization and Neighborhood Strategy Search for Scheduling Machines and Equipment and Routing of Tractors in Sugarcane Field Preparation[J]. Computers and Electronics in Agriculture, 2020, 178: 105733.
[23]	Wang Ning, Yang Xi, Wang Tianhai, et al. Collaborative Path Planning and Task Allocation for Multiple Agricultural Machines[J]. Computers and Electronics in Agriculture, 2023, 213: 108218.
[24]	Singh Alok, Anurag Singh Baghel. A New Grouping Genetic Algorithm Approach to the Multiple Traveling Salesperson Problem[J]. Soft Computing, 2009, 13(1): 95-101.
[25]	Alaya Ines, Solnon Christine, Ghedira Khaled. Ant Colony Optimization for Multi-objective Optimization Problems[C]//19th IEEE International Conference on Tools with Artificial Intelligence(ICTAI 2007). Piscataway: IEEE, 2007: 450-457.

参数	量值
作业宽幅d/m	2.4
农机轴距L/m	3.5
农机作业平均速度v_w/(km/h)	3.5
农机行驶平均速度v_r/(km/h)	15
农机转向平均速度v_turn/(km/h)	2.5
最大转向角θ_max /rad	0.6

农田序号	长度/m	宽度/m
1	173	100
2	133	92
3	139	52
4	111	42
5	73	58
6	97	90
7	120	66
8	103	127
9	115	98
10	74	44
11	225	94
12	49	134

算法	农机编号	作业距离/km	作业时间/h	完成时间/h	等待时间/h
MGA+A*	农机1 农机2 农机3 农机4	10.094 22.452 14.236 19.410	1.908 3.008 2.105 2.954	3.008	1.100
MGA+tA*	农机1 农机2 农机3 农机4	10.230 22.452 14.236 19.486	1.901 3.008 2.105 2.951	3.008	1.107
MOACO+A*	农机1 农机2 农机3 农机4	14.176 17.787 17.201 17.898	2.395 2.431 2.175 3.018	3.018	0.843
MOACO+tA*	农机1 农机2 农机3 农机4	14.276 17.787 17.201 17.898	2.391 2.431 2.175 3.018	3.018	0.843
PHMGA+A*	农机1 农机2 农机3 农机4	16.270 16.906 21.700 18.544	2.534 2.498 2.856 2.595	2.856	0.358
PHMGA+tA*	农机1 农机2 农机3 农机4	16.270 17.026 21.700 18.544	2.534 2.493 2.856 2.595	2.856	0.363