Year: 2021

Abstract:
Multi-objective optimization is used in various areas of robotics like control, planning etc. Their solutions are dependent on multiple objective functions, which 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 own trade off. For instance, the travelling salesman problem (TSP) is used in robotics for task/resource allocation. Often this allocation is influenced by multiple objective functions and is solved using Multi-objective travelling salesman problem (MOTSP). In this work, we present PA-Net, a network that generates good approximations of the Pareto front for the multi-objective optimization problems. Our training framework is applicable to other multi-objective optimization problems; however, in this work, we focus on solving MOTSP. Firstly, MOTSP 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 are able to generate good quality Pareto fronts with fast inference times. Finally, we present the application of PA-Net to find optimal visiting order in coverage planning.

heading: 1 INTRODUCTION
text: Travelling Salesman Problem (TSP) is a popular sequencing problem. TSP aims at finding a sequence or a tour of visiting each node in a given graph and finally returning to the starting node such that the overall cost is minimized. TSP and its variants are widely used in robotics for applications like path planning for UAVs (Xu & Che, 2019), multi-robot path planning (Yu et al., 2002), task allocation for robotic manipulators (Zacharia & Aspragathos, 2005), coverage planning (Bormann et al., 2018) etc.
We intend to use multi-objective travelling salesman problem (MOTSP) for application of coverage planning. Algorithms for coverage planning generates trajectories for robots that can cover a given area (Bormann et al., 2018). Area coverage is used in robotic applications like cleaning robots, surveillance etc. Grid based TSP planners (Bormann et al., 2018), segment a given map into multiple cells, and generate a coverage pattern for each cell.The optimal visiting order for these cells is generated by solving TSP that minimizes the length of the tour. Now imagine a scenario where a robot has to visit these cells and the order is dependent on multiple objectives such as tour length, priority order of the cells etc. So MOTSP would be a more appropriate choice in such a scenario. There is a wide variety of algorithms ranging from exact methods to evolution based methods to solve MOTSP (Lust & Teghem, 2010). Evolutionary algorithms like non-dominated sorting genetic algorithm-II (NSGA-II) (Beirigo & dos Santos, 2016) and multi-objective evolutionary algorithm (MOEA/D) (Peng et al., 2009) are a popular choice of methods to tackle MOTSP and other multi objective optimization problems. Many algorithms also use evolutionary algorithms coupled with local search heuristics (Jaszkiewicz, 2002; Ke et al., 2014; Cai et al., 2014). In practice, these evolutionary based methods suffer in performance and computation time with an increase in the scale of the problem (Zhang et al., 2016). We intend to address these issues using Deep Reinforcement Learning (DRL).
Contribution: In this work, we present Pareto frontier approximation network (PA-Net) that generates an approximation of a set of Pareto optimal tours for MOTSP. We use PA-Net to generate MOTSP tours for coverage planning. Our main contributions are: (1) The drawback of existing ap-
proaches (Li et al., 2020) is costly training of separate networks for different preferences in objective space. Our method avoids this costly training through the use of a single network, while providing generalizability over different preferences in objective space. (2) PA-Net can generate solutions for large number of preferences, which contributes to a dense approximation of Pareto front. Our network has competitive results on various metrics evaluating the quality of Pareto front and faster inference times. (3) Our design can be easily extended to generate a set of Pareto optimal solutions for other multi-objective reinforcement learning and Multi-Objective Optimization (MOO) tasks.
Related Work: Sequencing problems are a subset of Combinatorial Optimization (CO) where the decision variables are discrete. Most CO problems are NP-Hard, as a result state-of-the-art algorithms rely on handcrafted heuristics for making decisions that are otherwise too expensive to compute or mathematically not well-defined. Recently, researchers are addressing these issues using deep learning and machine learning (ML) (Bengio et al., 2020; Vesselinova et al., 2020; Mazyavkina et al., 2020). Many recent works have been dedicated to solving TSP and other sequencing problems using deep networks. Google Brain’s Pointer Network (Ptr-Net) (Vinyals et al., 2015) learns the conditional probability of an output sequence of elements that are discrete tokens corresponding to positions in an input sequence. They used Ptr-Net to solve Euclidean TSP (and other CO problems) in an end to end fashion, where the solutions from classical methods are used as baselines for training. Similarly, TSP was solved using 2D graph conv-nets followed by beam search (Joshi et al., 2019). RL was used to solve various combinatorial optimization problems in (Bello et al., 2016). Their network uses an RNN based encoder and a Ptr-Net. They trained their network using policy gradient. Similar methodology was adopted in (Deudon et al., 2018). They used transformers as the encoder. Kool et al. (2018) proposed an attention based network which used a baseline based on greedy rollouts. Their network outperformed other deep-learning based solvers. While these methods generated competitive results, however, they still lag in performance in comparison to TSP solvers like OR-Tools and Concorde.
Finding Pareto optimal solutions has been studied in deep learning literature for various multiobjective tasks. In supervised learning tasks, many works focussed on multi-objective classification tasks (Sener & Koltun, 2018; Lin et al., 2019; Mahapatra & Rajan, 2020; Ruchte & Grabocka, 2021; Navon et al., 2021). Similarly, many multi-objective RL methods have been to solve multi-objective MDPs (Roijers et al., 2013; Parisi et al., 2014). Some works in RL train many single policy networks to approximate Pareto front (Vamplew et al., 2017; Li et al., 2020). While others have trained a single network to generate a set of Pareto optimal solutions (Yang et al., 2019; Parisi et al., 2016).
There are various methodologies to tackle MOO problems. In ϵ-constrained methods optimize one of the objectives at a time while using the other objectives as constraints (Mavrotas, 2009; Chinchuluun & Pardalos, 2007). One of the most common ways is to use preference vectors (or weights). Some methods use the weighting vectors to scalarize the objective function and Pareto front can be obtained by solving the optimization for multiple preference vectors (Coello et al., 2009; Boyd et al., 2004). On the other hand, some methods (including ours) use these weighting vectors in constraints (Das & Dennis, 1998).
Li et al. (2020) solved MOTSP by training multiple single policy networks. They converted the MOO problem into a single objective using linear scalarization with the help of preference vectors. They train K different networks, each with different preference vector, to approximate the Pareto front. Their network, called DRL-MOA, generated competitive results in comparison to classical methods. However, the downside of their method is that it is redundant to train multiple networks and requires a lot of resources. Furthermore, solutions on concave regions of Pareto fronts cannot be uncovered using the linear scalarization technique, as proved in (Boyd et al., 2004). In our work, we train a single network that can predict solutions for any preference vector. This enables us to produce a much denser Pareto front. Instead of using linear scalarization, our network learns to solve a constrained optimization problem where the constraints are dependent on the preference vectors.
In this work, we present PA-Net, a framework of deep network trained using policy gradient that can approximate Pareto front for MOO problems. Our choice of using RL is motivated by success of Deep CO methods and the fact that it’s hard to generate training data for complex problems like MOTSP. We use PA-Net to find a set of Pareto optimal tours for MOTSP. An augmented version of the network presented in (Deudon et al., 2018) is adopted for PA-Net to solve MOTSP. The novelty of our algorithm is that we pose the problem of finding a set of Pareto optimal solutions as a con-
strained optimization problem, rather than using linear scalarization. We use preference vectors as constraints, which indicates the desired location of the solution in objective space. Finally, we train our network using the reward constrained policy optimization (Tessler et al., 2018), a constrained RL method. Our network performs better than other methods in computation time and generates competitive results in terms of quality of the Pareto front.

