Hierarchical Optimal Path Planning (HOPP) for Robotic Apple Harvesting

Abstract

Apples are among the most consumed fruits in the United States. Currently, almost all apples destined for the fresh market are picked by the human hand. Due to the shortage of seasonal manual labor and rising costs in manual apple picking, robotic apple harvesting has been explored for years. However, a challenge in developing and deploying an apple harvesting robotic system is how to deal with the unstructured apple tree environment. This work aims to demonstrate that structured 3D model representation of apple trees can significantly enable and facilitate robotic apple harvesting, particularly for optimal 3D path planning. Accordingly, a hierarchical optimal path planning (HOPP) algorithm is designed to significantly reduce or minimize the time cost during robotic apple harvesting in a 3D environment. The core idea of this HOPP algorithm is applying distance-constrained k-means clustering to group apples into 3D harvesting zones first, after which an optimal 3D robotic harvesting path is derived via the Traveling Salesman Problem (TSP) formulation and solution. Within each 3D apple harvesting zone, a second-stage optimal path planning is conducted by the TSP method on individual apples. Experiments showed that the proposed HOPP algorithm is promising.