摘 要

任务分配作为多移动机器人系统的关键技术，其性能好坏直接影响着多移动机器人系统的性能。利用基本粒子群优化算法解决任务分配问题具有计算简单、易于实现等优点，但基本粒子群算法也容易受到部分较优解的影响，算法稳定性差。

本文旨在对基本粒子群算法分析并改进，加强算法稳定性，更快的为多移动机器人系统寻出更优的任务分配方案。本文提出参数动态变化的改进策略。该改进策略可使粒子群算法在迭代中关键参数动态变化，进而使得粒子群在迭代的不同时期具有不同特性，从而提高算法性能。通过数值仿真对比验证改进后的粒子群算法在移动机器人任务分配上具有更优表现。

关键词：移动机器人；粒子群优化算法；任务分配

Abstract

As the key technology of multi mobile robot system, the performance of task allocation directly affects the performance of multi mobile robot system. The basic particle swarm optimization (BPSO) has the advantages of simple calculation and easy implementation, but the basic particle swarm optimization (BPSO) is easily affected by some better solutions, and the stability of the algorithm is poor.

The purpose of this paper is to analyze and improve the basic particle swarm optimization（PSO） algorithm, strengthen the stability of the algorithm, and find a better task allocation scheme for the multi mobile robot system faster. In this paper, an improved strategy of dynamic parameter change is proposed. The improved strategy can make the key parameters of PSO change dynamically in the iteration, and then make PSO have different characteristics in different periods of iteration, so as to improve the performance of the algorithm. Through the comparison and verification of numerical simulation, the improved PSO algorithm has better performance in the task allocation of mobile robot.

Key Words： PSO；mobile robots；task allocation strategy

目录

第1章 绪论 1

1.1研究背景 1

1.2研究现状 2

1.3研究目标与文章结构 3

第2章 基本粒子群算法及其改进策略 4

2.1基本粒子群算法简介及其基本思想 4

2.2基本粒子群算法优化模型及其优化步骤 4

2.3基本粒子群算法缺陷分析及改进策略 5

2.4本章小结 7

第3章 粒子群算法在机器人任务分配问题上的求解 9

3.1 多机器人任务分配的问题描述 9

3.2多机器人任务分配的模型描述 9

3.3多机器人任务分配的目标函数确立 10

3.4多移动机器人任务分配的约束条件确立 12

3.5 多移动机器人任务分配求解 12

3.6 本章小结 14

第4章 实验仿真和结果分析 16

4.1 仿真数据及参数设定 16

4.2小规模仿真对比及分析 16

4.3大规模仿真对比及分析 18

4.4 本章小结 21

第5章 总结与展望 22

参考文献 23

致 谢 25

第1章 绪论

1.1研究背景

随着机器人相关技术的快速发展以及机器人在人类的生产、生活等方面的广泛应用，人们对机器人的性能、能力的需求逐渐提高。随着机器人任务需求复杂度越来越高，单一机器人难以独立完成任务。有时即使能够独立完成，付出的时间成本和代价都超出可接受范围。比如智能仓库并未使用同时具备装卸功能和运送功能的智能物流机器人。因为其成本过高且运行效率低，不符合物流公司的经济效益。再如应急救援机器人要完成生命探测、环境扫描、极端环境生命维持、不同规格的挖掘和支撑等大量任务，目前来说将所有功能归于一个机器人会极大的拉低机器人整体效率，不符合应急救援的快速、最大化救援原则。人类日益增长的性能需要同相对落后的机器人生产之间的矛盾，是自机器人被应用开始就永恒存在的，这也正是机器人及相关技术发展的根本动力。

在生产与需求的矛盾中，多机器人系统（Multiple Robot System, MRS）应运而生。其在现有机器人技术基础上，通过多机器人耦合、多进程并行、机器人合作等方式完成超过单一机器人极限的作业或者达到更高的效率和更高的效益。特别在近十年来，网络通讯技术、物联网技术、计算机技术等发展迅猛。这些技术的发展为多机器人系统进入人们的日常生活的各个方面提供了有利的支持。多机器人系统主要由两大类技术支撑。其一为机器人相关技术，此为构建多机器人系统的基础。另一为多机器人任务分配，只有合理调度和分配才能使机器人达到壹加壹大于二的效果。合理健康的分配方法能够体现多机器人的系统优势，所以任务分配的优秀与否直接决定了多机器人系统的性能强弱。

多机器人系统应用于非常多的场合，而不同场合之间差距巨大。因此多机器人任务分配难以一概而论。适用于大部分的场合的分类方法是基于机器人与任务之间的数量关系以及时效问题。从任务被完成的方面，分为单机器人完成（Single Robot, SR）和多机器人完成（Multi-Robot, MR）。从机器人完成任务数量方面，分为可完成一个任务（Single Task, ST）和可完成多个任务（Multi-Task, MT）。从时效关系考虑分为实时分配(Instantaneous Assignment, IA)和提前分配(Time-extended Assignment, TA)。所以有以下八类：SR-ST-IA、SR-ST-TA、SR-MT-IA、SR-MT-TA、MR-ST-IA、MR-ST-TA、MR-MT-IA、MR-MT-TA。目前来说即使分成以上八类各类也没有统一高效的任务分配方法。原因是不同场合甚至同一场合使用不同机器人都会带来不同的限制条件。进而得到的最优分配策略也可能相距甚远。目前面向解决多机器人任务分配问题的研究大多会有明确的场景。例如京东亚洲一号仓的智能机器人分拣、多无人机空中表演任务。

多机器人任务分配问题在复杂任务情况下已被证明是一个非确定性多项式时间困难问题（Non-deterministic Polynomial Hard Problem, NP)，其特点为非确定性多项式和时间复杂度高，此为传统代数求解带来了巨大困难。直到近些年计算机性能的飞速提升，使使用传统优化算法解决成为了可能。但随着机器人数量和任务数量的增加，传统优化算法对计算量需求巨增。计算需求的相对较小的、基于群体智能的算法逐渐成为解决此类问题的首要选择，其中以粒子群算法最为突出。