Coverage Tours (with Turn Costs)

THIS TEXT IS STILL UNDER CONSTRUCTION

The Traveling Salesman Problem (TSP) stands as a prominent and extensively explored problem in combinatorial optimization. In the TSP, the goal is to determine the shortest possible route for a salesman who must visit a collection of cities and return to the start, optimizing for the least total distance traveled. Recognized as NP-hard, the TSP does not have an efficient algorithm for optimal solutions; however, through advanced algorithm engineering, it is now possible to solve relatively large instances to optimality.

Unlike the TSP, where the destinations are explicit points, many geometric touring problems require visiting areas or a collection of areas, rather than specific points. Furthermore, these problems often demand considerations beyond merely minimizing distance. Factors such as turn costs, which accrue when changing travel direction, become crucial in these scenarios.

In this project, I am delving into various geometric touring problems, encompassing scenarios both with and without turn costs. The aim is to extend our understanding and solution strategies beyond the classical TSP, accommodating the unique challenges posed by regional visits and additional cost factors.

TSP with Turn Costs in Grid Graphs

In addressing the challenge of covering a designated region, a common strategy is to transform the area into a grid graph and then apply the Traveling Salesman Problem (TSP) framework to it. While this approach might seem straightforward, it overlooks a significant aspect in many practical applications: turn costs. Turn costs are pivotal in activities such as lawn mowing, cleaning, painting, or surveillance, where the expense incurred in changing direction—owing to the need to decelerate, turn, and then accelerate again—is often significantly higher than moving straight. A relatable example is the extra effort involved in maneuvering a lawnmower at the end of each row while mowing a lawn.

This challenge, inherently NP-hard, was underscored in our investigation. The complexity of its cycle cover relaxation, a longstanding open question noted as Problem 53 in the Open Problems Project, was addressed in our work presented at (Fekete & Krupke, 2019). Here, we not only proved the NP-hardness of the problem but also developed a new approximation algorithm based on linear programming.

Further advancements in our research were showcased at (Fekete & Krupke, 2019), where we refined the algorithm for greater efficiency and implemented it in C++. Our experiments demonstrated an optimality gap of less than 10% for instances with tens of thousands of vertices. Additionally, our Integer Programming model significantly outperformed previous ones, allowing for the optimal solution of instances with up to 1000 vertices. We also extended our research to the prize-collecting variant of the problem, further enriching the scope of our study.

Partial Coverage Path Planning

In this project, we focused on creating a coverage tour optimizer for environments with polygonal shapes, tailored to accommodate the specific movement dynamics of robots. A key aspect of our approach was the ability to allow partial coverage, particularly concentrating on areas of importance. The initial stage involved a methodical process of converting the targeted area into an optimal grid or mesh structure. This task was crucial for ensuring that the coverage paths devised were both efficient and effective.

Building on the foundations laid in the previous part, we extended the approximation algorithm designed for regular square grids to suit arbitrary mesh structures. This adaptation was not straightforward and required careful consideration of the unique challenges posed by non-uniform grids.

Further, we incorporated several additional optimizations to enhance the algorithm’s performance. These improvements were aimed at refining the coverage paths, making them more practical and efficient for real-world applications.

The result of this project is a comprehensive framework that not only optimizes coverage trajectories in polygonal environments but also does so with a solid theoretical basis. This framework represents a step forward in robotic coverage optimization, offering a solution that is both practically viable and theoretically sound. It demonstrates our ability to bridge the gap between complex theoretical algorithms and their practical implementation in dynamic, real-world scenarios.

Lawn Mowing

The Lawn Mowing Problem seeks to find the shortest tour that covers a given polygonal area using a circular tool. Unlike the previous problems, the movement of the tool is not constrained by the environment. Our primary focus lies in the computation of optimal solutions for small instances without any discretization.

A key insight is that this problem can be viewed as a specific instance of the Close-Enough Traveling Salesman Problem (CE-TSP) with an infinite set of unit disks. Leveraging existing CE-TSP solvers, we have successfully calculated the first provable optimal solutions for very small instances of the Lawn Mowing Problem.

In our ongoing project, Exact Solvers with TSPN-Variants), we are dedicated to developing more efficient CE-TSP solvers tailored to this problem and already made some notable progress. These advancements will enable us to compute optimal solutions for moderately larger instances, allowing us to study the structure of the problem deeper and develop better heuristics for larger instances.

Lawn Mowing with Turn Costs

Once we have a good algorithm for the Close-Enough TSP with turn costs, we can apply it to the lawn mowing problem. The goal is to find optimal or near-optimal tours for lawn mowing with turn costs on small instances. This can then be used to understand more about the structure of the problem and develop heuristics for larger instances.

Milling (Lawn Mowing with Obstacles)

A further question is the computation of optimal tours for the Milling Problem, where the tool is not allowed to intersect with obstacles. This problem is significantly more difficult to solve, but we have some ideas on how to approach it.

Large Neighborhood Search for Geometric Problems

Large Neighborhood Searches (LNS) are a powerful technique to optimize many combinatorial problems to near-optimality. A key component of LNS is the neighborhood structure, which defines the set of solutions that can be reached from a given solution by a single operation. For geometric problems, the geometry often gives you a lot of structure that can be exploited to define an effective neighborhood for LNS. We already utilized this approach in ESA 2023 and ALENEX 2024 with great success. I am planning to further explore this approach in the future and apply it to other geometric problems.

Publications

2024

