Revisiting Boustrophedon Coverage Path Planning as a Generalized Traveling Salesman Problem

Rik Bähnemann, Nicholas R. J. Lawrance, Jen Jen Chung, Michael Pantic, Roland Siegwart, Juan I. Nieto

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

Abstract

In this paper, we present a path planner for low-altitude terrain coverage in known environments with unmanned rotary-wing micro aerial vehicles (MAVs). Airborne systems can assist humanitarian demining by surveying suspected hazardous areas (SHAs) with cameras, ground-penetrating synthetic aperture radar (GPSAR), and metal detectors. Most available coverage planner implementations for MAVs do not consider obstacles and thus cannot be deployed in obstructed environments. We describe an open-source framework to perform coverage planning in polygon flight corridors with obstacles. Our planner extends boustrophedon coverage planning by optimizing over different sweep combinations to find the optimal sweep path, and considers obstacles during transition flights between cells. We evaluate the path planner on 320 synthetic maps and show that it is able to solve realistic planning instances fast enough to run in the field. The planner achieves 14% lower path costs than a conventional coverage planner. We validate the planner on a real platform where we show low-altitude coverage over a sloped terrain with trees.
BibTeX
@inproceedings{bahnemann2019revisiting,
  author = {Rik Bähnemann and Nicholas R. J. Lawrance and Jen Jen Chung and Michael Pantic and Roland Siegwart and Juan I. Nieto},
  title = {{Revisiting Boustrophedon Coverage Path Planning as a Generalized Traveling Salesman Problem}},
  booktitle = {FSR},
  year = {2019},
  url = {https://openreview.net/forum?id=F4AXW5lqOw},
}
Figure