1.1目的及意义

随着现代工业、国防、太空和海洋探索以及整个国民经济和人民生活对机器人需求的不断增长, 机器人技术得到了快速的发展, 机器人在各个领域得到了广泛的应用。自 20 世纪 80年代以来, 随着分布式人工智能、机器人学、计算机科学和复杂系统研究的发展, 多机器人系统已经成为机器人研究领域的热点之一。相比于单机器人，多机器人具有工作效率高、可靠性高、智能沉余性好等优点。基于多机器人系统的诸多优点, 其在军事、工农业生产、空间探索、医学、交通控制、服务行业等领域的应用具有良好的应用前景。

多机器人技术研究的一个主要领域就是多机器人系统的任务分配问题（MRTA），其体现了系统高层组织形式与运行机制,是多机器人系统实现目标的基础.一方面,任务分配的好坏直接影响整个系统的效率,并且直接关系到系统中各机器人是否能最大限度发挥自身的能力,避免占用更多的资源;另一方面,当一个机器人没有能力完成当前任务时,如何在现有机制的基础上,通过有效的对话、协商使多机器人合作完成。从本质上讲就是要解决在多机器人系统中每一个机器人的状态和能力，分解当前工作任务，确定多机器人系统中的每一个机器人在什么时间，什么地点，做什么的问题。即把多机器人任务分配问题转化为一个在多维空间内寻找最优解的问题，从而利用优化算法在此空间寻找最优解即最优的多机器人任务分配方案，实现对多机器人的任务分配。

多机器人任务分配问题可以看作是最优分配问题(OAP)、整数线性规划问题、调度问题、网络流问题和组合优化问题.早期的多机器人任务分配方法多为集中式的,由一个管理者(leader)负责分配任务给系统中其他机器人,虽然可以得到全局最优解,但是存在着很多缺点,如不能求解未知环境和动态环境下的任务分配问题等。随着分布式人工智能的不断发展,分布式任务分配方法以其突出的柔性、鲁棒性和高效性受到越来越多的关注.与集中式方法相比,分布式任务分配方法能够更快得到解,但是多为近似最优解.。目前,多机器人任务分配方法主要有基于行为的分配方法、市场机制方法、群体智能方法、基于线性规划的方法、基于情感招募的方法、基于空闲链的方法等。其中粒子群优化算法（PSO）从属于群体智能方法，是一种基于群体的且有着深刻智能背景的优化算法，相比于其他优化算法，其具有易于工程实现、计算效率高、寻优能力强、鲁棒性强等优点，被广泛的运用于科学研究和工程实践中。。

本文的目标就是采用粒子群算法解决任务分配问题，从而实现多机器人的任务分配。

1.2 国内外研究现状

静态的任务分配模型指的是目标位置已知且不会发生改变的分配模型。该模型的特点在于相对目标一直处于静态过程之中，所以通常使用该模型作为任务预分配模型。预分配任务指的是在执行任务前提前获得目标点的位置信息，通过任务规划平台得到决策信息并加载给执行任务的机器人。由于该问题的静态特性，建模和求解相对容易，所以在该问题上的研究也比较多且得到了大量的研究成果。对于此类问题的求解主要可以分为传统求解算法和启发式算法两大类。传统算法包括：动态规划、分支与限定、广度优先搜索等算法。启发算法包括目前大部分的智能优化算法，如：遗传算法、PSO 算法、蚁群算法等。文[1]中作者采用混合整数线性规划构造优化函数，并且根据互异性对 PSO 算法进行改进求解模型。文[2]中的作者引进了多目标理论使用 pareto占有求出非劣解，并采用 MODPSO 算法求解模型。文[3]的作者将遗传算法的变异思想改进鱼群算法并根据决策者的偏好信息求解模型。

动态任务分配求解方法目前文献对于动态任务分配有两种概括：一种是执行任务之前不知道目标的具体位置坐标，利用多机器人分布式网络在执行任务的过程中不断的获取目标位置并执行任务的分配过程；另一种则是提前知道目标位置，在进行了预分配决策后，

任务目标位置发生移动或出现机器人执行任务中发生突发情况时，进行任务动态重分配的过程。两种情况皆是动态的任务分配且具有一定的不确定性，给问题建模和求解带来了不稳定因素，因此较为复杂。动态任务分配由于带有不确定因素，易出现突发状况，所以对算法实时性要求很高。文[4]中采用基于多智能体的分布式协同拍卖算法对任务重分配问题进行了研究，模拟当出现新目标时的任务重分配情况，取得了较好的成果。文[5]中的作者龙涛在考虑了传统合同网易陷入局部最优问题，对合同网类型进行了扩展，提出了一种基于扩展合同网的分布式任务分配方法为动态求解提供了思路。

从上述静态任务分配求解分析可以看出，智能优化算法已经被广泛的应用于任务分配求解。然而，由于任务分配问题是多目标优化问题，往往通过加权转化为单目标优化问题进行求解。传统的智能优化算法求解此类问题时存在一些固有缺陷，学者们需要针对这些缺陷加以改进，才能快速得到满意的分配解。