用于多机器人动态路径规划的多克隆人工免疫网络算法

摘要

本发明提供一种用于多机器人动态路径规划的多克隆人工免疫网络算法，是一种改进的人工免疫网络算法，该算法将多克隆人工免疫网络应用于多移动机器人动态路径规划问题，考虑机器人之间的相互影响以及移动障碍物对机器人的影响，定义了抗体浓度的计算公式，通过克隆算子、交叉算子、变异算子和选择算子，增加了抗体的多样性，解决了传统人工免疫网络的早熟收敛问题；并通过引入记忆单元，不仅保存了特定环境抗原对应的特异性抗体，而且增加了特异性抗体的初始浓度，减少了响应时间，有效地实现了未知环境下多移动机器人动态路径规划。

主权项

1.一种用于多机器人动态路径规划的多克隆人工免疫网络算法，其特征是，包括以下步骤：（1）抗原表示：机器人上配置的外传感器，感知周围环境信息，根据当前环境信息确定抗原，抗原表示机器人周围的环境信息，以利用外传感器获得的障碍物或目标点的方位信息作为抗原，抗原决定簇表示机器人上配置的外传感器检测到的数据集，该数据集包括：在二维平面内，从机器人所在位置到障碍物所在位置的向量与机器人运动方向之间的夹角，以及从机器人所在位置到目标点所在位置的向量与机器人运动方向之间的夹角；抗原由八位二进制数表示，前四位表示从机器人所在位置到目标点所在位置的向量与机器人运动方向之间的夹角θ_rrg，后四位表示从机器人所在位置到障碍物所在位置的向量与机器人运动方向之间的夹角θ_rro，即Ag=(θ_rrg,θ_rro)；（2）人工免疫网络算法：假设多移动机器人系统中有N_r个机器人，机器人的抗体Ab_i≡θ_i,i=1,2,...,N_Ab表示该机器人下一步可能的运动方向，将[0,2π]均匀离散化为N_Ab个区间，这样，每个机器人下一步的运动方向有N_Ab个选择，也就是，N_Ab是抗体数量；N_Ab越大，[0,2π]分得越细，机器人下一步可能运动方向的选择越多，有N_Ab个选择，分别为${\theta }_i=\frac{2\pi }{N_{\mathrm{Ab}}}(i-1),i=\mathrm{1,2},...,N_{\mathrm{Ab}};$设在某一时刻，机器人通过自身配置的外传感器得到环境信息，受到抗原刺激；同一机器人不同抗体之间存在相互刺激和抑制作用；不同机器人的抗体之间也存在相互刺激和抑制作用，由于抗原刺激、相同机器人不同抗体之间以及不同机器人的抗体之间的相互刺激和抑制作用，引起抗体的浓度发生变化，其计算公式如下：$\frac{{\mathrm{dA}}_{\mathrm{ri}}\left(t\right)}{\mathrm{dt}}=(m_{\mathrm{ri}}-k_{\mathrm{ri}})a_{\mathrm{ri}}\left(t\right)+\left(\underset{l=1}{\overset{N_r}{\Sigma }}\underset{j=1}{\overset{N_{\mathrm{Ab}}}{\Sigma }}\cos ({\theta }_{\mathrm{ri}}-{\theta }_{\mathrm{lj}})a_{\mathrm{lj}}\right)a_{\mathrm{ri}}\left(t\right),$$a_{\mathrm{ri}}\left(t\right)=\frac{1}{1+\exp (0.5-A_{\mathrm{ri}}\left(t\right))},$其离散化形式为：$A_{\mathrm{ri}}\left(n\right)=A_{\mathrm{ri}}(n-1)+(m_{\mathrm{ri}}-k_{\mathrm{ri}})a_{\mathrm{ri}}(n-1)+\left(\underset{l=1}{\overset{N_r}{\Sigma }}\underset{j=1}{\overset{N_{\mathrm{Ab}}}{\Sigma }}\cos ({\theta }_{\mathrm{ri}}-{\theta }_{\mathrm{lj}})a_{\mathrm{lj}}\right)a_{\mathrm{ri}}(n-1),$$a_{\mathrm{ri}}\left(n\right)=\frac{1}{1+\exp (0.5-A_{\mathrm{ri}}\left(n\right))},$其中，表示第r个机器人的第i个抗体θ_ri的浓度变化率，i=1,2,...,N_Ab；a_ri表示第r个机器人的第i个抗体θ_ri的浓度，N_Ab是抗体数量，θ_lj和a_lj分别表示前一时刻第l个机器人的第j个抗体θ_lj和其浓度；m_ri表示第r个机器人的第i个抗体θ_i与抗原Ag之间的亲和力，k_ri表示第r个机器人的第i个抗体θ_ri的自然死亡系数，n为迭代次数，各抗体浓度初始化为$a_{\mathrm{ri}}\left(0\right)=\frac{1}{N_{\mathrm{Ab}}},$i=1,2,...,N_Ab；第一个公式由三项组成，第一项表示来自抗原的刺激；第二项表示自然死亡率；第三项表示抗体之间相互的刺激和抑制作用，其中包括机器人自身抗体之间相互的刺激和抑制作用和不同机器人抗体之间相互的刺激和抑制作用，这符合抗体在机体内不是独立存在的生物原理；第二个公式保证抗体浓度的稳定性；通过多次迭代运算，各抗体的浓度逐渐收敛，抗体的浓度水平决定对给定的抗原选择哪个抗体，也就是，机器人识别抗原，选择浓度最高的抗体对应的方向作为机器人下一步运动方向。（3）多克隆算子：当步骤（2）中人工免疫网络算法，求解得到的抗体浓度解空间中部分或全部个体趋于同一极值时，对抗体浓度解空间进行多克隆操作；多克隆算子模拟生物免疫系统的多克隆机理，不仅采用变异来实现抗体间的信息交换，而且还充分利用抗体在变化过程中已经获得的对抗原反应的特异性，进一步增加克隆的多样性；假设步骤（2）中人工免疫网络算法得到的该机器人浓度趋于同一极值的抗体有p个${\theta }_{r1}^{*},...,{\theta }_{\mathrm{rp}}^{*}=\underset{{\theta }_{\mathrm{ri}}}{\arg }\underset{i\in \{1,{...N}_{\mathrm{Ab}}\}}{\max }{a}_{\mathrm{ri}}\left(t\right),$首先将这p个抗体进行分裂，即抗体解空间中的一个点c=1,…,p分裂成q_c个相同的点每个抗体c=1,…,p分裂的个数q_c取决于该抗体与抗原之间的亲和力大小；然后，经过克隆交叉、克隆变异和克隆选择之后获得新的抗体种群；经过多克隆操作之后，抗体的多样性会增加，能够有效避免早熟收敛问题，这样，选择浓度最高的抗体作为最终的抗体，确定机器人的下一步的运动方向；（4）记忆单元：记忆单元根据生物中的二次免疫应答存储特异性抗体，并重新计算每一个抗体的初始浓度，记忆单元的引入不仅保存了特定环境抗原对应的特异性抗体，而且增加了特异性抗体的初始浓度，从而减少了响应时间；记忆单元存储的是抗原以及与此抗原相对应的特异性抗体，对于多移动机器人动态路径规划问题，记忆单元存储的是机器人遇到的环境信息以及经多克隆免疫网络算法得到的与此环境信息相对应的机器人的下一步的运动方向；在每一个记忆单元中，前八位二进制数表示为抗原Ag=(θ_rrg,θ_rro)，后面的N_Ab位对应于N_Ab个抗体，机器人在外传感器获得环境信息建立了抗原Ag=(θ_rrg,θ_rro)后，首先判断记忆单元中是否存储有这一抗原，也就是以前是否遇到过这种环境，如果记忆单元中没有这种抗原Ag=(θ_rrg,θ_rro)，则判断机器人第一次遇到这种环境，将这种环境对应的抗原Ag=(θ_rrg,θ_rro)存储到一个新的记忆单元中的前八位，该记忆单元后面的N_Ab位都初始化为0；并将各抗体浓度初始化为i=1,2,...,N_Ab，通过步骤（2）的人工免疫网络算法和步骤（3）的多克隆算子多次迭代得到了下一步的运动方向后（即浓度最高的抗体θ_rf(t)相对应的运动方向），则该记忆单元中后面的N_Ab位的第f位置为1，也就是，该记忆单元存储了与此抗原Ag=(θ_rrg,θ_rro)相对应的特异性抗体；记忆单元中存储的数据格式为：机器人在外传感器（声纳传感器）获得环境信息建立了抗原Ag=(θ_rrg,θ_rro)后，如果判断记忆单元中存储有这一抗原Ag=(θ_rrg,θ_rro)，也就是以前遇到过这种环境，那么机器人将根据该记忆单元中这一抗原所对应的特异性抗体的情况计算各抗体初始浓度，对于i=1,2,...,N_Ab，其中MC是一个与记忆单元有关的常数，MC=0.01，这样，增加了以前遇到过得抗原Ag=(θ_rrg,θ_rro)的特异性抗体的初始浓度，减少非特异性抗体的初始浓度；接着，通过步骤（2）的人工免疫网络算法和步骤（3）的多克隆算子多次迭代得到了下一步的运动方向后（即浓度最高的抗体θ_rf(t)相对应的运动方向），则该记忆单元中后面的N_Ab位的第f位置为1；（5）选择浓度最高的抗体对应的运动方向作为机器人下一步的运动方向前进一步：选择浓度最高的抗体作为最终的抗体，并将该抗体对应的运动方向作为机器人下一步的运动方向，前进一步，前进一步后，若机器人与目标点之间的距离小于10cm，结束；否则，机器人继续通过自身配置的外传感器获取新的环境信息，继续步骤(1)。