机器人路径规划简述.ppt

1、机器人路径规划简述,主讲人：徐杰,何谓路径规划,路径规划是指,在具有障碍物的环境中,按照一定的评价标准,寻找一条从起始状态到目标状态的无碰撞最优路径的过程. 案例,机器人路径规划的方法,一.传统方法 1)自由空间法 2）图搜索法 3）栅格解耦法 4）人工势场法,二.智能方法 1)模糊逻辑法 2）遗传算法 3）神经网络法,遗传算法,遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法.,遗传算法的原理,遗传算法是的思想源于生物遗传学和适者生存的自然规律，是具有“生存+检测”的迭代过程的搜索算

2、法遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索其中，选择、交叉和变异构成了遗传算法的遗传操作参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容,算法过程如下,步骤1：初始化，随机产生一个规模为P的初始种群，其中每个个体为二进制位串的形式，也就是染色体，每个二进制为称为基因。步骤2：计算适应度，计算种群中每个个体的适应度。步骤3：选择，选择是指从群体中选择优良的个体并淘汰劣质个体的操作。它建立在适应函数评估的基础上。适应度越大的个体，被选择的可能性就越大，它的下一代的个数就越多。选择出来的个体放入

3、配对库中。步骤4：交叉，从种群中随机选择两个染色体，按一定的交叉概率进行基因交换，交换位置的选取也可以是随机的。步骤5：变异，从种群中随机选择一个染色体，按一定的变异概率进行基因变异。步骤6：若发现最优解或者到达迭代次数，则算法停止。否则，转步骤2。,举例说明,从前，一群扇贝在海岸边悠哉游哉地生活着。它们衣食不愁，连房子也有了着落，担忧的只有一件事：每隔一段时间，总有人来挖走它们之中的一部分。有意思的 是，这个人的家族以Firefox的图标作为纹章，所以他总是选择那些花纹长得比较不像Firefox图标的扇贝。经过几十万代的繁衍后，扇贝壳上的图案 逐渐变得与Firefox图标相差无几。,利用遗传

4、算法解决TSP问题,要解决TSP问题，首先要决定推销员路线的方法，最自然的方式是路径表法每个城市用字母或数字标明，城市间的路径用染色体表示，用合适的遗传操作来产生新的路线假设有七个城市，用l7来表示，在一个染色体中，整数的顺序表示推销员参观城市的顺序例如，染色体1653427表示右图所示的路线，销售员从城市1出发，到所有的其他城市参观一次并回到出发点。,遗传算法的应用,由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁

5、棒性，所以广泛应用于许多科学。,函数优化,函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。,组合优化,随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP问题非常有效

6、。例如遗传算法已经在求解旅行商问题、 背包问题、装箱问题、图形划分问题等方面得到成功的应用。 此外，GA也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。,遗传算法的应用,例如：著名的旅行推销问题(TSP)：给定有限个城市N，以及两个城市之间旅行的费用(或距离)，要找出花费最少(或路程最短)的路线，而每个城市都能到达，且仅到达一次后回到出发点这样的问题很难通过组合搜索技术得到解决TSP问题的搜索空间包含N个城市的所有可能组合，因此搜索空间的可能大小为N!因为城市的数目可能很大，因此逐条路径地检查是不可行的,总结,遗传算法对于复杂的优化问题无需建模和进行