TSPDiffuser: 巡回セールスマン経路計画のための学習サンプラーとしての拡散モデル
TSPDiffuser: Diffusion Models as Learned Samplers for Traveling Salesperson Path Planning Problems
障害物のある環境での巡回セールスマン経路計画に対し、拡散モデルを学習サンプラーとして用いてロードマップを構築し、目的地間の移動コストを効率的に見積もる手法を提案した。
著者: Ryo Yonetani
分類: cs.RO, cs.LG
原文アブストラクト
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.
