Using Synchronous Boolean Networks to Model Several Phenomena of Collective Behavior

In this paper, we propose an approach for modeling and analysis of a number of phenomena of collective behavior. By collectives we mean multi-agent systems that transition from one state to another at discrete moments of time. The behavior of a member of a collective (agent) is called conforming if the opinion of this agent at current time moment conforms to the opinion of some other agents at the previous time moment. We presume that at each moment of time every agent makes a decision by choosing from the set (where 1-decision corresponds to action and 0-decision corresponds to inaction). In our approach we model collective behavior with synchronous Boolean networks. We presume that in a network there can be agents that act at every moment of time. Such agents are called instigators. Also there can be agents that never act. Such agents are called loyalists. Agents that are neither instigators nor loyalists are called simple agents. We study two combinatorial problems. The first problem is to find a disposition of instigators that in several time moments transforms a network from a state where the majority of simple agents are inactive to a state with the majority of active agents. The second problem is to find a disposition of loyalists that returns the network to a state with the majority of inactive agents. Similar problems are studied for networks in which simple agents demonstrate the contrary to conforming behavior that we call anticonforming. We obtained several theoretical results regarding the behavior of collectives of agents with conforming or anticonforming behavior. In computational experiments we solved the described problems for randomly generated networks with several hundred vertices. We reduced corresponding combinatorial problems to the Boolean satisfiability problem (SAT) and used modern SAT solvers to solve the instances obtained.本文提出一种面向多类集体行为现象的建模与分析方法。本文所定义的集体，即多智能体系统（multi-agent systems），是指在离散时间节点上于不同状态间切换的系统。若某集体成员（智能体）在当前时刻的观点，与此前某一时刻其他智能体的观点保持一致，则称该智能体的行为为从众行为（conforming behavior）。我们假定，每个智能体在每一时刻均需从决策集合中完成抉择：其中决策1对应执行动作，决策0对应保持静止。本文采用同步布尔网络（synchronous Boolean networks）对集体行为进行建模。我们假定网络中可存在两类特殊智能体：一类是在每一时刻均执行动作的激发者（instigators）；另一类是始终保持静止的忠诚者（loyalists）。既非激发者亦非忠诚者的智能体，则被称为普通智能体（simple agents）。本文研究两类组合优化问题：第一类问题为，求解一组激发者配置方案，使其能在若干时间步内将网络从「普通智能体多数处于静止状态」的初始态，转换为「普通智能体多数处于激活状态」的目标态；第二类问题为，求解一组忠诚者配置方案，使网络能够回归至「普通智能体多数处于静止状态」的初始态。针对普通智能体表现出与从众行为相悖的反从众行为（anticonforming behavior）的网络，本文亦研究了类似的组合优化问题。针对具有从众或反从众行为的智能体集体，本文得到了若干理论分析结果。在计算实验环节，本文针对随机生成的含数百个节点的网络求解了上述问题：我们将对应组合优化问题归约为布尔可满足性问题（Boolean satisfiability problem, SAT），并借助现代SAT求解器对生成的算例进行求解。