Distilling Privileged Information for Dubins Traveling Salesman Problems with Neighborhoods
Min Kyu Shin Su-Jeong Park Seung-Keol Ryu Heeyeon Kim Han-Lim Choi









723 





















A]Min Kyu ShinAuthor, Email: mkshin@lics.kaist.ac.kr 
A]Su-Jeong Park
A]Seung-Keol Ryu
A]Heeyeon Kim 
A]Han-Lim ChoiCorresponding author, Email: hanlimc@kaist.ac.kr 


[A]Korea Advanced Institute of Science and Technology (KAIST)




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.








§ INTRODUCTION


Motion planning with kinematic constraints should be considered in real-world vehicular applications such as mobile robots and fixed-wing aerial vehicles. Moreover, pathfinding to the points of interest should consider the sensors' specifications on the vehicles. The vanilla TSP, however, does not account for non-holonomic constraints or sensor specifications. To address this issue, one of the specific variations of TSP called the Dubins TSP with neighborhoods (DTSPN) has been studied. DTSPN differs from the vanilla TSP in two key ways. First, the vehicle moves at a constant speed with angular velocity as its control input while following Dubins kinematics. Second, if the target points are within the sensor range of the vehicle, they are automatically marked as "visited". 
Therefore, the vehicle does not have to go directly to the points of interest.


A standard approach to solve DTSPN is to generate sample visiting points around the task points to construct an Asymmetric TSP (ATSP) visiting those sample points <cit.> so that algorithms for ATSP (e.g., branch-and-cut <cit.>, Lin-Kernighan heuristic (LKH)<cit.>) can be utilized. However, the complexity of this procedure grows with the number of sample visiting points; thus, it has a limitation in producing tours in a real-time manner.












On the other hand, learning-based methods have recently been widely studied as they can quickly generate solution path points for TSP in the form of heuristic solvers. Some research has been conducted to solve the TSP problem using the attention model, focusing on scenarios with up to 100 nodes <cit.>. Such transformer models have many parameters to learn due to their complex structure, requiring significant memory and leading to extended training times. These limitations become more evident when applied to the DTSPN, which considers the sensor radius and kinematics of the vehicle. Furthermore, conventional neural networks <cit.>, and transformer <cit.> consider only points of interest, while the agent needs to pass neighborhoods of the points in DTSPN. Also, it is very challenging to train with model-free learning due to the large state-action space. The agent should explore and find a better solution with model-free RL, but it could be difficult to train if the solution space is much smaller than the state-action space. In brief, conventional learning for TSP and model-free learning cannot solve DTSPN.













In our early guess, imitation learning could be a breakthrough to overcome the challenges. We designed imitation learning with expert data from the existing method <cit.>. Behavioral Cloning (BC) and Generative Adversarial Imitation Learning (GAIL) train agents using expert trajectories, which consist of the expert's states and actions, especially when the reward function is unknown. However, BC can easily lose generalization, and GAIL also has difficulties training both a discriminator and an actor network. To overcome exploration, Hindsight Experience Replay (HER)<cit.> is suggested. HER was effective in the sparse reward problem but was not much researched on many goal problems such as <cit.> including the DTSP. RL with demonstrations is an emerging method to train online using expert data or policy. Deep Q-Learning (DQfD) <cit.> and DDPG from Demonstrations (DDPGfD)  <cit.> initialize the model with expert demonstrations offline and train the model with model-free RL. Jump-Start with Reinforcement Learning (JSRL) <cit.> uses an expert policy in the initial episode and follows a more learning policy when the agent achieves better.





Inspired by the distilling of privileged information research <cit.>, we propose an algorithm called Distilling Privileged information for Dubins Traveling Salesman Problems (DiPDTSP). In DiPDTSP, we distill the knowledge acquired by experts into an adaptation network that doesn’t use privileged information. So, the agent can understand the environments from the expert's perspective, where only the locations of tasks are given. We performed several steps to distill the expert's knowledge. First, we collect the expert's state and action sets from the existing heuristic methods<cit.> and train the policy and value networks to initialize. The expert's trajectories are also used as a criterion for the reward function that guides the agent to sense all task points. Since the hand-crafted reward function might not be well-designed, imitation learning that learns reward function directly from expert trajectories is adopted as our baseline model.

