From Multi-Target Sensory Coverage to Complete Sensory Coverage: An Optimization-Based Robotic Sensory Coverage Approach

Abstract

This paper considers progressively more demanding off-line shortest path sensory coverage problems in an optimization framework. In the first problem, a robot finds the shortest path to cover a set of target nodes with its sensors. Because this mixed integer nonlinear optimization problem (MINLP) is NP-hard, we develop a polynomial-time approximation algorithm with a bounded approximation ratio. The next problem shortens the coverage path when possible by viewing multiple targets from a single pose. Its polynomial-time approximation simplifies the coverage path geometry. Finally, we show how the complete sensory coverage problem can be formulated as a MINLP over a decomposition of a given region into arbitrary convex polygons. Extensions of the previously introduced algorithms provides a polynomial time solution with bounded approximation. Examples illustrate the methods.