Semi-boustrophedon coverage with a dubins vehicle

摘要: This paper addresses the problem of generating coverage paths — that is, pass within some sensor footprint every point in an environment for vehicles with Dubins motion constraints. We extend previous work solves this as a traveling salesman (TSP) by introducing practical heuristic algorithm to reduce runtime while maintaining near-optimal path length. Furthermore, we show optimal is NP-hard reducing from Exact Cover problem, which provides justification our algorithm's conversion instances TSP instances. Extensive experiments demonstrate does indeed produce length comparable significantly less time.