摘 要

移动机器人随着人工智能的发展在生产生活中的作用越来越重要，广泛运用于工业生产、家庭服务、灾害救险等领域，其关键技术之一是路径规划技术。智能车间内日益复杂的任务对单机器人提出了挑战，是以多机器人的路径规划受到了众多学者的关注。强化学习算法不需要建立精确的环境模型，通过“试错”的方式与环境交互，具有自学习的特点，为多机器人的路径规划提供了理论基础。本文针对传统的强化学习算法解决多机器人路径规划时学习速度较慢的问题，主要进行了以下几方面的研究：

首先，介绍了多机器人路径规划应用在车间中的研究背景，详细分析了当前多移动机器人系统及强化学习算法的发展和现状，并简单描述了本文的主要内容和组织结构。

其次，介绍了强化学习的基本知识，包括马尔科夫决策过程和四要素，简单描述了算法的过程，在此基础上介绍了几种无模型的强化学习算法。

第三，针对静态的车间环境模型，介绍了Q-learning和 Q()算法解决单机器人的路径规划问题，重点分析了Q值表、资格迹的引入以及算法的流程。通过在MATLAB中设计的仿真实验验证了算法的有效性及Q()算法的优越性，为多机器人路径规划奠定了基础。

第四，为解决多机器人系统路径规划中存在的收敛速度慢、无法动态避障的问题，利用独立式强化学习的思想减小机器人的联合状态-动作空间，将优先级引入Q()算法实现动态避障。仿真实验验证了算法的有效性，但仍存在学习速度较慢，规划路径长的问题。基于此，提出SA- Q()算法通过运用模拟退火策略改变动作选择策略来加快收敛速度，得到更优质的解。仿真实验验证了改进算法的优越性。

最后，总结本文所做的工作，并指出了有待进一步研究的问题。

关键词：多机器人；路径规划；Q-learning；资格迹；模拟退火

Abstract

As artificial intelligence develops, the effect of mobile robots in manufacturing and life is increasingly important, and they are extensively used in domains like industrial production, household services, disaster relief and so on. The key issue of mobile robot is path planning technology. The increasingly complex tasks in smart workshop pose a challenge to single robot, therefore many researchers have concerned the path planning of multiple robots. Reinforcement learning algorithms do not require the establishment of accurate environment models. They interact with the environment through "trial and error" methods and have the characteristics of self-learning, thus provide a theoretical basis for multi-robot path planning. In this thesis, in order to overcome the difficulty of slow learning speed when the traditional reinforcement learning algorithms are applied in multi-robot path planning, the main researches are as follows:

Firstly, it elaborates the background of multi-robot path planning used in workshop. Reinforcement learning algorithms and multi-mobile robot systems are presented with their development and conditions. The major idea and structure of this article are briefly described.

Secondly, the basic knowledge of reinforcement learning includes Markov decision process and four elements are introduced, and the process of reinforcement learning is briefly described. On this basis, several model-free reinforcement learning algorithms are introduced.

Thirdly, for the static workshop environment model, the Q-learning and Q (λ) algorithm is introduced to solve the path planning problem of a single robot, the Q value table, the introduction of eligibility trace and the process of the algorithm are mainly analyzed. The usefulness of the algorithm and the advantage of the Q (λ) algorithm are testified in simulation experiments designed in MATLAB, laying a foundation for multi-robot path planning.

Fourth, in order to solve the problems of slow convergence and obstacle avoidance in multi-robot system, the idea of independent reinforcement learning is used to reduce the joint state-action space, and priority is introduced into the Q (λ) algorithm to achieve dynamic obstacle avoidance. Simulation experiments testify the effectiveness of the algorithm, but there are still problems with slow learning speed and long path. Based on this, the SA-Q (λ) algorithm is raised to speed up the convergence rate and obtain a better solution by using the simulated annealing strategy. Simulation experiments testify the superiority of the improved algorithm.

