Enhanced Multi-Objective A* Using Balanced Binary Search Trees

• URL: http://arxiv.org/abs/2202.08992v1
• Date: Fri, 18 Feb 2022 02:54:58 GMT
• Title: Enhanced Multi-Objective A* Using Balanced Binary Search Trees
• Authors: Zhongqiang Ren, Sivakumar Rathinam, Maxim Likhachev and Howie Choset
• Abstract summary: 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.
• Score: 35.63053398687847
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work addresses the Multi-Objective Shortest Path Problem (MO-SPP): Given a graph where each edge is associated with a non-negative cost vector, MO-SPP aims to find all the Pareto-optimal paths connecting the given start and goal nodes. To solve MO-SPP, the popular 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. The computational efficiency of MOA* algorithms directly depend on how efficiently one can maintain the frontier sets. Recently, several techniques have been developed in the literature to address this issue mainly for two objectives. In this work, we introduce a new method to efficiently maintain these frontiers for multiple objectives by leveraging balanced binary search trees. We provide extensive simulation results for problems with three, four and five objectives to show that our method outperforms existing techniques by an order of magnitude in general.

Related papers

• 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)
• MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem [5.580214316179672]
  The MG-MAPF problem requires each agent to visit pre-assigned multiple goal points at least once without conflict. We propose the Multi-Goal Conflict-Based Search (MGCBS), which is based on Decoupling the goal Safe interval visiting order search and the Single-agent pathfinding. Our method can consistently obtain optimal results and execute up to 7 times faster than the state-of-the-art method in our evaluation.
  arXiv  Detail & Related papers  (2024-04-30T12:49:54Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  We introduce an original variant of Monte-Carlo Tree Search (MCTS) tailored to multi-agent pathfinding. Specifically, we use individual paths to assist the agents with the the goal-reaching behavior. We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure.
  arXiv  Detail & Related papers  (2023-07-25T12:33:53Z)
• SparseTrack: Multi-Object Tracking by Performing Scene Decomposition based on Pseudo-Depth [84.64121608109087]
  We propose a pseudo-depth estimation method for obtaining the relative depth of targets from 2D images. Secondly, we design a depth cascading matching (DCM) algorithm, which can use the obtained depth information to convert a dense target set into multiple sparse target subsets. By integrating the pseudo-depth method and the DCM strategy into the data association process, we propose a new tracker, called SparseTrack.
  arXiv  Detail & Related papers  (2023-06-08T14:36:10Z)
• Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids [0.190365714903665]
  We show that 2-colored MAPF, where the agents are divided into two teams, each with its own set of targets, remains NP-hard. For the flowtime objective, we establish a tractability frontier based on the number of directions agents can move in. This result sheds new light on the structure of optimal solutions, which may help guide algorithm design for the general problem.
  arXiv  Detail & Related papers  (2023-05-25T17:56:24Z)
• Enhanced Multi-Objective A* with Partial Expansion [22.45142249108214]
  Multi-Objective Shortest Path Problem (MO-SPP), typically posed on a graph, determines a set of paths while optimizing multiple objectives. To address this problem, several Multi-Objective A* (MOA*) algorithms were recently developed to quickly compute solutions with quality guarantees. This work thus aims at reducing the high memory consumption of MOA* with little increase in the runtime.
  arXiv  Detail & Related papers  (2022-12-06T05:48:11Z)
• Multi-Robot Active Mapping via Neural Bipartite Graph Matching [49.72892929603187]
  We study the problem of multi-robot active mapping, which aims for complete scene map construction in minimum time steps. The key to this problem lies in the goal position estimation to enable more efficient robot movements. We propose a novel algorithm, namely NeuralCoMapping, which takes advantage of both approaches.
  arXiv  Detail & Related papers  (2022-03-30T14:03:17Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• S$^*$: A Heuristic Information-Based Approximation Framework for Multi-Goal Path Finding [0.0]
  We develop a novel framework for a Multi-Goal Path Finding (MGPF) problem that provides a 2-approximation guarantee. MGPF aims to find a least-cost path from an origin to a destination such that each node in a given set of goals is visited at least once along the path. We present numerical results to illustrate the advantages of our framework over conventional alternates in terms of the number of expanded nodes and run time.
  arXiv  Detail & Related papers  (2021-03-15T06:27:37Z)
• Subdimensional Expansion for Multi-objective Multi-agent Path Finding [10.354181009277623]
  Multi-agent path planners typically determine a path that optimize a single objective, such as path length. Many applications, however, may require multiple objectives, say time-to-completion and fuel use, to be simultaneously optimized in the planning process. This paper presents an approach that bypasses this so-called curse of dimensionality by leveraging our prior multi-agent work with a framework called subdimensional expansion.
  arXiv  Detail & Related papers  (2021-02-02T06:58:28Z)

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.