heading: 2 BACKGROUND
text: Here we review the definition of Pareto optimality, with a brief primer on solving TSP using DRL.

heading: 2.1 PROBLEM SETUP
text: A MOO is defined as: minx F⃗ (x) = (f1(x), f2(x), ...fm(x)) (1)
where F⃗ (x) is a vector of m-objective functions and x ∈ X is the decision variable in Rn. In such problems, often different objectives are conflicting in nature, i.e. no single solution can simultaneously optimize all the objectives. Instead, a set of Pareto optimal solutions provide the best solutions with different trade-offs between various objectives. Pareto optimality is defined as follows:
• Dominance: A solution xa is said to dominate xb (xa ≺ xb) if and only if fi(xa) ≤ fi(xb), ∀i ∈ {1, ...m} and fj(xa) < fj(xb) such that ∃j ∈ {1, ...m} . • Pareto Optimality: A solution x∗ is said to be Pareto optimal if there does not exist any solution x ′ such that x ′ ≺ x∗. A set of all such points form a Pareto frontier denoted by Υ.
The Euclidean TSP is defined over a graph of n cities, where each city has coordinates a ∈ R2. A TSP tour π provides a sequence of visiting cities exactly once and then returning to the starting city. MOTSP is a MOO problem that aims to find a set of Pareto optimal TSP tours Π (Π ⊂ Zn) on a complete graph s, while optimizing for m objectives. Each city in s can have p a set of features. In case of bi-objective TSP, the input graph s is a sequence of n nodes in a four dimensional space s = {a1i , a2i }i=1:n, where ami ∈ R2 for each m ∈ {1, 2} (Li et al., 2020). The goal is to find a tour π ∈ Π that visits each city once and can simultaneously optimize the objectives for m ∈ {1, 2}:
fm(π|s) = ∥∥amπ(n) − amπ(1)∥∥2 + n−1∑
i=1 ∥∥amπ(i) − amπ(i+1)∥∥2 (2)