Considering these challenges, this paper presents the following three main contributions:



    
  * We propose a new learning approach to address the DTSPN by combining two methods: Distilling PI and RL with demonstrations.
    
  * Accordingly, we promote efficient exploration by initializing the policy and value networks via behavioral cloning using expert trajectories and privileged information.
    
  * The proposed algorithm computes the DTSPN path about 50 times faster than the heuristic method using only the given positions of tasks and agents.



 



§ RELATED WORKS




 §.§ Dubins TSP with Neighborhoods


DTSPN was solved using exact methods and heuristic methods. Traditional transformation methods use the strategy for converting DTSPN into ATSP to apply the exact method <cit.>. It shows that the DTSPN problem makes ATSP with the number of nodes multiplied by the number of samples for each node. Intersecting neighborhood concepts are introduced that can transform DTSPN into Generalized TSP (GTSP) <cit.>. After transforming DTSPN into ATSP, LKH3 <cit.> and exact method <cit.> are applied to solve ATSP. Finally, LKH3 generates the TSP path of each drone and they follow their own path with respect to Dubins vehicle kinematics.



 §.§ Combining demonstrations with Reinforcement Learning


Previous research has effectively integrated reinforcement learning with demonstrations, accelerating the learning process for tasks ranging from the cart-pole swing-up task <cit.> to more complex challenges like humanoid movements <cit.> and dexterous manipulation <cit.>. These studies initialize policy search methods with policies trained via behavioral cloning or model-based methods.

Recent advancements have further expanded the use of demonstrations in RL, with developments in deep RL algorithms like DQN <cit.> and DDPG <cit.>. For instance, DQfD <cit.> refines a Q-function by implementing a margin loss, ensuring that expert actions are assigned higher Q values than other actions.DDPGfD <cit.> tackles simple robotic tasks, like peg insertion, by incorporating demonstrations into DDPG’s replay buffer.
Additionally, the DDPG approach was combined with HER <cit.> to solve complicated multi-step tasks <cit.>.
The Demo Augmented Policy Gradient (DAPG) <cit.> approach integrates demonstrations into the policy gradient method by augmenting the RL loss function. The DeepMimic <cit.> approach combines demonstrations into reinforcement learning by incorporating imitation terms in the reward function. Moreover, JSRL, one of our baselines combined with PPO, utilizes a guided policy that provides a curriculum of starting states resulting in efficient exploration <cit.>.

Existing studies have focused on integrating demonstrations through established RL methods, such as initializing policies, modifying the loss function, shaping rewards, and utilizing replay buffers.
Our research extends this domain by adhering to foundational strategies and applying the Learning Using Privileged Information (LUPI) technique. This approach enables us to extract more nuanced information from demonstrations, thereby presenting a novel method for integrating demonstrations with RL.



 §.§ Learning using Privileged Information


Learning using privileged information (LUPI) frameworks <cit.> is a noticeable strategy to enhance the performance of various tasks ranging from image classification to machine translation, effectively managing uncertainty <cit.>. LUPI leverages privileged information that is only available during the training stage. Privileged information is used to bridge the gap between training and testing conditions. DiPCAN proposes a pedestrian collision avoidance model only using a first-person FOV by reconstructing the privileged pedestrian position <cit.>. Meanwhile, several works use expert trajectories for dynamic models <cit.> and combine RL and LUPI <cit.>. Unlike the related works we've mentioned, our work doesn't require an additional teacher's policy network, and student policy directly accesses the expert's trajectory. However, it is only available at the first stage of training, not the whole process. 

