Approaches to asynchronous decentralized decision making

Motivated by the ideas of asynchronous relaxation algorithms this paper inv estigates optimal decision-making problems that exhibit decentralized chara cteristics. Such problems consist of a collection of interacting sub-system s, each one described by local properties and dynamics, joined together by the need to accomplish a common task which achieves overall optimal perform ance. Special properties of such systems that make them ideally suited for the framework of asynchronous computing are (a) the lack of a single overal l objective describing the collective performance, and (b) the asynchronism in implementing topologically optimal decisions based on information which is local in space and time. A methodology for decentralized decision makin g is developed based on the solution of a series of sub-problems in which e ach minimizes a local objective while maximizing a common Lagrangian functi on, by generating independent approximations of an ascent direction in the space of the dual variables. The concepts are illustrated by means of motiv ating examples. (C) 1999 Elsevier Science Ltd. All rights reserved.