Optimization Approaches for a Dubins Vehicle in Coverage Planning Problem and Traveling Salesman Problems

Abstract

The motivation of this dissertation is a path planning task for an autonomous robot-trailer system in geophysical surveys. The path planning task includes two main stages. In the first stage, an efficient coverage path is required to obtain a fully sensor coverage of a site to provide a complete map of anomalies. After the locations of anomalies are determined, in the second stage, an efficient traversal path is required to visit these anomalies to mark or obtain more data for further identification. The first stage can be regarded as the coverage path planning problem and the second stage can be regarded as a special case of traveling salesman problem. The robot-trailer system is modeled as a Dubins vehicle that can only move forward and turn with upper bounded curvature. Motivated by this autonomous inspection task, the author makes several contributions to the solution of coverage path planning problem and the solution of traveling salesman problems.

In the coverage path planning, the author presents an optimization approach that takes the vehicle's characteristics into account to minimize the non-working travel of the vehicle. Since turns are often costly for Dubins vehicle, minimizing the cost of turns usually produces more working efficiency. Prior researches on coverage path planning tend to fall into two complementary categories: (1) minimize the number of turns, by finding the optimal decomposition of a complex field into subfields and the optimal driving directions; (2) minimize the cost on a fixed number of turns, by finding the optimal visiting sequence of subfields and the optimal traversal sequence of parallel tracks for each subfield. This dissertation firstly presents a new algorithm to find the optimal decomposition that belongs to the first category; then designs a novel traversal pattern of parallel field tracks that belongs to the second category; finally extends the proposed traversal pattern to connect with the decomposition approach in the first category, providing a complete coverage path planning method for the mobile robot. Experiments show that the proposed method can provide feasible solutions and the total wasted distance can be greatly reduced, when compared against classical boustrophedon path or recent state-of-the-art.

In the traveling salesman problems, given a set of waypoints and the turning constraint on the vehicle, the addressed problem is to determine a visiting sequence of these waypoints, and to assign a configuration of the vehicle at each waypoint. The objective function is to minimize the total distances traveled by the vehicle. A genetic algorithm is designed to find the shortest path and the performance is evaluated in numerical study. The proposed genetic algorithm can perform very well in both low waypoint density and high waypoint density situations. The author then takes the sensor scope into consideration to further minimize the total travel distance. The problem can be regarded as a special case of the Traveling Salesman Problem with Neighborhoods (TSPN). The concept of a neighborhood is used to model the physical size of the sensor scope. The neighborhoods are represented by disks in this dissertation. The author uses a two-step approach to solve the problem: (1) design a new algorithm for the TSPN to search the optimal visiting sequence and entry positions; (2) design a new algorithm for the Dubins vehicle to determine the heading at each entry position. The theoretical and numerical studies show that the proposed approach can perform very well for both disjoint and overlapped disks cases. The practical experiment shows that the model is feasible for the robot-trailer application.

While the authors focus on a robot-trailer system in this dissertation, the proposed algorithm could be applied to any Dubins vehicle that has similar mission requirements.