Similarly, knowledge distillation trains a compact student model to mimic the behavior of a larger teacher model, transferring its expertise within resource-constrained settings <cit.>. It is primarily used for model compression; recently, it has proliferated in computer vision area <cit.>. Distilling policy networks in deep reinforcement learning <cit.> ensures rapid, robust learning through entropy regularization <cit.>. Distillation accelerates learning in the multi-task learning domain <cit.>. The robustness of distilling is highlighted by  <cit.>. Our distillation model has the encoder and the adaptation network. The adaptation network will mimic the encoder's output vector even if the PI is not given. 




§ APPROACH




 §.§ Dubins Kinematics with Deep RL

The Dubins TSP with neighborhoods can be formulated as a Markov Decision Process(MDP), {S, A, P, R,γ}. Denote s_t, a_t to the agent state and its action at time t. With the assistance of the expert path as privileged information, the privileged states s_e are parameterized as s_e= [p, p_e, p_T, d_T], 
where p = [x, y, θ] is position and heading angle of the agent, p_e = [p_e1, p_e2, p_e3, p_e4] is the position and angles between the four neighboring waypoints from the expert path, p_T = [p_T1, p_T2,…, p_Tn] is the relative position and angle between task and agent, and d_t = [d_T1, d_T2,…, d_Tn] is the binary variable whether each task is sensed or not. Without the guidance of an expert, the common states s retains the same parameters as the expert states but excludes the expert path information. Therefore, s = [p, p_T, d_T].
The action is the agent's heading angle. Let the action be the angular velocity a_t = w_t. The agent moves with the Dubins kinematics, maximizing the episodic returns.

















    𝔼_π[∑_t=0γ^t R_t]

such that,

    θ̇_̇ṫ   = a_t 
    ẋ_̇ṫ   = v · cosθ_t 
    ẏ_̇ṫ   = v · sinθ_t

Note that the kinematics Eq <ref>-<ref> are not changed whether the state includes expert information. The goal of the MDP problem is to minimize the goal time while the goal is sensing all the tasks. The d_i is initially deactivated or zero, and when the T_i is sensed, d_i is activated and set to 1. The agent is assumed to move with constant velocity by Dubins kinematics. The actions are discretized into 7 between [-0.6π, 0.6π] rad/s with a turning radius of 30m. 

Without experts' trajectories, designing rewards that effectively guide an agent's task-sensing order becomes a significant challenge. Whether the rewards are sparse or dense, based on the proximity to the nearest task, deriving a DTSP path is difficult. However, leveraging expert trajectories simplifies the problem and facilitates more straightforward model training. 
In this problem, the original goal is to sense all the tasks in the short path, but we can change it into following an expert path that senses all the tasks reasonably. Consequently, the reward function should be designed to encourage the agent to adhere to this expert path. This problem has not yet been widely researched, so the reward function needs to be newly designed for this paper. 
We design the reward function consisting of two terms: imitation rewards R^I and task rewards R^G as follows.







    R = R^I + R^G (5)



    R^I = 
        -10    if r >60m 
     
        0.1-(r-5)^2/125    if  r>5m 
    
        0    otherwise(6)



    R^G = 
        10    if Π_i=1^20 d_i = 1 
    
        0.1+5∑_i=1^20d_i    if d_i activated
    
        0.1    otherwise(7)


Here, r is the relative distance between the expert path and the current agent’s position.
The agent gets R^I rewards to guide the agent to follow the expert path and penalize if the agent gets far from the expert path. If the agent is over 6m away from the expert path, it gets negative rewards based on the distance.
The task rewards R^G encourage the agent to sense all the tasks. The agent gets a reward for each step of the exploration. When the vehicle finds the tasks that have not been found (i.e. at the moment d_i is activated), the agent gets five for each task. The episode terminates when the agent senses all the tasks or is over 60m away from the expert path in the training phase. But we terminate only when all the tasks are sensed or the time step reaches 300 to test performance with baselines.



 §.§ Pretraining with Behavioral Cloning
 

