基于群体智能的图形构造 - 群体智能组（Swarm Intelligence Group）.ppt

软件学院 张昕 王琦 吴杰蔚 赵薇 指导老师 梁阿磊 群体智能(Swarm Intelligence)是近年来发展迅速的人工智能学科领域，主要思想来源于分散、自组织的动物群体和人类社会的智能行为。 粒子群算法(PSO)，蚁群算法 群体机器人(Swarm Robotics)是群体智能在多机器人学中的应用。 健壮性(Robustness)，灵活性(Flexibility)，可伸缩性(Scalability) * 针对图形构造这一多机器人协作的经典场景，提出一种基于群体智能的分布式算法。 图形构造指的是机器人个体经过交互组合成特定的全局模式的过程。 * 宾大SWARM实验室2005年提出 源于地形与水流的物理模型，定位算法 地形上每点的地势（势能）高低使用f(x,y)表示，目标图形上的点f(x,y)=0，不在图形上的点f(x,y)0。通过线性插值方法求出地形函数 * 机器人控制： 优点：通讯量小、机器人路径确定简单、任务分配简单 缺点：引入了硬件难以实现的斥力、引力，地势函数计算复杂 * 地势函数离散化，采用四连通flood fill算法计算，省去了复杂的线性方程求解 简化了机器人控制，直接选取四周空闲的最低地势点 去除了复杂的引力、斥力，引入了我们自己发明的碰撞避免和死锁处理 有关死锁处理，请参考我们主页 * 模拟器：Player/Stage平台（USC） 硬件：第三版“小老鼠”（软件学院群体智能组） * 在Player/Stage上完全实现了我们的算法，能拼出很多复杂的图形 在“小老鼠”上面基本实现了我们的算法 Demo * 算法未考虑嵌套图形处理，需修改地势函数生成方式或加入其它机制 当前硬件比较粗糙，数量较少，对算法实现制约较大。目前实验室第四版“小老鼠”己将近完成，在数量和质量上都有上升。 * 基于群体智能提出了一套分布式的图形构造算法 改进了宾大SWARM实验室的梯度算法 在模拟器和硬件平台上实现了算法 算法无法处理嵌套图形 有关项目更多请参考我们主页 * *