Zapping Zika with a Mosquito-Managing Drone: Computing Optimal Flight Patterns with Minimum Turn Cost (Multimedia Contribution)

Authors Aaron T. Becker, Mustapha Debboun, Sándor P. Fekete, Dominik Krupke, An Nguyen



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.62.pdf
  • Filesize: 1.4 MB
  • 5 pages

Document Identifiers

Author Details

Aaron T. Becker
Mustapha Debboun
Sándor P. Fekete
Dominik Krupke
An Nguyen

Cite AsGet BibTex

Aaron T. Becker, Mustapha Debboun, Sándor P. Fekete, Dominik Krupke, and An Nguyen. Zapping Zika with a Mosquito-Managing Drone: Computing Optimal Flight Patterns with Minimum Turn Cost (Multimedia Contribution). In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 62:1-62:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.SoCG.2017.62

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.
Keywords
  • Covering tours
  • turn cost
  • complexity
  • exact optimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, and Baruch Schieber. The angular-metric Traveling Salesman Problem. SIAM Journal on Computing, 29(3):697-711, 2000. Google Scholar
  2. David L. Applegate, Robert E. Bixby, Vašek Chvátal, and William J. Cook. The Traveling Salesman Problem: A computational study. Princeton University Press, 2011. Google Scholar
  3. Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sándor P. Fekete, Joseph S. B. Mitchell, and Saurabh Sethia. Optimal covering tours with turn costs. In Proc. 12th Ann. ACM-SIAM Symp. Disc. Algorithms (SODA 2001), pages 138-147. SIAM, 2001. Google Scholar
  4. Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sándor P. Fekete, Joseph S. B. Mitchell, and Saurabh Sethia. Optimal covering tours with turn costs. SIAM Journal on Computing, 35(3):531-566, 2005. Google Scholar
  5. Esther M. Arkin, Sándor P. Fekete, and Joseph S. B. Mitchell. The lawnmower problem. In Proc. 5th Canad. Conf. Sympos. Geom. (CCCG93), pages 461-466, 1993. Google Scholar
  6. Esther M. Arkin, Sándor P. Fekete, and Joseph S. B. Mitchell. Approximation algorithms for lawn mowing and milling. Computational Geometry, 17(1):25-50, 2000. Google Scholar
  7. William Cook. In pursuit of the traveling salesman: Mathematics at the limits of computation. Princeton University Press, 2012. Google Scholar
  8. Erik D. Demaine, Joseph S. B. Mitchell, and O'Rourke Joseph. The open problems project. URL: http://cs.smith.edu/~orourke/TOPP/.
  9. Sándor P. Fekete and Dominik Krupke. Covering tours and cycle covers with turn costs: Hardness and approximation. Manuscript, 2017. Google Scholar
  10. Sándor P. Fekete and Gerhard J. Woeginger. Angle-restricted tours in the plane. Computational Geometry, 8(4):195-218, 1997. Google Scholar
  11. Dominik Krupke. Algorithmic methods for complex dynamic sweeping problems. Master’s thesis, Department of Computer Science, TU Braunschweig, Braunschweig, Germany, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail