规划算法：让机器人编队能避开移动的障碍物

麻省理工学院的研究人员，研究出一种机器人团队规划算法，让机器人团队能够避开移动的障碍物。...

普通机器人团队的规划算法

单个机器人的运动往往要靠控制算法，来检测障碍，规划路径，执行动作。而一组机器人组成的团队一起运动，则需要更加可靠的规划算法来保证，避开障碍和相互冲突。

机器人团队的规划算法分为两种：一种是集中式算法，让单个电脑决定整个团队的行动。另外一种是分布式算法，让每个机器人根据自己的观察，自己做决定。

在集中式算法中，一旦中央控制的电脑脱机，整个系统将分崩离析。分布式算法，则能够更好的处理通信不稳定的情况，但是设计却比较大，因为每个机器人都要都要去猜测其他的机器人在做什么。许多关于分布式算法的研究，更多专注于做更加可靠的集体决策，而不是在机器人环境中，如何避开障碍物的问题。

新算法的效果

在五月份的国际机器人和自动化的会议上，MIT的研究人员将展示一种，对于一组机器人的分布式计划算法，不仅可以避开静态的障碍物，而且包括移动的障碍物。新算法相对于目前的分布式算法，大大减少了对于通信带宽的要求，其强大的数学能力，保证机器人可以避免冲突。

在一组小型无人机编队的模拟中，分布式算法，执行了和集中式算法一样的飞行计划。无人机组成了他们喜欢的队形，一个固定高度的正方形，为了避免障碍物，正方形进行了旋转，并且无人机之间的距离缩短了。偶尔的情况下，无人机将单飞，或者形成一种队形，他们中间的一双，在不同的高度飞行。

新算法的原理

Daniela Rus，麻省理工学院电子工程和计算机科学系的教授，以及计算机科学和人工智能实验室的主任，他的小组开发了这种算法，说道：

“因为这种算法完成了许多有挑战性的目标，这真让人兴奋。一组机器人具有一个本地目标，来保持队形。一个全局目标，即他们要去哪里或者沿着何种轨道移动。你让他们在静态障碍物，和意料不到的动态障碍物的环境中飞行，并且保证他们将记住本地和全局目标。虽然他们必然会产生一些偏差，但是这些偏差很微小。

交换地图

在一个典型的分布式小组规划算法中，每个机器人都会向他的队友们广播它对于环境的观察，并且所有的机器人在保持队形的基础上，将执行同样的规划算法。

但是研究人员发现一种减少计算和通信负载的方法，通过一致性规划来实现。这个根本的算法是，每个机器人，在他们自己的观察基础上，在即时的周围环境中，映射出一个无障碍的区域，并且只将这个地图传送给它最近的伙伴。当机器人从邻居那里接收到地图，它自己计算出地图上的交叉点，并且继续传递。

这样降低机器人通信数据的大小，描述了100张地图的交叉点，相对于两个地图，并不需要更多的数据。同时，也减少了需要通信的机器人的数量，因为每个机器人只和他们的邻居通信。然而，最终每个机器人都有一张地图，反射出他们团队成员检测出的障碍。

四维地图

.

地图不是三维的，而是四维的。第四个维度是时间。这就是算法能计算出移动障碍物的原因。一张三维的地图必须在几秒钟时间内，检测障碍物地点的改变，所以产生了这样的四维地图。但是，它以一种在数学上紧凑的方式来处理。

算法假设障碍物有恒定的速度，现实世界可能不是这样。但是，每个机器人一秒钟几次更新他们的地图，在一个足够短的时间内，加速度物体的速度不会动态改变。

研究的进展

在最新的地图基础上，每个机器人计算出轨道，最大化他们的本地目标，保持队形，以及它的全局目标。研究人员也在轮式机器人上测试他们的算法，目标是一起在房间内，携带一个物体。同时，人类也在机器人周围移动，来模仿人和机器人共同工作的环境。如果大家有什么关于物联网，智能硬件，创新方向的技术或者产品问题想了，请写评论告诉IntelligentThings，我会定期参看大家的问题，并选择一些来回答。

    关注 IntelligentThings