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
- Zonal RL-RRT: Integrated RL-RRT Path Planning with Collision Probability and Zone Connectivity [11.134855513221359]
We introduce a novel path-planning algorithm, Zonal RL-RRT, that leverages kd-tree partitioning to segment the map into zones while addressing zone connectivity.
Our algorithm achieves a 3x improvement in time efficiency compared to basic sampling methods such as RRT and RRT* in forest-like maps.
Compared to learning-based methods like NeuralRRT* and MPNetSMP, as well as the RRT*J, our algorithm demonstrates, on average, 1.5x better performance in the same environments.
arXiv Detail & Related papers (2024-10-31T17:57:51Z) - Truncating Trajectories in Monte Carlo Policy Evaluation: an Adaptive Approach [51.76826149868971]
Policy evaluation via Monte Carlo simulation is at the core of many MC Reinforcement Learning (RL) algorithms.
We propose as a quality index a surrogate of the mean squared error of a return estimator that uses trajectories of different lengths.
We present an adaptive algorithm called Robust and Iterative Data collection strategy Optimization (RIDO)
arXiv Detail & Related papers (2024-10-17T11:47:56Z) - Robust Stochastic Shortest-Path Planning via Risk-Sensitive Incremental Sampling [9.651071174735804]
We propose a risk-aware Rapidly-Exploring Random Trees (RRT*) planning algorithm for Shortest-Path (SSP) problems.
Our motivation rests on the step-wise coherence of the Conditional Value-at-Risk (CVaR) risk measure and the optimal substructure of the SSP problem.
Our simulation results show that incorporating risk into the tree growth process yields paths with lengths that are significantly less sensitive to variations in the noise parameter.
arXiv Detail & Related papers (2024-08-16T11:21:52Z) - 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) - 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) - 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) - 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.