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

• SCoTT: Wireless-Aware Path Planning with Vision Language Models and Strategic Chains-of-Thought [78.53885607559958]
  A novel approach using vision language models (VLMs) is proposed for enabling path planning in complex wireless-aware environments. To this end, insights from a digital twin with real-world wireless ray tracing data are explored. Results show that SCoTT achieves very close average path gains compared to DP-WA* while at the same time yielding consistently shorter path lengths.
  arXiv  Detail & Related papers  (2024-11-27T10:45:49Z)
• 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)
• 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)
• 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.