# GHOST: Solving the Traveling Salesman Problem on Graphs of Convex Sets

Source: https://www.youtube.com/watch?v=TCJ2psQi74M
Recap page: https://rapidrecap.app/video/TCJ2psQi74M
Generated: 2025-11-13T00:03:53.957+00:00

---
## Quick Overview

The GHOST algorithm, introduced in the paper "GHOST: Solving the Traveling Salesman Problem on Graphs of Convex Sets," provides a significantly more efficient and mathematically grounded approach to finding optimal paths in complex, constrained environments compared to traditional methods like MICP, primarily by utilizing a lower-bound cost estimate derived from the graph structure itself.

**Key Points:**
- GHOST solves the Traveling Salesman Problem (TSP) on graphs of convex sets, addressing a complex real-world scenario.
- The method improves upon traditional Mixed-Integer Convex Programming (MICP) by offering a tighter lower bound for pruning search branches.
- The lower bound cost for a path is calculated using a structure called "passage triplets," which represents the minimum cost to traverse between sets of points.
- For a specific example, the lower bound cost for a tour visiting sets costing $1 and $6 was calculated to be $1.0055, which is provably close to optimal.
- GHOST's approach avoids the computational explosion associated with exploring every possible sequence, unlike brute-force methods.
- The algorithm structures the problem using a two-level hierarchy, separating the overall high-level task plan from the low-level physical trajectory planning.

![Screenshot at 04:03: The speaker introduces the two-level hierarchy of GHOST, contrasting the high-level combinatorial search \(which determines the sequence of sets\) with the low-level physical trajectory planning \(which calculates the actual movement within the environment\).](https://ss.rapidrecap.app/screens/TCJ2psQi74M/00-04-03.png)

**Context:** The video discusses a research paper detailing an algorithm named GHOST, designed to solve the Traveling Salesman Problem (TSP) when the nodes are not single points but entire convex sets in a 3D space, such as those encountered in robotics, like path planning for drones or assembly line arms operating around obstacles. This problem is significantly harder than standard TSP because the robot must consider the cost of navigating between entire regions rather than just discrete points.

## Detailed Analysis

The discussion centers on the GHOST algorithm for solving the Traveling Salesman Problem on graphs where nodes are convex sets, a challenging task in robotics involving navigating around obstacles. The speaker contrasts GHOST with traditional methods like MICP, which often fail due to the combinatorial explosion of potential paths when dealing with complex environments. GHOST achieves efficiency by calculating a lower bound cost estimate based on the structure of the problem, specifically using "passage triplets" derived from the graph's geometry. For instance, a path involving sets costing $1 and $6 was estimated to have a lower bound cost of $1.0055, which is provably close to the true optimal cost for that segment. The algorithm employs a two-level hierarchy: the high level determines the sequence of sets (the combinatorial part), and the low level calculates the smooth, feasible physical trajectory between them. This structure allows GHOST to prune sub-optimal paths much faster than MICP, as it can guarantee that any path that exceeds the lower bound cost can be safely ignored, leading to much faster, near-optimal solutions in practice.

### TSP on Convex Sets

- The problem involves finding the shortest tour visiting convex sets (like obstacle regions) in 3D space
- This contrasts with standard TSP where nodes are single points
- The complexity arises from continuous motion between sets.

### GHOST Algorithm Superiority

- GHOST outperforms MICP by providing a tighter lower bound cost estimate for pruning search branches
- The lower bound is calculated using 'passage triplets' derived from the graph structure.

### Cost Estimation Example

- For a path involving sets costing $1 and $6, the lower bound cost is $1.0055, which is provably close to the true optimal cost
- This lower bound is used to guide the search efficiently.

### Hierarchical Structure

- GHOST uses a two-level hierarchy: high-level search determines the sequence of sets (combinatorial), and low-level planning determines the smooth physical path (trajectory optimization)
- This structure prevents the algorithm from getting bogged down exploring every possible path.

### Implementation Details

- The paper suggests that GHOST's structure could be extended to other graph optimization problems, particularly those involving multi-agent coordination and complex constraints.

![Screenshot at 00:00: Podcast intro screen featuring two hosts at microphones with the text "Become a member today!"](https://ss.rapidrecap.app/screens/TCJ2psQi74M/00-00-00.png)
![Screenshot at 00:04: Speaker introduces the problem: solving the Traveling Salesman Problem set in complex real-world environments.](https://ss.rapidrecap.app/screens/TCJ2psQi74M/00-00-04.png)
![Screenshot at 01:24: Visual representation of the graph structure being discussed, highlighting the difference between discrete points and convex regions.](https://ss.rapidrecap.app/screens/TCJ2psQi74M/00-01-24.png)
![Screenshot at 02:32: Speaker explains that the path cost depends entirely on where the robot enters and exits the $6 set.](https://ss.rapidrecap.app/screens/TCJ2psQi74M/00-02-32.png)
![Screenshot at 03:36: Speaker mentions that GHOST uses a two-level hierarchy to manage the complexity.](https://ss.rapidrecap.app/screens/TCJ2psQi74M/00-03-36.png)
![Screenshot at 04:03: The speaker emphasizes the importance of calculating the lower bound cost for the high-level search.](https://ss.rapidrecap.app/screens/TCJ2psQi74M/00-04-03.png)
![Screenshot at 05:56: Visual representation of the 'passage triplet' concept, which is key to calculating the lower bound.](https://ss.rapidrecap.app/screens/TCJ2psQi74M/00-05-56.png)
![Screenshot at 07:03: The speaker quotes the paper, noting the GHOST path cost is provably close to optimal, unlike simple straight-line distances.](https://ss.rapidrecap.app/screens/TCJ2psQi74M/00-07-03.png)
![Screenshot at 09:13: Speaker begins discussing performance improvements compared to traditional methods.](https://ss.rapidrecap.app/screens/TCJ2psQi74M/00-09-13.png)
![Screenshot at 11:08: The speaker highlights that GHOST's guarantee of mathematical optimality is great, but real-world speed is what matters.](https://ss.rapidrecap.app/screens/TCJ2psQi74M/00-11-08.png)