Solving the TSP of the Obstacle Grid Map with SGP Vertex Extraction and Filtering Algorithm

In the obstacle grid map, due to the limited search directions of classical path algorithms and meta-heuristic algorithms, the shortest paths they solve are not true shortest paths (TSP), but rather shortest grid paths (SGP). In this paper, a SGP vertex extraction and filtering algorithm is proposed to extract and filter the key nodes in the SGP path, so as to obtain the TSP path under the same conditions. Experimental validation shows that the shortest path lengths found by the proposed SGP vertex extraction and filtering algorithm are shorter than those obtained by heuristic path algorithms, and it also outperforms recent new algorithms in comparative experiments. As the map scale increases and the obstacle rate rises, the advantages of this path algorithm become more pronounced.