On the Problem of Covering a 3-D Terrain

Authors

  • Eduard Eiben Royal Holloway University of London
  • Isuru Godage DePaul University
  • Iyad Kanj DePaul University
  • Ge Xia Lafayette College

DOI:

https://doi.org/10.1609/aaai.v34i06.6603

Abstract

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