Fictitious Play for Complex Systems Optimization

复杂系统优化的虚拟游戏

• 批准号: 0422752
• 负责人: Marina Epelman
• 金额: --
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-08-15 至 2008-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0422752&HistoricalAwards=false
• 关键词: Fictitious; Play; Complex; Systems; Optimization

Increasingly, the need arises to solve large-scale complex optimization problems modeled by simulations that allow little or no structural assumptions on the form of their objective functions. And yet their complexity and scope demand integrated approaches to finding optimal designs. This grant will fund the investigation of the potential of a fictitious play paradigm as an algorithmic approach to such problems, both from theoretical and practical points of view. Fictitious Play (FP), which is an iterative process originating in game theory, executes a non-cooperative game repeatedly among players represented by a partition of the decision variables of the underlying system optimization problem. Best replies, as opposed to jointly optimal strategies, can thus dramatically reduce the computational complexity of the problem. Proposed work will focus on computationally practical variants of such an algorithm, and their application to two practical problems: design of dynamic traffic signal timing plans and large-scale instances of Dynamic Programming. In particular, as part of our research, we hope to establish close links between concepts and results in game theory and dynamic programming that so far appear to be unexplored.The opportunity to seek better system performance using realistic simulations of complex systems with an algorithm that gracefully scales and offers the opportunity to compute in parallel can have significant benefits for areas such as, but not limited to, transportation and manufacturing. If successful, this research will not only lead to potential improvements in these application arenas, but will also provide a general and efficient algorithmic tool for improving design of complex realistically-modeled large scale systems, which promises to be broadly and easily applicable. The research promises to produce significant interactions with industry and government to insure realism for the models and data developed.

越来越多地，需要解决大规模的复杂优化问题模拟，允许很少或根本没有结构假设的形式，其目标函数。然而，它们的复杂性和范围需要综合方法来找到最佳设计。这笔赠款将资助从理论和实践角度调查虚拟游戏范式作为解决此类问题的算法方法的潜力。虚拟博弈（FP）是一种起源于博弈论的迭代过程，它在由底层系统优化问题的决策变量的划分所代表的参与者之间重复执行非合作博弈。与联合最优策略相反，最佳回复可以显著降低问题的计算复杂度。建议的工作将集中在计算实际的变种，这样的算法，和他们的应用程序的两个实际问题：设计的动态交通信号配时计划和大规模的动态规划的实例。特别是，作为我们研究的一部分，我们希望在博弈论和动态规划中的概念和结果之间建立密切的联系，这是迄今为止似乎尚未探索的。使用复杂系统的真实模拟来寻求更好的系统性能的机会，使用一种优雅地扩展并提供并行计算机会的算法，可以为以下领域带来显著的好处，但不限于，运输和制造业。如果成功的话，这项研究不仅会导致在这些应用领域的潜在改进，但也将提供一个通用的和有效的算法工具，以改善复杂的现实建模的大规模系统的设计，这有望是广泛和易于应用。该研究有望与行业和政府产生重要的互动，以确保开发的模型和数据的真实性。