TLDR: This research simplifies the Close Enough Traveling Salesman Problem (CETSP) for drone trajectory optimization. It uses Manhattan distance with linear regression for better Euclidean distance approximation, models sensor areas as squares or hexagons, and introduces a fragmented solving approach. The method improves computational efficiency and solution quality for UAV data collection.
The article discusses a new method for optimizing the paths of Unmanned Aerial Vehicles (UAVs), or drones, when they are collecting data from sensors scattered across an area. This challenge is framed as a “Close Enough Traveling Salesman Problem” (CETSP). Unlike the traditional Traveling Salesman Problem where a drone must visit exact points, in CETSP, the drone only needs to get “close enough” to a sensor to collect its data. This means it can visit any point within a sensor’s communication range, which is typically a circular area.
The core idea behind this research is to simplify the complex mathematical equations used to solve the CETSP. The original problem involves quadratic equations, which can be computationally intensive, especially as the number of sensors increases. The author proposes several reformulations to make the problem easier to solve.
One key simplification involves changing how distances are calculated. Instead of using the standard Euclidean distance (straight-line distance), the paper explores using Manhattan distance (like navigating a city grid, moving only horizontally or vertically). While Manhattan distance is simpler, it can sometimes underestimate or overestimate the true Euclidean distance. To address this, the research introduces linear regression, a machine learning technique, to find coefficients that help approximate the Euclidean distance more accurately from the Manhattan distance.
Another simplification focuses on the “emission areas” of the sensors. Instead of complex circular regions, the paper proposes modeling these areas as simpler convex shapes like squares or hexagons. Inscribing a square or a hexagon within the circular communication range helps linearize the problem constraints, making them easier for solvers like CPLEX to handle. The study found that small hexagons generally lead to better travel costs for small and medium-sized instances, while small squares perform better for larger instances due to the reduced search space complexity.
The paper also introduces two linearization options for the objective function, which aims to minimize the total travel distance. Linearization 2 proved more effective in optimizing trajectory costs for most tested cases. Furthermore, a technique called “8D Projection” is explored, where the distance between sensors is projected onto eight new axes. This method helps refine the approximation of the Euclidean distance and has shown significant improvements in reducing displacement costs without increasing computation time.
A notable contribution of this research is the “Fragmented CPLEX-based approach.” This method breaks down the large CETSP into smaller, more manageable chunks. It first identifies groups of intersecting sensor areas, defines “super-nodes” for these intersections, solves a basic Traveling Salesman Problem for these super-nodes, and then refines the drone’s hitting points within each sensor’s emission area. This fragmented approach has shown to improve both travel cost and computation time compared to solving the entire problem at once with CPLEX.
Also Read:
- ClustOpt: A Novel Way to Visualize and Understand Optimization Algorithms
- Smarter AI Decisions: New Methods for Dynamic Abstraction in Monte Carlo Tree Search
In conclusion, this research offers practical strategies for optimizing UAV trajectories for data collection. By simplifying distance calculations, modeling sensor areas with convex shapes, and employing a fragmented solving method, the proposed approach effectively manages computational resources while maintaining solution quality. This work is crucial for enhancing the efficiency and practicality of drone-based data collection in various real-world applications. For more in-depth details, you can refer to the full research paper available at Optimizing UAV Trajectories via a Simplified Close Enough TSP Approach.