While model-free RL often shows generalization performance than model-based learning, it can be intractable when the search space is much larger than the solution space. To deal with the intractability, we initialize the policy and value network using learning from the expert's trajectories. The bunch of the expert's trajectories is called the demonstrations. We collect 5000 demonstrations with the same initial points, but the random positions of the tasks using <cit.>. The derived paths are used to calculate action inversely. The greedy controller chooses one of the discretized actions that closely find the next path point for each step. The datasets containing expert state, action, and reward train the initial actor network in a behavioral cloning manner. By following the expert trajectories, the expected Q-value can also be calculated so that the critic network is initialized by minimizing MSE loss between model outputs and the Q-value of expert datasets.
The expected Q-value can also be calculated along the expert trajectories with designed reward functions. The critic network is initialized by minimizing MSE loss between model outputs and the Q-value of expert datasets. 



 §.§ Phase 1: RL Fine-tuning with Privileged Information
 

Even though the model was initialized with BC, BC does not guarantee the policy's effectiveness due to the distributional shift between expert states and the policy's state.
After the model is initialized with behavioral cloning, the training phase consists of two procedures: RL fine-tuning with privileged information from the experts and PI-free policy adaptation to solve DTSPN without an expert.
In phase 1 of Fig. 2, The model-free PPO networks consist of an encoder and a policy network(so as a critic). Encoder gets the common state s and privileged information p_e. The encoder derives the latent variable z; the policy and critic network get common state s and the latent variable z and derive action and Q-value, respectively. The initialized encoders and actor-critic networks are trained in a model-free PPO manner. We generate one thousand new problems and expert paths and observe performance and convergence.




 §.§ Phase 2: PI-free Policy Adaptation
 
Returning to the original problem, the agent should sense all the tasks without access to expert data, including the order of tasks. To do that, the agent should replicate the action from phase 1 regardless of the availability of privileged information p_e. Given that the input state differs from that used in phase 1, a distinct network, “adaptation” in Fig. <ref> should be introduced that gets only common states s and derives latent variable z'. The adaptation network should imitate the encoder network to make the same action when combining the policy network. The adaptation network is trained to derive z' in the direction of minimizing mean squared error(MSE), ||z-z'||^2. The policy network got the same input as model-free RL. For phase 2, supervised learning, we use the same 5,000 episodes when initializing PPO networks and encoders. After the phase 2 training, The agent can calculate action with given positions of task and agent, and without privileged information, p_e, by learning that given situations are identical regardless of the existence of p_e.




§ EXPERIMENTS




 §.§ Experiment Setup

We collected state, action, and reward tuples from 5,000 episodes, organizing these into mini-batches of 512 for processing. The actor network was initialized using an Adam optimizer with a learning rate of 0.001 and optimized using a cross-entropy loss function. Throughout 1,000 epochs, we monitored the training process to ensure convergence, achieving a validation accuracy of 92% for the behavior cloning policy.

Subsequently, we trained the PPO model while freezing the actor network, allowing the agent to follow the expert policy over 3 million steps. This process involved collecting experiences to calculate the Q-value using our designed dense reward function, which incorporates a discount factor of γ=0.95. During this phase, only the critic network was trained to minimize the Mean Squared Error (MSE) loss. In the final stage, we trained the PPO model for an additional 3 million steps, updating both the actor and critic networks using the PPO loss function. Adam optimizers were employed for both networks, with learning rates set at 0.003 for the actor and 0.001 for the critic, respectively. The initialization of the networks, model-free RL, and supervised RL takes about 3 hours each with an i7-8700CPU and NVIDIA GTX 1060 graphics card. 

We evaluate the proposed model in the environment shown in Fig. <ref>. The map size is 800m x 800m. The agent starts from a specific point on the map, aligning its heading angle with that of the expert path's initial point. Tasks within this environment are uniformly distributed across the map's domain. The vehicle is equipped with a sensing radius of 58 meters. We tested a few baselines and conducted ablation studies of DiPDSTP. 



 §.§ Baselines

