Efficient Options for Characterizing and Deriving Groups of Interactive Agents

用于表征和导出交互式代理组的有效选项

• 批准号: RGPIN-2015-06230
• 负责人: Wareham, Harold
• 金额: $ 1.31万
• 依托单位: Memorial University of Newfoundland
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=668210
• 关键词: Efficient; Options; Characterizing; Deriving; Groups

We live in a world of societies, from anthills to wolf packs to human families and tribes. Societies vary widely in how their members think, act, and interact with each other (how different is an ant from a wolf? A wolf from a human being?). Societies also have their own capabilities -- they can thrive in the face of environmental changes and the loss of even moderate numbers of members (think how rapidly an anthill is rebuilt when it is kicked over) and perform complex tasks beyond the capabilities of any individual member (like building cities and going to the moon). ****Now that we can create artificial agents using computers, we want these agents to form their own societies with all the advantages of natural ones -- imagine swarms of small cheap robots collaborating to quickly build housing after natural disasters, or non-player characters (NPC) in computer games that can interact naturally with both each other and human players in intricate unscripted stories that never repeat and never end. However, it is remarkably difficult to characterize how such artificial multi-agent systems (MAS) act (Will a given robot swarm always construct housing that is safe to live in? Can a human player find out how to kill the Black Wizard by talking and trading with a given set of NPC?), let alone design MAS to reliably perform specified tasks. This is not surprising given well-known difficulties in understanding and manipulating natural MAS (Will an ocean ecosystem collapse if a particular species goes extinct? What measures can a government implement to stave off a recession?). ****In my proposed research, I will use parameterized complexity analysis to find new practical methods for characterizing and designing MAS. Existing methods using heuristics like simulation and evolutionary algorithms operate quickly but are not guaranteed to be correct (in that they may fail to find valid solutions or claim that a produced solution is the best when better ones exist). However, given restrictions on the agents and their interactions in a typical MAS, there may yet be methods that are both correct and fast under those restrictions. My analysis will work outwards from the very simplest MAS, gradually adding more complex agent abilities and interactions, to chart the frontier between the types of MAS that can and cannot be dealt with efficiently. My research should lead to greatly improved methods for creating, understanding, and manipulating both artificial and natural MAS.********

我们生活在一个社会的世界里，从蚁丘到狼群再到人类家庭和部落。社会在成员的思想、行为和相互作用方面差异很大(蚂蚁和狼有多大不同？从人变成狼？)社会也有自己的能力——它们可以在环境变化和适度成员损失的情况下蓬勃发展（想想蚁丘被踢翻后重建的速度有多快），并执行超出任何成员能力的复杂任务（如建造城市和登月）。****既然我们可以使用计算机创造人工智能体，我们希望这些智能体能够形成自己的社会，拥有自然社会的所有优势——想象一下，一群小型廉价机器人在自然灾害后迅速合作建造房屋，或者电脑游戏中的非玩家角色（NPC）可以在复杂的无脚本故事中与彼此和人类玩家自然互动，永远不会重复，永远不会结束。然而，描述这种人工多智能体系统（MAS）的行为是非常困难的（给定的机器人群是否总是建造安全居住的房屋？）人类玩家是否能够通过与一组NPC交谈和交易而知道如何杀死Black Wizard ?)，更不用说设计能够可靠地执行特定任务的MAS了。考虑到众所周知的理解和操纵自然MAS的困难(如果某个特定物种灭绝，海洋生态系统会崩溃吗？政府可以采取哪些措施来避免经济衰退？****在我提出的研究中，我将使用参数化复杂性分析来寻找表征和设计MAS的新的实用方法。使用模拟和进化算法等启发式方法的现有方法运行迅速，但不能保证是正确的（因为它们可能无法找到有效的解决方案，或者在存在更好的解决方案时声称生成的解决方案是最好的）。然而，考虑到典型MAS中对代理及其相互作用的限制，可能存在在这些限制下既正确又快速的方法。我的分析将从最简单的MAS向外扩展，逐渐增加更复杂的代理能力和交互，以绘制能够有效处理和不能有效处理的MAS类型之间的边界。我的研究应该会大大改善创造、理解和操纵人工和自然mas的方法。********