多机器人系统(Multi-Robot System,MRS)是由多个机器人所组成,为完成任务而进行分工协作的系统。它通常运行在动态环境中,需根据环境与用户需求的变化来调整系统行为。本文关注MRS的基于任务序列的行为组织方式。其中每个机器人具有一个任务序列,表示该机器人的任务集合的执行顺序。由于环境与用户需求的变化可导致任务序列原有执行条件遭到破坏,使其性能指标下降,甚至无法正常执行,要求MRS能对任务序列进行维护,即根据其执行条件变化来对其持续调整,从而使得其各种性能指标满足预期要求或提高。开放环境下MRS任务序列维护面临以下关键科学问题:(1)环境变化时,任务序列的一致性问题:环境变化可能导致MRS对任务集合以及任务间限制条件进行动态调整,进而导致任务序列的不一致性——即存在二个以上的任务,由于它们在任务序列中的位置不符合限制条件,使任务序列无法正常执行。因此MRS需根据不一致性情况对任务序列进行调整。(2)环境存在资源限制时,任务序列的可行性问题:任务序列中各个任务的资源需求、环境中的可用资源,以及二者的动态变化,可导致某些任务的资源需求无法得到满足——即不可行,从而降低任务完成率,因此,MRS需根据各任务的资源需求得到满足的情况来调整任务序列,从而满足尽可能多的任务的资源需求。本文针对上述问题,从“任务序列模型”、“任务序列一致性维护机制”、“任务序列可行性维护机制”等方面进行研究,取得以下的研究成果。1.多机器人系统(MRS)任务序列模型该模型针对MRS的特点,从任务序列执行、任务资源消耗这二个角度描述MRS任务序列。从任务序列执行角度,该模型定义了:(1)任务序列基本构成,(2)限制任务序列执行的各种因素(统称为任务配置)及其动态变化,(3)任务序列调整操作,用于描述任务序列维护机制。从任务资源消耗角度,该模型定义了:(1)任务序列资源需求,(2)任务序列执行成本(即资源消耗量);基于上述概念,描述了阻碍任务序列执行的二种情况:(1)任务序列存在死锁,(2)任务资源需求未被满足;上述情况用于引出任务序列维护机制需解决的主要问题。该模型提供了任务序列相关概念,分析了研究问题,为后续研究奠定了理论基础。2.基于任务再分配的任务序列一致性维护机制针对动态环境下MRS任务配置变化可能导致的任务序列的不一致性,提出任务序列一致性维护机制。该机制设计包括以下方面:(1)基于任务配置与任务序列,定义任务间的可达性函数,并提出任务序列一致性判据。(2)基于此判据,设计根据任务配置动态变化来检测不一致性的算法。(3)利用任务再分配思想,设计任务序列不一致性更正算法,消除不一致性。(4)周期性调用任务再分配算法,降低任务序列的执行成本,处理任务序列动态变化对执行成本的不良影响。通过理论分析,证明该机制能在有限次循环之后,消除任务序列中的不一致性。通过实验,检验了该机制的运行效果,并说明了在该机制持续运行时,通过周期性执行任务再分配算法对于任务序列执行成本的降低作用。3.基于资源传递的任务序列可行性维护机制在资源受限、任务存在资源需求的环境中,任务可能由于资源需求未得满足而无法执行。对此,本文提出基于资源传递的任务序列可行性维护机制,持续提高资源需求得到满足的任务所占的比例。该机制设计包括以下方面:(1)任务序列可行性维护算法,用于向任务序列中插入资源传递任务,把资源从具有冗余资源的机器人向急需资源的机器人进行转移。(2)基于任务再分配的任务序列执行效率维护算法,对任务序列的执行成本进行降低,处理资源传递对执行成本的不良影响,且在维护过程中显式考虑可行性维护算法的作用,避免二个算法优化目标之间的冲突。通过理论分析,证明了可行性维护算法的如下性质:(1)不会向任务序列中引入新的不一致性,故不存在与一致性维护机制的冲突;(2)使MRS的各个任务序列的可行性都能得到单调提高,即不会以牺牲某个机器人为代价来满足另一个机器人的资源需求。通过实验,说明了(1)可行性维护算法能在任务配置动态变化时对任务序列可行性进行有效维护。(2)执行效率维护算法能与可行性维护算法较好结合,对任务序列执行成本进行持续降低。