Solving the Global Path Planning of an Unmanned Ground Vehicle Using a Clustered Travelling Salesman Path Problem Approach
Veekeong Saw, Amirah Rahman, Wen Eng Ong · 2025
Global path planning (GPP) is an important feature in the development of unmanned ground vehicles (UGV). In this chapter, the multi-criteria path planning problem with multiple checkpoints for the GPP of a UGV is considered. The GPP problem is modelled as the travelling salesman path problem with unique endpoints (stTSPP). A solution scheme that solves the GPP problem in two-level clustered TSPP fashion by partitioning the checkpoints into multiple clusters is proposed. A global 2-opt heuristic is also introduced to improve the solution quality. For evaluation purposes, the solution scheme is implemented in computational experiments with various settings. Experimental results show that the quality of solution paths obtained are highly influenced by the way the checkpoints are clustered.