Distilling Privileged Information for Dubins Traveling Salesman Problems with Neighborhoods

2024/04/25 by Min Kyu Shin, Su-Jeong Park, Shin, Min Kyu +7 · 1 citation
Computer Science · #Artificial Intelligence (cs.AI) #Data Management and Algorithms #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2404.16721

openalex publication_date 2024/04/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper presents a novel learning approach for Dubins Traveling Salesman Problems(DTSP) with Neighborhood (DTSPN) to quickly produce a tour of a non-holonomic vehicle passing through neighborhoods of given task points. The method involves two learning phases: initially, a model-free reinforcement learning approach leverages privileged information to distill knowledge from expert trajectories generated by the LinKernighan heuristic (LKH) algorithm. Subsequently, a supervised learning phase trains an adaptation network to solve problems independently of privileged information. Before the first learning phase, a parameter initialization technique using the demonstration data was also devised to enhance training efficiency. The proposed learning method produces a solution about 50 times faster than LKH and substantially outperforms other imitation learning and RL with demonstration schemes, most of which fail to sense all the task points.

Cited by

• Comparing Behavioural Cloning and Reinforcement Learning for Spacecraft Guidance and Control Networks

Related

• Learn to Tour: Operator Design For Solution Feasibility Mapping in Pickup-and-delivery Traveling Salesman Problem
• A Gradient Descent Method for The Dubins Traveling Salesman Problem
• Travel the Same Path: A Novel TSP Solving Strategy
• WiSM: Windowing Surrogate Model for Evaluation of Curvature-Constrained\n Tours with Dubins vehicle
• A Unified Deep Reinforcement Learning Approach for Close Enough Traveling Salesman Problem