An Effective Way to Large-Scale Robot-Path-Planning Using a Hybrid Approach of Pre-Clustering and Greedy Heuristic. Issue 14 (5th December 2020)

• Record Type: Journal Article
• Authors: Wang, W. C.; Chen, R.
• Is Part Of: Applied artificial intelligence. Volume 34:Issue 14(2020)
• Page Start: 1159
• Page End: 1175
• Publication Date: 2020-12-05
• Subjects: Artificial intelligence -- Periodicals; 006.3
• DOI: 10.1080/08839514.2020.1824094
• Languages: English
• ISSNs: 0883-9514

Abstract

ABSTRACT: 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 by k -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.