Efficient Options for Characterizing and Deriving Groups of Interactive Agents

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

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.