---
title: "An Approximation Algorithm for the Subpath Planning Problem"
authors:
  - "Masoud Safilian"
  - "S. Mehdi Hashemi"
  - "Sepehr Eghbali"
  - "Aliakbar Safilian"
doi: ""
url: "https://ijcai.org/proceedings/2016/101"
pdf: "https://ijcai.org/proceedings/2016/0101.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "669-674"
track: ""
keywords:
---

# An Approximation Algorithm for the Subpath Planning Problem

Masoud Safilian, S. Mehdi Hashemi, Sepehr Eghbali, Aliakbar Safilian

*Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence*, pages 669-674.

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