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

• URL: http://arxiv.org/abs/2203.01298v2
• Date: Thu, 3 Mar 2022 15:24:31 GMT
• Title: Pareto Frontier Approximation Network (PA-Net) to Solve Bi-objective TSP
• Authors: Ishaan Mehta and Sajad Saeedi
• Abstract summary: Travelling salesperson problem (TSP) is a classic resource allocation problem used to find an optimal order of doing a set of tasks. We present PA-Net, a network that generates good approximations of the Pareto front for the bi-objective travelling salesperson problem. We also present the application of PA-Net to find optimal visiting order in a robotic navigation task/coverage planning.
• Score: 1.4884785898657995
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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, scheduling etc. In this work, we solve TSP for two objectives using reinforcement learning. 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 own trade off. In this work, we present 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 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 a robotic navigation task/coverage planning.

Related papers

• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  Sequentially solving similar optimization problems under strict runtime constraints is essential for many applications. We propose learning to predict emphmultiple diverse initial solutions given parameters that define the problem instance. We find significant and consistent improvement with our method across all evaluation settings and demonstrate that it efficiently scales with the number of initial solutions required.
  arXiv  Detail & Related papers  (2024-11-04T15:17:19Z)
• Preference-Optimized Pareto Set Learning for Blackbox Optimization [1.9628841617148691]
  No single solution exists that can optimize all the objectives simultaneously. In a typical MOO problem, the goal is to find a set of optimum solutions (Pareto set) that trades off the preferences among objectives. Our formulation leads to a bilevel optimization problem that can be solved by e.g. differentiable cross-entropy methods.
  arXiv  Detail & Related papers  (2024-08-19T13:23:07Z)
• Towards Efficient Pareto Set Approximation via Mixture of Experts Based Model Fusion [53.33473557562837]
  Solving multi-objective optimization problems for large deep neural networks is a challenging task due to the complexity of the loss landscape and the expensive computational cost. We propose a practical and scalable approach to solve this problem via mixture of experts (MoE) based model fusion. By ensembling the weights of specialized single-task models, the MoE module can effectively capture the trade-offs between multiple objectives.
  arXiv  Detail & Related papers  (2024-06-14T07:16:18Z)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
  In Multi-objective Reinforcement Learning (MORL) agents are tasked with optimising decision-making behaviours. We focus on the case of linear utility functions parameterised by weight vectors w. We introduce a method based on Upper Confidence Bound to efficiently search for the most promising weight vectors during different stages of the learning process.
  arXiv  Detail & Related papers  (2024-05-01T09:34:42Z)
• Deep Reinforcement Learning for Traveling Purchaser Problems [63.37136587778153]
  The traveling purchaser problem (TPP) is an important optimization problem with broad applications. We propose a novel approach based on deep reinforcement learning (DRL), which addresses route construction and purchase planning separately. By introducing a meta-learning strategy, the policy network can be trained stably on large-sized TPP instances.
  arXiv  Detail & Related papers  (2024-04-03T05:32:10Z)
• MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with Known Pareto Front [71.19090689055054]
  Multi-objective AI planning suffers from a lack of benchmarks exhibiting known Pareto Fronts. We propose a tunable benchmark generator, together with a dedicated solver that provably computes the true Pareto front of the resulting instances. We show how to characterize the optimal plans for a constrained version of the problem, and then show how to reduce the general problem to the constrained one.
  arXiv  Detail & Related papers  (2023-04-28T07:09:23Z)
• Pareto Manifold Learning: Tackling multiple tasks via ensembles of single-task models [50.33956216274694]
  In Multi-Task Learning (MTL), tasks may compete and limit the performance achieved on each other, rather than guiding the optimization to a solution. We propose textitPareto Manifold Learning, an ensembling method in weight space.
  arXiv  Detail & Related papers  (2022-10-18T11:20:54Z)
• Pareto Conditioned Networks [1.7188280334580197]
  We propose a method that uses a single neural network to encompass all non-dominated policies. PCN associates every past transition with its episode's return and trains the network such that, when conditioned on this same return, it should reenact said transition. Our method is stable as it learns in a supervised fashion, thus avoiding moving target issues.
  arXiv  Detail & Related papers  (2022-04-11T12:09:51Z)
• Pareto Navigation Gradient Descent: a First-Order Algorithm for Optimization in Pareto Set [17.617944390196286]
  Modern machine learning applications, such as multi-task learning, require finding optimal model parameters to trade-off multiple objective functions. We propose a first-order algorithm that approximately solves OPT-in-Pareto using only gradient information.
  arXiv  Detail & Related papers  (2021-10-17T04:07:04Z)
• Efficient Multi-Objective Optimization for Deep Learning [2.0305676256390934]
  Multi-objective optimization (MOO) is a prevalent challenge for Deep Learning. There exists no scalable MOO solution for truly deep neural networks.
  arXiv  Detail & Related papers  (2021-03-24T17:59:42Z)
• A Hybrid 2-stage Neural Optimization for Pareto Front Extraction [3.918940900258555]
  A major obstacle to optimal trade-off solutions is that they don't always converge to each other. We propose a two-stage approach that is accurate and cost-effective.
  arXiv  Detail & Related papers  (2021-01-27T20:56:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.