Tối ưu hóa đường đi cho phương tiện Dubins trong quy hoạch vùng và vấn đề người bán hàng du lịch - Nghiên cứu của Xin Yu tại Auburn University

Optimization Approaches for a Dubins Vehicle in Coverage Planning Problem and Traveling Salesman Problems by Xin Yu A dissertation submitted to the Graduate Faculty of Auburn University in partial fulfillment of the requirements for the Degree of Doctor of Philosophy Auburn, Alabama May 10, 2015 Keywords: Coverage Path Planning, Traveling Salesman Problem, Dubins Vehicles, Combination Optimization Copyright 2015 by Xin Yu Approved by John Y. Hung, Chair, Professor of Electrical and Computer Engineering David M. Bevly, Professor of Mechanical Engineering Thaddeus A. Roppel, Associate Professor of Electrical and Computer Engineering Bogdan M.

Wilamowski, Professor of Electrical and Computer Engineering 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 decom- position 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 decom- position approach in the first category, providing a complete coverage path planning method ii for the mobile robot. Experiments show that the proposed method can provide feasible solu- tions 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.

iii Acknowledgments The author would like to express thanks to the members of his committee Dr. Wilamowski for their valuable assistance and guidance. The author also thanks the university reader Dr. Sinclair for his valuable suggestions on this dissertation.

Special thanks are given to Dr. Hung for the many hours of guidance and encouragement he has provided during this research. His suggestions have aided in the design of algorithms and experiments, and his advice has improved the visualization and written presentation of this work. Thanks are also expressed to the Siwei Wang, Aditya Singh, Michael L.

Payne and William J. Woodall for their collaboration and the wealth of background knowledge they have provided. Particular thanks go to David W. Hodo for his extensive previous work for the basis of this research and his invaluable support while performing the experiments.

This work would not have been possible without the funding and support provided by the Environmental Technology Certification Program (ESTCP) through the Army Corp of Engineers Huntsville Center. Finally, the author dedicate this dissertation to his family and Zhongyuan Jia. None of this would be possible without their tremendous love and enthusiasm. iv Table of Contents Abstract.

iv List of Figures. viii List of Tables .1 Motivation and Problem Statement .2 Organization and Contributions of the Dissertation .1 Coverage Path Planning .1 Optimal Decomposition and Track Layout .2 Optimal Traversal Sequence .3 Some Unresolved Issues .2 Traveling Salesman Problems .1 Traveling Salesman Problem .2 Dubins Traveling Salesman Problem .3 Traveling Salesman Problem with Neighborhoods .4 Dubins Traveling Salesman Problem with Neighborhoods .5 Some Unresolved Issues. 14 3 Coverage Path Planning: Optimal Decomposition and Track Layout .3 Coverage of Convex field .4 Coverage of Non-convex field .2 Optimal Coverage for Each Convex Polygon .4 Merging Adjacent Polygons .5 Time Complexity Analysis. 32 4 Coverage Path Planning: Optimal Visiting Sequence .3 Optimization on a single convex field .3 Cost Between Nodes .5 Transformation from GTSP into ATSP .6 Complexity of the Proposed Algorithm .4 Extension to multiple fields .1 Effect of Parity (Even or Odd Number of Tracks with One Depot) .2 Effect of Specified Start/End Position .3 Performance with Unspecified Start/End Position .4 Performance on Multiple Decomposed Subfields.

60 5 Dubins Traveling Salesman Problem .3 Algorithm Design for DTSP .2 Encoding and Initialization. 70 6 Dubins Traveling Salesman Problem with Neighborhoods .1 Find the Optimal ETSP Tour .3 Alternating Iterative Algorithm for TSPN .4 Compute the Headings for Entry Points to Form a DTSP .1 Review of Contributions. 99 vii List of Figures 1. (a) Munitions Debris located during surface sweep and ex- cavated anomalies.

(b) An 81mm mortar. Image courtesy of ECC. Source: http: //www.com/2009-07/uxo_lands_restoration_and_release.2 (a) Geophysical survey operated by an UXO technician. Image courtesy of David W.

