计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2011年
11期
2047-2054
,共8页
多agent系统%联盟结构%势结构%任一时间%分组
多agent繫統%聯盟結構%勢結構%任一時間%分組
다agent계통%련맹결구%세결구%임일시간%분조
联盟形成是多agent系统中的一个关键问题,找到最优的联盟结构是NP-完全的.Sandholm和Larson等人已经证明,要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的.在搜索联盟结构图的最底两层之后如何进一步搜索,是个长期以来未能完全解决的问题.在任务分配等实际问题中,不同联盟存在同势同值的特征,或同势的2个联盟的值相差不大.研究了最优势结构生成问题,分析了基于势结构的分组思想,并提出一个以势结构为搜索单位的新的任一时间联盟结构生成算法.算法在最小搜索之后给出进一步降低限界至2的搜索,也讨论了限界从2降到1的过程中由底向上的补充搜索.从搜索的势结构数和联盟结构数以及达到的限界上明显优于由Sandholm和Dang等人给出的算法,是基于势结构的联盟生成问题的一个重要进展.
聯盟形成是多agent繫統中的一箇關鍵問題,找到最優的聯盟結構是NP-完全的.Sandholm和Larson等人已經證明,要建立最壞情況下的限界k,搜索聯盟結構圖的最底兩層是必要且是充分的.在搜索聯盟結構圖的最底兩層之後如何進一步搜索,是箇長期以來未能完全解決的問題.在任務分配等實際問題中,不同聯盟存在同勢同值的特徵,或同勢的2箇聯盟的值相差不大.研究瞭最優勢結構生成問題,分析瞭基于勢結構的分組思想,併提齣一箇以勢結構為搜索單位的新的任一時間聯盟結構生成算法.算法在最小搜索之後給齣進一步降低限界至2的搜索,也討論瞭限界從2降到1的過程中由底嚮上的補充搜索.從搜索的勢結構數和聯盟結構數以及達到的限界上明顯優于由Sandholm和Dang等人給齣的算法,是基于勢結構的聯盟生成問題的一箇重要進展.
련맹형성시다agent계통중적일개관건문제,조도최우적련맹결구시NP-완전적.Sandholm화Larson등인이경증명,요건립최배정황하적한계k,수색련맹결구도적최저량층시필요차시충분적.재수색련맹결구도적최저량층지후여하진일보수색,시개장기이래미능완전해결적문제.재임무분배등실제문제중,불동련맹존재동세동치적특정,혹동세적2개련맹적치상차불대.연구료최우세결구생성문제,분석료기우세결구적분조사상,병제출일개이세결구위수색단위적신적임일시간련맹결구생성산법.산법재최소수색지후급출진일보강저한계지2적수색,야토론료한계종2강도1적과정중유저향상적보충수색.종수색적세결구수화련맹결구수이급체도적한계상명현우우유Sandholm화Dang등인급출적산법,시기우세결구적련맹생성문제적일개중요진전.
