Post Triangular Rewiring Method for Shorter RRT Robot Path Planning

• URL: http://arxiv.org/abs/2107.05344v1
• Date: Mon, 12 Jul 2021 12:10:37 GMT
• Title: Post Triangular Rewiring Method for Shorter RRT Robot Path Planning
• Abstract summary: '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.
• Score: 3.680403821470857
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: This paper proposed the 'Post Triangular Rewiring' method that minimizes the sacrifice of planning time and overcomes the limit of Optimality of sampling-based algorithm such as Rapidly-exploring Random Tree (RRT) algorithm. The proposed 'Post Triangular Rewiring' method creates a closer to the optimal path than RRT algorithm before application through the triangular inequality principle. The experiments were conducted to verify a performance of the proposed method. When the method proposed in this paper are applied to the RRT algorithm, the Optimality efficiency increase compared to the planning time.

Related papers

• RRT-Rope: A deterministic shortening approach for fast near-optimal path planning in large-scale uncluttered 3D environments [4.297070083645049]
  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.
  arXiv  Detail & Related papers  (2026-06-30T16:54:00Z)
• Alternating minimization for square root principal component pursuit [2.449191760736501]
  We develop efficient algorithms for solving the square root principal component pursuit (SRPCP) problem. Specifically, we propose a tuning-free alternating minimization (AltMin) algorithm, where each iteration involves subproblems enjoying closed-form optimal solutions. We introduce techniques based on the variational formulation of the nuclear norm and Burer-Monteiro decomposition to further accelerate the AltMin method.
  arXiv  Detail & Related papers  (2024-12-31T14:43:50Z)
• 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)
• Efficient and high-performance routing of lattice-surgery paths on three-dimensional lattice [0.2209921757303168]
  We propose a fast and high-performance scheduling algorithm for lattice-surgery instructions. We numerically show that this method reduced the execution time of benchmark programs generated from quantum phase estimation algorithms by 2.7 times.
  arXiv  Detail & Related papers  (2024-01-29T01:28:42Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Path Planning using Reinforcement Learning: A Policy Iteration Approach [0.0]
  This research aims to shed light on the design space exploration associated with reinforcement learning parameters. We propose an auto-tuner-based ordinal regression approach to accelerate the process of exploring these parameters. Our approach provides 1.82x peak speedup with an average of 1.48x speedup over the previous state-of-the-art.
  arXiv  Detail & Related papers  (2023-03-13T23:44:40Z)
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs [113.8752163061151]
  We study episodic reinforcement learning (RL) in non-stationary linear kernel Markov decision processes (MDPs) We propose the underlineperiodically underlinerestarted underlineoptimistic underlinepolicy underlineoptimization algorithm (PROPO) PROPO features two mechanisms: sliding-window-based policy evaluation and periodic-restart-based policy improvement.
  arXiv  Detail & Related papers  (2021-10-18T02:33:20Z)
• Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
  We propose a new reinforcement learning based ZO algorithm (ZO-RL) with learning the sampling policy for generating the perturbations in ZO optimization instead of using random sampling. Our results show that our ZO-RL algorithm can effectively reduce the variances of ZO gradient by learning a sampling policy, and converge faster than existing ZO algorithms in different scenarios.
  arXiv  Detail & Related papers  (2021-04-09T14:50:59Z)
• Average-Reward Off-Policy Policy Evaluation with Function Approximation [66.67075551933438]
  We consider off-policy policy evaluation with function approximation in average-reward MDPs. bootstrapping is necessary and, along with off-policy learning and FA, results in the deadly triad. We propose two novel algorithms, reproducing the celebrated success of Gradient TD algorithms in the average-reward setting.
  arXiv  Detail & Related papers  (2021-01-08T00:43:04Z)
• qRRT: Quality-Biased Incremental RRT for Optimal Motion Planning in Non-Holonomic Systems [16.323822608442836]
  This paper presents a sampling-based method for optimal motion planning in non-holonomic systems. It uses the principle of learning through experience to deduce the cost-to-go of regions within the workspace.
  arXiv  Detail & Related papers  (2021-01-07T17:10: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)
• Variance-Reduced Off-Policy Memory-Efficient Policy Search [61.23789485979057]
  Off-policy policy optimization is a challenging problem in reinforcement learning. Off-policy algorithms are memory-efficient and capable of learning from off-policy samples.
  arXiv  Detail & Related papers  (2020-09-14T16:22:46Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  We introduce a framework for designing primal methods under the decentralized optimization setting where local functions are smooth and strongly convex. Our approach consists of approximately solving a sequence of sub-problems induced by the accelerated augmented Lagrangian method. When coupled with accelerated gradient descent, our framework yields a novel primal algorithm whose convergence rate is optimal and matched by recently derived lower bounds.
  arXiv  Detail & Related papers  (2020-06-11T18:49:06Z)

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.