免疫算法在路径规划中的应用

免疫算法在路径规划中的应用

【摘要】本文中模拟生物免疫过程，建立了免疫算法的数学模型。并研究了它在静态和动态环境下移动机器人的路径规划中的应用。并验证其应用的有效性。

【关键词】免疫算法;智能车路径规划;仿真实验

Abstract：this article simulated biological immune process，and established the mathematical model of immune algorithm.It is studied the application of mobile robot path planning in static and dynamic environment.

Key words：Immune algorithm;Intelligent vehicle path planning;Simulation experiment

1.概述

随着机器人相关技术的发展，对于智能车辆控制的准确性要求越来越高，控制系统的数学模型的好坏直接影响着控制的有效性和准确性。智能算法用于建模困难或本质为非线性或复杂对象的控制系统，效果优于常规控制方法，若系统的转动惯量，结构参数等存在误差是仍能实现精确跟踪，鲁棒性良好。

为解决路径规划及壁障问题，我们在局部环境中，出现智能车辆必须放弃期望轨迹避开障碍物的情况下，研究基于免疫算法的智能车辆避障控制方法：首先在局部环境下，生成占有栅格地图;再生成障碍物的极坐标柱状图;设计了基于免疫算法的车辆避障方法。

2.免疫算法

人工免疫系统（Artificial Immune Sys-tem，简称AIS）是在免疫学及其理论的基础上发展而来的，因此需对生物免疫系统进行研究。生物免疫系统是复杂程度很高的系统，在检测和消除干扰问题上表现出了精确的调节能力。免疫系统展示了许多可以将其融入人工智能系统的性质：如多样性、动态性、适应性、鲁棒性、自适应、自治性、自我监测、错误耐受等等。

在免疫算法用于路径规划中，我们有如下，如表1所示。

表1 对应关系

免疫系统 路径规划

障碍物 抗体

可行栅格 抗原

亲和力 路径选择可行度

抗体变异 动态障碍物

算法步骤：

考察车辆的路径规划问题，智能车从初始点gs出发，寻找一条通往目标点的最优路径。如果智能车某时刻ti位于栅格点的gi，那么它下一步必然选择gi周围的可行栅格。

步骤1：确定载入的抗原（障碍物），随机产生初始抗体即随机产生候选解，创建一个总量为N的初始种群抗体集合P（可行栅格）。

步骤2：计算抗体亲和力：对于每个vP，评估g（v）和创建克隆种群C，亲和力g设为对应的函数。

步骤3：从种群C中选择n个亲和力最高的抗体形成临时抗体集v’。

步骤4：克隆亲和力高的抗体：克隆上一步n个亲和力最高的抗体，其中每个抗体被单独克隆，抗体亲和度越高，被克隆的抗体规模越大。通过评估g（v’），如果g（v’）>g（v）那么通过克隆v’取代v。即，选择路径最优。

其中：

（1）

g（v）是抗体克隆总数量，是一个克隆因子，N是抗体集合P的总数量，i是以递减排序的最有抗体序号，ceil是向上取整算子。通过上述的条件判断和克隆取代操作，可使最优抗体的规模逐步扩大。

步骤5：对新的种群中的部分抗体进行变异操作（加入动态障碍物）。

步骤6：重新计算变异后的亲和力并令n加1，重复第四步操作。

步骤7：判断gi是否满足终止条件，即是否到达目的地gd;若不是返回步骤2，将gi设为gi+1，否则算法结束，输出最优路径。

3.免疫算法路径规划仿真

3.1 环境模型

假定：①移动机器人在二维有限空间中运动;②机器人的工作空间中分布着

有限个障碍物;③把障碍物边界向外扩展机器人体在长、宽方向上最大尺寸的l/2，机器人中心位置可用点来表示，即所谓“点机器人”。

记A为移动机器人R在二维平面上的凸多边形有限运动区域，以A的左下角为坐标原点，水平向右为X轴正方向，垂直向上为Y轴正方向，建立直角坐标系XOY，则有A在X、Y轴上的最大值分别为Xmax和Ymax。以占为步长将X，Y分别进行划分，由此形成环境的栅格图表示。每行的栅格数Nx=Xmax/，每列的栅格数NY=Ymax/，考虑到A为任意形状，可在其边界补以障碍栅格，使其成为正方形或者是长方形。每个障碍物至少占有一个栅格，当不满一个栅格时，算一个栅格。任意一个栅格g，都有确定的坐标g（x，y）及相应的序号S，其中x为g所在的行号，y为g所在的列号。定义g（l，l）的序号为1，g（l，2）的序号为2，…，则坐标g（x，y）与序号S之间的关系可表示为：

式中，mod为求余运算，int为舍余取整运算，i=l，2，…，M，M为地图中栅格的总数。由此，我们可构建一个8x8的栅格地图如图1所示。

3.2 静态路径规划

为了验证算法的有效性，我们建立了在各种复杂环境下，只要有通路存在，本算法都可以迅速的规划出最优路径。如图2所示。

图1 栅格地图

图2 最优路径

3.3 动态路径规划

本实验的目的是让移动机器人避开所有的障碍物，并且追捕到运动目标。即，通过变异操作实现动态障碍物的克隆取代。其仿真结果如图3（a）、（b）、（c）在动态障碍物，在不同位置时的路径规划。只要存在到达目标点的通路，本算法必能快速的规划出最优路径。

图3 动态路径规划

4.结论

本文研究了静态和动态环境下移动机器人的路径规划问题。首先，描述了仿真环境建立，然后，较为详细地介绍了免疫算法，并研究了它在静态和动态环境下移动机器人的路径规划中的应用。并验证其应用的有效性。

参考文献

[1]Farmer J，Packard N，Perelson A.The immune system，adaption，and machine learning.Physical D：Nonlinear Phenomena，1986，22（1-3）：187-204.

[2]Dasgupta D.Artificial neural networks and artificial immune systems：Similarities and differences.Proceedings of IEEE International Conference on systems，Man，and Cybernetics，1997：873-878.

[3]邓志燕，陈炽坤.基于改进遗传算法的移动机器人路径规划研究[J].机械设计与制造，2010，7.