RRT-Rope: A deterministic shortening approach for fast near-optimal path planning in large-scale uncluttered 3D environments

• URL: http://arxiv.org/abs/2606.31948v1
• Date: Tue, 30 Jun 2026 16:54:00 GMT
• Title: RRT-Rope: A deterministic shortening approach for fast near-optimal path planning in large-scale uncluttered 3D environments
• Abstract summary: Rapidly-exploring Random Tree (RRT) algorithms are popular because of their probabilistic completeness and rapidity in finding a feasible path.<n>Shortcutting an RRT is an old idea that has been proven to outperform RRT variants.<n>This paper introduces a new method, RRT-Rope, that aims at finding a near-optimal solution in a drastically shorter amount of time.
• Score: 4.297070083645049
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many path planning algorithms have been introduced so far, but most are costly, in path cost and in processing time, in large-scale uncluttered 3D environments such as underground mining stopes explored by an unmanned aerial vehicle (UAV). Rapidly-exploring Random Tree (RRT) algorithms are popular because of their probabilistic completeness and rapidity in finding a feasible path in single-query problems. Many of the algorithms (e.g. Informed RRT*, RRT#) developed to improve RRT need considerable time to converge in large environments. Shortcutting an RRT is an old idea that has been proven to outperform RRT variants. This paper introduces a new method, RRT-Rope, that aims at finding a near-optimal solution in a drastically shorter amount of time. The proposed approach benefits from fast computation of a feasible path with an altered version of RRT-connect, and post-processes it quickly with a deterministic shortcutting technique, taking advantage of intermediate nodes added to each branch of the tree. This paper presents simulations and statistics carried out to show the efficiency of RRT-Rope, which gives better results in terms of path cost and computation time than other popular RRT variations and shortening techniques in all our simulation environments, and is up to 70% faster than the next best algorithm in a representative stope.

Related papers

• Process Reward Informed Tree Rollout for Effective Multi-Turn RL [58.392997761968566]
  In long-horizon agentic tasks, a uniform rollout strategy can waste budget on uninformative dead-end attempts.<n>We propose Process-Scorer Guided Adaptive Tree Rollout (PATR), a quality-aware rollout framework for multi-turn agent RL.<n>PATR uses task-appropriate process feedback to score partial trajectories, selectively branches from promising states, reuses shared prefixes, and conservatively stops paths to reduce wasted sampling.
  arXiv  Detail & Related papers  (2026-07-17T04:16:58Z)
• Performance Comparison of Classical and Neural Sampling Algorithms for Robotic Navigation [0.0]
  Three algorithms, namely RRT*, Neural RRT*, and Neural Informed RRT*, are implemented and evaluated.<n>Results indicate that neural-guided planners improve path quality, producing up to 14% shorter paths and 55--75% smoother trajectories.
  arXiv  Detail & Related papers  (2026-05-24T11:27:31Z)
• Convex-Neural RRT*: Fast and Reliable Learning-Guided Sampling for High-Quality Robot Path Planning [0.0]
  This paper proposes Convex-Neural RRT*, an enhanced RRT* variant that incorporates neural guidance to predict informative waypoint regions near high-quality paths.<n>The proposed algorithm is evaluated against Neural RRT*, Neural Informed RRT*, classical RRT*, and LTA* across three environment types and 18 benchmark maps.<n> Experimental results show that Convex-Neural RRT* reduces time by 30-75% compared to neural-guided variants and up to 88-98% relative to LTA*, with larger improvements observed in complex environments.
  arXiv  Detail & Related papers  (2026-05-24T11:17:57Z)
• SCoTT: Strategic Chain-of-Thought Tasking for Wireless-Aware Robot Navigation in Digital Twins [78.53885607559958]
  We propose SCoTT, a wireless-aware path planning framework.<n>We show that SCoTT achieves path gains within 2% of DP-WA* while consistently generating shorter trajectories.<n>We also show the practical viability of our approach by deploying SCoTT as a ROS node within Gazebo simulations.
  arXiv  Detail & Related papers  (2024-11-27T10:45:49Z)
• 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)
• Finding Transformer Circuits with Edge Pruning [71.12127707678961]
  We propose Edge Pruning as an effective and scalable solution to automated circuit discovery.<n>Our method finds circuits in GPT-2 that use less than half the number of edges compared to circuits found by previous methods.<n>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)
• CBAGAN-RRT: Convolutional Block Attention Generative Adversarial Network for Sampling-Based Path Planning [0.0]
  We propose a novel image-based learning algorithm using a Convolutional Block Attention Generative Adrial Network (CBAGAN-RRT)<n>Our algorithm outperforms the previous state-of-the-art algorithms using both the image quality generation metrics and path planning metrics.
  arXiv  Detail & Related papers  (2023-05-13T20:06:53Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• Post Triangular Rewiring Method for Shorter RRT Robot Path Planning [3.680403821470857]
  'Post Triangular Rewiring' method minimizes the sacrifice of planning time. It overcomes the limit of Optimality of sampling-based algorithm such as Rapidly-exploring Random Tree (RRT) algorithm.
  arXiv  Detail & Related papers  (2021-07-12T12:10:37Z)
• Rotation Coordinate Descent for Fast Globally Optimal Rotation Averaging [47.3713707521106]
  We present a fast algorithm that achieves global optimality called rotation coordinate descent (RCD) Unlike block coordinate descent (BCD) which solves SDP by updating the semidefinite matrix in a row-by-row fashion, RCD directly maintains and updates all valid rotations throughout the iterations. We mathematically prove the convergence of our algorithm and empirically show its superior efficiency over state-of-the-art global methods.
  arXiv  Detail & Related papers  (2021-03-15T11:31:34Z)
• 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)
• AM-RRT*: Informed Sampling-based Planning with Assisting Metric [3.42658286826597]
  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.
  arXiv  Detail & Related papers  (2020-10-28T01:39:40Z)
• RNN Training along Locally Optimal Trajectories via Frank-Wolfe Algorithm [50.76576946099215]
  We propose a novel and efficient training method for RNNs by iteratively seeking a local minima on the loss surface within a small region. We develop a novel RNN training method that, surprisingly, even with the additional cost, the overall training cost is empirically observed to be lower than back-propagation.
  arXiv  Detail & Related papers  (2020-10-12T01:59:18Z)

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.