Source: http://www.edu/\nobreakspace{}hododav/ projects/segway_project/DSCN3821. (b) An autonomous robot-trailer system for geophysical survey. The towing robot is a modified Segway R RMP 440.1 Remaining issues in finding optimal traversal sequence: (a) the non-working travel distances from track C to track A are different between path 1 and path 2, (b) optimal traversal of endpoints may skip a track (3-4).1 Different track directions for convex fields.2 Different track directions for non-convex fields. (b) The proposed convex decomposition (3.4 Eight event types: OPEN (1), CLOSE (5), SPLIT (9), MERGE (12), FLOOR CONVEX (2, 3, 4, 10), FLOOR CONCAVE (11), CEIL CONVEX (6, 7, 8, 14) and CEIL CONCAVE (13, 15).

The sweep line is horizontally swept from left to right. Arrows indicate the track directions. (b) Solution of the proposed algorithm. Arrows indicate the track directions.

(b) Solution of the proposed algorithm.7 Test field near Auburn University and solution of the proposed algorithm.1 Example Dubins Paths [3] .2 GTSP node representation: (a) A given set of parallel field tracks (dashed lines) (b) Each track has two directed path options (dashed lines, SP: starting point, EP: ending point) (c) Corresponding GTSP node representation and two feasible GTSP solutions (in gray and in black) .3 Illustration of transformation from GTSP into ATSP: (a) A GTSP representation with arc costs for the example in Fig. Note that only an essential subset of arcs is shown for clarity of illustration. (b) A zero-cost directed cycle is created for each cluster by adding zero-cost arcs between consecutive nodes in each cluster. (The dash arcs in blue have zero cost.) (c) The inter-cluster arcs are circularly shifted so they emanate from the previous node in its cycle.

(d) A large finite cost β is added to each inter-cluster arc. Here ĉi,j = ci,j + β, where +∞ > β > P (i,j)∈A ci,j. The optimal ATSP tour is shown in red with a cost of ĉ1,6 +ĉ6,3 +ĉ3,1. The GTSP solution can be extracted from the ATSP solution by taking only the first node visited in each cluster.4 (a) GTSP pattern for odd number of tracks (11 tracks) with one depot.

(b) GTSP pattern for even number of tracks (10 tracks) with one depot. Shaded area is field that must be covered. The number on each track is the visiting order of that track. Arrows indicate the driving direction on each track.5 (a) B pattern [4] for odd number of tracks (11 tracks) with one depot.

The result of B pattern skips one track in this case by traversing the endpoints of tracks, i., the area in middle of the field is not covered. (b) B pattern [4] for even number of tracks (10 tracks) with one depot. The number on each endpoint of tracks is the visiting order of that endpoint.6 GTSP pattern for specified start and end positions (25 tracks). (a) Start position and end position are on the same side of two different tracks.

(b) Start position and end position are on the opposite side of two different tracks. Shaded area is field that must be covered. The number on each track is the visiting order of that track. Arrows indicate the driving direction on each track.

(a) Start position and end position are on the same side of two different tracks. (b) Start position and end position are on the opposite side of two different tracks. The number on each endpoint of tracks is the visiting order of that endpoint. The B pattern skips one track in case (a) by traversing the endpoints of tracks, which results an infeasible solution.9 Set pattern [3] (20 tracks, trapezoidal shaped field) Set pattern is also called “Zamboni pattern”, or “overlapping concentric ovals”.10 B pattern with no specified start position and end position (20 tracks, trapezoidal shaped field).11 GTSP pattern with no specified start position and end position (20 tracks, trape- zoidal shaped field).12 Savings in non-working distance by using GTSP pattern instead of Boustrophe- don pattern.13 Savings in non-working distance by using GTSP pattern instead of Set pattern [3].14 Savings in non-working distance by using GTSP pattern instead of B pattern [4].15 GTSP pattern for multiple subfields (4 m turning radius, 2.

The number on each track is the track number. Visiting sequence is in the paper.16 GTSP pattern for multiple subfields (6 m turning radius, 2.17 GTSP pattern and B pattern for multiple subfields (6 m turning radius, 2. (a) Solution of GTSP pattern with restricted connections. (b) Solution of B pattern with restricted connections.18 GTSP pattern and B pattern for multiple subfields (6 m turning radius, 3.

(a) Solution of GTSP pattern with restricted connections. (b) Solution of B pattern with restricted connections.19 Savings in non-working distance by using GTSP pattern instead of Boustrophe- don pattern for multiple subfields.20 Savings in non-working distance by using GTSP pattern instead of Set pattern [3] for multiple subfields.1 20x20 square (low density) case comparison.2 5x5 square (high density) case comparison.