摘 要

近年来，家庭服务机器人作为智能机器人的重要应用渐渐进入普通人的视野，而路径规划问题作为研究移动机器人的关键点应得到充分重视。在使用栅格法建立环境地图后，本研究基于传统的遗传算法，对其进行改进后应用于室内机器人的路径规划中。传统的遗传算法产生的可行路径转角过大的问题需要被解决，文中在适应度函数中新增了转向次数参数用来约束转角问题，同时优化了交叉算子和变异算子以达到提高算法运算效率的目的，另外引入了插入算子使初始种群更灵活地产生。最后，将改进的遗传算法同传统遗传算法一并在MATLAB平台进行仿真实验，分析仿真的结果，发现与传统遗传算法相比，改进遗传算法得到的路径长度有缩短但不明显，转角过大问题改善显著同时算法运算效率也有提升。

关键词：室内机器人；路径规划；栅格法；遗传算法；适应度函数

Abstract

In recent years, as an important application of intelligent robots, home service robots have gradually entered the field of vision of ordinary people, and the problem of path planning as a key point in the study of mobile robots should be given full attention. After using the grid method to establish the environment map, this study is based on the traditional genetic algorithm, which is improved and applied to the path planning of indoor robots. The problem of excessively large turn angle of the feasible path generated by the traditional genetic algorithm needs to be solved. In this paper, the turn number parameter is added to the fitness function to restrict the turn problem, and the cross operator and mutation operator are optimized to improve the algorithm operation. For the purpose of efficiency, an insertion operator is additionally introduced to make the initial population more flexible. Finally, the improved genetic algorithm is combined with the traditional genetic algorithm to simulate the experiment on the MATLAB platform, and the simulation results are analyzed. Compared with the traditional genetic algorithm, the path length obtained by the improved genetic algorithm is shortened but not obvious, and the angle is too large Significant improvements have also been made while algorithmic efficiency has also improved.

Key Words：indoor robots；path planning；grid method；genetic algorithm；fitness function

目 录

1 绪论 1

1.1 引言 1

1.2 研究背景 1

1.3 路径规划研究现状 2

1.4 本文研究的内容 2

2 应用于路径规划的遗传算法基础理论 3

2.1 遗传算法简介 3

2.2 遗传算法基本原理 3

2.2.1. 编码设计 3

2.2.2. 初始种群 4

2.2.3. 适应度函数 4

2.2.4. 选择算子 4

2.2.5. 交叉算子 5

2.2.6. 变异算子 6

2.3 遗传算法的基本流程 7

3 移动机器人路径规划 8

3.1 环境建模 8

3.2 遗传算法路径规划方法设计 10

3.2.1. 编码方法 10

3.2.2. 初始种群的产生 11

3.2.3. 适应度函数的设计 12

3.2.4. 遗传操作的设计 13

4 仿真及结果分析 17

5 总结与展望 21

参考文献 22

致谢 23

绪论

引言

这个时代因为计算机技术的发展步伐变得越来越快，其中机器人技术作为一颗明日之星，受到很高的重视且拥有极大的发展可能。机器人技术和人工智能等名词常常出现在我国的各种发展规划中，可以说未来是机器人作为主要生产力的时代。

自主移动的智能机器人能够感知其工作空间，提取并分析来自传感器的重要数据，然后定位它在环境中的位置、识别障碍物并规划出可行的路径。路径规划所要做的就是产生从起点到目标位置的可行路径，并决定优化该路径使得机器人运动的更高效。这类自主移动的智能机器人已经成为工业、交通、农业乃至家庭日常生活中不可或缺的资源，它们广泛用于运输物资、清洁以及维护等工作。要完成这些工作，智能机器人必须具备感知、定位、规划和导航的能力，这些保证移动机器人能够根据感知到的环境信息自主地做出决策。

运动规划是机器人学里不可避免的研究课题，该课题的目的是通过传感器感知环境，提取重要信息（障碍物位置、起始位置、到达位置）^[1]。帮助建立地图模型，定位其在环境中的位置，选择一种路径规划方案并用它找到两个位置之间的最优路径，并最终从起点导航到目标点，期间要避开所有的障碍物。

研究背景

移动机器人需要的计算机技术、传感器技术和相关的控制理论发展迅速^[2]，由这些学科研究交叉得到的机器人学也有阶段性进展。相比于以前只能完成简单重复动作的初级机器人，现代智能机器人在各种智能算法的辅助下能够应用在自主性要求较高的领域，上至军用航空航天下至家用服务型机器人都有着它的身影。

移动机器人的相关研究最早可追溯到二十世纪六七十年代，从一开始机器人的目的就是自主完成给定任务，只是之前碍于技术和算法问题搁置不前。计算机技术开始快速迭代后移动机器人技术也搭着快车高速发展起来。移动机器人的实现方法各异但它的最终目的都为改变过：它要在它所在的工作环境下，利用智能算法借助控制理论完成路径规划。