Becker, Aaron T. ;
Debboun, Mustapha ;
Fekete, Sándor P. ;
Krupke, Dominik ;
Nguyen, An
Zapping Zika with a Mosquito-Managing Drone: Computing Optimal Flight Patterns with Minimum Turn Cost (Multimedia Contribution)
Abstract
We present results arising from the problem of sweeping a mosquito-infested area with an Un-manned Aerial Vehicle (UAV) equipped with an electrified metal grid. This is related to the Traveling Salesman Problem, the Lawn Mower Problem and, most closely, Milling with TurnCost. Planning a good trajectory can be reduced to considering penalty and budget variants of covering a grid graph with minimum turn cost. On the theoretical side, we show the solution of a problem from The Open Problems Project that had been open for more than 15 years, and hint at approximation algorithms. On the practical side, we describe an exact method based on Integer Programming that is able to compute provably optimal instances with over 500 pixels. These solutions are actually used for practical trajectories, as demonstrated in the video.
BibTeX - Entry
@InProceedings{becker_et_al:LIPIcs:2017:7239,
author = {Aaron T. Becker and Mustapha Debboun and S{\'a}ndor P. Fekete and Dominik Krupke and An Nguyen},
title = {{Zapping Zika with a Mosquito-Managing Drone: Computing Optimal Flight Patterns with Minimum Turn Cost (Multimedia Contribution)}},
booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)},
pages = {62:1--62:5},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-038-5},
ISSN = {1868-8969},
year = {2017},
volume = {77},
editor = {Boris Aronov and Matthew J. Katz},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7239},
URN = {urn:nbn:de:0030-drops-72394},
doi = {10.4230/LIPIcs.SoCG.2017.62},
annote = {Keywords: Covering tours, turn cost, complexity, exact optimization}
}
|
Keywords: |
|
Covering tours, turn cost, complexity, exact optimization |
|
Seminar: |
|
33rd International Symposium on Computational Geometry (SoCG 2017)
|
|
Issue date: |
|
2017 |
|
Date of publication: |
|
2017 |
2017
