Turning Energy-Aware Route Planning With an Extended TSP and Double-Layer State Graph: Experimental Evaluation With a Crawler Mobile Robot

For mobile robots with multiple destinations that must be visited only once, the Traveling Salesman Problem (TSP) provides an optimal route. The optimality may not be achieved for crawler robots, which are often used in the forestry industry and have a higher energy consumption during turning. This is because, in the standard TSP, travel points are represented as nodes of a graph, and travel costs are represented by edges, which do not account for the cost of turning. Our method solves this problem by a double-layer state graph to express the change in the orientation by choosing a combination of two points associated with each travel point. Since the standard TSP algorithm cannot be applied to this graph, we use the Generalized Traveling Salesman Problem (GTSP) algorithm, an extension of the TSP. To confirm the effectiveness of our method, we evaluated the planned routes through experiments conducted with a prototype crawler robot. The routes that minimized energy consumption showed an average 17 % reduction in energy consumption, while the routes that minimized travel time achieved an average 5 % reduction in travel time compared to the standard TSP algorithm.