An Effective Way to Large-Scale Robot-Path-Planning Using a Hybrid Approach of Pre-Clustering and Greedy Heuristic

摘要

Robot-path-planning seeks the shortest path to optimize the motion cost for robots. In robot-path-planning, the computational time will significantly increase if the moving targets rise largely, also known as the large-scale TSP. Hence, the current algorithms for the shortest path planning may be ineffective in the large-scale TSP. Aimed at the real-time applications that a robot must achieve as many goals as possible within limited time and the computational time of a robot has to be short enough to provide the next moving signal in time. Otherwise, the robot will be trapped into the idle status. This work proposes a hybrid approach, called the pre-clustering greedy heuristic, to tackle the reduction of computational time cost and achieve the near-optimal solutions. The proposed algorithm demonstrates how to lower the computational time cost drastically via smaller data of a sub-group, divided byk-means clustering, and the intra-cluster path planning. An algorithm is also developed to construct the nearest connections between any two unconnected clusters, ensuring the inter-cluster tour is the shortest. As a result, by utilizing the proposed heuristic, the computational time is significantly reduced and the path length is more efficient than the benchmark algorithms, while the input data grow up to a large scale. In applications, the proposed work can be applied practically to the path planning with large-scale moving targets, for example, the employment for the ball-collecting robot in a court.