AM-RRT*: Informed Sampling-based Planning with Assisting Metric
- URL: http://arxiv.org/abs/2010.14693v2
- Date: Thu, 9 Sep 2021 12:38:56 GMT
- Title: AM-RRT*: Informed Sampling-based Planning with Assisting Metric
- Authors: Daniel Armstrong and Andr\'e Jonasson
- Abstract summary: We present a new algorithm that extends RRT* and RT-RRT* for online path planning in complex, dynamic environments.
Our method extends RRT-based sampling methods to enable the use of an assisting distance metric to improve performance in environments with obstacles.
- Score: 3.42658286826597
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we present a new algorithm that extends RRT* and RT-RRT* for
online path planning in complex, dynamic environments. Sampling-based
approaches often perform poorly in environments with narrow passages, a feature
common to many indoor applications of mobile robots as well as computer games.
Our method extends RRT-based sampling methods to enable the use of an assisting
distance metric to improve performance in environments with obstacles. This
assisting metric, which can be any metric that has better properties than the
Euclidean metric when line of sight is blocked, is used in combination with the
standard Euclidean metric in such a way that the algorithm can reap benefits
from the assisting metric while maintaining the desirable properties of
previous RRT variants - namely probabilistic completeness in tree coverage and
asymptotic optimality in path length. We also introduce a new method of
targeted rewiring, aimed at shortening search times and path lengths in tasks
where the goal shifts repeatedly. We demonstrate that our method offers
considerable improvements over existing multi-query planners such as RT-RRT*
when using diffusion distance as an assisting metric; finding near-optimal
paths with a decrease in search time of several orders of magnitude.
Experimental results show planning times reduced by 99.5% and path lengths by
9.8% over existing real-time RRT planners in a variety of environments.
Related papers
- Finding Transformer Circuits with Edge Pruning [71.12127707678961]
We propose Edge Pruning as an effective and scalable solution to automated circuit discovery.
Our method finds circuits in GPT-2 that use less than half the number of edges compared to circuits found by previous methods.
Thanks to its efficiency, we scale Edge Pruning to CodeLlama-13B, a model over 100x the scale that prior methods operate on.
arXiv Detail & Related papers (2024-06-24T16:40:54Z) - SPARE: Symmetrized Point-to-Plane Distance for Robust Non-Rigid Registration [76.40993825836222]
We propose SPARE, a novel formulation that utilizes a symmetrized point-to-plane distance for robust non-rigid registration.
The proposed method greatly improves the accuracy of non-rigid registration problems and maintains relatively high solution efficiency.
arXiv Detail & Related papers (2024-05-30T15:55:04Z) - Learning Radio Environments by Differentiable Ray Tracing [56.40113938833999]
We introduce a novel gradient-based calibration method, complemented by differentiable parametrizations of material properties, scattering and antenna patterns.
We have validated our method using both synthetic data and real-world indoor channel measurements, employing a distributed multiple-input multiple-output (MIMO) channel sounder.
arXiv Detail & Related papers (2023-11-30T13:50:21Z) - Vertex-based Networks to Accelerate Path Planning Algorithms [3.684936338492373]
We propose the utilization of vertices-based networks to enhance the sampling process of RRT*, leading to more efficient path planning.
We employ focal loss to address the associated data imbalance issue, and explore different masking configurations to determine practical tradeoffs in system performance.
arXiv Detail & Related papers (2023-07-13T20:56:46Z) - Maximize to Explore: One Objective Function Fusing Estimation, Planning,
and Exploration [87.53543137162488]
We propose an easy-to-implement online reinforcement learning (online RL) framework called textttMEX.
textttMEX integrates estimation and planning components while balancing exploration exploitation automatically.
It can outperform baselines by a stable margin in various MuJoCo environments with sparse rewards.
arXiv Detail & Related papers (2023-05-29T17:25:26Z) - CBAGAN-RRT: Convolutional Block Attention Generative Adversarial Network
for Sampling-Based Path Planning [0.0]
We propose a novel image-based learning algorithm (CBAGAN-RRT) using a Convolutional Block Attention Generative Adversarial Network.
The probability distribution of the paths generated from our GAN model is used to guide the sampling process for the RRT algorithm.
We train and test our network on the dataset generated by citezhang 2021 and demonstrate that our algorithm outperforms the previous state-of-the-art algorithms.
arXiv Detail & Related papers (2023-05-13T20:06:53Z) - Reinforcement Learning for Branch-and-Bound Optimisation using
Retrospective Trajectories [72.15369769265398]
Machine learning has emerged as a promising paradigm for branching.
We propose retro branching; a simple yet effective approach to RL for branching.
We outperform the current state-of-the-art RL branching algorithm by 3-5x and come within 20% of the best IL method's performance on MILPs with 500 constraints and 1000 variables.
arXiv Detail & Related papers (2022-05-28T06:08:07Z) - Learning Space Partitions for Path Planning [54.475949279050596]
PlaLaM outperforms existing path planning methods in 2D navigation tasks, especially in the presence of difficult-to-escape local optima.
These gains transfer to highly multimodal real-world tasks, where we outperform strong baselines in compiler phase ordering by up to 245% and in molecular design by up to 0.4 on properties on a 0-1 scale.
arXiv Detail & Related papers (2021-06-19T18:06:11Z) - Stagnation Detection in Highly Multimodal Fitness Landscapes [0.0]
Stagnation detection has been proposed as a mechanism for randomized searchs to escape from local optima.
In this paper, we investigate a new mechanism called radius memory which can be added to stagnation detection to control the search radius more carefully.
We implement this idea in an algorithm called SD-RLS$textm$ and show compared to previous variants of stagnation detection that it yields speed-ups.
arXiv Detail & Related papers (2021-04-09T14:33:52Z) - Conditional Generative Adversarial Networks for Optimal Path Planning [30.892250698479064]
We propose a novel learning-based path planning algorithm based on the conditional generative adversarial networks (CGAN) and a modified RRT* algorithm (denoted by CGANRRT*)
The CGAN model is trained by learning from ground truth maps, each of which is generated by putting all the results of executing RRT algorithm 50 times on one raw map.
We demonstrate the efficient performance of this CGAN model by testing it on two groups of maps and comparing CGAN-RRT* algorithm with conventional RRT* algorithm.
arXiv Detail & Related papers (2020-12-06T02:53:50Z) - Autonomous UAV Exploration of Dynamic Environments via Incremental
Sampling and Probabilistic Roadmap [0.3867363075280543]
We propose a novel dynamic exploration planner (DEP) for exploring unknown environments using incremental sampling and Probabilistic Roadmap (PRM)
Our method safely explores dynamic environments and outperforms the benchmark planners in terms of exploration time, path length, and computational time.
arXiv Detail & Related papers (2020-10-14T22:52:37Z)
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.