【泡泡图灵智库】一种在未知的复杂环境中在线生成四旋翼的无碰撞轨迹算法

泡泡图灵智库，带你精读机器人顶级会议文章

标题：Online Generation of Collision-Free Trajectories for Quadrotor Flight in Unknown Cluttered Environments

作者：Jing Chen, Tianbo Liu, and Shaojie Shen

来源：ICRA2016

播音员：

编译：杨小育

审核：

欢迎个人转发朋友圈；其他机构或自媒体如需转载，后台留言申请授权

摘要

       大家好，今天为大家带来的文章是 —— Online Generation of Collision-Free Trajectories for Quadrotor Flight in Unknown Cluttered Environments，该文章目前发表于ICRA 2016。

        我们提出了一种在未知的复杂环境中在线生成四旋翼的无碰撞轨迹算法。 在真实环境下，四旋翼飞行器只有有限的传感器，并且需要在未知的环境中运行。在飞行时，使用机载传感器逐步建立基于八叉树的环境表示。利用八叉树这种数据结构，我们的算法可以在线生成由大型重叠三维网格组成的自由空间飞行走廊。然后使用基于优化的方法进行轨迹平滑，生成的轨迹被约束在安全飞行走廊内，并且满足更高阶的动力学约束。我们的方法在一般性能的计算机上可以在几分之一秒内生成有效轨迹，从而使得在线重规划成为可能，以应对新障碍不断出现的复杂环境。我们构建了一个完整的四旋翼测试平台，上面搭载了机载传感器，具有状态估计、地图构建、姿态控制等功能，并集成了本文所提出的方法，实验结果表明无人机可以顺利通过复杂的未知环境。

主要贡献

1、提出一种基于机载传感器且算力有限情况下的无人机无碰撞轨迹规划方法

2、提出一种有效飞行区域膨胀方法

3、提出了一种基于轨迹极值点约束的轨迹生成方法

算法流程

图 1 整个系统的架构图

1、虚拟飞行走廊生成

1.1、基于八叉树的环境地图表示

1.2、初始化飞行走廊

        每个栅格使用如下的方式表示：

        作者使用标准的A*算法进行飞行走廊的初始化，以欧式距离作为cost

1.3、膨胀飞行走廊

        障碍物评价函数如下所示

图 2 （a）本文方法生成的无碰撞轨迹；（b）作者先前方法生成的轨迹；（c）路标点方法生成的轨迹

图3 使用1.3中的方法进行飞行走廊膨胀。蓝色为初始飞行走廊，绿色为膨胀后的走廊

2、 在飞行走廊约束下的轨迹生成

2.1、多项式轨迹生成

        各个分段的轨迹表示：

        目标函数：

2.2、飞行走廊的约束

        走廊重叠区域的约束项，重叠区域见图4（b）：

        走廊非重叠区域的约束项：

图 4 极值点方法约束条件的示意图

主要结果

1、与state-of-art方法（RRT*）的对比实验

图 5 作者在四种环境下的对比实验。蓝色方块代表障碍物，绿色方块代表为膨胀的飞行走廊，白色方块代表膨胀后的飞行走廊；绿色曲线为RRT*生成的轨迹，蓝色曲线为作者先前方法生成的轨迹，红色曲线为本文方法生成的轨迹

图 6 三种规划方法的计算耗时。青色为RRT*方法的耗时，绿色为作者先前方法的耗时，红色为本文方法的耗时，可以看出无论经不经飞行走廊膨胀，作者的方法都耗时很短

2、仿真环境下的对比实验

图7 模拟四旋翼飞行器在有限传感的未知环境中导航。红线是生成的轨迹，蓝线是已经飞过的路径；蓝色和透明的白色立方体分别是原始和膨胀的障碍物；绿色立方体代表最初的走廊，白色斑块代表最终膨胀的飞行走廊

图 8 图7实验的耗时情况

3、 室内环境下的对比实验

图 9 室内实验场景

图 10 室内场景下，进行的五次重规划计算耗时情况

图 11 混乱的未知室内环境中的自主飞行

图 12 室内飞行试验的期望轨迹（彩色）和实际飞行路径（灰色）

4、 室外环境下的对比实验

作者在自主室外飞行实验中测试本文的方法，如图13所示，所有系统参数与室内实验相同，速度达到1.8m / s。由于可以通过单次激光扫描检测所有障碍物，因此在该实验中不发生轨迹再生。走廊初始化，走廊生成和轨迹生成分别仅需0.003,0.013和0.051秒。

图 13 室外实验场景

Abstract 

        We present an online method for generating collision-free trajectories for autonomous quadrotor flight through cluttered environments. We consider the real-world scenario that the quadrotor aerial robot is equipped with limited sensing and operates in initially unknown environments. During flight, an octree-based environment representation is incrementally built using onboard sensors. Utilizing efficient operations in the octree data structure, we are able to generate free-space flight corridors consisting of large overlapping 3-D grids in an online fashion. A novel optimization-based method then generates smooth trajectories that both are bounded entirely within the safe flight corridor and satisfy higher order dynamical constraints. Our method computes valid trajectories within fractions of a second on a moderately fast computer, thus permitting online re-generation of trajectories for reaction to new obstacles. We build a complete quadrotor testbed with onboard sensing, state estimation, mapping, and control, and integrate the proposed method to show online navigation through complex unknown environments.

如果你对本文感兴趣，想要下载完整文章进行阅读，可以关注【泡泡机器人SLAM】公众号。

点击阅读原文，即可获取本文下载链接。

欢迎来到泡泡论坛，这里有大牛为你解答关于SLAM的任何疑惑。

有想问的问题，或者想刷帖回答问题，泡泡论坛欢迎你！

泡泡网站：www.paopaorobot.org

泡泡论坛：http://paopaorobot.org/bbs/

泡泡机器人SLAM的原创内容均由泡泡机器人的成员花费大量心血制作而成，希望大家珍惜我们的劳动成果，转载请务必注明出自【泡泡机器人SLAM】微信公众号，否则侵权必究！同时，我们也欢迎各位转载到自己的朋友圈，让更多的人能进入到SLAM这个领域中，让我们共同为推进中国的SLAM事业而努力！

商业合作及转载请联系liufuqiang_robot@hotmail.com