# TSPDiffuser: Diffusion Models as Learned Samplers for Traveling Salesperson Path Planning Problems

arXiv: https://arxiv.org/abs/2406.02858 · HTML: https://mlsanity.com/paper/2406.02858/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Diffusion and flow policies for robotics, one of 14 directions in Diffusion models.
- Builds on 28 of its 46 references that are in the map.
- First posted on arXiv 5 Jun 2024.

## Placed in

- Diffusion models / [Diffusion and flow policies for robotics](https://mlsanity.com/diffusion/diffusion-and-flow-policies-for-robotics/)

## Builds on (most cited first, 28 of 28)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [U-Net: Convolutional Networks for Biomedical Image Segmentation](https://mlsanity.com/paper/1505.04597/) (2015)
- [High-Resolution Image Synthesis with Latent Diffusion Models](https://mlsanity.com/paper/2112.10752/) (2021)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Denoising Diffusion Implicit Models](https://mlsanity.com/paper/2010.02502/) (2020)
- [Photorealistic Text-to-Image Diffusion Models with Deep Language Understanding](https://mlsanity.com/paper/2205.11487/) (2022)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Consistency Models](https://mlsanity.com/paper/2303.01469/) (2023)
- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [Diffusion Models: A Comprehensive Survey of Methods and Applications](https://mlsanity.com/paper/2209.00796/) (2022)
- [Planning with Diffusion for Flexible Behavior Synthesis](https://mlsanity.com/paper/2205.09991/) (2022)
- [Offline Reinforcement Learning as One Big Sequence Modeling Problem](https://mlsanity.com/paper/2106.02039/) (2021)
- [On Evaluation of Embodied Navigation Agents](https://mlsanity.com/paper/1807.06757/) (2018)
- [Gibson Env: Real-World Perception for Embodied Agents](https://mlsanity.com/paper/1808.10654/) (2018)
- [Diffusion models as plug-and-play priors](https://mlsanity.com/paper/2206.09012/) (2022)
- [Planning with Goal-Conditioned Policies](https://mlsanity.com/paper/1911.08453/) (2019)
- [AdaptDiffuser: Diffusion Models as Adaptive Self-evolving Planners](https://mlsanity.com/paper/2302.01877/) (2023)
- [NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem](https://mlsanity.com/paper/2110.07983/) (2021)
- [Learning Sampling Distributions for Robot Motion Planning](https://mlsanity.com/paper/1709.05448/) (2017)
- [Motion Planning Networks](https://mlsanity.com/paper/1806.05767/) (2018)
- [PRM-RL: Long-range Robotic Navigation Tasks by Combining Reinforcement Learning and Sampling-based Planning](https://mlsanity.com/paper/1710.03937/) (2017)
- [Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem](https://mlsanity.com/paper/2304.09407/) (2023)
- [Robot Motion Planning in Learned Latent Spaces](https://mlsanity.com/paper/1807.10366/) (2018)
- [Neural Path Planning: Fixed Time, Near-Optimal Path Generation via Oracle Imitation](https://mlsanity.com/paper/1904.11102/) (2019)
- [Learning to Plan in High Dimensions via Neural Exploration-Exploitation Trees](https://mlsanity.com/paper/1903.00070/) (2019)
- [Learned Critical Probabilistic Roadmaps for Robotic Motion Planning](https://mlsanity.com/paper/1910.03701/) (2019)
- [Trajectory-based Traveling Salesman Problem for Multirotor UAVs](https://mlsanity.com/paper/2211.16820/) (2022)
- [PKE-RRT: Efficient Multi-Goal Path Finding Algorithm Driven by Multi-Task Learning Model](https://mlsanity.com/paper/2308.07972/) (2023)

## Abstract (arXiv)

This paper presents TSPDiffuser, a novel data-driven path planner for traveling salesperson path planning problems (TSPPPs) in environments rich with obstacles. Given a set of destinations within obstacle maps, our objective is to efficiently find the shortest possible collision-free path that visits all the destinations. In TSPDiffuser, we train a diffusion model on a large collection of TSPPP instances and their respective solutions to generate plausible paths for unseen problem instances. The model can then be employed as a learned sampler to construct a roadmap that contains potential solutions with a small number of nodes and edges. This approach enables efficient and accurate estimation of travel costs between destinations, effectively addressing the primary computational challenge in solving TSPPPs. Experimental evaluations with diverse synthetic and real-world indoor/outdoor environments demonstrate the effectiveness of TSPDiffuser over existing methods in terms of the trade-off between solution quality and computational time requirements.