On the Problem of Covering a 3-D Terrain
DOI:
https://doi.org/10.1609/aaai.v34i06.6603Abstract
We study the problem of covering a 3-dimensional terrain by a sweeping robot that is equipped with a camera. We model the terrain as a mesh in a way that captures the elevation levels of the terrain; this enables a graph-theoretic formulation of the problem in which the underlying graph is a weighted plane graph. We show that the associated graph problem is NP-hard, and that it admits a polynomial time approximation scheme (PTAS). Finally, we implement two heuristic algorithms based on greedy approaches and report our findings.
Downloads
Published
2020-04-03
How to Cite
Eiben, E., Godage, I., Kanj, I., & Xia, G. (2020). On the Problem of Covering a 3-D Terrain. Proceedings of the AAAI Conference on Artificial Intelligence, 34(06), 10361-10368. https://doi.org/10.1609/aaai.v34i06.6603
Issue
Section
AAAI Technical Track: Robotics