Bi-objective Search with Bi-directional A*

• URL: http://arxiv.org/abs/2105.11888v1
• Date: Tue, 25 May 2021 12:46:25 GMT
• Title: Bi-objective Search with Bi-directional A*
• Authors: Saman Ahmadi, Guido Tack, Daniel Harabor, Philip Kilby
• Abstract summary: Bi-objective A*-based search (BOA*) has shown state-of-the-art performance in large networks. This paper develops a bi-directional variant of BOA*, enriched with several speed-ups. Our experimental results on 1,000 benchmark cases show that our bi-directional A* algorithm for bi-objective search (BOBA*) can optimally solve all of the benchmark cases within the time limit.
• Score: 8.140473195463905
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bi-objective search is a well-known algorithmic problem, concerned with finding a set of optimal solutions in a two-dimensional domain. This problem has a wide variety of applications such as planning in transport systems or optimal control in energy systems. Recently, bi-objective A*-based search (BOA*) has shown state-of-the-art performance in large networks. This paper develops a bi-directional variant of BOA*, enriched with several speed-up heuristics. Our experimental results on 1,000 benchmark cases show that our bi-directional A* algorithm for bi-objective search (BOBA*) can optimally solve all of the benchmark cases within the time limit, outperforming the state of the art BOA*, bi-objective Dijkstra and bi-directional bi-objective Dijkstra by an average runtime improvement of a factor of five over all of the benchmark instances.

Related papers

• Bidirectional Bounded-Suboptimal Heuristic Search with Consistent Heuristics [7.049213272184215]
  This paper focuses on bounded-suboptimal bidirectional search, where a bound on the suboptimality of the solution cost is specified.<n>We build upon the state-of-the-art optimal bidirectional search algorithm, BAE*, and introduce several variants of BAE* specifically tailored for the bounded-suboptimal context.
  arXiv  Detail & Related papers  (2025-11-13T12:56:35Z)
• A Preprocessing Framework for Efficient Approximate Bi-Objective Shortest-Path Computation in the Presence of Correlated Objectives [21.108406629056173]
  We consider the bi-objective shortest-path (BOSP) problem in the presence of correlated objectives.<n>BOSP is generally computationally challenging as the size of the search space is exponential in the number of objective functions and the graph size.<n>We propose an efficient algorithm that reduces the search effort in the presence of correlated objectives.
  arXiv  Detail & Related papers  (2025-05-28T11:26:14Z)
• Parallelizing Multi-objective A* Search [20.505862615134674]
  The Multi-objective Shortest Path (MOSP) problem is a classic network optimization problem. 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.
  arXiv  Detail & Related papers  (2025-03-13T05:43:49Z)
• On Parallel External-Memory Bidirectional Search [16.87919636127611]
  This paper presents a framework that integrates uni- and bi-directional best-first search algorithms. We then develop a PEM variant of the state-of-the-art bidirectional search (BiHS) algorithm BAE* (PEM-BAE*) Empirical evaluation shows that PEM-BAE* outperforms the PEM variants of A* and the MM algorithm, as well as a parallel variant of IDA*.
  arXiv  Detail & Related papers  (2024-12-30T17:29:51Z)
• Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
  Quality-Diversity (QD) algorithms aim to find a set of high-performing, yet diverse solutions. This paper tries to shed some light on the optimization ability of QD algorithms via rigorous running time analysis.
  arXiv  Detail & Related papers  (2024-01-19T07:40:24Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  We present the first efficient scalable and general framework that can directly search on the tasks of interest. Inspired by the innate tree structure of the underlying math expressions, we re-arrange the spaces into a super-tree. We adopt an adaptation of the Monte Carlo method to tree search, equipped with rejection sampling and equivalent- form detection.
  arXiv  Detail & Related papers  (2022-09-27T17:51:31Z)
• ARES: An Efficient Algorithm with Recurrent Evaluation and Sampling-Driven Inference for Maximum Independent Set [48.57120672468062]
  This paper introduces an efficient algorithm for the Maximum Independent Set (MIS) problem, incorporating two innovative techniques. The proposed algorithm outperforms state-of-the-art algorithms in terms of solution quality, computational efficiency, and stability.
  arXiv  Detail & Related papers  (2022-08-16T14:39:38Z)
• Enhanced Multi-Objective A* Using Balanced Binary Search Trees [35.63053398687847]
  Multi-objective A* (MOA*) like algorithms maintain a "frontier" set at any node during the search to keep track of the non-dominated paths that reach that node. We introduce a new method to efficiently maintain these frontiers for multiple objectives by leveraging balanced binary search trees.
  arXiv  Detail & Related papers  (2022-02-18T02:54:58Z)
• B2EA: An Evolutionary Algorithm Assisted by Two Bayesian Optimization Modules for Neural Architecture Search [3.126118485851773]
  We develop Btextsuperscript2EA that is a surrogate assisted EA with two BO surrogate models and a mutation step in between. Btextsuperscript2EA is robust and efficient over the 14 benchmarks for three difficulty levels of target performance.
  arXiv  Detail & Related papers  (2022-02-07T08:50:21Z)
• Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
  Multipartite entity resolution aims at integrating records from multiple datasets into one entity. We apply two procedures, a Greedy algorithm and a large scale neighborhood search, to solve the assignment problem. We find evidence that design-based multi-start can be more efficient as the size of databases grow large.
  arXiv  Detail & Related papers  (2021-12-06T20:34:55Z)
• A survey on multi-objective hyperparameter optimization algorithms for Machine Learning [62.997667081978825]
  This article presents a systematic survey of the literature published between 2014 and 2020 on multi-objective HPO algorithms. We distinguish between metaheuristic-based algorithms, metamodel-based algorithms, and approaches using a mixture of both. We also discuss the quality metrics used to compare multi-objective HPO procedures and present future research directions.
  arXiv  Detail & Related papers  (2021-11-23T10:22:30Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  We propose to reformulate the result diversification problem as a bi-objective search problem, and solve it by a multi-objective evolutionary algorithm (EA) We theoretically prove that the GSEMO can achieve the optimal-time approximation ratio, $1/2$. When the objective function changes dynamically, the GSEMO can maintain this approximation ratio in running time, addressing the open question proposed by Borodin et al.
  arXiv  Detail & Related papers  (2021-10-18T14:00:22Z)
• ES-Based Jacobian Enables Faster Bilevel Optimization [53.675623215542515]
  Bilevel optimization (BO) has arisen as a powerful tool for solving many modern machine learning problems. Existing gradient-based methods require second-order derivative approximations via Jacobian- or/and Hessian-vector computations. We propose a novel BO algorithm, which adopts Evolution Strategies (ES) based method to approximate the response Jacobian matrix in the hypergradient of BO.
  arXiv  Detail & Related papers  (2021-10-13T19:36:50Z)
• A binary variant of gravitational search algorithm and its application to windfarm layout optimization problem [0.7734726150561088]
  A novel binary variant of GSA called A novel neighbourhood archives embedded gravitational constant in GSA for binary search space (BNAGGSA)' is proposed in this paper. The proposed algorithm produces a self-adaptive step size mechanism through which the agent moves towards the optimal direction with the optimal step size. To check the applicability of the proposed algorithm in solving real-world applications, a windfarm layout optimization problem is considered.
  arXiv  Detail & Related papers  (2021-07-25T16:56:19Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers. We propose a class of non-adaptive ranking algorithms that rely on a least-squares intrinsic optimization criterion for the estimation of qualities.
  arXiv  Detail & Related papers  (2020-02-26T16:19:09Z)
• Multi-objective beetle antennae search algorithm [4.847470451539327]
  The proposed multi-objective beetle antennae search algorithm is tested using four well-selected benchmark functions. The results show that the proposed multi-objective beetle antennae search algorithm has higher computational efficiency with satisfactory accuracy.
  arXiv  Detail & Related papers  (2020-02-24T06:34:32Z)

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.