From Multi-Target Sensory Coverage to Complete Sensory Coverage: An Optimization-Based Robotic Sensory Coverage Approach
- Creators
-
Burdick, Joel W.
- Bouman, Amanda
-
Rimon, Elon
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.
Additional Information
© 2021 IEEE. This work was supported in part by a grant from Beyond Limits and BP Inc. to the Caltech Center for Autonomous Systems and Technologies, as well as DARPA through the Subterranean Challenge program.Additional details
- Eprint ID
- 112509
- Resolver ID
- CaltechAUTHORS:20211217-98144000
- Beyond Limits
- BP
- Defense Advanced Research Projects Agency (DARPA)
- Created
-
2021-12-17Created from EPrint's datestamp field
- Updated
-
2021-12-17Created from EPrint's last_modified field
- Caltech groups
- Center for Autonomous Systems and Technologies (CAST)