Efficient Options for Characterizing and Deriving Groups of Interactive Agents

我们生活在一个社会的世界里，从蚁丘到狼群，再到人类家庭和部落。不同的社会在其成员的思想、行为和互动方式上存在很大差异(蚂蚁和狼有什么不同？人类的狼？)社会也有自己的能力--面对环境变化和即使是适度数量的成员流失，它们也能蓬勃发展(想想蚂蚁丘被踢倒后重建的速度有多快)，并执行任何单个成员都无法完成的复杂任务(比如建造城市和登月)。 现在我们可以用计算机创造人工代理人，我们希望这些代理人利用自然代理人的所有优势形成自己的社会-想象一群廉价的小机器人在自然灾害后合作快速建造房屋，或者电脑游戏中的非玩家角色(NPC)可以在复杂的无剧本故事中与彼此和人类玩家自然互动，永远不会重复，永远不会结束。然而，很难描述这种人工多智能体系统(MAS)是如何发挥作用的(一个给定的机器人群体总是会建造安全居住的住房吗？人类玩家能通过与一组给定的NPC交谈和交易来了解如何杀死黑巫师吗？)，更不用说设计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.