Networked Multi-Agent Systems: Coping with Adversarial Agents and Links

网络化多智能体系统由一组参与者组成，称为智能体，它们通过网络进行交互以共同执行协作任务。网络化多智能体系统在许多应用领域都很有用，包括分布式机器人、传感器网络和智能电网。由于其许多潜在的应用，网络多智能体系统一直是激烈的研究活动在过去几十年的焦点。过去许多关于网络化多智能体系统的工作都假设智能体和它们通信的网络链路都是可靠的。在实际的多智能体系统中，一些系统组件可能会失败或可能会受到对手的危害。故障代理可能行为不正确或以对抗的方式，类似地，故障或受损的网络链接可能不正确地传递消息。该项目致力于多代理系统的分布式算法的设计和分析，这些算法对代理和链接的对抗行为具有鲁棒性，这些行为可能来自故障或攻击。该项目集中在两个重要的多代理系统，即分布式优化和分布式假设检验类问题。这些问题的鲁棒解决方案可以用于获得多智能体系统中其他相关问题的鲁棒解决方案。因此，该项目有可能产生的解决方案，提高实用的多智能体系统的鲁棒性。该项目的范围包括设计强大的算法，其理论分析，以及开发一个软件工具来评估这些算法。该项目的教育部分包括本科生和研究生参与项目活动，并将项目研究成果纳入相关的研究生课程。该项目旨在开发能够容忍拜占庭故障的多代理算法。拜占庭故障模型捕获可能由故障或受损代理或链路表现出的任意行为。一个拜占庭式的有缺陷的代理人可能在本质上是对抗性的，并且可能表现得任意。错误代理可能的错误行为包括不正确地执行计算，以及向其他代理发送不正确或不一致的消息。类似地，拜占庭故障链路可能导致篡改通过链路发送的消息。多智能体算法，可以容忍拜占庭故障也是强大的存在范围广泛的错误行为可能在一个实际的系统。在多智能体优化和多智能体假设检验的背景下，该项目探讨了许多研究挑战，包括以下内容：（i）识别容忍拜占庭代理或链路故障所必需的和足够的网络属性，同时实现分布式计算的期望属性，（ii）评估消息的多跳转发对多代理计算的影响，（iii）用于网络自适应以提高性能的机制，以及（iv）分析大规模网络中的算法行为。 通过对这些问题的研究，该项目旨在制定基本原则，指导为不同类型的分布式计算设计健壮的容错算法。用于评估算法的工具包括数学分析以及基于模拟的实验。

Networked multi-agent systems consist of a group of participants, referred to as agents,that interact over a network to collectively perform collaborative tasks. Networked multi-agent systems are useful in many application domains, including distributed robotics, sensor networks, and smart grids. Due to their many potential applications, networked multi-agent systems have been a focus of intense research activity over the past several decades. Much of the past work on networked multi-agent systems assumes that the agents, and network links over which they communicate, are both reliable. In practical multi-agent systems, some of the system components may fail or may be compromised by an adversary. Faulty agents may behave incorrectly or in an adversarial manner, and similarly, faulty or compromised network links may deliver messages incorrectly. This project addresses the design and analysis of distributed algorithms for multi-agent systems that are robust to adversarial behavior of agents and links, which may result from failures or attacks. The project focusses on two important classes of problems in multi-agent systems, namely, distributed optimization and distributed hypothesis testing. Robust solutions to these problems may be used to obtain robust solutions to other related problems in multi-agent systems. Thus, the project has the potential to yield solutions that improve robustness of practical multi-agent systems. The project scope includes design of robust algorithms, their theoretical analysis, as well as development of a software tool to evaluate these algorithms. The educational component of the project includes participation of undergraduate and graduate students in project activities, and incorporation of project research outcomes into a related graduate course.The project aims to develop multi-agent algorithms that can tolerate Byzantine failures. The Byzantine fault model captures arbitrary behavior that may be exhibited by faulty or compromised agents or links. A Byzantine faulty agent may be adversarial in nature, and may behave arbitrarily. Possible misbehaviors of a faulty agent include performing computations incorrectly, and sending incorrect or inconsistent messages to other agents. Similarly, a Byzantine faulty link can result in tampering of messages sent over the link. Multi-agent algorithms that can tolerate Byzantine failures are also robust in presence of a wide range of faulty behaviors possible in a practical system. In the context of multi-agent optimization and multi-agent hypothesis testing, the project explores many research challenges, including the following: (i) identifying network properties that are necessary and sufficient to tolerate Byzantine agent or link failures, while achieving desirable properties for the distributed computation, (ii) evaluating the impact of multi-hop forwarding of messages on the multi-agent computation, (iii) mechanisms for network adaptation to improve performance, and (iv) analysis of algorithm behavior in large-scale networks. Through the work on these issues, the project aims to develop fundamental principles that can guide the design of robust fault-tolerant algorithms for different types of distributed computations. The tools used for evaluating the algorithms include mathematical analysis as well as simulation-based experimentation.