NTRS - NASA Technical Reports Server

Back to Results
Adaptive Multi-Agent Systems for Constrained OptimizationProduct Distribution (PD) theory is a new framework for analyzing and controlling distributed systems. Here we demonstrate its use for distributed stochastic optimization. First we review one motivation of PD theory, as the information-theoretic extension of conventional full-rationality game theory to the case of bounded rational agents. In this extension the equilibrium of the game is the optimizer of a Lagrangian of the (probability distribution of) the joint state of the agents. When the game in question is a team game with constraints, that equilibrium optimizes the expected value of the team game utility, subject to those constraints. The updating of the Lagrange parameters in the Lagrangian can be viewed as a form of automated annealing, that focuses the MAS more and more on the optimal pure strategy. This provides a simple way to map the solution of any constrained optimization problem onto the equilibrium of a Multi-Agent System (MAS). We present computer experiments involving both the Queen s problem and K-SAT validating the predictions of PD theory and its use for off-the-shelf distributed adaptive optimization.
Document ID
Document Type
Macready, William (NASA Ames Research Center Moffett Field, CA, United States)
Bieniawski, Stefan (Stanford Univ. Stanford, CA, United States)
Wolpert, David H. (NASA Ames Research Center Moffett Field, CA, United States)
Date Acquired
August 21, 2013
Publication Date
January 1, 2004
Subject Category
Theoretical Mathematics
Distribution Limits
Work of the US Gov. Public Use Permitted.
Document Inquiry