机器人足球第四章多机器人规划.ppt

第四章 多机器人规划,2,内 容 提 纲,为什么需要多个机器人完成任务？ 多机器人系统的分类 多机器人系统的路径规划思想,3,1. 多机器人系统的必要性,通过群体行为完成某种任务在自然界中无处不在。 如，蜂群，蚁群，菌群 虽然有的任务中只需要单个机器人，但是有的任务需要多个机器人。比如，探索一个未知的星球，推动物体，清理有毒垃圾。,4,多机器人系统相对单机器人系统的优势 在某些情况下，使用多个小的、简单的机器人比使用一个大的、复杂的机器人完成任务具有更高的效率 设计者可以选择一些折衷的设计方案 更加经济，可扩展，具有更好的抗失败能力 简单机器人比复杂机器人的造价低 多机器人系统可包含不同数量的简单机器人 多个简单机器人执行任务失败的概率比单个复杂机器人执行任务失败的概率低,5,群体机器人系统的两个极端 一个群体可以由完全自治的机器人组成，它们两两之间可以通信。 另一个群体由受远程控制的多个附属物组成，而整个群体可以看成是一个具有分布式执行器的单机器人系统。,6,多机器人系统称为群体机器人系统（Collective of Robots），或者叫蜂群（Swarm），表示为ri 机器人成员在功能上不存在依赖性，也不存在持久的物理连接 由单个机器人构成的系统为单机器人系统，表示为R,7,2.从多Agent角度对任务的分类,2.1 本质上需要多Agent才能完成的任务 两把距离遥远的钥匙，必须被同时旋转才能打开某一扇门（需要多个Agent） 两把距离较近的钥匙，必须被同时旋转才能打开某一扇门（需要一个Agent） 两把距离遥远的钥匙，必须在一段时间内均被旋转才能打开某一扇门（需要一个飞速的Agent）,8,注：两个Agent只有通过通信才能完成以上任务 执行任务的初始时，通过同步时钟，然后约定在某个时刻同时旋转钥匙 在一个Agent旋转钥匙的同时，发信号给另一个Agent,9,2.2 传统上，由多个Agent完成的任务 现代运输、工业生产（流水线）、农业、渔业 这类任务的特点： 执行任务之初，Agent相互通信用于分配任务 每个成员单独执行任务，忽略其他成员的存在 这类系统的缺点 群体成员未感知到的任务不会被完成,10,2.3 本质上由单Agent完成的任务 在单个地点上的单任务 这些任务的解决不宜采用多Agent群体,11,2.4 用多Agent系统解决的效果可能比单Agent更好的任务 例1：在一个有限区域寻找一个特定物体的任务，群体ri比单个机器人R完成任务的速度可能更快 但是，ri完成任务的速度不一定比R更快。取决于两个因素：群体成员之间的通信和单个成员与R的能力的接近程度。,12,如果群体成员不通信，可能发生什么情况？ 如果群体成员的能力比R的能力弱，可能发生什么情况？ 例2：排雷、清除航空母舰甲板上的异物。使用群体ri比单个机器人R，更加可靠 成员很容易被损伤 单个成员的失败不会导致任务执行的失败，而R的失败必然导致任务执行的失败,13,在2.4这类任务中，群体成员之间的通信对群体完成任务的性能具有重要的影响 通信的方式有两种：直接的、间接的 直接通信：成员带有一个专门的通信管道 间接通信：一个成员使用感知器观测其他成员的行为 问题：成员间通信的量越大，则系统的性能就越高么？,14,3. 机器人群体系统的分类角度,Dudek等人提出了以上7个角度，用于分类多Agent系统。,15,3.1 群体规模(Collective Size),SIZE-ALONE: 单机器人系统 SIZE-PAIR：双机器人系统 SIZE-LIM：多机器人系统。成员数目n相对于任务规模来看比较小。 SIZE-INF：规模无限的机器人系统。 问题： SIZE-LIM型群体和SIZE-INF型群体执行搜索任务时，哪个完成任务的可能性更大？我们总能使用SIZE-INF型群体么？,16,3.2 通信范围（Communication Range）,COM-NONE：机器人成员不能直接与其他机器人通信，智能通过感知器观测到对方的存在、不存在和行为。成员之间也不可以互发信号 COM-NEAR：机器人成员只能与其附近的机器人通信（距离可以物理空间上的距离也可以是拓扑空间上的距离） 拓扑空间距离的例子：军队中的士兵由树形的结构组织 COM-INF：一个机器人成员可以与其它任意机器人通信,17,3.3 通信的拓扑结构(Communication Topology),广播式通信 按地址通信 树形通信 网状通信,18,3.4 通信带宽（Communication Bandwidth）,通信影响群体的性能：如果成员具有专用的通信通道，则处理通信的时间很短；如果成员在通信时不能进行其他动作，那么通信代价就高。 BAND-INF：在这种群体中，通信是无代价的。 BAND-MOTION：通信代价与移动成员的代价成正比。 例如：蜂群中，蜜蜂通过跳八字舞进行通信。传递的信息与跳舞的运动代价成正比,19,BAND-LOW：通信代价高。远远高出将一个机器人丛一个位置移动到另一个位置的代价 BAND-ZERO：无通信，任何成员无法感知到其他成员,20,3.5 群体的可重配置程度（Collective Recongurability）,指 群体在空间上重新组织的速度。 蜂群中的成员可根据其他成员的空间位置快速改变自身的空间位置。以固定步伐前进的部队和高速公路上的汽车重新配置空间距离的速度就慢。,21,3.5 群体的可重配置程度（Collective Recongurability）,ARR-STATIC：静态组织。群体的拓扑结构式固定的 ARR-COM：群体可以通过通信进行重组 ARR-DYN：动态组织。群体中成员的拓扑关系可以任意改变,22,3.6 成员的处理能力(Processing ability of each collective unit),群体中的每个成员具有不同的计算模型。有的成员的计算模型可能比图灵机弱一些，比如，有穷状态自动机。但是，即使单个成员的计算模型简单，整个群体的计算能力可能是很强的。,23,3.6 成员的处理能力(Processing ability of each collective unit),PROC-SUM：成员的计算模型是一个非线性求和单元。例如，神经网络中的神经元。 PROC-FSA：成员的计算模型是一个有穷状态自动机。 PROC-PDA：成员的计算模型是一个下推自动机 PROC-TME：成员的计算模型是一个图灵机,24,3.7 群体的构成,群体成员可能在物理构成上是异构的。即使使用相同的物理部件，也可能在软件上是异构的。 CMP-IDENT：群体的成员均具有相同的硬件和软件 CMP-HET：群体成员具有不同的硬件，导致软件也不相同,25,3.8 群体系统的案例,研究者成功设计了多个具有相对优势的群体机器人系统 案例1：成员具有有穷状态自动机的计算模型，而群体的计算能力与图灵机接近 案例2：对于搜索任务，群体系统比单独一个移动的、能做标记的机器人更高效,26,案例3： 群体机器人中，如果每个成员都能感知到对方，可以在一个存在少量路标的环境中进行自我定位，而单个机器人不能。 案例4： 在无路标环境中，群体机器人可以通过相互感知实现自我定位。,27,4. 多机器人规划的基本思想,多Agent系统（Multi-Agent System, MAS）：在同一环境中，存在协作关系的多个Agent组成的系统。 特点：控制多Agent系统的路径规划系统的复杂度随着移动Agent的数目呈指数级别增长,28,单Agent路径规划方法不能用于求解多Agent规划问题，原因包括: 成员之间要避免碰撞 成员之间要避免死锁 多Agent规划系统的难点包括： 计算代价 信息交换策略 通信代价,29,4.1 对障碍物的分类,Usually other agents are modelled as unscheduled, non-negotiable, mobile obstacles in MASPPs. Category of Obstacles from Arai et. al. (89),30,4.2 多Agent系统的规划方法,集中式（Centralised Approaches） 分散式（Decoupled Approaches） 组合式（Combined Techniques）,31,4.2.1 多Agent系统的集中式路径规划方法,使用一个方法对所有的Agent的路径进行规划 优点： 可以找到最优解 使用系统的全部信息 缺点： 计算复杂度随着Agent的数目呈指数级别增长 对一个Agent的规划失败，则无法继续对其他Agent进行规划,32,4.2.2 多Agent系统的分散式路径规划方法,该方法首先为每个机器人Ri计算一条相应的规划解Plani，然后处理这些解之间的路径冲突，如果解决冲突成功则将规划解作为每个机器人的路径规划解，否则返回“无解”。 优点： 一个Agent的路径的计算时间和相邻Agent的数目成正比 具有健壮性 缺点： 不完备：为什么？例：多Agent系统内有两个机器人R1和R2，对于它们的目标，R1存在两个规划解Plan11,Plan12，R2存在两个规划解Plan21,Plan22，并且Plan11和Plan21之间的冲突是无法解决的。那么，如果分散式规划方法首先为R1计算出Plan11、为R2计算出Plan21，由于Plan11和Plan21的冲突无法解决，分散式规划方法将返回“无解”。然而，实际上，Plan11和Plan22是该多Agent规划问题的一个解，未被分散式方法计算出，因此说，分散式方法是不完备的。,33,4.2.3 多Agent系统的组合式路径规划方法,Use cumulative information for global path planning, use local information for local planning（使用累积的信息对单个Agent的全局路径进行规划，使用本地信息对该Agent局部的路径进行规划） “Think Global Act Local”,34,Thinking Globally 对于一个Agent，计算从其从当前位置到目的位置的完整路径 使用A*算法完成,35,Act Locally： 为了避开障碍物，采用反应式的规划方法，基于局部信息进行路径规划 优点是： 不需要环境的全部信息； 制定决策的过程快速,36,反应式避障规划的思想 根据成员的优先级进行反应（Priority assignment） 根据规则进行反应（Rule-Based methods） 例如：出于左侧的Agent首先运动,