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

网络化多代理系统：应对对抗性代理和链接

• 批准号: 1610543
• 负责人: Nitin Vaidya
• 金额: $ 35.87万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2018-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1610543&HistoricalAwards=false
• 关键词: Networked; Multi; Agent; Systems; Coping

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.

网络多代理系统由一组参与者组成，称为代理，它们通过网络进行交互以集体执行协作任务。网络多代理系统在许多应用程序域中都有用，包括分布式机器人技术，传感器网络和智能电网。由于它们的许多潜在应用，在过去的几十年中，网络多代理系统一直是激烈的研究活动的重点。过去的大部分网络多代理系统上的工作都假设代理商以及它们传达的网络链接都是可靠的。在实用的多机构系统中，某些系统组件可能会失败或可能被对手损害。错误的代理可能会出现错误或以对抗性的方式行为，类似地，错误或折衷的网络链接可能会错误地传递消息。该项目介绍了针对代理和链接的对抗性行为的多代理系统的分布式算法的设计和分析，这可能是由于故障或攻击而造成的。该项目的重点是多代理系统中的两个重要类别的问题，即分布式优化和分布式假设测试。解决这些问题的强大解决方案可用于获得多代理系统中其他相关问题的强大解决方案。因此，该项目有可能产生解决方案，以改善实际多代理系统的鲁棒性。项目范围包括强大算法的设计，其理论分析以及开发用于评估这些算法的软件工具。该项目的教育组成部分包括参与本科生和研究生参与项目活动，并将项目研究成果纳入相关的研究生课程。该项目旨在开发可以容忍拜占庭式失败的多机构算法。拜占庭断层模型捕获了可能通过错误或受损的代理或链接表现出的任意行为。拜占庭有缺陷的代理本质上可能是对抗性的，并且可能是任意行为的。错误的代理可能不当行为包括错误地执行计算，以及向其他代理发送不正确或不一致的消息。同样，拜占庭故障链接可能会导致通过链接发送的消息篡改。在实用系统中可能存在广泛的错误行为的情况下，可以忍受拜占庭失败的多代理算法也是强大的。 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性能和（iv）大规模网络中算法行为的分析。 通过这些问题的工作，该项目旨在制定基本原理，以指导针对不同类型的分布式计算的稳健耐故障算法的设计。用于评估算法的工具包括数学分析以及基于仿真的实验。