第6期 曹鹏飞，等：面向多机器人动态任务分配的事件驱动免疫网络算法 ·955· 式中：g为抗原对抗体的激励表达式；1为调整参 交互量。从通信量来看，由于本系统采用混合式 数，0<<1。 结构实现，每一个机器人都拥有服务子进程专门 2.4算法流程 服务，每个服务子进程为相应机器人选择当前最 在多机器人系统中，采用混合式的结构实现 合适的任务，在服务端进行任务冲突解决，并不 文中算法，服务端通过多进程模拟机器人，实现 需要机器人实际通信解除冲突。只在任务的下达 任务的分配，可以降低网络通信消耗，每个进程 和任务反馈时需要进行通信，所以一次任务分配 与一个实际的机器人通过网络通信，保持状态同 中每个机器人的通信量是O1)。 步，多个机器并行运行。算法步骤如下： 计算量表示机器人选择一次任务所需要计算 ①初始化系统抗原抗体信息； 的时间复杂度。机器人每次选择任务，都需要进 ②计算空闲机器人与待分配任务和待协作 行m次综合激励计算，选择合适的任务，然后需 任务的综合激励值： 要进行n次比较解决任务冲突问题，当有k个机 ③各机器人自主解除冲突，选择合适的任 器人任务冲突，需要2k次计算解决任务冲突，故 务，并向任务处移动； 计算量是O(m++2)。 ④机器人判断能否完成任务，若能跳到⑥， 按照任务分配类型，文中算法满足“同时”、 否则转到⑤： “再分配”，“同时”指可以考虑多个待分配任务， ⑤机器人状态更改，事件触发，转到②，等待 “再分配”指任务能够进行重分配。这种任务分 合适的空闲机器协作； 配方法明显优于“顺序”、“无再分配”、无法适应 ⑥机器人独自或协作完成相应任务： 动态环境的算法，故不做对比。本文算法ALLI ⑦系统终止，否则转到⑧： ANCE、BLE7性能比较如表2所示。 ⑧状态更新，事件触发，转到②。 表2任务分配算法性能 算法的程序流程图如图2所示： Table 2 Task allocation algorithm performance 算法 计算需求通信需求 任务分配情况 (开始 本文算法 O(n+m+2K) 01) 可重分配、自主协作 系统初始化 ALLANCE O(mn) 0(m) 可重分配 空闲机器人综合激励计算 BLE O(mn) O(mn) 可重分配 任务选择，机器人被激励 3仿真与实验结果分析 能否完成任务 N 为了验证基于事件驱动免疫网络算法的有效 y 性，在MATLAB2012b平台上，设置动态的清理 独自或协作执行 搜集，进行多机器人实验。设计不同场景，分别 验证文中算法的动态任务分配和协作性能，以及 N 结束 机器人状态更新 系统自主处理任务死锁能力。系统监测节点可以 实时感知任务是否产生及产生的位置，而任务能 事件触发 否独自完成需要机器人任务执行过程中进行判 断，事先无法获知。 结束 3.1仿真实验及其结果分析 图2多机器人动态任务分配流程 3.1.1实验环境参数 Fig.2 Multi-robot dynamic task allocation 仿真环境设定为10m×10m的区域，实验中 2.5算法性能分析 以圆形“o”代表机器人，以正方形“口”表示任务， 多机器人系统的通信和计算消耗是任务分配 R/1代表1号机器人，且其能力值为1，T/1代表 算法中重要的衡量指标，对于维持整个系统的 任务1，且其完成需要的能力值为1，机器人的移 稳定起着重要的作用。为了和其他算法进行比 动速率设为=0.1m/s(可自行设定)，任务优先级 较，以机器人数量n和任务量m的函数形式O() 设为p=1(可自行设定，不失一般性)。算法中参数 来描述通讯量和计算量。 设置为：11=0.6,12=0.4,13=0.2,1=0.5,1=0.5， 通讯量表示机器人在一次任务选择时的信息 1=0.2,=0.6,=0.4,=0.6,C=0.6,7=5,=5。式中：gij 为抗原对抗体的激励表达式；η 为调整参 数，0<η<1。 2.4 算法流程 在多机器人系统中，采用混合式的结构实现 文中算法，服务端通过多进程模拟机器人，实现 任务的分配，可以降低网络通信消耗，每个进程 与一个实际的机器人通过网络通信，保持状态同 步，多个机器并行运行。算法步骤如下： ① 初始化系统抗原抗体信息； ② 计算空闲机器人与待分配任务和待协作 任务的综合激励值； ③ 各机器人自主解除冲突，选择合适的任 务，并向任务处移动； ④ 机器人判断能否完成任务，若能跳到⑥， 否则转到⑤； ⑤ 机器人状态更改，事件触发，转到②，等待 合适的空闲机器协作； ⑥ 机器人独自或协作完成相应任务； ⑦ 系统终止，否则转到⑧； ⑧ 状态更新，事件触发，转到②。 算法的程序流程图如图 2 所示： 开始 系统初始化 空闲机器人综合激励计算 结束 Y Y N 任务选择 , 机器人被激励 能否完成任务 机器人状态更新 独自或协作执行 结束 事件触发 N 图 2 多机器人动态任务分配流程 Fig. 2 Multi-robot dynamic task allocation 2.5 算法性能分析 多机器人系统的通信和计算消耗是任务分配 算法中重要的衡量指标[14] ，对于维持整个系统的 稳定起着重要的作用。为了和其他算法进行比 较，以机器人数量 n 和任务量 m 的函数形式 O(·) 来描述通讯量和计算量。 通讯量表示机器人在一次任务选择时的信息 交互量。从通信量来看，由于本系统采用混合式 结构实现，每一个机器人都拥有服务子进程专门 服务，每个服务子进程为相应机器人选择当前最 合适的任务，在服务端进行任务冲突解决，并不 需要机器人实际通信解除冲突。只在任务的下达 和任务反馈时需要进行通信，所以一次任务分配 中每个机器人的通信量是 O(1)。 计算量表示机器人选择一次任务所需要计算 的时间复杂度。机器人每次选择任务，都需要进 行 m 次综合激励计算，选择合适的任务，然后需 要进行 n 次比较解决任务冲突问题，当有 k 个机 器人任务冲突，需要 2k 次计算解决任务冲突，故 计算量是 O(m+n+2k)。 按照任务分配类型，文中算法满足“同时”、 “再分配”，“同时”指可以考虑多个待分配任务， “再分配”指任务能够进行重分配[16]。这种任务分 配方法明显优于“顺序”、“无再分配”、无法适应 动态环境的算法，故不做对比。本文算法 ALLI￾ANCE[4] 、BLE[17] 性能比较如表 2 所示。 表 2 任务分配算法性能 Table 2 Task allocation algorithm performance 算法 计算需求 通信需求 任务分配情况 本文算法 O(n+m+2K) O(1) 可重分配、自主协作 ALLANCE O(mn) O(m) 可重分配 BLE O(mn) O(mn) 可重分配 3 仿真与实验结果分析 为了验证基于事件驱动免疫网络算法的有效 性，在 MATLAB 2012b 平台上，设置动态的清理 搜集，进行多机器人实验。设计不同场景，分别 验证文中算法的动态任务分配和协作性能，以及 系统自主处理任务死锁能力。系统监测节点可以 实时感知任务是否产生及产生的位置，而任务能 否独自完成需要机器人任务执行过程中进行判 断，事先无法获知。 3.1 仿真实验及其结果分析 3.1.1 实验环境参数 仿真环境设定为 10 m×10 m 的区域，实验中 以圆形“○”代表机器人，以正方形“□”表示任务， R1 /1 代表 1 号机器人，且其能力值为 1，T1 /1 代表 任务 1，且其完成需要的能力值为 1，机器人的移 动速率设为 v=0.1 m/s(可自行设定)，任务优先级 设为 p=1(可自行设定，不失一般性)。算法中参数 设置为：λ 1=0.6，λ 2=0.4，λ 3=0.2，λ 4=0.5，λ 5=0.5， λ6=0.2，α=0.6，β=0.4，η=0.6，C=0.6，T=5，n=5。 第 6 期 曹鹏飞，等：面向多机器人动态任务分配的事件驱动免疫网络算法 ·955·