Parallelizing Multi-objective A* Search

• URL: http://arxiv.org/abs/2503.10075v1
• Date: Thu, 13 Mar 2025 05:43:49 GMT
• Title: Parallelizing Multi-objective A* Search
• Authors: Saman Ahmadi, Nathan R. Sturtevant, Andrea Raith, Daniel Harabor, Mahdi Jalili,
• Abstract summary: The Multi-objective Shortest Path (MOSP) problem is a classic network optimization problem.<n>Recent studies on multi-objective search with A* (MOA*) have demonstrated superior performance in solving difficult MOSP instances.<n>This paper presents a novel search framework that allows efficient parallelization of MOA* with different objective orders.
• Score: 20.505862615134674
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Multi-objective Shortest Path (MOSP) problem is a classic network optimization problem that aims to find all Pareto-optimal paths between two points in a graph with multiple edge costs. Recent studies on multi-objective search with A* (MOA*) have demonstrated superior performance in solving difficult MOSP instances. This paper presents a novel search framework that allows efficient parallelization of MOA* with different objective orders. The framework incorporates a unique upper bounding strategy that helps the search reduce the problem's dimensionality to one in certain cases. Experimental results demonstrate that the proposed framework can enhance the performance of recent A*-based solutions, with the speed-up proportional to the problem dimension.

Related papers

• Dynamic Parallel Tree Search for Efficient LLM Reasoning [102.16694475391665]
  Tree of Thoughts (ToT) enhances Large Language Model (LLM) reasoning by structuring problem-solving as a spanning tree. We propose Dynamic Parallel Tree Search (DPTS), a novel parallelism framework that aims to dynamically optimize the reasoning path in inference. Experiments on Qwen-2.5 and Llama-3 with Math500 and GSM8K datasets show that DPTS significantly improves efficiency by 2-4x on average.
  arXiv  Detail & Related papers  (2025-02-22T14:13:37Z)
• OPMOS: Ordered Parallel Multi-Objective Shortest-Path [0.7864304771129751]
  The Multi-Objective Shortest-Path (MOS) problem finds a set of Pareto-optimal solutions from a start node to a destination node in a multi-attribute graph. A generalized MOS algorithm maintains a "frontier" of partial paths at each node and performs ordered processing. The OPMOS framework, proposed herein, unlocks ordered parallelism and efficiently exploits the concurrent execution of multiple paths in MOS.
  arXiv  Detail & Related papers  (2024-11-25T18:53:49Z)
• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  The framework combines Monte Carlo Tree Search (MCTS) with iterative Self-Refine to optimize the reasoning path. The framework has been tested on general and advanced benchmarks, showing superior performance in terms of search efficiency and problem-solving capability.
  arXiv  Detail & Related papers  (2024-10-03T18:12:29Z)
• 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)
• Real-Time Image Segmentation via Hybrid Convolutional-Transformer Architecture Search [51.89707241449435]
  In this paper, we address the challenge of integrating multi-head self-attention into high-resolution representation CNNs efficiently. We develop a multi-target multi-branch supernet method, which fully utilizes the advantages of high-resolution features. We present a series of models via the Hybrid Convolutional-Transformer Architecture Search (HyCTAS) method that searches for the best hybrid combination of light-weight convolution layers and memory-efficient self-attention layers.
  arXiv  Detail & Related papers  (2024-03-15T15:47:54Z)
• MOLE: Digging Tunnels Through Multimodal Multi-Objective Landscapes [0.0]
  Locally efficient (LE) sets, often considered as traps for local search, are rarely isolated in the decision space. The Multi-Objective Gradient Sliding Algorithm (MOGSA) is an algorithmic concept developed to exploit these superpositions. We propose a new algorithm, the Multi-Objective Landscape Explorer (MOLE), which is able to efficiently model and exploit LE sets in MMMOO problems.
  arXiv  Detail & Related papers  (2022-04-22T17:54:54Z)
• Pareto Set Learning for Neural Multi-objective Combinatorial Optimization [6.091096843566857]
  Multiobjective optimization (MOCO) problems can be found in many real-world applications. We develop a learning-based approach to approximate the whole Pareto set for a given MOCO problem without further search procedure. Our proposed method significantly outperforms some other methods on the multiobjective traveling salesman problem, multiconditioned vehicle routing problem and multi knapsack problem in terms of solution quality, speed, and model efficiency.
  arXiv  Detail & Related papers  (2022-03-29T09:26:22Z)
• Multi-objective Conflict-based Search for Multi-agent Path Finding [10.354181009277623]
  Multi-objective path planners typically compute an ensemble of paths while optimizing a single objective, such as path length. This article presents an approach named Multi-objective Conflict-based Search (MO-CBS) that bypasses this so-called curse of dimensionality.
  arXiv  Detail & Related papers  (2021-01-11T10:42:38Z)
• Follow the bisector: a simple method for multi-objective optimization [65.83318707752385]
  We consider optimization problems, where multiple differentiable losses have to be minimized. The presented method computes descent direction in every iteration to guarantee equal relative decrease of objective functions.
  arXiv  Detail & Related papers  (2020-07-14T09:50:33Z)
• Decomposition in Decision and Objective Space for Multi-Modal Multi-Objective Optimization [15.681236469530397]
  Multi-modal multi-objective optimization problems (MMMOPs) have multiple subsets within the Pareto-optimal Set. Prevalent multi-objective evolutionary algorithms are not purely designed to search for multiple solution subsets, whereas, algorithms designed for MMMOPs demonstrate degraded performance in the objective space. This motivates the design of better algorithms for addressing MMMOPs.
  arXiv  Detail & Related papers  (2020-06-04T03:18:47Z)
• Pareto Multi-Task Learning [53.90732663046125]
  Multi-task learning is a powerful method for solving multiple correlated tasks simultaneously. It is often impossible to find one single solution to optimize all the tasks, since different tasks might conflict with each other. Recently, a novel method is proposed to find one single Pareto optimal solution with good trade-off among different tasks by casting multi-task learning as multiobjective optimization.
  arXiv  Detail & Related papers  (2019-12-30T08:58:40Z)

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.