【SI】梯度算法技术分析——本科拼字母10 doc

1、.梯度算法技术分析梯度算法技术分析上海交通大学软件学院嵌入式实验室群体智能组(SI)之本科拼字母小组修订历史记录日期版本说明作者2010-7-5<1.0>初始版本吴杰蔚，张昕目录梯度算法技术分析1修订历史记录21算法简介32算法分析32.1势能的表示32.2机器人的控制43算法优缺点43.1优点43.2缺点44软件实现中的问题及解决方案55硬件实现的难度65.1全局坐标的感知65.2斥力与碰撞力的模拟66参考资料61 算法简介梯度算法是由美国宾夕法尼亚大学GRASP实验室提出的一种用于Pattern Formation的算法。Pattern Formation是指控制一组机器人协同

2、工作共同形成或维持一种特定的图形。梯度算法灵感来自于地形与水流的物理模型。简单的说，就是将目标图形设置为地形的最低处，机器人模拟的是一滴一滴的水滴，最终机器人将从高地形往低地形走，且其相互之间还受到碰撞力和引力的影响，最终构成指定的图形。而梯度算法主旨就是模拟出这样一个势能的模型。2 算法分析2.1 势能的表示描述该算法的论文题目是Controlling Swarms of Robots Using Interpolated Implicit Functions，从题目就可看出本算法是使用隐式函数来表示的，地形上每点的地势（势能）高低使用f(x,y)表示，图形上的点f(x,y)=0，不在图形上

3、的点f(x,y)>0，用颜色来表示，大概如下图：白色部分为图形至于如何将图形转换为隐式函数，论文中是以插值的方式实现的，具体来说，分以下几步：1. 确定图形上的几个点p1，p2，p3，pn。2. 给出函数: 其中|qi-pj|表示2点间的欧几里德距离，h是一个合适的距离计算函数，论文中给出了一个函数是。3. 将图形上已确定的点带入解出未知数w1，w2，wn，由此确定隐式函数。2.2 机器人的控制机器人的控制由以下3个函数给出： （上面的点号表示导数）其中qi表示位置，vi表示速度，ui表示加速度，第三个函数中，第一项为梯度项，第二项为运动阻力，第三项为斥力，第四项为碰撞力。其中斥力只在图

4、形附近出现，目的是让机器人在图形上均匀分布，同时避免任务分配的问题。3 算法优缺点3.1 优点l 避免了机器人之间的大量通讯。当势能图传给每个机器人的时候，每个机器人即按照已知的势能图走即可，除了在势能发生变化的时候需要通讯外，其他时候都不需要。l 无需为每个机器人自动设置路径，只要往低势能方向走即可。l 不需要考虑任务的分配，通过引力与斥力自动调整机器人在图形中的位置。3.2 缺点l 需要知道大量全局坐标信息。l 控制函数中的常数难以确定。l 控制函数过于复杂，难以实现。4 软件实现中的问题及解决方案由于论文算法中的方法过于复杂，我们对算法进行了简化实现。l 问题：要根据隐函数公式，计算出梯

5、度算子难度比较大解决：将其简化，直接对图形栅格化，做成离散的势能函数，具体方法是确定最低点（图形上的点）后，利用floodfiil的方法计算每个点到图形上的点的最短距离，作为势能值。离散化的势能：l 问题：梯度算法中用斥力和碰撞力来避免任务分配，但是实际操作中，引力和斥力模型的调整系数很难调整，效果很不理想解决：将斥力和碰撞力去除，但这样会引入避障与任务分配的问题，我们通过将到达目的点机器人修改地形中的势能来避免避障问题（就是将达到的点抹去，重新计算势能），以及机器人的任务分配问题，做下来，效果不算理想，容易出现死锁的问题。死锁的一个例子（唯一比自己低的位置被其他个体所占据）：5 硬件实现的难

6、度5.1 全局坐标的感知这个算法要求每个机器人拥有共同的坐标系。那么如何保证机器人之间的坐标系是相同的是不太容易实现的。l 如果预先设置好机器人初始的位置，那么在行走的过程中出现走偏，走歪等对坐标系的偏差就会加大，之后构造的图形与原来的图形之间就会不一样。l 如果使用GPS定位，限于精度的原因，在较小的环境内，很难有较好的效果。5.2 斥力与碰撞力的模拟以现有的传感设备模拟出机器人相互之间的排斥的效果是十分困难的。机器人本身的控制精细度也不能达到斥力所能反应的精细度。而碰撞力，由于碰撞的实际情况过于复杂，难以准确估算它对控制产生的影响。6 参考资料2005-C Luiz Chaimowicz, Nathan Michael and Vijay Kumar. “Controlling Swarms of Robots Using Interpolated Implicit Functions”. Proceedings of the 2005 IEEE International