An Improved Approximation Algorithm for the Subpath Planning Problem and Its Generalization

An Improved Approximation Algorithm for the Subpath Planning Problem and Its Generalization

Hanna Sumita, Yuma Yonebayashi, Naonori Kakimura, Ken-ichi Kawarabayashi

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 4412-4418. https://doi.org/10.24963/ijcai.2017/616

This paper focuses on a generalization of the traveling salesman problem (TSP), called the subpath planning problem (SPP). Given 2n vertices and n independent edges on a metric space, we aim to find a shortest tour that contains all the edges. SPP is one of the fundamental problems in both artificial intelligence and robotics. Our main result is to design a 1.5-approximation algorithm that runs in polynomial time, improving the currently best approximation algorithm. The idea is direct use of techniques developed for TSP. In addition, we propose a generalization of SPP called the subgroup planning problem (SGPP). In this problem, we are given a set of disjoint groups of vertices, and we aim to find a shortest tour such that all the vertices in each group are traversed sequentially. We propose a 3-approximation algorithm for SGPP. We also conduct numerical experiments. Compared with previous algorithms, our algorithms improve the solution quality by more than 10% for large instances with more than 10,000 vertices.
Keywords:
Planning and Scheduling: Theoretical Foundations of Planning
Combinatorial & Heuristic Search: Combinatorial search/optimisation