1. 

   Near-Optimal Coverage Path Planning with Turn Costs

   Dominik Krupke

   In 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX) , 2024

   Abs

   Coverage path planning is a fundamental challenge in robotics, with diverse applications in aerial surveillance, manufacturing, cleaning, inspection, agriculture, and more. The main objective is to devise a trajectory for an agent that efficiently covers a given area, while minimizing time or energy consumption. Existing practical approaches often lack a solid theoretical foundation, relying on purely heuristic methods, or overly abstracting the problem to a simple Traveling Salesman Problem in Grid Graphs. Moreover, the considered cost functions only rarely consider turn cost, prize-collecting variants for uneven cover demand, or arbitrary geometric regions. In this paper, we describe an array of systematic methods for handling arbitrary meshes derived from intricate, polygonal environments. This adaptation paves the way to compute efficient coverage paths with a robust theoretical foundation for real-world robotic applications. Through comprehensive evaluations, we demonstrate that the algorithm also exhibits low optimality gaps, while efficiently handling complex environments. Furthermore, we showcase its versatility in handling partial coverage and accommodating heterogeneous passage costs, offering the flexibility to trade off coverage quality and time efficiency.

2023

1. 

   A Closer Cut: Computing Near-Optimal Lawn Mowing Tours

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

   In 2023 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX) , 2023

   Abs

   For a given polygonal region P, the Lawn Mowing Problem (LMP) asks for a shortest tour T that gets within Euclidean distance 1 of every point in P; this is equivalent to computing a shortest tour for a unit-disk cutter C that covers all of P. As a geometric optimization problem of natural practical and theoretical importance, the LMP generalizes and combines several notoriously difficult problems, including minimum covering by disks, the Traveling Salesman Problem with neighborhoods (TSPN), and the Art Gallery Problem (AGP). In this paper, we conduct the first study of the Lawn Mowing Problem with a focus on practical computation of near-optimal solutions. We provide new theoretical insights: Optimal solutions are polygonal paths with a bounded number of vertices, allowing a restriction to straight-line solutions; on the other hand, there can be relatively simple instances for which optimal solutions require a large class of irrational coordinates. On the practical side, we present a primal-dual approach with provable convergence properties based on solving a special case of the TSPN restricted to witness sets. In each iteration, this establishes both a valid solution and a valid lower bound, and thereby a bound on the remaining optimality gap. As we demonstrate in an extensive computational study, this allows us to achieve provably optimal and near-optimal solutions for a large spectrum of benchmark instances with up to 2000 vertices.

2. 

   The Lawn Mowing Problem: From Algebra to Algorithms

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

   In 31st Annual European Symposium on Algorithms (ESA 2023) , 2023

   Abs

   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.

2019

1. 

   Covering Tours and Cycle Covers with Turn Costs: Hardness and Approximation

   Sándor P. Fekete ,  and  Dominik Krupke

   In Algorithms and Complexity - 11th International Conference, CIAC 2019, Rome, Italy, May 27-29, 2019, Proceedings , 2019

   Abs

   We investigate a variety of geometric problems of finding tours and cycle covers with minimum turn cost, which have been studied in the past, with complexity and approximation results, and open problems dating back to work by Arkin et al. in 2001. Many new practical applications have spawned variants: For full coverage, every point has to be covered, for subset coverage, specific points have to be covered, and for penalty coverage, points may be left uncovered by incurring a penalty. We make a number of contributions. We first show that finding a minimum-turn (full) cycle cover is NP-hard even in 2-dimensional grid graphs, solving the long-standing open Problem 53 in The Open Problems Project edited by Demaine, Mitchell and O’Rourke. We also prove NP-hardness of finding a subset cycle cover of minimum turn cost in thin grid graphs, for which Arkin et al. gave a polynomial-time algorithm for full coverage; this shows that their boundary techniques cannot be applied to compute exact solutions for subset and penalty variants. On the positive side, we establish the first constant-factor approximation algorithms for all considered subset and penalty problem variants for very general classes of instances, making use of LP/IP techniques. For these problems with many possible edge directions (and thus, turn angles, such as in hexagonal grids or higher-dimensional variants), our approximation factors also improve the combinatorial ones of Arkin et al. Our approach can also be extended to other geometric variants, such as scenarios with obstacles and linear combinations of turn and distance costs.

2. 

   Practical Methods for Computing Large Covering Tours and Cycle Covers with Turn Cost

   Sándor P. Fekete ,  and  Dominik Krupke

   In Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments, ALENEX 2019, San Diego, CA, USA, January 7-8, 2019 , 2019

   Abs

   We study the problem of computing provably optimal and near-optimal solutions for the NP-hard problem of finding covering tours and cycle covers with turn cost, which are of practical importance for a variety of applications, such as pest control and precision farming. Previous work has largely focused on theoretical aspects, such as complexity and approximation. We develop a number of algorithm engineering techniques and refinements to make such theoretical insights practically useful, resulting in a comprehensive study for solving a wide spectrum of large instances. We compute provably optimal solutions for instances with more than 1000 pixels, from the largest previous solved instance size of 76 (de Assis and de Souza 2011). Making use of additional algorithm engineering techniques for handling very large instances, we also compute near-optimal solutions for instances with up to 300 000 pixels, for which we give solutions that are typically within a few percent of our computed lower bounds. We also provide an experimental comparison of a practically refined version of our new theoretical approach with the approximation technique of Arkin et al. that dates back to 2001; we show that our new LP/IP-based approximation method closes 70% of the remaining optimality gap to the lower bound.