The travelling salesperson problem (TSP) is a classic resource allocation
problem used to find an optimal order of doing a set of tasks while minimizing
(or maximizing) an associated objective function. It is widely used in robotics
for applications such as planning and scheduling. In this work, we solve TSP
for two objectives using reinforcement learning (RL). Often in multi-objective
optimization problems, the associated objective functions can be conflicting in
nature. In such cases, the optimality is defined in terms of Pareto optimality.
A set of these Pareto optimal solutions in the objective space form a Pareto
front (or frontier). Each solution has its trade-off. We present the Pareto
frontier approximation network (PA-Net), a network that generates good
approximations of the Pareto front for the bi-objective travelling salesperson
problem (BTSP). Firstly, BTSP is converted into a constrained optimization
problem. We then train our network to solve this constrained problem using the
Lagrangian relaxation and policy gradient. With PA-Net we improve the
performance over an existing deep RL-based method. The average improvement in
the hypervolume metric, which is used to measure the optimality of the Pareto
front, is 2.3%. At the same time, PA-Net has 4.5x faster inference time.
Finally, we present the application of PA-Net to find optimal visiting order in
a robotic navigation task/coverage planning. Our code is available on the
project website.

本文利用强化学习算法解决双目标 TSP 问题，提出 Pareto frontier approximation network（PA-Net）方法来生成多项式子集，最终应用于机器人导航覆盖规划任务中，可以优化 Pareto 前沿的表现并提高计算速度 4.5 倍。

利用 Pareto 前沿近似网络（PA-Net）求解双目标 TSP

Pareto Frontier Approximation Network (PA-Net) to Solve Bi-objective TSP

End-to-end training of neural network solvers for graph combinatorial
optimization problems such as the Travelling Salesperson Problem (TSP) have
seen a surge of interest recently, but remain intractable and inefficient
beyond graphs with few hundreds of nodes. While state-of-the-art
learning-driven approaches for TSP perform closely to classical solvers when
trained on trivially small sizes, they are unable to generalize the learnt
policy to larger instances at practical scales. This work presents an
end-to-end neural combinatorial optimization pipeline that unifies several
recent papers in order to identify the inductive biases, model architectures
and learning algorithms that promote generalization to instances larger than
those seen in training. Our controlled experiments provide the first principled
investigation into such zero-shot generalization, revealing that extrapolating
beyond training data requires rethinking the neural combinatorial optimization
pipeline, from network layers and learning paradigms to evaluation protocols.
Additionally, we analyze recent advances in deep learning for routing problems
through the lens of our pipeline and provide new directions to stimulate future
research.

本文提出了一种神经组合优化方法，将学习算法与模型架构相结合，以实现在训练过程中看不到的更大规模的问题的推广。通过对零样本推广的原理研究，控制实验提供了第一手数据，并提供了深度学习的新方向。