Multi-Resolution A*
- URL: http://arxiv.org/abs/2004.06684v1
- Date: Tue, 14 Apr 2020 17:38:11 GMT
- Title: Multi-Resolution A*
- Authors: Wei Du, Fahad Islam and Maxim Likhachev
- Abstract summary: 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.
- Score: 19.562565022582785
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Heuristic search-based planning techniques are commonly used for motion
planning on discretized spaces. The performance of these algorithms is heavily
affected by the resolution at which the search space is discretized. Typically
a fixed resolution is chosen for a given domain. While a finer resolution
allows for better maneuverability, it significantly increases the size of the
state space, and hence demands more search efforts. On the contrary, a coarser
resolution gives a fast exploratory behavior but compromises on maneuverability
and the completeness of the search. To effectively leverage the advantages of
both high and low resolution discretizations, we propose Multi-Resolution A*
(MRA*) algorithm, that runs multiple weighted-A*(WA*) searches having different
resolution levels simultaneously and combines the strengths of all of them. In
addition to these searches, MRA* uses one anchor search to control expansions
from these searches. We show that MRA* is bounded suboptimal with respect to
the anchor resolution search space and resolution complete. We performed
experiments on several motion planning domains including 2D, 3D grid planning
and 7 DOF manipulation planning and compared our approach with several
search-based and sampling-based baselines.
Related papers
- Hybrid Search for Efficient Planning with Completeness Guarantees [63.02803974708516]
We propose an efficient approach to augment a subgoal search method to achieve completeness in discrete action spaces.
This solution achieves the best of both worlds: the practical efficiency of high-level search and the completeness of low-level search.
arXiv Detail & Related papers (2023-10-19T15:16:43Z) - A Multi-Heuristic Search-based Motion Planning for Automated Parking [0.0]
In unstructured environments like parking lots or construction sites, it is challenging to achieve real-time planning.
We are adopting a Multi-Heuristic Search approach, that enables the use of multiple functions and their individual advantages.
The Multi-Heuristic A* algorithm is benchmarked against a very popular search-based algorithm, Hybrid A*.
arXiv Detail & Related papers (2023-07-15T17:33:06Z) - Searching a High-Performance Feature Extractor for Text Recognition
Network [92.12492627169108]
We design a domain-specific search space by exploring principles for having good feature extractors.
As the space is huge and complexly structured, no existing NAS algorithms can be applied.
We propose a two-stage algorithm to effectively search in the space.
arXiv Detail & Related papers (2022-09-27T03:49:04Z) - 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) - 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) - AMRA*: Anytime Multi-Resolution Multi-Heuristic A* [21.927948636840682]
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.
arXiv Detail & Related papers (2021-10-11T14:51:29Z) - Selection-Expansion: A Unifying Framework for Motion-Planning and
Diversity Search Algorithms [69.87173070473717]
We investigate the properties of two diversity search algorithms, the Novelty Search and the Goal Exploration Process algorithms.
The relation to MP algorithms reveals that the smoothness, or lack of smoothness of the mapping between the policy parameter space and the outcome space plays a key role in the search efficiency.
arXiv Detail & Related papers (2021-04-10T13:52:27Z) - MRDet: A Multi-Head Network for Accurate Oriented Object Detection in
Aerial Images [51.227489316673484]
We propose an arbitrary-oriented region proposal network (AO-RPN) to generate oriented proposals transformed from horizontal anchors.
To obtain accurate bounding boxes, we decouple the detection task into multiple subtasks and propose a multi-head network.
Each head is specially designed to learn the features optimal for the corresponding task, which allows our network to detect objects accurately.
arXiv Detail & Related papers (2020-12-24T06:36:48Z) - 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) - Multi-Resolution POMDP Planning for Multi-Object Search in 3D [26.683481431467783]
We present a POMDP formulation for multi-object search in a 3D region with a frustum-shaped field-of-view.
We design a novel octree-based belief representation to capture uncertainty of the target objects at different resolution levels.
We demonstrate our approach on a mobile robot to find objects placed at different heights in two 10m$2 times 2$m regions by moving its base and actuating its torso.
arXiv Detail & Related papers (2020-05-06T14:54:01Z)
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.