Dubins Traveling Salesman Problem with Neighborhoods: A Graph-Based Approach
We study the problem of finding the minimum-length curvature constrained closed path through a set of regions in the plane. This problem is referred to as the Dubins Traveling Salesperson Problem with Neighborhoods (DTSPN). An algorithm is presented that uses sampling to cast this infinite dimension...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2013-02-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | http://www.mdpi.com/1999-4893/6/1/84 |
| _version_ | 1818357558604201984 |
|---|---|
| author | Jason T. Isaacs João P. Hespanha |
| author_facet | Jason T. Isaacs João P. Hespanha |
| author_sort | Jason T. Isaacs |
| collection | DOAJ |
| description | We study the problem of finding the minimum-length curvature constrained closed path through a set of regions in the plane. This problem is referred to as the Dubins Traveling Salesperson Problem with Neighborhoods (DTSPN). An algorithm is presented that uses sampling to cast this infinite dimensional combinatorial optimization problem as a Generalized Traveling Salesperson Problem (GTSP) with intersecting node sets. The GTSP is then converted to an Asymmetric Traveling Salesperson Problem (ATSP) through a series of graph transformations, thus allowing the use of existing approximation algorithms. This algorithm is shown to perform no worse than the best existing DTSPN algorithm and is shown to perform significantly better when the regions overlap. We report on the application of this algorithm to route an Unmanned Aerial Vehicle (UAV) equipped with a radio to collect data from sparsely deployed ground sensors in a field demonstration of autonomous detection, localization, and verification of multiple acoustic events. |
| first_indexed | 2024-12-13T20:15:01Z |
| format | Article |
| id | doaj.art-c0d076dc01dd4634abadc281607f2d01 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-12-13T20:15:01Z |
| publishDate | 2013-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-c0d076dc01dd4634abadc281607f2d012022-12-21T23:32:50ZengMDPI AGAlgorithms1999-48932013-02-0161849910.3390/a6010084Dubins Traveling Salesman Problem with Neighborhoods: A Graph-Based ApproachJason T. IsaacsJoão P. HespanhaWe study the problem of finding the minimum-length curvature constrained closed path through a set of regions in the plane. This problem is referred to as the Dubins Traveling Salesperson Problem with Neighborhoods (DTSPN). An algorithm is presented that uses sampling to cast this infinite dimensional combinatorial optimization problem as a Generalized Traveling Salesperson Problem (GTSP) with intersecting node sets. The GTSP is then converted to an Asymmetric Traveling Salesperson Problem (ATSP) through a series of graph transformations, thus allowing the use of existing approximation algorithms. This algorithm is shown to perform no worse than the best existing DTSPN algorithm and is shown to perform significantly better when the regions overlap. We report on the application of this algorithm to route an Unmanned Aerial Vehicle (UAV) equipped with a radio to collect data from sparsely deployed ground sensors in a field demonstration of autonomous detection, localization, and verification of multiple acoustic events.http://www.mdpi.com/1999-4893/6/1/84traveling salesman problemgraph transformationnonholonomic vehicles |
| spellingShingle | Jason T. Isaacs João P. Hespanha Dubins Traveling Salesman Problem with Neighborhoods: A Graph-Based Approach Algorithms traveling salesman problem graph transformation nonholonomic vehicles |
| title | Dubins Traveling Salesman Problem with Neighborhoods: A Graph-Based Approach |
| title_full | Dubins Traveling Salesman Problem with Neighborhoods: A Graph-Based Approach |
| title_fullStr | Dubins Traveling Salesman Problem with Neighborhoods: A Graph-Based Approach |
| title_full_unstemmed | Dubins Traveling Salesman Problem with Neighborhoods: A Graph-Based Approach |
| title_short | Dubins Traveling Salesman Problem with Neighborhoods: A Graph-Based Approach |
| title_sort | dubins traveling salesman problem with neighborhoods a graph based approach |
| topic | traveling salesman problem graph transformation nonholonomic vehicles |
| url | http://www.mdpi.com/1999-4893/6/1/84 |
| work_keys_str_mv | AT jasontisaacs dubinstravelingsalesmanproblemwithneighborhoodsagraphbasedapproach AT joaophespanha dubinstravelingsalesmanproblemwithneighborhoodsagraphbasedapproach |