Multi-agent Path Planning in Apple Orchard with Tight Tree Rows Based on Improved A-Star Algorithm for Frost Protection

Frost is one of the severe weather events causing economic losses in agriculture. The traditional heating method is to use gas heaters at fixed locations during frost events in orchards, but fixed heaters have limited heating capacity. To solve this problem, unmanned ground vehicles (UGVs) can be applied to carry gas heaters to different low-temperature locations in orchards for multiple heating cycles. In this study, a path-planning algorithm with multiple UGV-based heaters (agents) was proposed based on the A-star algorithm to create collision free paths in a 2D grid orchard with tight row apple trees. A novel method was proposed to estimate the path cost matrix in the orchard environment and a linear optimization method was used to improve the A-star algorithm by coupling the multiple start points and goal points, i.e., the optimal task assignment. The canopy that was heated in any cycle was taken as being protected and an estimating method of protection performance was presented. The simulated results show that the improved A-star algorithm had higher search efficiency, resulting in 36.8% and 98.7% less total path cost and computational time than the traditional A-Star algorithm. More importantly, under the paths generated by the improved A-Star algorithm, 72.8% of the tree rows in the simulated orchard environment were protected by multiple agents in multiple heating cycles. Overall, this study provides a concept of preventing orchard frost damage with multiple UGV-based heaters based on the improved A-Star algorithm.