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

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

Abstract

This paper introduces a significantly improved 1.5-approximation algorithm for the Subpath Planning Problem (SPP), a variant of the Traveling Salesman Problem (TSP) where specific segments of the route are pre-defined. By refining the classic Christofides’ algorithm to handle these fixed subpaths directly, the authors achieve the 1.5-approximation threshold—the gold standard for metric TSP. Furthermore, the authors propose a new generalization called the Subgroup Planning Problem (SGPP) and demonstrate a 10% improvement in solution quality over previous state-of-the-art methods on large-scale datasets.

Introduction: The Subpath Planning Problem

The Subpath Planning Problem (SPP) involves finding the shortest possible loop (tour) that incorporates a set of mandatory segments, or "subpaths." This problem arises in practical applications such as robotics, where a robot might need to follow specific lines or "nicks" on a surface (e.g., car polishing) rather than just visiting discrete points.

SPP is a strict generalization of the Traveling Salesman Problem; if every subpath consists of a single point, the problem reduces to TSP. Given that TSP is NP-hard, SPP is at least as difficult. Previous theoretical guarantees for SPP were limited to a 2-approximation. This work aims to bridge that gap, reaching a 1.5-approximation ratio.

An SPP instance with n=3 subpaths (a) and a resulting tour (b).

Methodology

The researchers developed two primary algorithms to address SPP and its generalization.

1. 1.5-Approximation for SPP

The core innovation is a direct adaptation of Christofides’ algorithm. Unlike previous methods that transformed SPP into a standard TSP instance—thereby introducing "noise" and worsening the approximation ratio—this approach respects subpaths natively.

  • S-Spanning Tree: The algorithm first constructs a Minimum Spanning Tree (MST) forced to include all mandatory subpaths. This is achieved by contracting each subpath into a single point, finding a standard MST, and then uncontracting them.
  • Matching and Eulerian Cycles: Similar to the standard Christofides approach, a minimum-weight perfect matching is found for odd-degree vertices to create a graph where every vertex has an even degree, enabling an Eulerian cycle.
  • Smart Shortcutting: During the shortcutting phase, the algorithm ensures it never shortcuts across a mandatory subpath, preserving problem constraints while maintaining the 1.5 ratio.

2. 3-Approximation for SGPP

The authors also introduce the Subgroup Planning Problem (SGPP). In this variant, vertices are clustered into groups, and the agent must visit all vertices within a group consecutively before moving to the next. The proposed approach involves finding an approximate path within each group first, then treating those paths as subpaths in the SPP algorithm.

An SGPP instance showing clustered groups (a) and a tour connecting them (b).

Experimental Evaluation

The algorithms were evaluated using VLSI (Very Large Scale Integration) datasets, with instances ranging from 130 to over 21,000 vertices. Since these are standard TSP benchmarks, the authors generated subpaths using two methods:

  1. Proximity-based: Connecting nearby points to simulate logical paths.
  2. Random: Connecting distant points to create more challenging metric instances.

Key Results and Insights

The study yielded several significant findings:

  • Theoretical Advancement: The best-known approximation ratio for metric SPP was improved from 2.0 to 1.5. The authors proved this 1.5-approximation is "tight," meaning further improvement would likely require a breakthrough in the general TSP problem.
  • Solution Quality: Numerical experiments showed that the new algorithm outperformed the previous state-of-the-art (Safilian et al., 2016) by more than 10% in tour length for large instances.
  • Computational Efficiency: The algorithm maintains a complexity of $O(n^3)$. It solved instances with 10,000 vertices in under 20 minutes, making it approximately 30% faster than previous methods by avoiding complex transformations.
  • Metric Flexibility: The algorithm only requires the triangle inequality to hold for edges outside mandatory subpaths, increasing its applicability to real-world robotics.

Conclusion and Future Work

While the 1.5-approximation represents a major step forward, it remains bounded by the current limits of metric TSP algorithms. Future research could explore a 2.75-approximation for SGPP by incorporating "Clustered TSP" techniques. Additionally, integrating kinematic constraints, such as turning radii, would be essential for practical hardware implementation in robotics.

Summary updated

Abstract

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.
BibTeX
@inproceedings{sumita2017improved,
  author = {Hanna Sumita and Yuma Yonebayashi and Naonori Kakimura and Ken-ichi Kawarabayashi},
  title = {{An Improved Approximation Algorithm for the Subpath Planning Problem and Its Generalization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/616},
}
Figure