Fast Obstacle Avoidance Path Generation Algorithm for Multi-Target Point Coverage Traversal

Obstacle avoidance path planning with multi-target point coverage traversal has high computational complexity and long solution time, in this paper, the problem of generating the initial obstacle avoidance coverage path is decomposed into two subproblems of covering point generation and covering point traversal path to be solved separately. For the generation of coverage points, an improved iterative self-organizing data (ISODATA) clustering algorithm is given to cluster the target points, and the center of the clustering is taken as the coverage point; for the traversal of coverage points, a probabilistic roadmap method (PRM) based on the identification of connectivity components is proposed to obtain the traversal path. For the multi-PRM (mPRM) algorithm proposed in this paper, it is compared with the multi Rapidly-exploring Random Tree (mRRT) algorithm in four different scenarios. The mPRM algorithm shows significant superiority by reducing the number of sampling points by 90% and improving the computation time by 95%, while the solution success rate reaches 100%.