[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Document Open Access Logo

The Lawn Mowing Problem: From Algebra to Algorithms

Authors Sándor P. Fekete , Dominik Krupke , Michael Perk , Christian Rieck , Christian Scheffer

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.45.pdf
  • Filesize: 1.25 MB
  • 18 pages

Document Identifiers

Author Details

Sándor P. Fekete
  • Department of Computer Science, TU Braunschweig, Germany
Dominik Krupke
  • Department of Computer Science, TU Braunschweig, Germany
Michael Perk
  • Department of Computer Science, TU Braunschweig, Germany
Christian Rieck
  • Department of Computer Science, TU Braunschweig, Germany
Christian Scheffer
  • Faculty of Electrical Engineering and Computer Science, Bochum University of Applied Sciences, Bochum, Germany

Funding

Work at TU Braunschweig has been partially supported by the German Research Foundation (DFG), project "Computational Geometry: Solving Hard Optimization Problems" (CG:SHOP), grant FE407/21-1.

Cite As Get BibTex

Sándor P. Fekete, Dominik Krupke, Michael Perk, Christian Rieck, and Christian Scheffer. The Lawn Mowing Problem: From Algebra to Algorithms. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 45:1-45:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ESA.2023.45

Abstract

For a given polygonal region P, the Lawn Mowing Problem (LMP) asks for a shortest tour T that gets within Euclidean distance 1/2 of every point in P; this is equivalent to computing a shortest tour for a unit-diameter cutter C that covers all of P. As a generalization of the Traveling Salesman Problem, the LMP is NP-hard; unlike the discrete TSP, however, the LMP has defied efforts to achieve exact solutions, due to its combination of combinatorial complexity with continuous geometry. 
We provide a number of new contributions that provide insights into the involved difficulties, as well as positive results that enable both theoretical and practical progress. (1) We show that the LMP is algebraically hard: it is not solvable by radicals over the field of rationals, even for the simple case in which P is a 2×2 square. This implies that it is impossible to compute exact optimal solutions under models of computation that rely on elementary arithmetic operations and the extraction of kth roots, and explains the perceived practical difficulty. (2) We exploit this algebraic analysis for the natural class of polygons with axis-parallel edges and integer vertices (i.e., polyominoes), highlighting the relevance of turn-cost minimization for Lawn Mowing tours, and leading to a general construction method for feasible tours. (3) We show that this construction method achieves theoretical worst-case guarantees that improve previous approximation factors for polyominoes. (4) We demonstrate the practical usefulness beyond polyominoes by performing an extensive practical study on a spectrum of more general benchmark polygons: We obtain solutions that are better than the previous best values by Fekete et al., for instance sizes up to 20 times larger.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Geometric optimization
  • covering problems
  • tour problems
  • lawn mowing
  • algebraic hardness
  • approximation algorithms
  • algorithm engineering

Metrics

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

Related Versions

Supplementary Materials

References

  1. David L Applegate, Robert E Bixby, Vašek Chvátal, and William J Cook. The Traveling Salesman Problem: A Computational Study. Princeton Series in Applied Mathematics. Princeton University Press, 2007. URL: https://doi.org/10.1016/j.orl.2007.06.002.
  2. 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. URL: https://doi.org/10.1137/S0097539703434267.
  3. Esther M. Arkin, Sándor P. Fekete, and Joseph S. B. Mitchell. The lawnmower problem. In Canadian Conference on Computational Geometry (CCCG), pages 461-466, 1993. URL: https://cglab.ca/~cccg/proceedings/1993/Paper79.pdf.
  4. Esther M. Arkin, Sándor P. Fekete, and Joseph S. B. Mitchell. Approximation algorithms for lawn mowing and milling. Computational Geometry, 17:25-50, 2000. URL: https://doi.org/10.1016/S0925-7721(00)00015-8.
  5. Esther M. Arkin, Martin Held, and Christopher L. Smith. Optimization problems related to zigzag pocket machining. Algorithmica, 26(2):197-236, 2000. URL: https://doi.org/10.1007/s004539910010.
  6. Rik Bähnemann, Nicholas Lawrance, Jen Jen Chung, Michael Pantic, Roland Siegwart, and Juan Nieto. Revisiting Boustrophedon coverage path planning as a generalized traveling salesman problem. In Field and Service Robotics, pages 277-290, 2021. URL: https://doi.org/10.1007/978-981-15-9460-1_20.
  7. Chanderjit Bajaj. The algebraic degree of geometric optimization problems. Discrete & Computational Geometry, 3(2):177-191, 1988. URL: https://doi.org/10.1007/BF02187906.
  8. Michael J. Bannister, William E. Devanny, David Eppstein, and Michael T. Goodrich. The galois complexity of graph drawing: Why numerical solutions are ubiquitous for force-directed, spectral, and circle packing drawings. Journal of Graph Algorithms and Applications, 19(2):619-656, 2015. URL: https://doi.org/10.7155/jgaa.00349.
  9. 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. In Symposium on Computational Geometry (SoCG), pages 62:1-62:5, 2017. Video at https://www.youtube.com/watch?v=SFyOMDgdNao. URL: https://doi.org/10.4230/LIPIcs.SoCG.2017.62.
  10. Károly Bezdek. Körök optimális fedései (Optimal Covering of Circles). PhD thesis, Eötvös Lorand University, 1979. Google Scholar
  11. Károly Bezdek. Über einige optimale Konfigurationen von Kreisen. Ann. Univ. Sci. Budapest Rolando Eötvös Sect. Math, 27:143-151, 1984. Google Scholar
  12. Richard Bormann, Joshua Hampp, and Martin Hägele. New brooms sweep clean - an autonomous robotic cleaning assistant for professional office cleaning. In IEEE International Conference on Robotics and Automation (ICRA), pages 4470-4477, 2015. URL: https://doi.org/10.1109/ICRA.2015.7139818.
  13. Tauã M. Cabreira, Lisane B. Brisolara, and Paulo R. Ferreira Jr. Survey on coverage path planning with unmanned aerial vehicles. Drones, 3(1):4, 2019. URL: https://doi.org/10.3390/drones3010004.
  14. Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, Megan Owen, and Michiel H. M. Smid. A note on the unsolvability of the weighted region shortest path problem. Computational Geometry, 47(7):724-727, 2014. URL: https://doi.org/10.1016/j.comgeo.2014.02.004.
  15. Howie Choset. Coverage for robotics-a survey of recent results. Annals of Mathematics and Artificial Intelligence, 31(1):113-126, 2001. URL: https://doi.org/10.1023/A:1016639210559.
  16. Howie Choset and Philippe Pignon. Coverage path planning: The Boustrophedon cellular decomposition. In Field and Service Robotics, pages 203-209, 1998. URL: https://doi.org/10.1007/978-1-4471-1273-0_32.
  17. International Business Machines Corporation. IBM ILOG CPLEX Optimization Studio, 2023. Google Scholar
  18. George Dantzig, Ray Fulkerson, and Selmer Johnson. Solution of a large-scale traveling-salesman problem. Journal of the Operations Research Society of America, 2(4):393-410, 1954. URL: https://doi.org/10.1287/opre.2.4.393.
  19. Günther Eder, Martin Held, Steinthór Jasonarson, Philipp Mayer, and Peter Palfrader. Salzburg database of polygonal data: Polygons and their generators. Data in Brief, 31:105984, 2020. URL: https://doi.org/10.1016/j.dib.2020.105984.
  20. Gershon Elber and Myung-Soo Kim. Offsets, sweeps and Minkowski sums. Computer-Aided Design, 31(3), 1999. URL: https://doi.org/10.1016/S0010-4485(99)00012-3.
  21. Brendan Englot and Franz Hover. Sampling-based coverage path planning for inspection of complex structures. In International Conference on Automated Planning and Scheduling (ICAPS), pages 29-37, 2012. URL: http://www.aaai.org/ocs/index.php/ICAPS/ICAPS12/paper/view/4728.
  22. Gábor Fejes Tóth. Thinnest covering of a circle by eight, nine, or ten congruent circles. Combinatorial and Computational Geometry, 52:361-376, 2005. URL: http://library.msri.org/books/Book52/files/18fejes.pdf.
  23. Sándor P. Fekete, Utkarsh Gupta, Phillip Keldenich, Christian Scheffer, and Sahil Shah. Worst-case optimal covering of rectangles by disks. In Symposium on Computational Geometry (SoCG), pages 42:1-42:23, 2020. URL: https://doi.org/10.4230/LIPIcs.SoCG.2020.42.
  24. Sándor P. Fekete, Phillip Keldenich, and Christian Scheffer. Covering rectangles by disks: The video. In Symposium on Computational Geometry (SoCG), pages 71:1-75:5, 2020. URL: https://doi.org/10.4230/LIPIcs.SoCG.2020.75.
  25. Sándor P. Fekete and Dominik Krupke. Practical methods for computing large covering tours and cycle covers with turn cost. In Algorithm Engineering and Experiments (ALENEX), pages 186-198, 2019. URL: https://doi.org/10.1137/1.9781611975499.15.
  26. Sándor P. Fekete, Dominik Krupke, Michael Perk, Christian Rieck, and Christian Scheffer. A closer cut: Computing near-optimal lawn mowing tours. In Symposium on Algorithm Engineering and Experiments (ALENEX), pages 1-14, 2023. URL: https://doi.org/10.1137/1.9781611977561.ch1.
  27. Sándor P. Fekete, Dominik Krupke, Michael Perk, Christian Rieck, and Christian Scheffer. The lawn mowing problem: From algebra to algorithms, 2023. URL: https://doi.org/10.48550/arXiv.2307.01092.
  28. Erich Friedman. Circles covering squares web page. https://erich-friedman.github.io/packing/circovsqu, 2014. Online, accessed January 10, 2023.
  29. Enric Galceran and Marc Carreras. A survey on coverage path planning for robotics. Robotics and Autonomous Systems, 61(12):1258-1276, 2013. URL: https://doi.org/10.1016/j.robot.2013.09.004.
  30. Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. Google Scholar
  31. Martin Held. On the Computational Geometry of Pocket Machining, volume 500 of LNCS. Springer, 1991. URL: https://doi.org/10.1007/3-540-54103-9.
  32. Martin Held, Gábor Lukács, and László Andor. Pocket machining based on contour-parallel tool paths generated by means of proximity maps. Computer-Aided Design, 26(3):189-203, 1994. URL: https://doi.org/10.1016/0010-4485(94)90042-6.
  33. Aladár Heppes and Hans Melissen. Covering a rectangle with equal circles. Periodica Mathematica Hungarica, 34(1-2):65-81, 1997. URL: https://doi.org/10.1023/A:1004224507766.
  34. Israel N. Herstein. Topics in algebra. John Wiley & Sons, 1991. Google Scholar
  35. Katharin R. Jensen-Nau, Tucker Hermans, and Kam K. Leang. Near-optimal area-coverage path planning of energy-constrained aerial robots with application in autonomous environmental monitoring. IEEE Transactions on Automation Science and Engineering, 18(3):1453-1468, 2021. URL: https://doi.org/10.1109/TASE.2020.3016276.
  36. Johannes B. M. Melissen and Peter C. Schuur. Covering a rectangle with six and seven circles. Discrete Applied Mathematics, 99(1-3):149-156, 2000. URL: https://doi.org/10.1016/S0166-218X(99)00130-4.
  37. Ghulam Murtaza, Salil S. Kanhere, and Sanjay K. Jha. Priority-based coverage path planning for aerial wireless sensor networks. In IEEE International Conference on Intelligent Sensors, Sensor Networks and Information Processing (IPSN), pages 219-224, 2013. URL: https://doi.org/10.1109/ISSNIP.2013.6529792.
  38. Eric H. Neville. On the solution of numerical functional equations. Proceedings of the London Mathematical Society, 2(1):308-326, 1915. URL: https://doi.org/10.1112/plms/s2_14.1.308.
  39. David Nistér, Richard I. Hartley, and Henrik Stewénius. Using galois theory to prove structure from motion algorithms are optimal. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2007. URL: https://doi.org/10.1109/CVPR.2007.383089.
  40. Timo Oksanen and Arto Visala. Coverage path planning algorithms for agricultural field machines. Journal of Field Robotics, 26(8):651-668, 2009. URL: https://doi.org/10.1002/rob.20300.
  41. David Pisinger and Stefan Ropke. Large neighborhood search. Handbook of metaheuristics, pages 99-127, 2019. URL: https://doi.org/10.1007/978-3-319-91086-4_4.
  42. Gokarna Sharma, Ayan Dutta, and Jong-Hoon Kim. Optimal online coverage path planning with energy constraints. In International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pages 1189-1197, 2019. URL: https://dl.acm.org/doi/10.5555/3306127.3331820.
  43. Solver, Concorde TSP. Concorde TSP Solver, 2023. URL: https://www.math.uwaterloo.ca/tsp/concorde.html.
  44. Xiaoming Zheng, Sven Koenig, David Kempe, and Sonal Jain. Multirobot forest coverage for weighted and unweighted terrain. IEEE Transactions on Robotics, 26(6):1018-1031, 2010. URL: https://doi.org/10.1109/TRO.2010.2072271.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact