On the Problem of Covering a 3-D Terrain

Eduard Eiben; Isuru Godage; Iyad Kanj; Ge Xia

doi:10.1609/AAAI.V34I06.6603

On the Problem of Covering a 3-D Terrain

Eduard Eiben
, Isuru Godage
, Iyad Kanj
, Ge Xia

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English
Title of host publication	The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020
Publisher	AAAI Press
Pages	10361-10368
Number of pages	8
Volume	34
Edition	6
DOIs	https://doi.org/10.1609/AAAI.V34I06.6603
Publication status	Published - 3 Apr 2020

Access to Document

10.1609/AAAI.V34I06.6603

Cite this

@inproceedings{e14f1c8939e845dcb143604f549521c7,

title = "On the Problem of Covering a 3-D Terrain",

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.",

author = "Eduard Eiben and Isuru Godage and Iyad Kanj and Ge Xia",

year = "2020",

month = apr,

day = "3",

doi = "10.1609/AAAI.V34I06.6603",

language = "English",

volume = "34",

pages = "10361--10368",

booktitle = "The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020",

publisher = "AAAI Press",

edition = "6",

}

TY - GEN

T1 - On the Problem of Covering a 3-D Terrain

AU - Eiben, Eduard

AU - Godage, Isuru

AU - Kanj, Iyad

AU - Xia, Ge

PY - 2020/4/3

Y1 - 2020/4/3

N2 - 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.

AB - 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.

U2 - 10.1609/AAAI.V34I06.6603

DO - 10.1609/AAAI.V34I06.6603

M3 - Conference contribution

VL - 34

SP - 10361

EP - 10368

BT - The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020

PB - AAAI Press

ER -