计算机工程与科学
計算機工程與科學
계산궤공정여과학
COMPUTER ENGINEERING & SCIENCE
2008年
12期
85-89
,共5页
骆剑彬%胡山立%苏射雄%林耀海
駱劍彬%鬍山立%囌射雄%林耀海
락검빈%호산립%소사웅%림요해
多Agent系统%联盟结构%任务%势结构
多Agent繫統%聯盟結構%任務%勢結構
다Agent계통%련맹결구%임무%세결구
联盟形成是多Agent系统中的一个关键问题.目前,大多数学者都在CFG下研究联盟结构生成问题.然而,在很多实际应用中,联盟的形成往往是为了完成任务集中某些任务.但是,在CFG中并没有把联盟和任务一起考虑.显然,加入任务后,问题将变得更复杂.Dang等人已经证明,这是个NP难问题,并且要建立最坏情况下的限界K(n,m),搜索面向任务联盟结构集合L1、L2(除{(A,φ),(φ,T})是必要且充分的,接着提出一个限界具有保证的任一时间算法.本文深刻分析了面向任务联盟结构间的关系,引入更小的搜索粒度(面向任务势结构),提出一种新的任一时间搜索算法;在搜索完最小搜索之后,进一步搜索CTS集合CTS(n,m,b)对应的部分面向任务联盟结构,渐进给出越来越低的限界,大大改进了Dang等人的工作.
聯盟形成是多Agent繫統中的一箇關鍵問題.目前,大多數學者都在CFG下研究聯盟結構生成問題.然而,在很多實際應用中,聯盟的形成往往是為瞭完成任務集中某些任務.但是,在CFG中併沒有把聯盟和任務一起攷慮.顯然,加入任務後,問題將變得更複雜.Dang等人已經證明,這是箇NP難問題,併且要建立最壞情況下的限界K(n,m),搜索麵嚮任務聯盟結構集閤L1、L2(除{(A,φ),(φ,T})是必要且充分的,接著提齣一箇限界具有保證的任一時間算法.本文深刻分析瞭麵嚮任務聯盟結構間的關繫,引入更小的搜索粒度(麵嚮任務勢結構),提齣一種新的任一時間搜索算法;在搜索完最小搜索之後,進一步搜索CTS集閤CTS(n,m,b)對應的部分麵嚮任務聯盟結構,漸進給齣越來越低的限界,大大改進瞭Dang等人的工作.
련맹형성시다Agent계통중적일개관건문제.목전,대다수학자도재CFG하연구련맹결구생성문제.연이,재흔다실제응용중,련맹적형성왕왕시위료완성임무집중모사임무.단시,재CFG중병몰유파련맹화임무일기고필.현연,가입임무후,문제장변득경복잡.Dang등인이경증명,저시개NP난문제,병차요건립최배정황하적한계K(n,m),수색면향임무련맹결구집합L1、L2(제{(A,φ),(φ,T})시필요차충분적,접착제출일개한계구유보증적임일시간산법.본문심각분석료면향임무련맹결구간적관계,인입경소적수색립도(면향임무세결구),제출일충신적임일시간수색산법;재수색완최소수색지후,진일보수색CTS집합CTS(n,m,b)대응적부분면향임무련맹결구,점진급출월래월저적한계,대대개진료Dang등인적공작.