Exploration is the main challenge of learning how to generate a DTSP path. In previous research, HER was used to overcome exploration difficulties <cit.>. HER is known to perform well in the sparse reward setting rather than dense rewards. Although many baselines used HER, it is commonly used with an off-policy algorithm, so PPO, which we used to train with model-free RL, is not applicable. Therefore, the additional off-policy algorithms DQN and SAC are implemented to combine with HER. Also, to use the sparse reward, we only give a reward of 1 and -1 when the agent senses the task each time and the time step exceeds the maximum time steps respectively.

We compare our DiPDTSP to the following baselines.


  §.§.§ BC <cit.>
  We train π_θ policy from the expert's trajectory using supervised learning. We treat the expert's demonstrations as state-action pairs (s,a^*), and minimize the Cross-Entropy loss function L(a^*, π_θ(s)) 


  §.§.§ GAIL <cit.>
 
Using GANs, we train the discriminator to identify if the data is from the expert's trajectories. The loss function is a minimax loss, E_τ(log(D(s,a))) + E_τ(log(1-D(s,a))). D is an indicator that tells whether the behavior policy is equal to the expert's policy. It follows the TRPO rule with cost log(D).



  §.§.§ PPO <cit.> with dense rewards
 
We train π_θ policy using only common states s and our designed reward function in Section <ref> by Proximal Policy Optimization, a single-step on-policy model-free algorithm. In other words, it only trains to follow the expert path with guided rewards without distilling the PI process.



  §.§.§ PPO with frozen policy network
 
In Phase 1 of our training method, we trained both the encoder and policy networks. However, we attempted to train only the encoder network for the ablation study while freezing the subsequent network components and remaining other processes the same. These components were initially trained with BC initialization, allowing for RL fine-tuning with fewer variables.




  §.§.§ PPO with JSRL <cit.>
 
We train π_θ policy using only common states s and the sparse reward function in Section <ref> by PPO, a single-step on-policy model-free algorithm.
In the initial process, the agent follows the expert policy with <cit.> while it achieves most of the goals, then the agent tries to explore with learning policy to sense a few of remained goals. If the agent satisfies the predefined achievement or average success rate, the part of following expert policy is reduced, and the exploring or exploiting with learning policy increases.



  §.§.§ DQfD <cit.> + HER
 
In the single Q network, DQN is trained with demonstrations with sparse rewards and online. The full demonstrations are initially stacked in the replay buffer and utilized to initialize the Q-network. Then, it starts to train online, and the offline demonstrations are covered with online experience. In total, it uses a mixture of offline and online data and full online data at last.






  §.§.§ Overcoming exploration in RL with demonstrations <cit.>
 
It originally utilized DDPG, Q-filter, HER, and JSRL. We replaced DDPG with SAC to accommodate discrete actions. During training, the loss function maximizes cumulative reward while minimizing the BC loss between actions from the learning model and experts. We label this method as "SAC(overcome)" for simplicity.




 §.§ Evaluation Metrics

To compare the performance of DiPDTSP with other baseline methods in Sec. <ref>, we define several evaluation metrics.



  §.§.§ Average reward and return
 
Our objective functions in RL, average reward and discounted return, represent how the agent closely follows the expert and senses the tasks. We tested our method and baselines using the dense reward in Sec. <ref>. The higher reward and return represent that the agent follows the expert trajectories closely.



  §.§.§ Sensing rate
 
The sensing rate indicates the average number of visited tasks out of 20. Because of rigorous termination conditions, the agent cannot sense all task points within a single episode. The sensing rate reflects the agent's performance straightforwardly. 



  §.§.§ Time

The time metric indicates the running time of the algorithms with successful episodes.
If none of the episodes succeed, we exclude the evaluation of the method with this metric.
We compare DiPDTSP and other baseline methods with the above evaluation metrics. The baselines are also trained with the same data in the same total timesteps as DiPDTSP. 














 §.§ Simulation Results

