Revisiting Boustrophedon Coverage Path Planning as a Generalized Traveling Salesman Problem

EasyChair Preprint no. 1457

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 with cameras, ground-penetrating synthetic aperture radar, 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.

Keyphrases: Coverage Planning, Demining, Generalized Traveling Salesman Problem, obstacles, polygon, UAV

@Booklet{EasyChair:1457,
  author = {Rik Bähnemann and Nicholas Lawrance and Jen Jen Chung and Michael Pantic and Roland Siegwart and Juan Nieto},
  title = {Revisiting Boustrophedon Coverage Path Planning as a Generalized Traveling Salesman Problem},
  howpublished = {EasyChair Preprint no. 1457},

  year = {EasyChair, 2019}}