专栏首页mwangblogVGRAPH路径规划(Lozano-Perez and Wesley, 1979)

VGRAPH路径规划(Lozano-Perez and Wesley, 1979)

本文中的方法来自文章:

  • Lozano-Pérez T, Wesley M A. An algorithm for planning collision-free paths among polyhedral obstacles[J]. Communications of the ACM, 1979, 22(10): 560-570.

本文参考了以下项目代码(特别是地图数据、增长障碍物部分代码、线段是否相交检查部分代码),特表示感谢:

  • https://github.com/jingxixu/vgraph

点击原文链接获取本文代码下载链接。

算法的主要思想是,将运动体看作一个点,通过将障碍物“增长”适当的程度,以满足避碰需求。在图中搜寻一条从起点到目标点的路径即可。

该路径的重要特性是它由通过障碍物顶点序列将原点连接到目的地的直线组成。在具有任意多边形运动体的平面中运动的情况下,连接任何两个可访问点的最短无碰撞路径始终具有此属性。

如下图所示,正方形运动体(绿色框)要从当前位置(起点)移动到终点(红色*),不考虑运动体的旋转,以运动体的中心为参考点,为该参考点确定一条路径。

由于运动体被看作一个点,因此需要对障碍物进行增长,以满足避碰需要:

从上图可见,即便运动体的参考点(正方形中心)在增长后障碍物的边缘,运动体与障碍物之间正好不会发生碰撞。

之后,寻找可直接相连的路径:

最后,搜索地图以得到最短通行路径:

本文分享自微信公众号 - mwangblog(mwangblog),作者:WM

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 存储器与存储单元

    mwangblog
  • 开始使用Android Studio

    mwangblog
  • 使用ABT(The asynchronous backtracking algorithm)算法求解四皇后问题

    将4个皇后放入4×4的棋盘中,修改4个皇后的位置,使他们不能“立即”攻击对方。这里我们假设4个皇后被放置在不同的行中,仅能修改4个皇后的列的位置。

    mwangblog
  • 【玩转腾讯云】比快更快,Github Action + 云开发部署静态网站

    云开发静态托管是云开发提供的静态网站托管的能力,静态资源(HTML、CSS、JavaScript、字体等)的分发由腾讯云对象存储 COS 和拥有多个边缘网点的腾...

    Booker Zhao
  • AI芯片的历史和现状

    人的思维活动是否能用计算机来替代,从图灵的论文《计算机器与智能》和图灵测试,到最初级的神经元模拟单元——感知机,到现在多达上百层的深度神经网络,对人工智能的探索...

    刘盼
  • scRNA-seq课程第一单元-背景介绍

    14年高考没考好,阴差阳错读了某二本的生物信息学专业,是我们学校生物信息学专业的第一届(xiao)学(bai)生(shu),记得刚进校门整个班的同学围着老师问生...

    生信技能树jimmy
  • Mockito 2 关于打标(stubbing)

    https://github.com/cwiki-us-demo/mockito-demo-java/blob/master/src/test/java/com...

    HoneyMoose
  • 元素居中的多种实现方式!

    优点:只需在子元素child上设置css样式,不用关心父元素的 缺点:兼容性较差,如果需要兼容,更改html样式,改为table样式

    十月梦想
  • 打印1到最大的n位数

    这道题是面试过可能会遇到的手写代码题。如n为3时,那么需要打印1到999。需要注意的是当输入的n很大时,最大的n位数是不能通过int或者long long in...

    Dabelv
  • CES 2017展前概况:这些黑科技你可千万别错过!

    VRPinea

扫码关注云+社区

领取腾讯云代金券