联盟形成是多Agent系统研究中最为重要的挑战之一,如何对Agent进行划分使得联盟结构的社会福利最大化是当前面临的主要问题。假设每个Agent都具有理性和自利性,为了追求自身的效用最大化而选择和其它的Agent进行联盟,进而使整个系统实现社会福利最大化。目前,联盟结构生成问题面临很大的计算挑战,即使添加了约束条件,也需要新的算法来更快更有效地解决该问题。合作博弈理论模型是联盟形成研究的基础,其中比较典型的是基于特征函数形式的可转移效用博弈模型,不过,其不仅没有考虑Agent之间形成联盟的可能性,也没有考虑Agent之间协同工作的方式,这会对模型和技术的实用性带来一定的限制。同时,大多数的合作博弈模型假设任意Agent都能够形成联盟,并且一个Agent集可以形成任意数量的联盟,这种假设过于宽泛,而现实生活中有一些具体的约束存在。针对上述问题,对联盟形成过程中上述两种常见假设进行约束,将形成联盟的数量约束为k,形成联盟的Agent之间有一定的信任效用约束,提出了信任效用关系的联盟形成,即具有较高的信任效用关系的Agent之间才允许生成联盟。对于本身不具有信任效用关系的Agent,则通过成员之间的传递建立联系。然后,在保证Agent个体理性和联盟中不存在块的前提下,借鉴图像处理的s-t-cut算法,提出两个多项式时间的联盟结构生成算法MT-s-t-cut和MTU-s-t-cut,求解给定情况下的最优联盟结构。最后,仿真实验验证了信任能够影响形成的联盟结构,社会福利随Agent数量的增加而增加,并且算法的运行时间远小于DP和ODP-IP算法。