• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

EwingKang/Dubins-RRT-for-MATLAB: RRT (Rapidly-Exploring Random Trees) using Dubi ...

原作者: [db:作者] 来自: 网络 收藏 邀请

开源软件名称(OpenSource Name):

EwingKang/Dubins-RRT-for-MATLAB

开源软件地址(OpenSource Url):

https://github.com/EwingKang/Dubins-RRT-for-MATLAB

开源编程语言(OpenSource Language):

MATLAB 100.0%

开源软件介绍(OpenSource Introduction):

Dubins-RRT-for-MATLAB

About

RRT (Rapidly-Exploring Random Trees) using Dubins curve, with collision check in MATLAB
4000 Dubins RRT iteration with collision

Intro

RRT, the Rapidly-Exploring Random Trees is a ramdomized method of exploring within dimensions. This method can effectively generate a path to reach any point within certain limited steps due to its random characteristics. This method is proprosed by LaValle, Steven M. in October 1998, in his technical report to Computer Science Department of Iowa State University as "Rapidly-exploring random trees: A new tool for path planning" Today, multiple variation of RRT method is widely applied with path planning problem among UAVs for ground based, aerial, and marinetime vehicles.
In RRT_Dubins.m, the paths connecting each points, or the "edges" to the "vertices" are replaced with Dubins curve. This is a very common practice when dealing with dynamic system. Specifically for non-holonomic system, such as cars, airplanes or ships. Replacements of Dubins curve means the branches growing out of a vertex is always smooth in the sense tengency. This makes the path generated more feassibly then the original straight line connection style if taking dynamics into consideration.

Algorithm

For the sake of simplicity, I will discuss the algorithm only with 2-D planes. The problem is, given a starting point and limited boundary, how do we reach everypoint within the area systematically? The method itself is very simple, only repeative iteration of are 4 steps.

  1. Generate a random point, i.e, a "vertex"
  2. Find the closest vertex from the existing list (euclidean distance or dubins path distance).
  3. Create an "edge" connect the new vertex to the closest existing vertex.
  4. Check if the newly generated vertex and edge has collision with obstacles or not. Go back to step1 if conflict.
  5. Append (add) the new vertex and edge to the known vertices and edges list.
  6. Start from step1 As the iteration goes, it looks like a tree consists of edges is growing within the boundary and thus named so.

Running the programs

There are 4 main programs, see the comments in each file for more detail

  • RRT.m
    standard baseline RRT algorithm
  • RRT_Dubins.m
    RRT with Dubins curve as edge
  • RRT_obstacles.m
    RRT with obstacles and collision check
  • RRT_Dubins_obstacles.m
    Final complete algorithm: RRT with Dubins curve and collision check

Note: All plotting related function have the filename starts with plot_xxxxx_xxxx.m.

Execution Time

  • RRT_Dubins_obstacles.m
    The searching function for now is a dumb exhaustive search over a un-ordered list, program running time grows exponentially with amount of iterations. Here are some of the resutls, note the time will very each time you run the program:
    • i = 100 0.198196 / 0.292975 sec
    • i = 1000 11.011770 sec
    • i = 10000 1121.169987 sec

100 iterations1000 iterations10000 iterations

References

License

Released under GPLv3 license
Copyright (c) 2018 Ewing Kang

Dubins path generator is a MATLAB re-written from Andrew Walker's work, which was originally distributed under MIT license in C language.

See LICENSE file for more info.

TODOS

  • RRT+Dubins+collisioncheck
  • fast localsearch
  • tree growing animation



鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap