ML Anthology

An Approximation Algorithm for the Subpath Planning Problem

Masoud Safilian, S. Mehdi Hashemi, Sepehr Eghbali, Aliakbar Safilian
IJCAI 2016 pp. 669-675
/ijcai/2016/safilian2016ijcai-approximation/

Abstract

The subpath planning problem (SPP) is a branch of path planning problem, which has widespread applications in automated manufacturing process as well as vehicle and robot navigation. This problem aims to find the shortest path or tour subject to covering a set of given subpaths. By casting SPP to a graph routing problem, we propose a deterministic 2-approximation algorithm finding near optimal solutions, which runs in O(n3) time. PDF

PDF IJCAI Semantic Scholar

Cite

Text

Safilian et al. "An Approximation Algorithm for the Subpath Planning Problem." International Joint Conference on Artificial Intelligence, 2016.

Markdown

[Safilian et al. "An Approximation Algorithm for the Subpath Planning Problem." International Joint Conference on Artificial Intelligence, 2016.](https://mlanthology.org/ijcai/2016/safilian2016ijcai-approximation/)

BibTeX

@inproceedings{safilian2016ijcai-approximation,
  title     = {{An Approximation Algorithm for the Subpath Planning Problem}},
  author    = {Safilian, Masoud and Hashemi, S. Mehdi and Eghbali, Sepehr and Safilian, Aliakbar},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2016},
  pages     = {669-675},
  url       = {https://mlanthology.org/ijcai/2016/safilian2016ijcai-approximation/}
}