论文标题
帕累托边境近似网络（PA-NET）解决双向目标TSP
Pareto Frontier Approximation Network (PA-Net) to Solve Bi-objective TSP
论文作者
论文摘要
旅行销售人员问题（TSP）是一个经典的资源分配问题，用于找到完成一组任务的最佳顺序，同时最大程度地减少（或最大化）相关的目标函数。它被广泛用于机器人技术，以用于计划和调度等应用程序。在这项工作中，我们使用增强学习（RL）解决了TSP的两个目标。通常，在多目标优化问题中，相关的目标功能本质上可能是冲突的。在这种情况下，最优性是根据帕累托最优性定义的。物镜空间中的这些帕累托最佳解决方案组成的帕累托前部（或边境）。每个解决方案都有其权衡。我们介绍了Pareto Frontier近似网络（PA-NET），该网络为双目标旅行销售员问题（BTSP）生成了良好的帕累托前部近似值。首先，将BTSP转换为受约束的优化问题。然后，我们使用拉格朗日放松和政策梯度来训练我们的网络，以解决这一受约束的问题。使用PA-NET，我们改善了现有基于RL的方法的性能。用于衡量帕累托阵线最佳性的超量量指标的平均改进为2.3％。同时，PA-NET的推理时间更快。最后，我们介绍了PA-NET的应用，以在机器人导航任务/覆盖范围计划中找到最佳的访问顺序。我们的代码可在项目网站上找到。
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.
