Master’s Thesis: Algorithmic methods for complex dynamic sweeping problems
TU Braunschweig, 2016
Most research on touring and covering problems focuses only on distance costs, but in practice many of these problems have significant turn costs. Adding turn costs to a problem can make it considerably harder, e.g. when considering only distance costs, the minimum 2-factor can be obtained in polynomial time, but it becomes NP-hard with turn costs. We investigate the problem variants of finding a minimum cost cycle cover resp. tour for full coverage (every point has to be covered), subset coverage (specific points have to be covered), and penalty coverage (no point has to be covered but every uncovered point has an individual penalty) in grid graphs as well as in polygonal environments. We first show that finding a minimum turn cycle cover in 2-dimensional grid graphs is already NP-hard, solving the open Problem 53 in The Open Problems Project. This also implies the hardness of most other considered problems in this thesis. On the positive side, we propose constant factor approximation algorithms for all considered problem variants in grid graphs. For full coverage in more general grid graphs (e.g., hexagonal grids) our approximation technique results in a better approximation factor than the one of Arkin et al. . To the best of our knowledge, we provide the first approximation algorithms for the other problem variants. Our approximation technique for grid graphs can be extended to polygonal environments where every point is only allowed to be covered in a specific amount of orientations. Aggarwal et al. provide an O ( log n ) -factor approximation algorithm for the non-discretized full coverage problem without obstacles. Our approximation algorithms, for topographies with obstacles, provide approximation factors which do not depend on the problem size, but only on the resolution of the discretization for the full coverage as well as penalty coverage variant. We also provide different integer programs to obtain optimal solutions. In our experiments we were able to increase the optimal solvable problem size to around 700 points for full coverage in 2-dimensional grid graphs, compared to the previous results of around 70 points by de Assis and de Souza. For use with a drone equipped with an electrical lattice to hunt mosquitoes, we further propose two simple practical heuristics for planing tours which try to maximize the expected catch ratio, based on the success of previous runs with limited energy.
Please note that the code has been written with enormous time pressure. If I had more time and the code had been more important (the main results are theoretical after all), the code would have been much better.
The integer program and the approximation algorithm have been reimplemented with vastly improved code quality for a queued publications. Please see this repository.
Experimental data and instances
You can download the used instances and the tables with the experimental results: experiments.tar.gz (3.9MiB)
- Sándor P Fekete and Dominik Krupke. Covering Tours with Turn Cost: Variants, Approximation and Practical Solution. In European Workshop on Computational Geometry (EuroCG 2017), 2017
- There will be a Video partially related to this thesis on the SoCG
- Further publications in progress.
- The IP for the LP-relaxation for the grid graph approximation can be replaced by formulation 1. This drastically improves the runtime.
- There is a minor mistake in the explanation of the NP-hardness proof. The gadget for x1 iff x2 and x3 has the additional condition x_2 or x_3. This, however, has to be fulfilled anyways in the corresponding application which is probably the reason I didn’t notice it in my ‘brute force evaluation’. The proof has become much simpler thanks to this observation. Queued for publication, write me if you would like access in advance.
- During the preparation of the experimental result table it has been noticed that there was a bad entry for the second integer program for full coverage in grid graphs. It wasn’t able to solve the largest entry. This does not change the results because the second formulations was anyway the weakest one. (The reason for this error was probably accidentally pressing a button in ViM)
- ‘Figure 4.8: Analogous to Fig. 4.8’ should of course be ‘Figure 4.8: Analogous to Fig. 4.7’.
- I tried to quickly add more precise runtime complexities ‘in the last minute’. This was a relatively bad idea because I was already too tired and made some mistakes. Please note that the general statements are still true but a few details are inaccurate:
- Chapter 4: The theoretical complexity of solving the provided linear program using Karmarkar’s algorithm is higher than stated but still polynomial. A new implementation of this algorithm (which, however, needs some additional ideas) allows solving instances with more than 100.000 pixel so this is actually just a theoretical detail which does not influence the practicality.
- Chapter 5: ‘the approximation factor and the runtime both depend linearly on the maximum number of orientations’: The runtime dependency is polynomial, not linear. Only the number of vertices in the artificial graph grows linear. In the concrete analysis in the previous chapter, it is stated correctly.