Principled Analysis and Synthesis of Agent Systems Using Tools from Statistical Physics

摘要

The computational problem underlying the TASK (Taskable Agent Software Kit) domain is to find a solution to a large set of interacting, distributed constraints using a set of autonomous agents. The central hypothesis upon which our work is based is that large systems of distributed constraints behave much like physical systems with many interacting components. For example, sets of constraints can undergo phenomena such as sudden phase transitions from having many solutions to having no solution. Furthermore, analysis using the mathematical tools of statistical physics yields empirically-verifiable predictions that are stronger than those that can be obtained by a classical theoretical analysis. In this project, we (1) provided a complexity analysis for the agent RACE challenge problem, (2) developed a framework for fair bidding strategies in this domain, (3) demonstrated tradeoffs between aggressive and non-aggressive agents, (4) developed combinatorial auction test suites for agent system development, and (5) developed a series of software tools in support of large-scale agent software platforms.