heading: 2.2 TSP USING DRL
text: An attention based network to solve TSP was proposed by Deudon et al. (2018). We will refer to this network as TSP-Net. We use a modified version of TSP-Net for our network. TSP-Net uses an actor-critic network which is trained using REINFORCE (Williams, 1992). The input to the network is a graph s. Each city coordinates is embedded into a higher dimension. These embedded representations are then passed on to a Multi-Headed attention encoder that generates an encoded representation of the complete graph. Both actor and critic networks share the same encoder architecture. The decoder network of the actor uses a Pointer-Network (Ptr-Net) to generate the TSP tours. The tour is sequentially constructed, where at each step an appropriate city is selected based on the current state and the previous actions by the Ptr-Net. The actor network θ, is trained to minimize the total tour length given by equation 2. The network is trained on a batch of TSP problem instances of size B. The training objective for the actor is given by:
D(θ) = Es∼S [Eπ∼pθ(.|S)[Q(π|S)]] (3) Here, S is the distribution from which training graphs are drawn and pθ(π|S) is the probability of a tour generated by the Ptr-Network. The decoder of the critic with parameters ϕ, is a feed forward network that predicts the baseline for the objective function.

heading: 3 METHODOLOGY
text: This section provides our mathematical formulation for MOO. We use the formulation to train a network that can generate a good approximation of the Pareto front for MOTSP.

heading: 3.1 PROBLEM FORMULATION
text: We intend to generate a good quality approximation to Pareto front denoted by Υ̃, where Υ̃ ⊂ Υ. The set Υ̃ should capture a range of possible dominant solutions in the objective space.
MOTSP is an extension of TSP to the MOO domain. Let the vector cost function for a MOTSP is given by F⃗ (π) where F⃗ ∈ Rm and the tour π ∈ Π (Π ⊂ Zn). The optimization problem can be written as:
minπ F⃗ (π) = (f1(π)...fm(π)) (4)
Where fi : π → fi(π) for fi(π) ∈ R. We further assume that all the cost functions are strictly positive:
fi(π) > 0 ∀i ∈ {1...m} (5)
In order to find the Pareto front, we convert the MOO in equation 4 to a set of constrained optimization problem. This is done by discretizing the objective space using a collection of unit preference vectors W : {w⃗1...w⃗K}. These preference vectors are a set of rays emanating from origin that uniformly divide the objective space. Each element in w⃗k lies in the interval {0, 1} and also ||w⃗k||2 = 1. The key idea is to solve a surrogate optimization problem along each preference vector in order to generate a set of dominant solutions for equation 4. This surrogate optimization is expressed as a set of K constrained optimization problems where the kth problem corresponding to w⃗k ∈ W is given by:
minF⃗ (πk) J(F⃗ (πk)) = ||F⃗ (πk)||2
s.t. F⃗ (πk) ∈ Ck (6)
The constraint set is defined as Ck = {F⃗ (π) ∈ Ck : g(F⃗ (π), w⃗k) ≤ 0} and the corresponding tour set is defined as Ak = {π ∈ Ak : g(F⃗ (π), w⃗k) ≤ 0} . Here, the dot product constraint g(F⃗ (πk), w⃗k) is given by:
g(F⃗ (πk), w⃗k) = 1− w⃗k · F⃗ (πk)
J(πk) (7)
We assume Ak is non-empty. As a consequence of this assumption, Ck is also non-empty.
The constraint set Ck represents a set of vector cost F⃗ (πk) associated with πk ∈ Ak that lie on the unit preference vector w⃗k in objective space. The objective function in equation 6 minimizes L2-norm which finds the points closer to origin. Below, we state a theorem that is the motivating factor of our work:
Theorem 1. F⃗ ∗ ∈ Ck is the optimum solution of equation 6 if and only if it dominates all other points in the set.
Proof: Let F⃗ ” ∈ Ck minimize the equation 6 such that F⃗ ∗ ≺ F⃗ ”. This dominance relation implies that f∗i ≤ f”i ∀i ∈ {1, 2..m} and ∃j ∈ {1, 2..m} such that f∗j < f”j . This dominance relation leads to the following result:
||F⃗ ∗||2 < ||F⃗ ”||2 (8)
But this result is a contradiction because F⃗ ” minimizes equation 6. Hence, F⃗ ∗ ∈ Ck that dominates all other points in the set is the optimum solution for problem equation 6. ■
The dominant point in the set, i.e. F⃗ ∗ ∈ Ck is also unique in the set. An intuitive proof for this can be visualized using the case for Ck ⊂ R2 as shown in Fig. 1. Because of the dot product constraint, all the possible members in the set lie on the unit vector w⃗k. It is clear from the image that the point in the set Ck closest to origin dominates all other points and is in fact the optimum solution of equation 6. Further, there can be multiple solutions in Ak that lead to the dominant objective value, i.e. F⃗ ∗. Mathematically, the solution set Sk ⊂ Ak, where Sk = {π∗ ∈ Sk : F⃗ (π∗) = F⃗ ∗}, all π∗k ∈ Sk will generate dominant objective values. The essence of Theorem 1 is that it demonstrates the viability of approximating the Pareto front for problem in equation 4 through the surrogate optimization problem in equation 6. Solving optimization problem in equation 6 for large values of K can be computationally intractable. We address this issue, through the generalization power of deep neural networks. PA-Net learns to approximately solve equation 6 on a given input preference set and has an ability to generalize to other preferences as well. Unlike linear scalarization methods, our formulation can also find concave Pareto frontier. We demonstrate this with an example in Appendix.

