Title:	GENETIC ALGORITHM WITH MODIFIED OPERATORS FOR AN INTEGRATED TRAVELING SALESMAN AND COVERAGE PATH PLANNING PROBLEM
Author(s):	Wen-Chieh Tung and Jing-Sin Liu
ISBN:	978-989-8533-95-1
Editors:	Hans Weghorn
Year:	2019
Edition:	Single
Keywords:	Coverage Path Planning, Traveling Salesman Problem (TSP), TSP-CPP, Genetic Algorithm, Dynamic Programming, Modified Operators
Type:	Full Paper
First Page:	205
Last Page:	216
Language:	English
Cover:
Full Contents:	click to dowload
Paper Abstract:	Coverage path planning (CPP) is a fundamental task to many applications for machining, cleaning, mine sweeping, lawn mowing, performing missions with UAVs such as mapping, surveillance, SAR and air quality monitoring. One approach for a known environment with obstacles is to decompose the environment into cells such that each cell can be covered individually. We can then decide the visiting order of cells to connect those intra-cell paths together. Finding the shortest inter-cell path that visits every cell and returns to the origin cell is similar to the traveling salesman problem (TSP), and the additional variation to consider is that there are multiple intra-cell paths for each cell resulting from different choices of entry and exit points in each cell, and therefore affect the inter-cell path. This integrated traveling salesman and coverage path planning problem is called TSP-CPP, similar to TSP with neighborhood (TSPN). The solution to TSP-CPP requires the simultaneously determination of visiting order of sites with null or minimum repetition and the transition points of each visiting site. Recent approaches for TSP-CPP include dynamic programming (DP) for TSP adapted to TSP-CPP, or determination using brute force enumerative search on combinations of entry and exit points of every cell and then solve each combination of entry and exit points with TSP-solver. Both of them suffer from exponential complexity and are prohibitive for complex environments with large number of cells. In this paper, we propose an appropriate genetic algorithm implementation for TSP-CPP to achieve a good balance between time efficiency and path optimality to break the curse of dimension in DP. Our approach is demonstrated to find the true optimal solution as DP in all simulation environments and one hundred times faster than DP approach for maps decomposed with large cell number.
	Go Back