让无人驾驶飞机四处飞行而不打击事物并非易事。障碍物检测和运动规划是计算机科学中最棘手的挑战之一，因为创建实时飞行计划可以避免障碍并处理风和天气等惊喜。

  在本周公布的一对项目中，来自麻省理工学院计算机科学与人工智能实验室(CSAIL)的研究人员展示了一种软件，它允许无人机停在一角硬币上，在模拟的“森林”中的26个不同障碍物的上方，下方和周围进行发夹运动“。

  一个团队的视频显示了一个小型的四旋翼飞行器通过障碍线和PVC管道进行甜甜圈和八卦。无人机的重量仅为一盎司，从转子转子到转子的距离为3.5英寸，可以以每秒1米的速度飞过10平方英尺的空间。

  该团队的算法可在线获得，之前曾用于计划去年的DARPA机器人挑战中 CSAIL的Atlas机器人的足迹，将空间划分为“无障碍区域”，然后将它们连接在一起以找到一条无碰撞路线。

  “不是根据环境中障碍物的数量来规划路径，而是可以更容易地看到逆向：无人机通过的”免费“空间段，”最近的毕业生Benoit Landry '14 MNG说道。 '15，谁是刚刚接受IEEE机器人与自动化国际会议(ICRA)的相关论文的第一作者。“使用自由空间段是一种更”玻璃半满“的方法，对于小而杂乱的空间中的无人机来说效果更好。”

  在第二个CSAIL项目中，博士生Anirudha Majumdar展示了一架固定翼飞机，保证在没有任何先进的空间知识的情况下避开障碍物，甚至面对阵风和其他动力。他的方法是预先编写一个包含数十个不同“漏斗”的库，这些漏斗代表系统的最坏情况，通过严格的验证算法计算得出。

  “当无人机飞行时，它不断搜索图书馆，将一系列计算保证的路径拼接在一起以避开障碍物，”Majumdar说道，他是相关技术报告的第一作者。“许多单独的漏斗都不会没有碰撞，但是如果有足够大的库，你可以确定你的路线是清晰的。”

  两篇论文都是由麻省理工学院教授拉斯泰德拉克共同撰写的; ICRA论文将于5月在瑞典发表，也由博士生Robin Deits和Peter R. Florence共同撰写。

  无人机高密度

  鸟可能会让它看起来很简单，但飞行是一项非常复杂的工作。飞行物体可以在六个不同的方向上改变位置 - 前进/后退(“喘振”)，上/下(“起伏”)，左/右(“摇摆”)，以及通过前后旋转(“俯仰”) )，左右(“滚动”)和水平(“偏航”)。

  Majumdar说：“在每个时刻都需要12个不同的数字来描述系统的位置以及移动的速度，同时跟踪空间中可能妨碍你的其他物体。” “大多数技术通常无法实时处理这种复杂性。”

  一种常见的运动规划方法是通过诸如“ 快速探索随机树 ”之类的算法对整个空间进行采样。尽管通常有效，但基于采样的方法通常效率较低，并且难以在障碍物之间导航小间隙。

  兰德里的团队选择使用Deits新的基于自由空间的技术，他将其称为“半定规划迭代区域通胀”算法(IRIS)。然后，他们将IRIS与“混合整数半定规划”(MISDP)相结合，为每个“无空区域”分配特定的航班运动，然后执行整个计划。

  为了感知周围环境，无人机使用了运动捕捉光学传感器和车载惯性测量单元(IMU)，可帮助估算障碍物的精确定位。

  罗格斯大学(Rutgers University)计算机科学助理教授余敬进表示：“我对团队的板上传感器结合在一起以确定无人机位置的巧妙技术给我留下了最深刻的印象。” “这是系统为每组障碍创建独特路线的关键。”

  在目前的形式中，MISDP已经过优化，无法进行实时规划; 创建障碍路线的路线平均需要10分钟。但兰德里表示，做出某些牺牲会让他们更快地制定计划。

  “例如，你可以更广泛地将'自由空间区域'定义为两个或多个自由空间区域重叠的区域之间的联系，”兰德里说。“这将让你通过这些链接解决一般的动作计划，然后用所选区域内的特定路径填写细节。目前，我们同时解决这两个问题以降低能耗，但如果我们想更快地运行计划，那将是一个不错的选择。“

  与此同时，Majumdar的软件产生了更为保守的计划，但可以实时实现。他首先开发了一个由40到50个轨迹组成的库，每个轨道都有一个外部界限，无人机可以保留在其中。这些边界可以被视为“漏斗”，规划算法在其间选择将一系列步骤拼接在一起，使无人机能够在飞行中规划其飞行。

  像这样灵活的方法可以提供高水平的软件保证，即使面对周围环境和硬件本身的不确定性。该算法可以很容易地扩展到不同大小和有效载荷的无人机，以及地面车辆和步行机器人。

  至于环境，想象一下无人机在进行强力滚动操作之间做出选择，这将大大避开树，而不是直接飞行并避开少量树。

  “传统方法可能更喜欢第一种方法，因为大量避开障碍似乎更安全，”Majumdar说。“但这样的举动实际上可能更具风险，因为它更容易受到阵风的影响。我们的方法可以实时做出这些决定，如果我们希望无人机离开实验室并在现实场景中运行，这一点至关重要。“

  避开障碍的明确途径

  CSAIL的研究人员多年来一直在研究这个问题。Nick Roy教授一直在研究无人机的算法，以开发地图并实时避开物体 ; 11月，由博士生Andrew Barry领导的一个团队发布了一个视频演示算法，允许无人机以每小时30英里的速度在树木间飞镖。

  虽然这两架无人机的行程速度不如巴里那么快，但它们的演习通常更复杂，这意味着它们可以在更小，更密集的环境中航行。

  Yu说：“实现小型，现成的四轴飞行器的动态飞行是一项了不起的成就，也是一项具有许多潜在应用的成果。” “通过额外的开发，我可以想象这些机器被用作难以到达的地方的探测器，从探索洞穴到在倒塌的建筑物中进行搜索和救援。”

  兰德里现在在加利福尼亚州的3D机器人公司工作，他希望其他学者能够在研究人员的工作基础上进一步完善，这些工作都是开源的，可以在github上找到。

  “对于行业来说，一个巨大的挑战是确定哪些技术实际上足够成熟，可以用于实际产品，”兰德里说。“最好的方法是进行专注于所有角落情况的实验，并证明像这样的算法实际上可以在99.999%的时间内工作。