  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.
