【作者】 高平安；

【导师】 蔡自兴；

【作者基本信息】 中南大学 ， 计算机应用技术， 2010， 博士

【摘要】 人类可以借助多移动机器人系统执行工农业生产、军事国防和科学研究等领域中许多单调、繁重、复杂或危险的任务,实现降低人类劳动强度、提高工作效率、避免人员伤亡以及扩展人类活动空间等目的。任务分配是有效利用多移动机器人系统资源以充分发挥系统效能优势的重要基础,其重要性程度随系统成员的功能差异性和任务的结构复杂性的增加而增加。最优任务分配是最大化多移动机器人系统效能的前提条件,但在大多数情况下最优任务分配算法的计算复杂度随问题规模的指数级增长,当任务分配问题存在显著的动态不确定性时多移动机器人系统实现最优任务分配将愈加困难,在可接受的时间内实现最优分配的任务规模非常有限。基于市场交易机制的任务分配方法是一种具有良好鲁棒性、灵活性和可扩展性的任务分配方法,其最大优势在于适合动态不确定性环境下多移动机器人系统中各机器人分布地通过最大化个体效能实现最大化系统总效能的目的。本文研究多移动机器人系统协作任务的分布式市场分配方法,分别对多移动机器人系统的松散耦合任务分配、紧密耦合任务分配以及动态任务的重分配的市场方法进行研究,目的在于探索基于市场机制协调的多移动机器人系统提高分布式任务分配最优性和动态任务重分配效率的新方法。(1)本文通过引入代价标示图方法可以比较直观地描述移动机器人依次执行多个任务所消耗的移动代价、操作代价以及完成任务的回报等指标值。通过引入能力向量可以简洁地描述机器人能力的类型和大小,也便于描述不同机器人的能力异构性和机器人对应用任务能力需求的满足性。(2)分布式协调的多移动机器人系统中各机器人的协作行为具有显著的并发性,若系统不支持不同任务管理者并发协商任务分配,则全局任务分配的最优性和实时性会受到制约。给出了一种基于并发合同网协议的任务管理者招标和任务投标者投标的算法框架,并提出一种基于动态邻居集合的任务招标对象选择方法。并发的协商方法有利于提高任务分配的最优性,也利于减少实现任务分配消耗的协商时间。(3)针对松散耦合任务分配提出了一种基于序贯单项任务拍卖和任务分组分配的分布式任务分配方法。任务分配过程被划分成两个阶段,第一个阶段采用序贯单项任务拍卖过程确定每个机器人对每个任务的投标值,第二个阶段采用多个移动吸引子根据第一个阶段获得的投标值确定任务的分组,任务管理者根据分组结果确定任务的最终分配。新的方法可以显著提高任务分配的最优性,但增加的任务管理者的计算代价仅仅是O(m3),通讯代价的增加量是O(n),其中m是任务数量,n是参与任务分配的机器人数量。(4)需要多个机器人紧密协调的紧密耦合任务的分配可以划分成两个层次的分配,第一个层次的分配是指将需要多个机器人紧密协调执行的多个单机器人任务作为一个整体分配给某个机器人群组执行,第二个层次的分配是指将若干个存在严格的空间或时间约束性的单机器人任务分配给同一群组内不同的机器人执行。第一个层次的分配问题主要是为给定任务寻找最优的机器人联盟问题,第二个层次的分配问题主要是解决协作机器人执行任务的时序约束性问题。本文针对第一个层次的分配问题提出了一种基于二进制粒子群优化技术的单任务联盟生成算法,可以有效地为给定任务生成合适的机器人联盟。(5)针对多移动机器人系统的任务重分配问题,本文提出了一种基于预测控制理论的动态性强度估计方法,提出一种基于效用值变化强度估计的任务拍卖策略和投标策略,系统采用新的任务重分配策略可以显著低减少系统重分配任务的通讯代价和计算代价。更多还原

【Abstract】 Multiple mobile robot systems can be used to execute many stuffy, heavy, complex, and dangerous tasks instead of human being in many fields, such as industry autonomous production, national defense, and science research etc. Through using multiple mobile robot systems, the labors’work extensity can be lightened, the efficiency can be promoted, the casualty of human can be decreased, and the space that human being can be being is extended. Allocating tasks properly among the robots is the vital foundation to utilize the resources, and to exert the power of multiple mobile robot system. Task allocation is becoming more and more significant as the size of multi-robot system and the complexity of the global tasks increases. For any multi-robot system, optimizing the task allocation is a precondition to maximize the performance of the whole system. But in most of the cases, the computation complexity of any algorithm to optimizing task allocation is exponential to scale of the problem. Especially, as the task allocation problem is more dynamic and uncertain, it is more difficult for multiple mobile robot systems to allocation tasks within a reasonable time.Market-based approach to task allocation is robust, flexible, and scalable. The most important advantage of market-based approach is that it is suitable for distributed coordinated multi-robot systems in dynamic, uncertain environments to maximize the performance of the whole system through maximizing the individual performance.This thesis addressed some market-based approaches to task allocation, such as loosely-coupled task allocation, tightly-coupled task allocation, and dynamic task reallocation. The purpose of research is to find some new methods to improve the optimization of task allocation and task reallocation.(1) In order to prescribe the execution cost and the reward of a mobile robot that execute several tasks in turn, one kind of cost description graph was proposed. By using capability vector to show the kinds and magnitude of a robot’s capability, it is very convenient to express the heterogeneousness of the system, and the requirement of given tasks.(2) Concurrency is a notable characteristic of robots in distributed mobile robot team. The optimization of global task allocation is limited if the system restricts the robots to initiate task allocation negotiation concurrently. An auction algorithm and a biding algorithm were proposed based on the contract net confirmation protocol to implement concurrent task negotiation. A kind of dynamic neighbor set was presented to determine the potential bidders as well. The method is propitious to improve the optimization of task allocation and to reduce the time to negotiate.(3) A method combining sequent single-task auction mechanism and task clustering mechanism was proposed to improve optimization of loosely-coupled task allocation of multiple mobile robot systems. The allocation process includes two phrases. The tasks were pre-assigned by sequent single-task auction in the first phrase. Then, the task manger clusters the pre-assigned tasks by using movable attractors to optimize the allocation. The proposed method needs more computation cost of O(m3) to cluster m tasks than traditional sequential single-task auction methods, and only add O(n) communication cost to the system consisting of n robots.(4) As for tightly-coupled task allocation, it can be divided into two allocation level. The firs level is to find a group of robots to execute some tasks which demand several robots tightly coordinated. The second level is to allocation the tightly-coupled subtasks to robots within a group. The problem of the first level equals to find a robot coalition to execute some tightly-coupled subtasks as a whole. Robot coalition formation problem is only addressed in the chapter four. A particle swarm optimization algorithm was proposed to form an optimized robot coalition for a given task. The results of stimulated experiments verified the presented algorithm.(5) In order to reduce the cost of computation and communication for multi-robot system to reallocate unfinished tasks in dynamic uncertain environments, a new method to estimate the dynamic extensity of the task utility value was developed based on predictive control theory. The new strategy reduces magnitude auction call and biding proposal according to simulation experiments.更多还原