An Approximation Algorithm for the Subpath Planning Problem
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.
Masoud Safilian, S. Mehdi Hashemi, Sepehr Eghbali, and Aliakbar Safilian. 2016. An Approximation Algorithm for the Subpath Planning Problem. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 669–674. https://ijcai.org/proceedings/2016/101
Safilian, M., Hashemi, S. M., Eghbali, S., & Safilian, A. (2016). An Approximation Algorithm for the Subpath Planning Problem. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 (pp. 669–674). IJCAI. https://ijcai.org/proceedings/2016/101
@inproceedings{ijcai2016p101,
title = {An Approximation Algorithm for the Subpath Planning Problem},
author = {Safilian, Masoud and Hashemi, S. Mehdi and Eghbali, Sepehr and Safilian, Aliakbar},
booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-16}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Subbarao Kambhampati},
pages = {669--674},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/101},
}
TY - CPAPER TI - An Approximation Algorithm for the Subpath Planning Problem AU - Safilian, Masoud AU - Hashemi, S. Mehdi AU - Eghbali, Sepehr AU - Safilian, Aliakbar T2 - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2016 SP - 669 EP - 674 UR - https://ijcai.org/proceedings/2016/101 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