heading: 3.2 TRAINING METHODOLOGY
text: The reward constrained policy optimization is an actor-critic algorithm (Tessler et al., 2018). It uses a Lagrangian of the constrained problem as the objective function, where after each gradient update step, the Lagrangian multipliers are updated based on the constraint violation. We use the reward constrained policy optimization to train a network to solve the problem in equation 6 for all k ∈ {1...K}.
Algorithm 1: Training of PA-Net input : [θ, ϕ, ηA, ηC ], [W,α, λmin, λmax] ←− Initialization of network weights, set of preference vectors and corresponding parameters. output: Trained network parameters of PA-Net θ∗, ϕ∗. for i ←− 1, 2...N do
Ω : {s1 .... sB} ← Sample a Batch of TSP Graphs of size B from distribution S. for k ←− 1, 2...K do
for j ←− 1, 2...B do πjk ←− Actor network Generates TSP Tour for each s j and w⃗k .
bϕ(w⃗k, s j) ←− Critic Network predicts the baseline
Lk(π j k|s j) ←− Calculate the larangian using equation 11.
Actor Update: θ ←− θ − ηA · ∇θDAC(θ) Critic Update: ϕ ←− ϕ− ηC · { 2B ∑K k=1 ∑B j=1(bϕ(w⃗k, s j)− (Lk(πjk|s j))}
for k ←− 1, 2...K do λk ←− Update the lagrangian multipliers using equation 15
We intend to train a single network that generates a set of dominant tours T : {π1, ..., πK}. Hence, the problem in equation 6 for each πk ∈ T can be written in the parametric format as:
minθ J(πk(θ)) = ||F⃗ (πk(θ))||2 s.t. gk(F⃗ (πk(θ), w⃗k)) ≤ 0
(9)
Here, θ is the parameters of the actor network. The Lagrangian dual problem for equation 9 is:
Lk(θ, λk) = maxλk≥0 minθ J(πk(θ)) + λk · gk(F⃗ (πk(θ))) (10)
Here, λk is the kth Lagrangian multiplier corresponding to the preference vector w⃗k. PA-Net uses modified TSP-Net in order to generate a dominant set of tours T . We augment TSP-Net network by adding an input of a set of preference vectors W of size K. Each w⃗k ∈ W is encoded in higher dimensions using a feed-forward network. These additional layers learn features corresponding to different preferences. This encoding is then combined with the encoded representation of the graph and then passed on to the decoder. With this architecture, the network can be trained for various preferences. Complete details regarding the architecture is presented in Appendix. We use the Lagrangian in equation 10 as the reward for the network. The reward for each tour generated by the actor corresponding to each preference for a given graph can be written as:
Lk(π j k, w⃗k|s j) = J(πk(θ)|sj) + λk · gk(F⃗ (πk(θ))|sj). (11)
Based on this reward, the training objective for the actor can be written in our case as:
DAC(θ) = Es∼S [Ew⃗k∼W [Eπ∼pθ(.|s)[Lk(π, w⃗k|s)]]]. (12)
The critic network provides predictions bϕ(w⃗k, sj) on the reward given in equation 11. The critic network is trained on the mean squared error between its predictions and rewards of the actor, which is given by:
DCR(ϕ) = 1
B K∑ k=1 B∑ j=1 (bϕ(w⃗k, s j)− (Lk(πjk|s j))2 (13)
The gradient for the training of the actor network is approximated using REINFORCE (Williams, 1992):
∇θDAC(θ) ≈ 1
B K∑ k=1 B∑ j=1 [(Lk(π j k|s j)− bϕ(w⃗k, sj)) · ∇θlog(pθ(πjk|s j))]. (14)
The description of the training of PA-Net is given in Algorithm 1. We start with initialization of weights and learning rates for the network and the set of preference vectors, along with other hyperparameters that are the ascent rate of the Lagrangian multipliers α and [λmin, λmax] the limits for the multipliers. The network is trained for N iterations. At each iteration, a set of graphs Ω of size B are generated. For each sj ∈ Ω corresponding to every preference vector, w⃗k ∈ W a tour πjk. Based on generated tours, the objective for actor and critic are calculated. Then parameters of the network are updated using gradient descent. At the end of each iteration, the Lagrangian multiplier corresponding to each preference vector are updated in an ascent step using:
λi+1k = Γλ(λ i k + α · B∑ j=1 gk(F (π j k(θ), w⃗k))) (15)
Here Γλ(·) ensures that the multipliers remains within the limits, i.e. [λmin, λmax] and α is prespecified ascent rate. Although the network is trained on a fixed set of preferences W , it however can generalize to a larger set of preferences. A detailed discussion on preference selection mechanism and study on effect on network performance due to some key hyperparameters is presented in the Appendix.
There are a few caveats in solving equation 6 with our approach. The guarantees provided in Theorem 1 may not hold because the reward constrained policy optimization guarantees convergence of equation 9 to a saddle point (θ∗(λ∗), λ∗) which may not lead to the global optimum of equation 6. Further, a strong duality would have to be established between equation 9 and its dual form in equation 10. However, in practice our approach is able to generate competitive results as presented next.

heading: 4 EXPERIMENTS
text: In this section, we present experiments to evaluate the efficacy of PA-Net and use case of two objective MOTSP for coverage planning. The performance of PA-Net and other algorithms is compared on MOTSP instances with {2, 3 and 5} objectives, respectively. The performance of PA-Net is compared with deep learning based method DRL-MOA (Li et al., 2020), evolution based strategies: NSGA-II and MOEA/D (Peng et al., 2009) and OR-Tools solver (using linear scalarization) that primarily uses local search methods and meta-heuristics.
Experimental Details: All the above-mentioned algorithms are evaluated on a set of 25 randomly generated MOTSP instances. Each MOTSP instance is a graph s of size n×t, where, n the number of
cities and each city is represented by t dimensional features. These features are drawn uniformly at random from [0, 1]. Here, t = 4 for {2, 3}-objective TSP and t = 6 for 5-objective TSP. Two forms of objective functions are used, one with reward of L1-norm and the other one with L2-norm. For 2-objective instances, we use L2-norm for both objective. In the case of {3, 5}-objective instances, we use L2-norm for f1 and L1-norm for the remaining. The objective with L2-norm is generated using equation 2. Similarly, the objective for L1-norm for b∗ ∈ R is:
fi(π|s) = ∥∥b∗π(n) − b∗π(1)∥∥1 + n−1∑
j=1 ∥∥b∗π(ij) − b∗π(j+1)∥∥1 (16) The results of PA-Net are compared with other methods on the basis of average run time and the average hypervolume (HV) of the solutions obtained across 25 instances. HV is a hybrid metric used to evaluate Pareto fronts (Bérubé et al., 2009; Audet et al., 2020). It represents the volume covered by the non-dominated set of solutions with respect to the a reference point.A higher HV represents a better quality of the Pareto front, both in terms of optimality and coverage of the objective space. We use Monte-carlo sampling to calculate HV, where, HV is given by the percentage of points dominated by the solution set out of randomly sampled points in a fixed volume in the objective space. A fixed reference point is used to compare all the algorithms. It is calculated as the product of number of cities and unity vector, for example, reference point for 200-city bi-objective TSP is [200.0, 200.0]⊤.
For bi-objective TSP 100 solutions are evaluated for each case. In {3,5}-objective MOTSP 91 and 40 solutions are reported. Further, we also report 500 solutions for PA-Net in {3,5}-objective MOTSP to demonstrate its generalization ability. It should be noted that the preferences used in linear scalar-
ization are sampled from [0,1] and satisfy convexity constraints. In PA-Net the preferences used are unit vectors that uniformly segment the objective space.
The trained model of bi-objective TSP for DRL-MOA (Li et al., 2020) is used. For NSGA-II and MOEA/D, we use a MATLAB based software platform, PlatEMO (Tian et al., 2017). The experiments for PA-Net and DRL-MOA are carried out on NVIDIA V100 Volta GPU. Whereas, for NSGA-II, MOEA/D and OR tools experiments are carried out on dual-core Intel i5 processor.
Training Details:For all three instances of MOTSP problems we train separate networks i.e. PA-2, PA-3 and PA-5 for {2, 3, 5}-objective TSP respectively. All PA-Nets are trained on 120 city MOTSP instances. The preferences for PA-Net are randomly sampled (more details in Appendix).
The details of training of PA-Net and DRL-MOA are given in Table-1. The times are reported based on training from NVIDIA V100 Volta GPU. Note that in case of DRL-MOA, average training time for each preference network is ∼ 1hr (for {2,3,5} objective). So 100 networks are trained with the total training time ∼ 70hrs. Discussion: The results of quantitative comparison for 2-objective MOTSP is given in Table-2. Similarly, the results for {3, 5}-objective is summarized Table-3. Visualization for various MOTSP instances is given in Fig-2 (a)-(c). It is clear that OR tools achieves the best performance in terms of HV. However, it has longer runtimes as compared to other methods. On the other hand, evolutionary methods significantly underperform as the scale of the problem increases. This is likely because these algorithms are unable to explore the solution space well for larger problems. Running these algorithms for more iterations could potentially improve their performance in terms of HV, but this comes with an additional computational cost. Both PA-Net and DRL-MOA achieve competitive results in terms of HV. Our network achieves better performance as compared to DRL-MOA in 2 objective problem. PA-Net generates the complete Pareto front much faster as compared to other methods. Further, we have significantly lowered the training times as compared to DRL-MOA, see Table. 1. Another notable point is that for each problem set, PA-Net can infer solution from a single network, whereas DRL-MOA has to train and rely on multiple networks. For the {3,5}-objective case, while our network is much faster than DRL-MOA, our network lags behind in HV when using lower number of preferences. This issue can certainly be addressed with prolonged training and better tuning of the network and use of local search heuristics to refine solutions.
Application for Coverage Planning: We test our network for coverage planning. We assume a scenario where the robot has to visit all the cells while ensuring the maximum adherence to a precomputed priority order. Such a scenario is representative of real-world applications. For instance, a cleaning robot has to clean a large area where different regions have varied priorities based on the number of people visiting those areas. So the goal is to visit all the cells while minimizing the total distance travelled and maximizing the adherence to pre-computed priority order. This task can be cast as a 2-objective MOTSP instance. For this experiment, we use a different graph than the one used in the previous experiment. Each cell in the graph has four features {a, b, 0}. Here, a ∈ R2 is the Euclidean coordinates of the and b ∈ R+ is the priority. Note that a lower value of b corresponds to greater priority. So for this task we synthetically generate TSP instances of size 200 and 500 cells respectively. We compute tours from PA-2 and other algorithms. Comparative results for different algorithms for the coverage planning task are listed in Table-4. The plots for the Pareto front for this experiment are shown in Fig-2(d). An intuitive visualization of tours generated in this experiment can be found in Appendix and here.

heading: 5 CONCLUSIONS
text: We presented PA-Net, a network that approximates the Pareto frontier for the multi-objective TSP. Our results indicate a superior performance in terms of optimality of the solutions. This is achieved by segmenting the objective space using a set of unit vectors which represent trade-offs among various objectives. We then use these preference vectors to convert the unconstrained optimization problem into a set of constrained optimization problems. Then the network is trained using policy gradient to generate solutions for these constrained problems. While PA-Net is trained on a fixed number of preference vectors, it generalizes well to other unseen preferences as well. The effectiveness of our method is highlighted by the competitive results in terms of quality of solutions, faster inference and training times. Although we focus on multi-objective TSP in this work, our training framework can be applied to other MOO problems. We also demonstrated a use case of PA-net for a simple coverage planning application. The future direction is extending the work to multi-robot system that can also account for the uncertainty in the environment.

heading: APPENDIX

heading: CONVERGENCE TO CONCAVE PARETO FRONTS
text: The backbone of PA-Net is as follows: to generate a Pareto front for the Multi Objective Optimization (MOO) problem in equation 4, we solve a set of K constrained surrogate optimization problem given by equation 6. In order to show that our framework can work for MOO problems with concave frontier, we have generated solutions for a MOO problem with concave Pareto front by solving equation 6 for K preferences. The MOO problem we solve is taken from Lin et al. (2019) and is given by:
minx F⃗ (x) = [f1(x), f2(x)] ⊤, (17)
where, f1(x) = 1− exp(−Σdi=1(xi −
1√ d )2),
f2(x) = 1− exp(−Σdi=1(xi + 1√ d )2).
(18)
Here x = [x1, x2]⊤ ∈ R2+ and d = 2. The surrogate optimization in this case with preference w⃗k is given by:
minF⃗ (xk) J(F⃗ (x k)) = ||F⃗ (xk)||2
s.t. 1− w⃗k · F⃗ (x k)
J(F⃗ (xk)) ≤ 0
(19)
We solve the above problem in Matlab for K = 20. The preference is generated by w⃗k = [cos(ϕk), sin(ϕk)]
⊤, where ϕk ∈ {0, 90}. We also solve the MOO problem with a simple linear scalarization of objective. In this case, the preference is given by αk = [α1, α2]⊤ ∈ R2+ such that α1 + α2 = 1. We use K = 100 prefrences in this case. The kthobjective function for linear scalarization is:
minF⃗ (xk) R(F⃗ (x k)) = α1 · f1(xk) + α2 · f2(xk) (20)
The results are shown in the image below. It can be clearly seen that our method is able to produce the concave Pareto front. On the other hand, linear scalarization is unable to find solutions on the concave part of the Pareto front(Boyd et al., 2004) and converges to one solution for all preferences. This example demonstrates that our method can certainly be extended to MOO with concave Pareto fronts.

heading: NETWORK ARCHITECTURE
text: PA-Net uses a modified architecture of TSP-Net Deudon et al. (2018). TSP-Net aims at finding tours with minimal path length. On the other hand, PA-Net finds a set of Pareto optimal tours that are dependent on multiple criterias. The architecture of the for both PA-Net and TSP-Net is shown in Fig-4.
TSP-Net: The input to the network is a batch of N -city TSP graphs Ω : {s1....sB}. Each city, abi ∈ Rp in the input graph, is encoded to a higher dimension embedding dbi ∈ Rd using a multiheaded attention encoder (Vaswani et al., 2017; Deudon et al., 2018). So each graph sb ∈ Ω can be represented as Db : {db1...dbN}. This encoded graph sequence is then converted into a unified graph representation F bac: F bac = Wp(θ) ·Db (21) Here, θ are the parameters of the actor network and Wp is a matrix that projects the encoded graph sequence to a unified representation. This unified graph representation is then used by pointer network to generate TSP tours for the complete batch Ω. The details of the pointing mechanism to generate a tour can be found in (Vinyals et al., 2015; Deudon et al., 2018). The gradient at training time is computed using REINFORCE. The critic network uses the same attention based encoder to generate a unified graph representation (F bcr), which is then used by a feedforward network to predict the baseline for training.
PA-Net: For PA-Net, the input is a batch of TSP tours Ω and a set of preference vectors W : {w⃗1...w⃗K}. Like before, each city is encoded to a higher dimension embedding dbi . Each w⃗k is encoded using a feed forward network to obtain a higher dimension embedding hk ∈ Rd. Now, the encoding of each city is combined with the kth preference encoding to generate augmented embedding for the cities dbi,k:
dbi,k = d b i + hk (22)
From Eq-equation 22 augmented embeddings for all the cities in a graph are Dbk : {db1,k...dbN,k}. The unified graph representation F bk,ac, for G
b and kth preference, is obtained using Eq-equation 21. Finally, a set of K tours for each Gb is generated by the pointer network. The gradient at training time is computed using Eq-equation 14. The critic uses the same encoder architecture to generate an augmented unified graph representation (F bk,cr), which is used by the feed-forward network (FFN) to predict the baseline.

heading: PREFERENCE SELECTION
text: One of the key features of PA-Net is its ability to generate solutions for different preferences in the objective space. This is achieved by simultaneously training the network on a set of preferences W . Since each w⃗k ∈ W is a unit vector, it must satisfy ||w⃗k||2 = 1. For training of 2-objective network, these preferences can be generated by sampling unit vectors from the unit circle for angles in {0◦, 90◦}. For objectives more than two, selecting preferences is not so straight forward. In this case, the preference w⃗k ∈ Rp is generated using:
w⃗k = 1√
(a1k) 2 + ...(apk)
2 · (a1k.....a p k) ⊤, (23)
where aik is sampled from {0, 1} ∀i ∈ {1...p}. So using Eq-equation 23 preference vectors for higher dimension optimization are generated. The network is trained on a fixed set of preferences. Towards the end of the training, we resample the set of preference vectors after every fixed number of iterations. This step improves the generalizability of the network.
PA-NET VS TSP-NET + LS
The base network used in PA-Net is TSP-Net. Here, we evaluate the effect of using linear scalrization in TSP-Net and compare it with PA-Net. For this, we train 40 separate networks of TSP-Net for different preferences. Just like PA-Net, each network of TSP-Net+LS is trained on a graph of size 120 × 4 with batch size 60 and total training iterations of 20000. We then compare Pareto fronts generated by TSP-Net+LS and PA-Net. It should be noted that preferences used for PA-Net are unit vectors. So for inference on PA-Net, normalized preferences of TSP-Net+LS is used. The results are reported in Table 5. It is clear that PA-Net significantly outperforms TSP-Net+LS both in terms of HV and training times. Prolonged training of TSP-Net+LS may improve its performance, but that would lead to greater training times.

heading: ABLATION STUDIES
text: In order to understand the contribution of different parts of PA-Net a few ablation studies were performed on 2− objective MOTSP instances. Description for various studies performed are as follows:
• Ablation 1: For this study, PA-Net is trained without the feed forward network of preference encoder.
• Ablation 2: In this study, PA-Net is trained with only a single deep layer of the preference encoder. In the baseline network, we use 4 deep layers,
• Ablation 3: For this study, PA-Net is trained without the transformer based encoder. A single 1-D convolution layer is used to encode the input graph.
All of these networks are compared on the basis of HV and the total time taken to generate the Pareto front for 2− objective MOTSP where 100 preference vectors are used at inference time. The comparative results for different ablation studies are summarized in Tab. 6. Further, the number of trainable network parameters for each network are given in Table 7. The network trained for
Ablation 1 has the worst performance. This indicates that encoder to learn representation of preferences plays a critical role in the performance of PA-Net. Interestingly enough, it seems like the choice of encoder for both preferences and the input TSP graph does not have much impact on the performance. This indicates that a relatively faster network can be obtained by using a relatively simpler choice of encoder. Although, the network in Ablation 3 has significantly lower number of trainable parameters, yet its training time is not significantly lower. This is primarily due to the fact that during the training, K ×B TSP tours are generated in all the networks. This serves as the computation bottleneck for the network during the training. Hence, that’s why no significant difference in training times are observed.

heading: HYPERPARAMETER TUNING
text: In order to obtain the best performing network, we trained networks with different values of some key hyperparameters. These hyperparameters are:
• Number of preference vectors (K). • Maximum value of lagrangian multipliers (λmax) • Ascent rate of the lagrangian multiplier (α)
These networks trained on different values of the above-mentioned hyperparameters are compared on the basis of obtained HV for 2-objective MOTSP where 100 preference vectors were used at the inference time. These results are presented in Tab. 8. The following conclusions can be made:
• Higher values of K leads to better results. Intuitively, it makes sense because a higher number of preference vectors during training can help network learn better and generalize better. However, large K leads to longer training time. For example, training time of network with K = 20 is ∼ 14hrs and for K = 5 its ∼ 6hrs.
• While varying λmax mixed results were observed. For the most part, parameters in the baseline network gave a better performance,
• For ascent rate (α) it was observed that for most of the instances, extremely high values or extremly low values lead to sub-par performance.

heading: ADDITIONAL EXPERIMENTAL RESULTS
text: Euclidean 3-objective MOTSP: PA-Net was evaluated on another 3-objective Euclidean MOTSP problem. In this case, all three objectives are L2-norms. The generated Pareto fronts for 200 and 500 City MOTSP are shown in Fig-5(a)-(b). It can be clearly seen that PA-Net is able to generate a good approximation Pareto frontier. The 3-D Pareto Front can be visualized at: https://sites. google.com/view/pareto-approximate-net/home.
Euclidean 2-objective MOTSP: Results of 2-objective MOTSP (see Sec-4) for 200 and 1000 cities is shown in Fig-5(c)-(d)
Application for Coverage Planning: This experiment represents a setup where a robot has to visit multiple locations in a building floor like a mall, airport etc (see Sec-4). The sequence of visiting these locations is dependent on the path length and adherence to a pre-computed priority. The visualization of three tours generated by PA-Net for this scenario is shown in Fig-6(b)-(d). The square section in the middle of the environment is given the highest priorities, and the rest of the depots are assigned priorities randomly. In each plot of the tour shown in Fig-6, the first 100 depots visited are marked in red. It can be seen that Tour C visits the middle section first and has the least priority violation. On the other hand, emphasis in Tour A is to minimize the total tour length.

Review summaries:
This work proposes a Pareto frontier approximation network (PA-Net) to learn the Pareto frontier for multi-objective traveling salesman problem (MOTSP). The proposed method first converts the MOTSP into a set of constrained single-objective optimization problems with different preference-based constraints. Then it builds a modified TSP-Net with preference augmentation to solve all the constrained problems. For a new MOTSP instance, the trained network can generate different approximate Pareto solutions by adjusting the preference. The experimental results show that the proposed PA-Net method has a good performance on MOTSP instances with different numbers of cities and objectives.  

The authors have presented a Pareto frontier approximation network (PA-Net) for multi-objective travelling salesman problem. The authors showcased that the PA-Net was able to generate good quality Pareto fronts with fast inference times as opposed to other learning methods such as The authors leveraged the generalization by using deep neural networks to solve the large values of number of preference vectors that are computationally hard and showcased that the formulation can find concave Pareto frontier too.   Contributions:   a. Computation time in training the models and generalizing for other instances   b. The proposed approximation methodology performs well in hyper volume and on the computation time. 

The paper introduces a method to approximate a Pareto front for multi-objective TSP from neural combinatorial optimization using deep reinforcement learning. The PA-Net method uses a constrained optimization problem formalization with a preference vector to control the solution generation. An experimental evaluation is performed and PA-Net is compared to multi-objective genetic algorithms and one DRL-based method from the literature. PA-Net performs competitive and approximates the Pareto front well.

 This paper studied an NN-based method to approximate the Pareto front (PF) for multi-objective optimization (MOO) problems. As a practical example of the MOO problem, the authors focused on the MO traveling salesman problem (MOTSP) and developed a new approximation method.  A critical problem discussed in the paper is how to efficiently and effectively approximate the PF. In contrast to an existing work (Li et al. 2020) that separately training networks for different preferences, meaning that the training process is time-consuming, the proposed approach using PA-Net uses a single network (i.e., an augmented version of the TSP-Net).  The targeting MOO problem is converted to constrained optimization problems (key: divide problems using constraints and preference vectors). The Lagrangians of constraints are used to train a policy in an actor-critic manner using solutions and preference vectors.  From the experimental results, the advantage of the proposed PA-Net is shown in terms of (1) training time, (2) HV, and (3) computational time (i.e., inference time). Some graphical illustrations are helpful to compare the PFs estimated by different methods. Roughly speaking, the performance of the PA-Net outperformed existing methods.