AtHeartEngineer/PythonRobotics
1
1
Fork 0
mirror of https://github.com/AtsushiSakai/PythonRobotics.git synced 2026-01-14 23:27:59 -05:00
Code Issues Packages Projects Releases Wiki Activity
Files
gh-pages
PythonRobotics/modules/path_planning/rrt/rrt.html
GitHub Action ca03917e1a Add changes for 5ddf70615e
2023-05-28 08:23:48 +00:00

274 lines
18 KiB
HTML
Raw Permalink Blame History

<!DOCTYPE html>
<html class="writer-html5" lang="en" >
<head>
<meta charset="utf-8" /><meta name="generator" content="Docutils 0.17.1: http://docutils.sourceforge.net/" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Rapidly-Exploring Random Trees (RRT) &mdash; PythonRobotics documentation</title>
<link rel="stylesheet" href="../../../_static/pygments.css" type="text/css" />
<link rel="stylesheet" href="../../../_static/css/theme.css" type="text/css" />
<link rel="stylesheet" href="../../../_static/plot_directive.css" type="text/css" />
<link rel="stylesheet" href="../../../_static/copybutton.css" type="text/css" />
<link rel="stylesheet" href="../../../_static/custom.css" type="text/css" />
<link rel="stylesheet" href="../../../_static/dark_mode_css/general.css" type="text/css" />
<link rel="stylesheet" href="../../../_static/dark_mode_css/dark.css" type="text/css" />
<!--[if lt IE 9]>
<script src="../../../_static/js/html5shiv.min.js"></script>
<![endif]-->
<script data-url_root="../../../" id="documentation_options" src="../../../_static/documentation_options.js"></script>
<script src="../../../_static/jquery.js"></script>
<script src="../../../_static/underscore.js"></script>
<script src="../../../_static/doctools.js"></script>
<script src="../../../_static/clipboard.min.js"></script>
<script src="../../../_static/copybutton.js"></script>
<script src="../../../_static/dark_mode_js/default_dark.js"></script>
<script src="../../../_static/dark_mode_js/theme_switcher.js"></script>
<script src="../../../_static/js/theme.js"></script>
<link rel="index" title="Index" href="../../../genindex.html" />
<link rel="search" title="Search" href="../../../search.html" />
<link rel="next" title="Cubic spline planning" href="../cubic_spline/cubic_spline.html" />
<link rel="prev" title="Voronoi Road-Map planning" href="../vrm_planner/vrm_planner.html" />
</head>
<body class="wy-body-for-nav">
<div class="wy-grid-for-nav">
<nav data-toggle="wy-nav-shift" class="wy-nav-side">
<div class="wy-side-scroll">
<div class="wy-side-nav-search" >
<a href="../../../index.html" class="icon icon-home"> PythonRobotics
<img src="../../../_static/icon.png" class="logo" alt="Logo"/>
</a>
<div role="search">
<form id="rtd-search-form" class="wy-form" action="../../../search.html" method="get">
<input type="text" name="q" placeholder="Search docs" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
</div>
<script async src="https://pagead2.googlesyndication.com/pagead/js/adsbygoogle.js?client=ca-pub-9612347954373886"
crossorigin="anonymous"></script>
<!-- PythonRoboticsDoc -->
<ins class="adsbygoogle"
style="display:block"
data-ad-client="ca-pub-9612347954373886"
data-ad-slot="1579532132"
data-ad-format="auto"
data-full-width-responsive="true"></ins>
<script>
(adsbygoogle = window.adsbygoogle || []).push({});
</script>
</div><div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="Navigation menu">
<p class="caption" role="heading"><span class="caption-text">Contents</span></p>
<ul class="current">
<li class="toctree-l1"><a class="reference internal" href="../../../getting_started.html">Getting Started</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../introduction.html">Introduction</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../localization/localization.html">Localization</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../mapping/mapping.html">Mapping</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../slam/slam.html">SLAM</a></li>
<li class="toctree-l1 current"><a class="reference internal" href="../path_planning.html">Path Planning</a><ul class="current">
<li class="toctree-l2"><a class="reference internal" href="../dynamic_window_approach/dynamic_window_approach.html">Dynamic Window Approach</a></li>
<li class="toctree-l2"><a class="reference internal" href="../bugplanner/bugplanner.html">Bug planner</a></li>
<li class="toctree-l2"><a class="reference internal" href="../grid_base_search/grid_base_search.html">Grid based search</a></li>
<li class="toctree-l2"><a class="reference internal" href="../model_predictive_trajectory_generator/model_predictive_trajectory_generator.html">Model Predictive Trajectory Generator</a></li>
<li class="toctree-l2"><a class="reference internal" href="../state_lattice_planner/state_lattice_planner.html">State Lattice Planning</a></li>
<li class="toctree-l2"><a class="reference internal" href="../prm_planner/prm_planner.html">Probabilistic Road-Map (PRM) planning</a></li>
<li class="toctree-l2"><a class="reference internal" href="../visibility_road_map_planner/visibility_road_map_planner.html">Visibility Road-Map planner</a></li>
<li class="toctree-l2"><a class="reference internal" href="../vrm_planner/vrm_planner.html">Voronoi Road-Map planning</a></li>
<li class="toctree-l2 current"><a class="current reference internal" href="#">Rapidly-Exploring Random Trees (RRT)</a><ul>
<li class="toctree-l3"><a class="reference internal" href="#basic-rrt">Basic RRT</a></li>
<li class="toctree-l3"><a class="reference internal" href="#rrt">RRT*</a><ul>
<li class="toctree-l4"><a class="reference internal" href="#simulation">Simulation</a></li>
<li class="toctree-l4"><a class="reference internal" href="#ref">Ref</a></li>
</ul>
</li>
<li class="toctree-l3"><a class="reference internal" href="#rrt-with-dubins-path">RRT with dubins path</a></li>
<li class="toctree-l3"><a class="reference internal" href="#id2">RRT* with dubins path</a></li>
<li class="toctree-l3"><a class="reference internal" href="#rrt-with-reeds-sheep-path">RRT* with reeds-sheep path</a></li>
<li class="toctree-l3"><a class="reference internal" href="#informed-rrt">Informed RRT*</a></li>
<li class="toctree-l3"><a class="reference internal" href="#batch-informed-rrt">Batch Informed RRT*</a></li>
<li class="toctree-l3"><a class="reference internal" href="#closed-loop-rrt">Closed Loop RRT*</a></li>
<li class="toctree-l3"><a class="reference internal" href="#lqr-rrt">LQR-RRT*</a></li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="../cubic_spline/cubic_spline.html">Cubic spline planning</a></li>
<li class="toctree-l2"><a class="reference internal" href="../bspline_path/bspline_path.html">B-Spline planning</a></li>
<li class="toctree-l2"><a class="reference internal" href="../clothoid_path/clothoid_path.html">Clothoid path planning</a></li>
<li class="toctree-l2"><a class="reference internal" href="../eta3_spline/eta3_spline.html">Eta^3 Spline path planning</a></li>
<li class="toctree-l2"><a class="reference internal" href="../bezier_path/bezier_path.html">Bezier path planning</a></li>
<li class="toctree-l2"><a class="reference internal" href="../quintic_polynomials_planner/quintic_polynomials_planner.html">Quintic polynomials planning</a></li>
<li class="toctree-l2"><a class="reference internal" href="../dubins_path/dubins_path.html">Dubins path planning</a></li>
<li class="toctree-l2"><a class="reference internal" href="../reeds_shepp_path/reeds_shepp_path.html">Reeds Shepp planning</a></li>
<li class="toctree-l2"><a class="reference internal" href="../lqr_path/lqr_path.html">LQR based path planning</a></li>
<li class="toctree-l2"><a class="reference internal" href="../hybridastar/hybridastar.html">Hybrid a star</a></li>
<li class="toctree-l2"><a class="reference internal" href="../frenet_frame_path/frenet_frame_path.html">Optimal Trajectory in a Frenet Frame</a></li>
<li class="toctree-l2"><a class="reference internal" href="../coverage_path/coverage_path.html">Coverage path planner</a></li>
</ul>
</li>
<li class="toctree-l1"><a class="reference internal" href="../../path_tracking/path_tracking.html">Path Tracking</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../arm_navigation/arm_navigation.html">Arm Navigation</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../aerial_navigation/aerial_navigation.html">Aerial Navigation</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../bipedal/bipedal.html">Bipedal</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../control/control.html">Control</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../utils/utils.html">Utilities</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../appendix/appendix.html">Appendix</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../../how_to_contribute.html">How To Contribute</a></li>
</ul>
</div>
</div>
</nav>
<section data-toggle="wy-nav-shift" class="wy-nav-content-wrap"><nav class="wy-nav-top" aria-label="Mobile navigation menu" >
<i data-toggle="wy-nav-top" class="fa fa-bars"></i>
<a href="../../../index.html">PythonRobotics</a>
</nav>
<div class="wy-nav-content">
<div class="rst-content">
<div role="navigation" aria-label="Page navigation">
<ul class="wy-breadcrumbs">
<li><a href="../../../index.html" class="icon icon-home"></a> &raquo;</li>
<li><a href="../path_planning.html">Path Planning</a> &raquo;</li>
<li>Rapidly-Exploring Random Trees (RRT)</li>
<li class="wy-breadcrumbs-aside">
<a href="https://github.com/AtsushiSakai/PythonRobotics/blob/master/docs/modules/path_planning/rrt/rrt_main.rst" class="fa fa-github"> Edit on GitHub</a>
</li>
</ul>
<hr/>
</div>
<div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
<div itemprop="articleBody">
<section id="rapidly-exploring-random-trees-rrt">
<span id="id1"></span><h1>Rapidly-Exploring Random Trees (RRT)<a class="headerlink" href="#rapidly-exploring-random-trees-rrt" title="Permalink to this headline"></a></h1>
<section id="basic-rrt">
<h2>Basic RRT<a class="headerlink" href="#basic-rrt" title="Permalink to this headline"></a></h2>
<img alt="https://github.com/AtsushiSakai/PythonRoboticsGifs/raw/master/PathPlanning/RRT/animation.gif" src="https://github.com/AtsushiSakai/PythonRoboticsGifs/raw/master/PathPlanning/RRT/animation.gif" />
<p>This is a simple path planning code with Rapidly-Exploring Random Trees
(RRT)</p>
<p>Black circles are obstacles, green line is a searched tree, red crosses
are start and goal positions.</p>
</section>
<section id="rrt">
<h2>RRT*<a class="headerlink" href="#rrt" title="Permalink to this headline"></a></h2>
<figure class="align-default">
<img alt="https://github.com/AtsushiSakai/PythonRoboticsGifs/raw/master/PathPlanning/RRTstar/animation.gif" src="https://github.com/AtsushiSakai/PythonRoboticsGifs/raw/master/PathPlanning/RRTstar/animation.gif" />
</figure>
<p>This is a path planning code with RRT*</p>
<p>Black circles are obstacles, green line is a searched tree, red crosses are start and goal positions.</p>
<section id="simulation">
<h3>Simulation<a class="headerlink" href="#simulation" title="Permalink to this headline"></a></h3>
<a class="reference internal image-reference" href="../../../_images/rrt_star_1_0.png"><img alt="../../../_images/rrt_star_1_0.png" src="../../../_images/rrt_star_1_0.png" style="width: 600px;" /></a>
</section>
<section id="ref">
<h3>Ref<a class="headerlink" href="#ref" title="Permalink to this headline"></a></h3>
<ul class="simple">
<li><p><a class="reference external" href="https://arxiv.org/pdf/1105.1186.pdf">Sampling-based Algorithms for Optimal Motion Planning</a></p></li>
<li><p><a class="reference external" href="https://arxiv.org/abs/1005.0416">Incremental Sampling-based Algorithms for Optimal Motion Planning</a></p></li>
</ul>
</section>
</section>
<section id="rrt-with-dubins-path">
<h2>RRT with dubins path<a class="headerlink" href="#rrt-with-dubins-path" title="Permalink to this headline"></a></h2>
<img alt="https://github.com/AtsushiSakai/PythonRoboticsGifs/raw/master/PathPlanning/RRTDubins/animation.gif" src="https://github.com/AtsushiSakai/PythonRoboticsGifs/raw/master/PathPlanning/RRTDubins/animation.gif" />
<p>Path planning for a car robot with RRT and dubins path planner.</p>
</section>
<section id="id2">
<span id="id3"></span><h2>RRT* with dubins path<a class="headerlink" href="#id2" title="Permalink to this headline"></a></h2>
<img alt="https://github.com/AtsushiSakai/PythonRoboticsGifs/raw/master/PathPlanning/RRTStarDubins/animation.gif" src="https://github.com/AtsushiSakai/PythonRoboticsGifs/raw/master/PathPlanning/RRTStarDubins/animation.gif" />
<p>Path planning for a car robot with RRT* and dubins path planner.</p>
</section>
<section id="rrt-with-reeds-sheep-path">
<span id="id4"></span><h2>RRT* with reeds-sheep path<a class="headerlink" href="#rrt-with-reeds-sheep-path" title="Permalink to this headline"></a></h2>
<img alt="https://github.com/AtsushiSakai/PythonRoboticsGifs/raw/master/PathPlanning/RRTStarReedsShepp/animation.gif" src="https://github.com/AtsushiSakai/PythonRoboticsGifs/raw/master/PathPlanning/RRTStarReedsShepp/animation.gif" />
<p>Path planning for a car robot with RRT* and reeds sheep path planner.</p>
</section>
<section id="informed-rrt">
<span id="id5"></span><h2>Informed RRT*<a class="headerlink" href="#informed-rrt" title="Permalink to this headline"></a></h2>
<img alt="https://github.com/AtsushiSakai/PythonRoboticsGifs/raw/master/PathPlanning/InformedRRTStar/animation.gif" src="https://github.com/AtsushiSakai/PythonRoboticsGifs/raw/master/PathPlanning/InformedRRTStar/animation.gif" />
<p>This is a path planning code with Informed RRT*.</p>
<p>The cyan ellipse is the heuristic sampling domain of Informed RRT*.</p>
<p>Ref:</p>
<ul class="simple">
<li><p><a class="reference external" href="https://arxiv.org/pdf/1404.2334.pdf">Informed RRT*: Optimal Sampling-based Path Planning Focused via
Direct Sampling of an Admissible Ellipsoidal
Heuristic</a></p></li>
</ul>
</section>
<section id="batch-informed-rrt">
<span id="id6"></span><h2>Batch Informed RRT*<a class="headerlink" href="#batch-informed-rrt" title="Permalink to this headline"></a></h2>
<img alt="https://github.com/AtsushiSakai/PythonRoboticsGifs/raw/master/PathPlanning/BatchInformedRRTStar/animation.gif" src="https://github.com/AtsushiSakai/PythonRoboticsGifs/raw/master/PathPlanning/BatchInformedRRTStar/animation.gif" />
<p>This is a path planning code with Batch Informed RRT*.</p>
<p>Ref:</p>
<ul class="simple">
<li><p><a class="reference external" href="https://arxiv.org/abs/1405.5848">Batch Informed Trees (BIT*): Sampling-based Optimal Planning via the
Heuristically Guided Search of Implicit Random Geometric
Graphs</a></p></li>
</ul>
</section>
<section id="closed-loop-rrt">
<span id="id7"></span><h2>Closed Loop RRT*<a class="headerlink" href="#closed-loop-rrt" title="Permalink to this headline"></a></h2>
<p>A vehicle model based path planning with closed loop RRT*.</p>
<img alt="https://github.com/AtsushiSakai/PythonRoboticsGifs/raw/master/PathPlanning/ClosedLoopRRTStar/animation.gif" src="https://github.com/AtsushiSakai/PythonRoboticsGifs/raw/master/PathPlanning/ClosedLoopRRTStar/animation.gif" />
<p>In this code, pure-pursuit algorithm is used for steering control,</p>
<p>PID is used for speed control.</p>
<p>Ref:</p>
<ul class="simple">
<li><p><a class="reference external" href="http://acl.mit.edu/papers/KuwataGNC08.pdf">Motion Planning in Complex Environments using Closed-loop
Prediction</a></p></li>
<li><p><a class="reference external" href="http://acl.mit.edu/papers/KuwataTCST09.pdf">Real-time Motion Planning with Applications to Autonomous Urban
Driving</a></p></li>
<li><p><a class="reference external" href="https://arxiv.org/abs/1601.06326">[1601.06326] Sampling-based Algorithms for Optimal Motion Planning
Using Closed-loop Prediction</a></p></li>
</ul>
</section>
<section id="lqr-rrt">
<span id="id8"></span><h2>LQR-RRT*<a class="headerlink" href="#lqr-rrt" title="Permalink to this headline"></a></h2>
<p>This is a path planning simulation with LQR-RRT*.</p>
<p>A double integrator motion model is used for LQR local planner.</p>
<img alt="https://github.com/AtsushiSakai/PythonRoboticsGifs/raw/master/PathPlanning/LQRRRTStar/animation.gif" src="https://github.com/AtsushiSakai/PythonRoboticsGifs/raw/master/PathPlanning/LQRRRTStar/animation.gif" />
<p>Ref:</p>
<ul class="simple">
<li><p><a class="reference external" href="http://lis.csail.mit.edu/pubs/perez-icra12.pdf">LQR-RRT*: Optimal Sampling-Based Motion Planning with Automatically
Derived Extension
Heuristics</a></p></li>
<li><p><a class="reference external" href="https://github.com/MahanFathi/LQR-RRTstar">MahanFathi/LQR-RRTstar: LQR-RRT* method is used for random motion planning of a simple pendulum in its phase plot</a></p></li>
</ul>
</section>
</section>
</div>
</div>
<footer><div class="rst-footer-buttons" role="navigation" aria-label="Footer">
<a href="../vrm_planner/vrm_planner.html" class="btn btn-neutral float-left" title="Voronoi Road-Map planning" accesskey="p" rel="prev"><span class="fa fa-arrow-circle-left" aria-hidden="true"></span> Previous</a>
<a href="../cubic_spline/cubic_spline.html" class="btn btn-neutral float-right" title="Cubic spline planning" accesskey="n" rel="next">Next <span class="fa fa-arrow-circle-right" aria-hidden="true"></span></a>
</div>
<hr/>
<div role="contentinfo">
<p>&#169; Copyright 2018-2021, Atsushi Sakai.</p>
</div>
Built with <a href="https://www.sphinx-doc.org/">Sphinx</a> using a
<a href="https://github.com/readthedocs/sphinx_rtd_theme">theme</a>
provided by <a href="https://readthedocs.org">Read the Docs</a>.
</footer>
</div>
</div>
</section>
</div>
<script>
jQuery(function () {
SphinxRtdTheme.Navigation.enable(true);
});
</script>
</body>
</html>
Reference in New Issue View Git Blame Copy Permalink