Optimal Partitioning of Non-Convex Environments for Minimum Turn Coverage Planning

In this paper, we tackle the problem of generating a turn-minimizing coverage plan for a robot operating in an indoor environment. In coverage planning, the number of turns in the generated path affects the time to cover the environment and the quality of coverage, e.g. tools like cameras and cleaning attachments commonly have poor performance around turns. In many existing turn-minimizing coverage methods, the environment is partitioned into the least number of ranks, which are non-intersecting rectangles of width equal to the robot's tool width. This partitioning problem is typically solved using heuristics that do not guarantee optimality. In this work, we propose a linear programming (LP) approach to partition the environment into the least number of axis-parallel (horizontal and vertical) ranks with the goal of minimizing the number of turns taken by the robot. We prove that our LP method solves this problem optimally and in polynomial time. We then generate coverage plans for a set of indoor environments using the proposed LP method and compare the results against that of a state-of-the-art coverage approach.