TL;DR
This paper introduces a novel, open-source path planner for micro aerial vehicles (MAVs) that efficiently generates low-altitude terrain coverage paths in environments with obstacles. By reformulating coverage planning as a Generalized Traveling Salesman Problem (E-GTSP), their method significantly reduces path costs and computation times compared to traditional approaches, making it practical for real-world applications like humanitarian demining.
What Problem Does This Paper Address?
Humanitarian demining and other critical remote sensing tasks often require MAVs to survey large areas at low altitudes. However, real-world environments are rarely obstacle-free. Existing coverage planners often assume clear spaces or struggle to handle complex obstacles, limiting their deployment in challenging terrains with features like trees or buildings. These obstacles create "no-fly zones" (NFZs) that must be avoided, necessitating robust planning capabilities that can adapt in real-time. The paper addresses the need for an efficient and effective coverage path planner that can handle arbitrary polygonal environments with obstacles, optimize for path cost, and operate within practical time constraints for field deployment.
Methods
The core of the paper's contribution lies in its novel approach to coverage path planning. They extend the traditional "boustrophedon" (back-and-forth) coverage pattern by:
- Exact Cellular Decomposition: The environment is first decomposed into simpler, non-intersecting "monotone" cells. They explore two decomposition methods: Trapezoidal Cell Decomposition (TCD) and Boustrophedon Cell Decomposition (BCD), finding BCD generally leads to fewer cells and better results.
- Sweep Pattern Permutation: For each monotone cell, they generate multiple possible "sweep patterns." These patterns represent different orientations and starting points for the back-and-forth coverage within that cell.
- Generalized Traveling Salesman Problem (E-GTSP) Formulation: The problem of connecting these sweep patterns across all cells to achieve complete coverage with minimal cost is framed as an E-GTSP. This involves creating a graph where each node represents a specific sweep pattern for a cell, and edges represent the shortest paths between patterns in different cells. The cost of an edge includes both the travel time between patterns and the time to execute the target sweep pattern.
- Optimization: They utilize an off-the-shelf E-GTSP solver (specifically, the Gutin and Karapetyan (GK) memetic algorithm) to find the optimal tour that visits exactly one sweep pattern from each cell's cluster. This allows for optimizing over various sweep directions within each cell, unlike conventional planners that fix a single direction.
- Obstacle Handling: Obstacles (NFZs) are explicitly considered during the decomposition and in calculating the shortest paths between sweep patterns.
Datasets
The authors generated synthetic maps for evaluation, inspired by the EPFL aerial rooftop dataset. These maps are described as "rectangular worlds with an area of 1 ha and 0 to 15 rooftop obstacles." They also performed a real-world flight experiment on a DJI M600 Pro drone, covering a 1950 m² area with sparse trees.
Key Insights and Ideas
- Optimizing Sweep Directions per Cell: The most significant insight is that fixing a single sweep direction for the entire area is suboptimal. By allowing the planner to choose the best sweep pattern (orientation and start/end points) for each individual cell, substantial improvements in path cost can be achieved.
- E-GTSP as a Powerful Framework: Reformulating coverage planning as an E-GTSP provides a flexible and scalable way to handle complex environments and optimize for multiple criteria (implicitly, path cost). It allows for a more global optimization than simply connecting pre-defined paths.
- BCD vs. TCD Trade-offs: While both decomposition methods work, BCD generally leads to fewer cells and thus a smaller E-GTSP problem, resulting in shorter paths. However, it can have degenerate behavior in narrow regions.
- Practicality for Field Deployment: The planner's ability to solve realistic planning instances quickly enough for field use is a crucial takeaway, especially for applications requiring rapid replanning.
Key Results
- Path Cost Improvement: The proposed planner achieved up to a 14% improvement in path cost compared to a conventional coverage planner with a fixed sweep direction. They also observed a 29% improvement of BCD over TCD for their planner.
- Computational Efficiency: While generating the E-GTSP graph is computationally intensive (especially edge creation), the GK solver can handle the problem efficiently. For complex maps, their planner (E-GTSP with BCD) solved instances in under 65 seconds, which is deemed reasonable for field deployment. Exact solutions, in contrast, became intractable for maps with more than twenty hole vertices.
- Real-world Validation: A field experiment demonstrated the planner's ability to generate and execute a low-altitude coverage path over sloped terrain with trees, producing a usable digital terrain model.
Limitations and Future Work
- Terrain Slope: The current planner does not explicitly consider terrain slope during planning, which was addressed in the real-world experiment by fusing Lidar and Radar altimeter data for altitude control.
- Turning Maneuvers: The paper notes that imperfect reconstruction in the real flight was due to instantaneous acceleration movements. Collision-free trajectory smoothing is suggested to improve turning times and overall performance.
- GPSAR Configuration: Future work includes optimizing coverage for side-looking GPSAR configurations.
- Integration: Further integration into an airborne mine detection system is proposed.
Summary updated