An Approximation Algorithm for the Subpath Planning Problem / 669
Masoud Safilian, S. Mehdi Hashemi, Sepehr Eghbali, Aliakbar Safilian

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