机器人行走问题介绍.pdf

机器人行走问题 机器人行走问题 机机器器人人行行走走问问题题 摘要 摘要 摘摘要要 本文主要研究机器人在有障碍物的情况下的路径规划，并且要求机器人的行 走路径为平滑曲线。通过将机器人路径规划问题化为行走路径可行域中路径点的 选取问题，从而将其转化为图论中的最短路径问题。最后，通过对折线的平滑处 理得到机器人的最优路径。 对于路径点的选取，首先用计算机随机模拟路径点，用Floyd算法得到当前 随机路径点构成的网路图的最短路径。通过多次模拟结果的对比，缩小了各个模 拟点的选取范围，然后在此基础上提出了垂线法来选取节点，用Floyd算法得到 理论最短路径。最后，再对其做相应的平滑处理后得到最小安全距下的最短路径。 对于路径评估的两个目标函数（路径长度和安全度）的考虑，本文通过对其 分配不同的加权权重系数，将其转换为遗传算法中的适应度函数，用链接图法建 立环境模型并通过Floyd算法找出一条初始路径，并在充分考虑局部最优的可能 性下由理论最短路径选取另一条初始路径，通过比较经遗传算法优化后两条路径 的适应度函数大小，得到全局最优的安全最优路径。 对于问题一：本文在此基础上考虑最小安全条件及平滑条件，分别对3种障 碍物顶点折线的情形做出最优的平滑处理，从而得到最小安全距下的最短路径。 最后用路径长度与安全度作为路径评估的两个目标函数，通过遗传算法得到安全 最优路径。实验结果如下： 表1 问题一结果 路径 d d d RA RB RC Floyd算法 70.5075 107.9586 102.0516 遗传算法 73.3182 111.4842 108.8761 对于问题二：对于求R依次到A、B、C的最优路径的问题，本文通过在第一 问的基础上求得的dRA ，dAB ，dBC 的最优路径，再对目标点处A，B的折线进行 相应平滑处理。实验结果如下： 表2 问题二结果 路径 d RABC Floyd算法 159.3003 遗传算法 166.7941 Floyd Floyd 关键词 机器人 路径规划 计算机模拟 垂线法 FFllooyydd算法 遗传算法 1 1. 问题重述 下图是一个100×80的平面场景图，在R（0，0）点处有一个机器人，机器 人只能在该100×80的范围内活动，图中四个矩形区域是机器人不能与之发生碰 撞的障碍物，障碍物的数学描述分别为B1（20，40；5，10）、B2（30，30；10， 15）、B3（70，50；15，5）、B4（85，15；5，10），其中B1（20，40；5，10） 表示一个矩形障碍物，其中心坐标为（20，40），5表示从中心沿横轴方向左右各 5个单位，10表示