Finally, it summarizes the work done in this article and the difficulties need further study.

Key Words：Multi-robot；path planning；Q-learning；eligibility trace；simulated annealing

目 录

摘 要 I

Abstract II

第1章 绪论 1

1.1 研究背景 1

1.2 国内外研究现状分析 2

1.2.1 路径规划技术 2

1.2.2 多机器人的路径规划技术 2

1.2.3 强化学习的发展及现状 3

1.3 研究内容 4

第2章 强化学习基础 5

2.1 强化学习的基本过程 5

2.2 强化学习的四要素 6

2.3 强化学习的基本算法 7

2.3.1 蒙特卡罗法 7

2.3.2 时间差分法 7

2.4 本章小结 9

第3章 单机器人路径规划算法 10

3.1 问题描述 10

3.2 Q-learning算法简介 10

3.3 Q()算法简介 12

3.4 单机器人路径规划仿真实验设计 13

3.4.1 框架设计 13

3.4.2 路径规划流程 14

3.4.3 仿真结果与分析 15

3.5 本章小结 17

第4章 多机器人路径规划 18

4.1 引言 18

4.1.1 单机器人与多机器人系统 18

4.1.2 多机器人的路径规划 19

4.2 多机器人Q()算法设计 19

4.2.1 基本框架 19

4.2.2 动态避障 20

4.2.3 路径规划流程 21

4.3 Q()算法仿真实验 22

4.4 SA- Q()算法设计 23

4.4.1 SA- Q()算法简介 23

4.4.2 仿真实验设计 25

4.5 本章小结 26

第5章 总结与展望 27

5.1 总结 27

5.2 展望 27

参考文献 28

致 谢 31

第1章 绪论

1.1 研究背景

智能制造随着中国制造2025的提出全面兴起，其基础是以提高产品生产整体水平为主旨的智能车间。提升车间效率的核心在于由数量有限的工作台、智能机器人组成的车间调度系统。因此，智能机器人在车间中的应用受到了众多学者的关注。移动机器人就是智能机器人的典型代表之一，它的特点是可以在环境中自主四处移动^[1]，即它可以在没有外部引导设备的条件下在不断变化的环境中导航。在工业生产中，移动机器人被应用于自动化立体仓库、生产制造车间的柔性搬运、传输等环节。它不同于传统厂内物料搬运机械，无需人工操作，可以自主实现作业任务，从而减少了人工成本，提高了生产效率。Shakey是世界上第一台移动机器人，它是斯坦福研究院的人工智能中心于1966年到1972年研制成功的，随后从70年代末开始相关技术快速发展。导航技术是移动机器人的关键技术，其又与路径规划密不可分，准确的、高效的、灵活的路径规划算法是当前的研究重点^[1]。

路径规划指移动机器人按照某种性能指标（如能量、距离、时间等），根据传感器对环境的感知，自主搜索一条从起始状态到达目标状态的无碰撞路径^[2]，其中距离是最常用的指标。其涉及的主要问题包括：机器人能利用获得的环境信息从起始位置到达目标状态；机器人的路径中无障碍物；在实现前两点要求后尽可能保证规划出的路径为全局最优解^[3]。常用的局部路径规划算法包括模拟退火法、神经网络法、人工势场法、模糊逻辑法、动态窗口法及基于行为的路径规划方法等^[4]。上述算法各有优点，但存在无法实现自我学习，环境适应能力较差，无法处理动态的车间内不断出现的生产单元、设备和人员等障碍物的问题。强化学习的学习过程涉及智能体与环境的交互，其将学习分成“试探-评价”的过程，可直接从环境中收集经验而无需外部老师。环境反馈的强化信号不是用来教导机器人，只是对机器人的动作质量进行评价。这种算法不需要建立精确的环境模型也无需先验知识，使机器人能更好地适应复杂多变的环境，因此得到了广泛的应用。