PA-Net

Pareto Frontier Approximation Network (PA-Net) Applied to Multi-objective TSP

Anonymous Author(s)

PA-Net

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 better quality Pareto fronts with fast inference times as compared to other learning based and classical methods. Finally, we present the application of PA-Net to find optimal visiting order in coverage planning.

[Github] TBD

3-D Visualization of Pareto front for 3 objective MOTSP

The visualisation of the Pareto frontier for 3-objective 500-City multi-objective TSP. It can be seen that classical algorithms, e.g. NSGA and MOEA, are unable to explore the objective space well. Our network, PA-3, is able to generate a superior quality of the Pareto frontier both in terms of optimality and diversity.

Demonstration of MOTSP for robotics

The above images represent various solutions generated by PA-Net for 500 city bi-objective MOTSP where the first objective is the total tour length and the second objective represents the violation of pre-assigned priority. This graph used in this example emulates a building floor with various depot s(or cities) that are to be visited by a robot. The square section in the middle is given the highest priorities, and the rest of the depots are assigned priorities randomly. In each plot of the tour shown above, 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.

Convergence to Concave Pareto Fronts

Unlike linear scalarization methods, our framework is capable of finding solutions for Multi objective optimization (MOO) problem with concave pareto fronts. Our method can find solutions for MOO with concave Pareto front for different preferences in objective space. The plot above is for the following problem

Page updated

Google Sites

Report abuse