AMRA*: Anytime Multi-Resolution Multi-Heuristic A*

• URL: http://arxiv.org/abs/2110.05328v2
• Date: Thu, 23 Mar 2023 15:36:39 GMT
• Title: AMRA*: Anytime Multi-Resolution Multi-Heuristic A*
• Authors: Dhruv Mauria Saxena, Tushar Kusnur, Maxim Likhachev
• Abstract summary: Multi-Resolution A* (MRA*) searches over multiple resolutions. AMRA* tries to find a solution quickly using the coarse resolution as much as possible. It then refines the solution by relying on the fine resolution to discover better paths that may not have been available at the coarse resolution.
• Score: 21.927948636840682
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Heuristic search-based motion planning algorithms typically discretise the search space in order to solve the shortest path problem. Their performance is closely related to this discretisation. A fine discretisation allows for better approximations of the continuous search space, but makes the search for a solution more computationally costly. A coarser resolution might allow the algorithms to find solutions quickly at the expense of quality. For large state spaces, it can be beneficial to search for solutions across multiple resolutions even though defining the discretisations is challenging. The recently proposed algorithm Multi-Resolution A* (MRA*) searches over multiple resolutions. It traverses large areas of obstacle-free space and escapes local minima at a coarse resolution. It can also navigate so-called narrow passageways at a finer resolution. In this work, we develop AMRA*, an anytime version of MRA*. AMRA* tries to find a solution quickly using the coarse resolution as much as possible. It then refines the solution by relying on the fine resolution to discover better paths that may not have been available at the coarse resolution. In addition to being anytime, AMRA* can also leverage information sharing between multiple heuristics. We prove that AMRA* is complete and optimal (in-the-limit of time) with respect to the finest resolution. We show its performance on 2D grid navigation and 4D kinodynamic planning problems.

Related papers

• Space Net Optimization [1.0323063834827415]
  Most metaheuristic algorithms rely on a few searched solutions to guide later searches during the convergence process. We present a novel metaheuristic algorithm called space net optimization (SNO) It is equipped with a new mechanism called space net; thus, making it possible for a metaheuristic algorithm to use most information provided by all searched solutions to depict the landscape of the solution space.
  arXiv  Detail & Related papers  (2023-05-31T15:44:18Z)
• 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)
• Efficient Joint-Dimensional Search with Solution Space Regularization for Real-Time Semantic Segmentation [27.94898516315886]
  We search an optimal network structure that can run in real-time for this problem. A novel Solution Space Regularization (SSR) loss is first proposed to effectively encourage the supernet to converge to its discrete one. A new Hierarchical and Progressive Solution Space Shrinking method is presented to further achieve high efficiency of searching.
  arXiv  Detail & Related papers  (2022-08-10T11:07:33Z)
• Learning Resolution-Adaptive Representations for Cross-Resolution Person Re-Identification [49.57112924976762]
  Cross-resolution person re-identification problem aims to match low-resolution (LR) query identity images against high resolution (HR) gallery images. It is a challenging and practical problem since the query images often suffer from resolution degradation due to the different capturing conditions from real-world cameras. This paper explores an alternative SR-free paradigm to directly compare HR and LR images via a dynamic metric, which is adaptive to the resolution of a query image.
  arXiv  Detail & Related papers  (2022-07-09T03:49:51Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
  Minimax problems extend beyond the continuous domain to mixed continuous-discrete domains or even fully discrete domains. We introduce the class of convex-submodular minimax problems, where the objective is convex with respect to the continuous variable and submodular with respect to the discrete variable. Our proposed algorithms are iterative and combine tools from both discrete and continuous optimization.
  arXiv  Detail & Related papers  (2021-11-01T21:06:35Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Scale-Localized Abstract Reasoning [79.00011351374869]
  We consider the abstract relational reasoning task, which is commonly used as an intelligence test. Since some patterns have spatial rationales, while others are only semantic, we propose a multi-scale architecture that processes each query in multiple resolutions. We show that indeed different rules are solved by different resolutions and a combined multi-scale approach outperforms the existing state of the art in this task on all benchmarks by 5-54%.
  arXiv  Detail & Related papers  (2020-09-20T10:37:29Z)
• Learning What to Defer for Maximum Independent Sets [84.00112106334655]
  We propose a novel DRL scheme, coined learning what to defer (LwD), where the agent adaptively shrinks or stretch the number of stages by learning to distribute the element-wise decisions of the solution at each stage. We apply the proposed framework to the maximum independent set (MIS) problem, and demonstrate its significant improvement over the current state-of-the-art DRL scheme.
  arXiv  Detail & Related papers  (2020-06-17T02:19:31Z)
• Multi-Resolution A* [19.562565022582785]
  Heuristic search-based planning techniques are commonly used for motion planning on discretized spaces. We propose Multi-Resolution A* algorithm, that runs multiple weighted-A*(WA*) searches having different resolution levels simultaneously. We show that MRA* is bounded suboptimal with respect to the anchor resolution search space and resolution complete.
  arXiv  Detail & Related papers  (2020-04-14T17:38:11Z)
• sKPNSGA-II: Knee point based MOEA with self-adaptive angle for Mission Planning Problems [2.191505742658975]
  Some problems have many objectives which lead to a large number of non-dominated solutions. This paper presents a new algorithm that has been designed to obtain the most significant solutions. This new algorithm has been applied to the real world application in Unmanned Air Vehicle (UAV) Mission Planning Problem.
  arXiv  Detail & Related papers  (2020-02-20T17:07:08Z)

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.