Table. <ref> presents the results obtained from the proposed method, DiPDTSP, along with the baseline methods. Across all the baseline methods, they exhibit a common challenge of failing to sense 20 tasks in each episode. Most episodes terminate within 30 steps when employing imitation learning methods (Sec. <ref>, <ref>), while expert trajectory lengths typically span 150 to 300 steps. In comparison, the performance of imitation learning methods falls short of that achieved by PPO. The PPO model outperforms imitation learning methods, but its training speed is slow due to the large exploration space. The imitation learning methods struggle to solve DTSPN primarily due to challenges with distributional shifts and generalization difficulties. The agent only succeeds in sensing a few tasks. The agent gets far from the expert trajectories due to the compounding errors. The results suggest that imitation learning approaches may struggle to match the expert performance in challenging scenarios like the one presented in this multi-goal problem.

We experimented with various versions of PPO, the original with dense reward, jump start, and training-only encoder network. Dense reward with PPO succeeds better than imitation learning and HER method due to the intuitively guided reward function. However, it is not enough to succeed in achieving all goals. A process similar to ours involves freezing the subsequent network after the encoder during the first training phase (Sec. <ref>). This approach shows effective results in that the agent can perfectly sense all the tasks in some episodes. Still, the results show that more training variables need to be tuned. 

Also, using SAC and DQfD with HER with a sparse reward design shows worse performance than simple PPO with dense rewards. An agent in SAC suffers from exploring and sensing many goals perfectly during episodes. DQfD initially trains the expert demonstrations offline, but it is challenging to train with sparse rewards. This result shows that training for varying episodes and multi-goal problems is difficult, although the HER is known to be effective in training sparse reward problems.

The jump-start method is the method to overcome challenging exploration, it shows the effective performance of training that seems to follow the expert policy in the training process. JSRL and SAC(overcome) use BC initialization as ours. However, BC with and without privileged information p_e makes a large performance difference. We monitored the validation accuracy during BC initialization with 1,000 fixed pairs of training datasets. We checked that the validation accuracy of the training state with p_e is 92%, 59% otherwise without p_e. So our method uses BC initialization with p_e train with better-initialized models than JSRL and SAC(overcome). We can infer that p_e is a critical feature influencing BC performance as well as the model-free RL performance.


We apply three skills in DiPDTSP: (i)initializing networks and getting skills from experts by behavioral cloning, (ii) increasing generalizability using model-free learning and PI, and (iii) supervised learning to make the agent sense all task points without PI.
While other methods fail to recover when they choose undesired actions, the agent with DiPDTSP is more robust to deviations from the expert's trajectories. DiPDTSP can almost perfectly follow the expert path and sense all the tasks in all episodes shown in Table. <ref> and Fig.<ref>. The average reward, return, and optimality of DiPDTSP are slightly lower than the expert but very close to the expert performance. The proposed algorithm can generate a DTSPN path in less than 1 second, which is approximately 57 times faster than the heuristic method which takes about 39 seconds.

 


§ CONCLUSIONS

We have presented a learning framework that generates a DTSPN path using only the positions of the agent and the task points. The overall structure combines schemes for distilling PI and RL with demonstrations. 
Learning with privileged information enhances the learning performance of BC to initialize networks and model-free RL. The distilling process makes the model generate the same actions whether the agent has privileged information. The simulation results show that our work outperforms the existing imitation learning and RL with demonstration methods in sensing all task points. Our method closely follows the expert performance while taking more than 50x less computation time than the heuristic solver.




















This work was supported by Unmanned Vehicles Core Technology Research and Development Program through the National Research Foundation of Korea (NRF), Unmanned Vehicle Advanced Research Center (UVARC) funded by the Ministry of Science and ICT (MSIT), the Republic of Korea (#2020M3C1C1A0108237512). Also, the fourth author acknowledges financial supported by Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by MSIT (#2019-0-00075, Artificial Intelligence Graduate School Program(KAIST)).










