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.