% Paper for MAAMAW'97, Ronneby, May 1997
% Final version
% Fredrik Ygge and Hans Akkermans, 05-03-1996
\documentclass[12pt]{article}
\usepackage{times}
\usepackage{named}
\usepackage{psfig,local}
%\documentstyle[times,psfig,11pt,named,local]{article}
%\documentstyle[psfig,11pt,named,local]{article}
% Note: these are commands specifically defined in local.sty
%\textwidth 12.2cm
%\textheight 19.3cm
\openlinepar
\psdirectories{figs,icmfigs,dadsmfig,c:/text/dadsm-96/figs}
\begin{document}
\title{\bf Making a Case for Multi-Agent Systems}
\author{%
{\bf Fredrik Ygge} \footnotemark[3]
\and
{\bf Hans Akkermans} \footnotemark[4]
}
\date{%
\footnotemark[3]\
EnerSearch AB and University of Karlskrona/Ronneby \\
Department of Computer Science (IDE) \\
372 25 Ronneby, Sweden \\
Fredrik.Ygge@ide.hk-r.se,
http://www.rby.hk-r.se/$\ \tilde{}\ $fredriky \\[12pt]
%
\footnotemark[4]
AKMC and University of Twente \\
Department of Information Systems (INF/IS) \\
P.O. Box 217, NL-7500 AE Enschede, The Netherlands \\
akkermans@ecn.nl, J.M.Akkermans@cs.utwente.nl \\[12pt]
%
%{\em To appear in \\
%Proceedings MAAMAW'97, \\
%LNCS Series, Springer-Verlag, Berlin, D, \\
%held in Ronneby, Sweden, 13--16 May 1997}
}
\maketitle
\thispagestyle{empty}
\pagestyle{empty}
\begin{abstract}
Multi-Agent Systems (MAS) promise to offer solutions to problems where
established, older paradigms fall short. To be able to keep promises,
however, in-depth studies of advantages and weaknesses of MAS
solutions versus conventional ones in practical applications are
needed. In this paper we offer one such study. Climate control in
large buildings is one application area where MAS, and market-oriented
programming in particular, have been reported to be very successful.
We have therefore constructed and implemented a variety of market
designs for this problem, as well as different standard control
engineering solutions. This paper gives a detailed analysis and
comparison, so as to learn about differences between standard versus
MAS approaches, and yielding new insights about benefits and
limitations of computational markets.
\end{abstract}
\section{Introduction}
When new paradigms arise on the scientific horizon, they must prove
their value in comparison and competition with existing, more
established ones. The multi-agent (MAS) paradigm is no exception. In a
recent book on software agents, edited by Jeffrey Bradshaw
\cite{Bradshaw:97a}, Norman observes that perhaps ``the most relevant
predecessors to today's intelligent agents are servomechanisms and
other control devices''. And indeed, a number of applications for
which MAS have recently claimed success, are close to the realm of
what is traditionally called control engineering. One clear example is
the climate control of large buildings with many office rooms. Here,
Huberman \emph{et al.} \cite{Huberman:95a} have constructed a working
MAS solution based on a market approach, which has been reported to
outperform existing conventional control.
A key question is: in what respect and to what extent are multi-agent
solutions better than their alternatives? We believe that the
above-mentioned application provides a nice opportunity to study this
question in more detail. It is practically very relevant, it lends
itself to alternative solutions, and it is quite prototypical for a
wide range of industrial applications in resource allocation
(including the energy management applications we are working on
\cite{Ygge:96a}, the file allocation problem of Kurose and Simha
\cite{Kurose:89a}, and the flow problems investigated by Wellman
\cite{Wellman:93a}).
The contribution of this paper is a detailed analysis of a published
MAS approach to building climate control and a comparison between this
approach and traditional approaches. We also introduce a novel
approach to this problem based on a general equilibrium market. From
the analysis of these approaches we draw conclusions not only about
the suitability of these approaches, but of many other MAS approaches
as well.
The structure of the paper is as follows. Section~\ref{sec:office}
introduces the application: it describes the office environment and
gives the physical model for cooling power and the various temperature
and outside weather influences. First, we give a standard control
engineering solution, based on local and independent integral
controllers (Section~\ref{sec:controlA}). Next, we consider the
market-based approach as put forward by Huberman \emph{et al.}
\cite{Huberman:95a} (Section~\ref{sec:marketA}), and we discuss a
number of variations on this market design
(Section~\ref{sec:marketAP}), providing a kind of factor analysis for
its success. Section~\ref{sec:controlB} then shows the results of an
improved control engineering scheme that exploits global data.
Finally, we propose a market design of our own, based on local data
only, and make a comparison across the different approaches
(Section~\ref{sec:marketB}). Section~\ref{sec:conclusions} puts our
results into perspective and summarizes the conclusions.
\section{The Office Environment}
\label{sec:office}
In this section, we present the mathematical-physical model of the
office environment. For those readers who find the mathematics
forbidding, we first give a conceptual summary which makes it possible
to skip the equations. The offices are attached to a pipe in which the
resource (cold air) is transported as in Figure~\ref{fig:offenv}. The
characteristics of this system are similar to the characteristics of a
district heating system, but with offices instead of households. We
assume that there are 100 offices in total, and that they are equally
distributed towards East, South, West and North.
\postscript{12cm}{offenv}{\small \em Offices and air transportation.}
The thermodynamics of the office environment is actually quite simple.
Every office is seen as a storage place for heat, but heat may
dissipate to its environment. In the model, the thermodynamic
behaviour of an office is equivalent to a simple electrical
RC-circuit. Here, voltage is analogous to temperature, and electrical
current is analogous to heat flow. $C$ and $R$ then respectively
denote heat capacitance and heat losses to the environment.
A good general reference on thermodynamic models as we use here is
\cite{Incropera:90a}. The heat equations are continuous in time, but
are discretized according to standard procedures used in control
engineering, described \emph{e.g.}, in \cite{Ogata:90a}. The AI
aspects of thermodynamic model building with component libraries are
discussed extensively in \cite{Borst:97a}.
\subsection{Basic Physical Properties}
The resource treated is cooling power. Each office can only make use
of a fraction, $\eta$, of the available resource at that office,
$P_{aio}$, i.e.
\begin{equation}
P_{cio} \leq \eta\cdot P_{aio},
\label{eq:limit}
\end{equation}
where $P_{cio}$ is the consumed power. The available resource at one
office is equal to the available resource at the previous office minus
the consumed resource at the previous office. Throughout the paper we
use an $\eta$ of 0.5. The index $i$ denotes the time interval under
observation and the index $o$ denotes the office under observation.
This naming convention is used throughout the entire paper. In
addition, the index $k$ is also sometimes used for time intervals.
We treat everything in discrete time with a time interval of one
minute. For all offices the temperature, $T_{io}$, is described by
\begin{equation}
T_{io} = T_{0,o} + \sum_{k=1}^{i}(P_{hko}-P_{cko})/C_{o},
\label{eq:maintemp}
\end{equation}
where $P_{hko}$ is the heating power and $C_{o}$ is the thermal
capacitance. The heating power is described by
\begin{equation}
P_{hio} = (T_{vio}-T_{io})/R_{o},
\label{eq:tempflow}
\end{equation}
where $R_{o}$ is the thermal resistance and $T_{vio}$ is a virtual
outdoor temperature detailed below.
>From Eq.~(\ref{eq:maintemp}) and Eq.~(\ref{eq:tempflow}) we obtain
\begin{equation}
T_{io} = \frac{1}{1+\frac{1}{R_{o}C_{o}}}(T_{i-1,o}
+ \frac{\frac{T_{vio}}{R_{o}}-P_{cio}}{C_{o}}), \, i>0.
\label{eq:closedtemp}
\end{equation}
\subsection{Weather Model}
All external weather influences on the office environment are modelled
by a virtual temperature, representing outdoor temperature, sun
radiation etc. We assume that there is sunshine every day and that the
outdoor temperature, $T^{outd}$, varies from $22$ to $35^\circ$C
according to
\begin{equation}
T^{outd}_{i} = 22+13\cdot e^{-((i\cdot s-4) \, \,
mod \, \, 24 - 12)^2/20},
\label{eq:outdtemp}
\end{equation}
where $s$ is the length of each time interval expressed in hours, i.e.
here $s=1/60$.
The virtual temperature, $T_{vio}$, is described by
\begin{equation}
T_{vio} = T^{outd}_{i}+T_{ro}+T_{dio},
\label{eq:vtemp}
\end{equation}
where $T_{d}$ is a random disturbance, thought to represent small
fluctuations caused by e.g. the wind. $T_{d}$ is Gaussian distributed
with an average value of 0 and a standard deviation of 1. $T_{r}$ is a
sun radiation component. For the offices located at the East side
$T_{r}$ is described by
\begin{equation}
T_{ri}^{East} = 8\cdot e^{-((i\cdot s+4) \, \,
mod \, \, 24 - 12)^2/5}.
\label{eq:sunrade}
\end{equation}
and correspondingly for the South and the West offices
\begin{equation}
T_{ri}^{South} = 15\cdot e^{-(i\cdot s \, \,
mod \, \, 24 - 12)^2/5}
\label{eq:sunrads}
\end{equation}
and
\begin{equation}
T_{ri}^{West} = 8\cdot e^{-((i\cdot s-4) \, \,
mod \, \, 24 - 12)^2/5}.
\label{eq:sunradw}
\end{equation}
The various temperatures are plotted in Figure~\ref{fig:outdtemp}.
\postscript{14cm}{outdtemp}
{\small \em The leftmost plot shows the outdoor temperature,
$T^{outd}_{i}$. The middle plot shows the sun radiation components,
$T_{r}$, (with peaks at time 8, 12, and 16 hours for offices located
at the East, South, and West side respectively). Finally, the outdoor
temperature plus the sun radiation components are plotted to the
right.}
\subsection{Office Temperatures Without Control}
In Figure~\ref{fig:rsandcs}, the temperature for a South oriented
office is plotted with different thermal resistances, $R_{o}$, and
thermal capacitances, $C_{o}$. For simplicity we assume all $R_{o}$ to
be equal and all $C_{o}$ to be equal. From this figure we note two
things: first, the higher $R_{o}C_{o}$ the bigger the lag in
temperature changes, and second, the higher $R_{o}C_{o}$ the smaller
the fluctuations in temperature. For the experiments in this paper we
chose $R_{o}=10$ and $C_{o}=10$. An $R_{o}$ or a $C_{o}$ equal to zero
implies that $T_{io}=T_{vio}$, as can be seen by letting $R_{o}$ or
$C_{o}$ approach zero in Eq.~(\ref{eq:closedtemp}).
\postscript{13cm}{rsandcs}
{\small \em The indoor temperature for an uncontrolled office is
plotted for different values of the thermal resistance and the thermal
capacitance. Small values of the thermal resistance and capacitance
give higher peaks, while higher values give smoother curves.}
\subsection{Simulations}
All solutions discussed in this paper have been implemented in and
simulated by the authors using C++ on an IBM compatible PC running
Windows95. Furthermore, for guaranteeing that a fair comparison on the
same footing was carried out, all simulations have been independently
recreated and verified from the paper, as part of a master's thesis
project, using Python on an IBM compatible PC running Linux.
\section{{\sc Control-A}: Conventional Independent Controllers}
\label{sec:controlA}
\subsection{Integral Control for the Offices}
The application of regulating the office temperature has a long
tradition in control theory. The most widely known controllers are
different variants of the PID controller. The letters PID denote that
the control signal is proportional to the error (i.e. the difference
the between the setpoint and the actual value) --- the P;
proportional to the integral of the error --- the I; and proportional
to the derivative of the error --- the D. Here, we will use a variant
of the integrating controller, i.e., an I-controller, of the form
\begin{equation}
F_{io} = F_{i-1,o} + \beta(T_{io}-T^{setp}_{o}),
\label{eq:controller}
\end{equation}
where $F$ is the output signal from the controller and $\beta$ is a
gain parameter. For the simulations it is assumed that $F_{io}$ will
not be below 0 and that it will not exceed 3. The control signal
$F_{io}$ is sent to the actuator and the actual $P_{cio}$ is obtained
from
\begin{equation}
P_{cio} =
\left\{ \begin{array}{ll}
F_{io}, & F_{io} \leq \eta\cdot P_{aio} \\
\eta\cdot P_{aio}, & F_{io} > \eta\cdot P_{aio} \end{array}\right..
\label{eq:contrToPower}
\end{equation}
Plots of the office temperatures with different gains are shown in
Figure~\ref{fig:contr}. The gain of the controller is not critical for
this application. Too high a gain will result in the controller
overreacting when the temperature exceeds the setpoint, after which it
will be under the setpoint for quite some time. This leads to a larger
error than if smaller adjustments are made. Also, the amplitude of the
control signal then gets unnecessarily high, but the system does not
get dangerously unstable. We note that the maximum deviation here is
$\pm 0.06^\circ$C. Thus, controllers using any of the three gains
perform very well. Apart from the plots shown here, also a step
response has been analyzed. From a brief analysis we chose a gain of
10.
\postscript{13cm}{contr}
{\small \em The indoor temperature for an office, utilizing a
integral controller, is plotted for different controller gains.}
\paragraph{The Performance Measure}
We use the same evaluation of the building control as Huberman
\emph{et al.} \cite{Huberman:95a}, namely the standard deviation of
the deviation from the setpoint,
\begin{equation}
StdDev(T-T^{setp}) = \sqrt{\frac{1}{N}\sum_{o=1}^{N}
[(T_{io}-T_{o}^{setp})-(\langle T_{i}\rangle -
\langle T^{setp}\rangle)]^{2}}
\label{eq:stddev}
\end{equation}
where $T^{setp}$ is the setpoint temperature, $\langle T\rangle$ is
the temperature averaged over all offices, and $\langle
T^{setp}\rangle$ is the average setpoint temperature.
\postscript{15cm}{hund}
{\small \em The standard deviation, as defined in
Eq.~(\ref{eq:stddev}) for each interval, $i$, is plotted for different
amounts of available resource (130, 140, 150, and 160) with 100
offices. The lower the amount of available resource the higher the
standard deviation.}
\paragraph{Limitations on Available Resource}
So far we have assumed that the total amount of available resource is
unlimited. Now we assume that there is a maximum value for the power
that is inserted into the system. In such a situation offices that are
situated close to the air input will have a sufficient amount of cool
air, while those near the end will suffer if totally uncoordinated
controllers are used. Thus, the smaller the amount of the total
available resource, the larger the standard deviation will be. This is
visualized in Figure~\ref{fig:hund}. From the figure we have chosen an
upper limit for the total amount of resource of $140$.
\paragraph{Discussion}
As seen from the example, independent integrating controllers perform
very well when the resource is unlimited. On the other hand, when
there is a shortage of resource the standard deviation increases
dramatically.
\section{{\sc Market-A}: The Approach by Huberman \emph{et al.}}
\label{sec:marketA}
A MAS solution to the problem of building control has been presented
by Huberman \emph{et al.} \cite{Huberman:95a,Clearwater:93a}. The
approach taken is to model the resource allocation problem of the
building environment as a computational market where agents buy and
sell resource. The non-separability in terms of agents, i.e. the fact
that the amount of resource the penultimate agent can use depends
on how much resource the last agent receives, is ignored.
The basic idea is that every office is represented by an agent that is
responsible for making good use of the resource and to this end trades
resources with other agents. The agents create bids which are sent to
an auctioneer that calculates a clearing price, and makes sure that no
agent has to buy for a price higher than its bid nor has to sell for a
price lower than its bid.
Section~\ref{sec:orgform} describes the mathematical details of this
approach. The reader having no special interest in these details may
skip this part and take a look at the results of the corresponding
simulations in section~\ref{sec:simulations}.
\subsection{Original Formulation}
\label{sec:orgform}
All formulas in this section were taken from \cite{Huberman:95a} and
\cite{Clearwater:93a}.
\paragraph{Trade Volumes}
First, the decision for an agent to buy or sell is based on
\begin{equation}
t_{io} = \frac{T_{o}^{setp}}{T_{io}}\cdot
\frac{\langle T_{i}\rangle}{\langle T^{setp}\rangle}
\,\,\,\left\{ \begin{array}{ll}
t_{io}>1, & seller \\
t_{io}<1, & buyer \end{array}\right..
\label{eq:buyorsell}
\end{equation}
Then the total trade volume, $V$, is calculated from
\begin{equation}
V_{i} = \sum_{o=1}^{N} \left| 1 - t_{io} \right| ,
\label{eq:trade_vol}
\end{equation}
where N is the number of offices.
Then every agent calculates its request volume, $v$, according to
\begin{equation}
v_{io} = \alpha \frac{\left| 1 - t_{io} \right|}{V_{i}}.
\label{eq:rel_vol}
\end{equation}
When an agent buys or sells its $v$ the actual movement of a valve,
called $VAV$, is computed from
\begin{equation}
\Delta VAV_{io} = f(flow_{io},v_{io},VAV_{io}),
\label{eq:deltaVAV}
\end{equation}
where $f$ is an empirically determined function which is not
explicitly given in the papers \cite{Huberman:95a,Clearwater:93a}.
From this the actual $VAV$ position for each interval is updated
according to
\begin{equation}
VAV_{i+1,o} = VAV_{io} + \Delta VAV_{io}.
\label{eq:VAV}
\end{equation}
\paragraph{Bids}
The bids are based on the \emph{marginal utility}\footnote{What
Huberman \emph{et al.} call utility in their work
\cite{Huberman:95a,Clearwater:93a} is generally called marginal
utility in micro-economic theory.} of the form described by
\begin{equation}
U(t_{io}/T^{setp}_{o},m_{io}) =
[U(0,m_{io})]^{(1-t_{io}/T^{setp}_{o})} =
[U(0,m_{io})]^{(1-
\frac{\langle T_{i}\rangle}{T_{io}\langle T^{setp}\rangle})},
\label{eq:utility}
\end{equation}
with
\begin{equation}
U(0,m_{io}) = u_{3} - (u_{3} - u_{1})e^{-\gamma m_{io}} ,
\label{eq:U0}
\end{equation}
and
\begin{equation}
\gamma = ln \left[ \frac{u_{3}-u_{1}}{u_{3}-u_{2}} \right],
\label{eq:gamma}
\end{equation}
where $u_{1} = 20$, $u_{2} = 200$, and $u_{3} = 2000$, and $m$ is the
amount of money that an agent has, as given by
\begin{equation}
m_{io} = 100(2-VAV_{io}).
\label{eq:money}
\end{equation}
By observing Eq.~(\ref{eq:U0}) and Eq.~(\ref{eq:gamma}),
we note that the equations can be simplified to
\begin{equation}
\begin{array}{ll}
U(0,m_{io}) = & u_{3} - (u_{3} - u_{1})e^{-\gamma m_{io}} =
u_{3} - (u_{3} - u_{1})(e^{\gamma})^{-m_{io}} = \\
& u_{3} - (u_{3} - u_{1})
\left( \frac{u_{3} - u_{1}}{u_{3} - u_{2}}\right) ^{-m_{io}}.
\end{array}
\label{eq:SimpU0}
\end{equation}
Since the $VAV$ varies between 0 and 1, the amount of money an agent
has varies between 100 and 200, and thus $U(0,m)$ varies between
1999.85632 and 1999.99999. Hence, the notion of gold does not effect
the marginal utility in practice, as will be verified by the
simulations in Section~\ref{sec:marketAP}.
The bids are calculated from multiplying the marginal utility with
the previous price, $price$, according to
\begin{equation}
B_{i+1,o} =
U_{io}(t_{io}/T^{setp}_{o},m_{io})\times price_{i}.
\label{eq:bid}
\end{equation}
\paragraph{Auction}
All bids are sent to an auctioneer which calculates a market price
where supply meets demand. All agents which requested to buy and which
bids are above or equal to the market price are assigned the
corresponding amount, and, similarly, all agents which requested to
sell and which bids are below or equal to the market price are
assigned the corresponding of amount of resource.
\paragraph{Assumptions and Simplifications}
Since $f$ in Eq.~(\ref{eq:deltaVAV}) above is not explicitly given and
since the relation between the $VAV$ position and $P_{c}$ is specific
to the office environment, we need to make an assumption about how the
bid volumes relate to $P_{c}$. We take the simplest choice and let
Eq.~(\ref{eq:deltaVAV}) and Eq.~(\ref{eq:VAV}) be replaced by
\begin{equation}
F_{i+1,o} = F_{io} \pm v_{io},
\label{eq:Ptrade}
\end{equation}
where plus or minus depends on whether it was an accepted buy or sell
bid. $P_{cio}$ is obtained from Eq.~(\ref{eq:contrToPower}). This
simplification is not crucial to our central line of reasoning.
As pointed out by Clearwater \& Huberman \cite{Clearwater:93a}, the
purpose of the auction is only to reallocate between the agents and
not to affect the average temperature. This means that even if the
valves are not opened very much, there is plenty of resource in the
system, and if the offices are all above the setpoint, no valve can
open further without another one closing. In order not to complicate
the model further, the simulation is only performed in a time interval
where there is a total lack of resource, with the total available
resource assigned to the system. Thus, we do not implement a mechanism
that inserts and deletes the total resource to the system. We choose
to simulate between 3 p.m. and 7 p.m.
We assume the amount of money to be given by
\begin{equation}
m_{io} = 100(2 - \frac{F^{max}_{o} - F_{io}}{F^{max}_{o}}).
\label{eq:mymoney}
\end{equation}
Thus, the amount of money will vary from 100 to 200, as in the
original work.
Eq.~(\ref{eq:bid}) turns out to produce major problems in simulations.
Above we have seen that $U(0,m) \approx 2000$.
Equation~(\ref{eq:utility}) shows that $U(t_{io}/T^{setp}_{o},m_{io})$
is minimized for minimized $T_{io}$ and maximized
$\frac{\langle T_{i}\rangle}{\langle T^{setp}\rangle}$. As we can
expect $T_{io}$ to be well above $10^\circ C$ and
$\frac{\langle T_{i}\rangle}{\langle T^{setp}\rangle}$ to be well
below 2, we can be sure that $U(t_{io}/T^{setp}_{o},m_{io})$ will be
well above $2000^{1-\frac{2}{10}} \approx 437$. Thus, the bidding
price will never be below 437. Then, Eq.~(\ref{eq:bid}) tells us that
the market price will be at least $price_{0}\times 437^{i}$. This
leads to numerical overflow after only a few iterations. In practice
the market price scales with approximately $price_{0}\times 1300^{i}$
which of course is even worse. We note however that, since all agents
multiply their bids with the previous price, this has no effect on the
reallocation itself, but only affects the price level. Therefore, we
choose to omit multiplying by the previous price in our simulations,
noting that this leads to exactly the same allocations but avoids
numerical overflow. Hence, the bids are based on
Eq.~(\ref{eq:utility}) rather than Eq.~(\ref{eq:bid}).
The price at each auction is adjusted until supply meets demand. But,
since the bids are given using discrete volumes, supply will seldom
match demand \emph{exactly} at the clearing price. Normally, there
will be a very small excess demand or supply. If there is an excess
supply, all buyers that are willing to pay at most the clearing price
will buy, but not all sellers that are willing to accept at least the
clearing price can sell. In this situation, the sellers are selected
randomly from the valid candidates. The same procedure is used when
there is a small excess demand.
\subsection{Simulations}
\label{sec:simulations}
Figure~\ref{fig:orgsim} shows two plots. The upper plot is the
standard deviation when independent integrating controllers are used
and the lower one shows the agent-based control scheme as defined
above. We found that an $\alpha$, as described by
Eq.~(\ref{eq:rel_vol}), of $64$ led to the smallest overall standard
deviation. It is seen that the agent approach offers at least one
order of magnitude of improvement.
\postscript{10cm}{orgsim}{\small \em Standard deviation for
independent controllers (top) and agent-based control (bottom).}
Compared to the independent controllers this is indeed a major
advance. It is clear that the market coordination of the controllers
leads to a much smaller standard deviation and to higher comfort in
the offices. This validates the results of Huberman \emph{et al.}
\cite{Huberman:95a, Clearwater:93a}.
\section{{\sc Market-A}$'$: A Suite of Variations}
\label{sec:marketAP}
In this section we present a suite of variations on the scheme
presented in Section~\ref{sec:marketA}. The main aim is to see if the
scheme can be simplified without loss of performance.
\postscript{12cm}{nogold}{\small \em Standard deviation for the
original scheme and a scheme with the gold dependencies removed.}
\paragraph{Deleting the Gold Dependency}
Plots of the standard deviation with the original scheme as well as
with a scheme where all gold dependencies have been removed --- by
setting $U(0,m)$ in Eq.~(\ref{eq:U0}) to a constant value ($2000$) ---
are shown in Figure~\ref{fig:nogold}. The scheme without gold
dependencies performs approximately as good as the original scheme.
The reason for this, as pointed out earlier, is that $U(0,m)$'s gold
dependency is extremely weak. For the scheme without gold an $\alpha$
of $66$ turned out to be optimal.
\postscript{12cm}{notemp}{\small \em Standard deviation for the scheme
with the gold dependencies removed, compared to a scheme with both the
gold and temperature dependencies removed.}
\paragraph{Deleting the Temperature Dependency}
The next issue is the marginal utility's dependence on the current
temperature, i.e. the dependency of $U$ on $T$ in
Eq.~(\ref{eq:utility}). In Figure~\ref{fig:notemp} the standard
deviation is plotted for the scheme without gold, mentioned above, and
a scheme where the dependency on the temperature has been removed as
well. We see that also here the performance is approximately as good
as that of the original scheme. In order to remove the temperature
dependency from the marginal utility, we simply set all selling prices
to $10$ and all buying prices to $100$. If there is a mismatch between
supply and demand, say, supply exceeds demand, the agents that will
sell are picked randomly. Here, an $\alpha$ of $65$ turned out to be
optimal. Note that the temperature is still used to determine both the
bidding \emph{volume} and the decision \emph{whether} to buy or sell.
\postscript{13cm}{nocoord}{\small \em Standard deviation with the
auction scheme removed, compared to the original \textsc{Market-A}
scheme.}
\paragraph{Deleting the Auction}
Next, we let the agents assign their bids to themselves without any
auction whatsoever. This means that the sum total of the controller
outputs, $F_{io}$, might sometimes exceed the total amount of resource
and sometimes be below. The physical model is of course still obeyed
so that the total resource actually used, i.e. the sum of the cooling
power, $P_{cio}$, will never exceed the total amount of available
resource, as described by Eq.~(\ref{eq:limit}). The result of this
simulation is shown in Figure~\ref{fig:nocoord}. Note that this scheme
is roughly ten times better than the \textsc{Market-A} scheme. Here an
$\alpha$ of $17$ turned out to be optimal.
\paragraph{Discussion}
At first glance, it might seem counterintuitive that performance
actually \emph{improves} significantly when virtually all the core
mechanisms of the market are removed. First we showed that introducing
the market improves performance considerably and then we showed that
most market mechanisms are superfluous. What, then, is the big
difference between the uncoordinated integrating controller, the
\textsc{Control-A} scheme, and the scheme without any auction that we
ended up with? The simple answer, in our view, is the \emph{access to
global data}, in terms of the average temperature and the average
setpoint temperature (as seen from Eq.~(\ref{eq:buyorsell}) and
Eq.~(\ref{eq:rel_vol})), in the \textsc{Market-A} and
\textsc{Market-A}$'$ schemes.
\section{{\sc Control-B}: A Standard Controller Using Global Data}
\label{sec:controlB}
Having concluded that the access to global data is crucial for
performance, it is of course of interest to analyze what the
performance of an integrating controller, like the one introduced in
Eq.~(\ref{eq:controller}), \emph{but now incorporating global data},
would be.
We would like the controller to take into account not only its own
deviation from its setpoint, but also to consider the deviations of
the other offices from their setpoints. Therefore, the controller in
Eq.~(\ref{eq:controller}) is extended to
\begin{equation}
F_{io} = F_{i-1,o} + \beta[(T_{io}-T^{setp}_{o}) -
(\langle T_{i}\rangle - \langle T^{setp}\rangle)] ,
\label{eq:avgcontr}
\end{equation}
where $\beta$ is set to 10 as previously, and where $P_{cio}$, as
before, is obtained from Eq.~(\ref{eq:contrToPower}).
The plot from the simulation with this controller, compared to the
\textsc{Market-A} simulation, and to the \textsc{Market-A}$'$
simulation where the auction was removed, is shown in
Figure~\ref{fig:controlb}.
\postscript{12cm}{controlb}{\small \em Standard deviation with an
integrating controller that utilizes global data compared to the
\textsc{Market-A} scheme, and the \textsc{Market-A}$'$ scheme with the
auction removed.}
We see that the standard deviation is approximately the same for the
\textsc{Control-B} and the \textsc{Market-A}$'$ schemes. Thus, also
the \textsc{Control-B} scheme performs roughly ten times better than
\textsc{Market-A}. An important difference, though, is that {\sc
Control-B} employs the well-known integrating controller for which
there are well-understood methods and theories for e.g. stability
analysis\footnote{This holds under the assumption that the time scale
of the variations of the average temperature is much slower than the
fluctuation of the temperature. This is a very reasonable assumption
in the present case, however.}. In contrast, the {\sc Market-A} scheme
is not easily analyzable from a formal theory perspective, since it
does not rely on such well established concepts.
\section{{\sc Market-B}: A Market with Local Data Only}
\label{sec:marketB}
In the previous sections we have seen that the computational market
{\sc Market-A} was outperformed by the global control scheme
{\sc Control-B}. It is an interesting question if a simple and well
performing computational market approach can be devised that does {\em
not} depend on having available global information, in contrast to
both these schemes. In this section we show that this is indeed the
case.
We adopt the concept of resource allocation, as proposed by Wellman
\cite{Wellman:93a}, whereby general equilibrium theory is applied to
resource allocation. We note that any resource allocation problem with
a single resource, like the ones treated in
\cite{Ygge:96a,Kurose:89a}, can be viewed as a proper market exchange
with two commodities: the resource $r$ and money $m$. We then write
the utility function for each agent as $u(r,m) = u(r) + m$. The
competitive behaviour for each agent, then, is to trade $r$ for $m$
whenever $\frac{\partial u}{\partial r}$ is below the current market
price and vice versa. The \emph{equilibrium price} is a price, $p$,
for $r$ in terms of $m$, such that supply meets demand. Thus, at
market equilibrium all $\frac{\partial u}{\partial r} = p$ , except
for the agents that are at their boundary values. Agents being at
their upper bounds will have a $\frac{\partial u}{\partial r} \geq p$,
and agents at their lower bounds will have a $\frac{\partial
u}{\partial r} \leq p$. We note that the resulting equilibrium is
identical to the Kuhn-Tucker conditions for maximizing the sum of the
utilities, when the utilities are concave and independent. Under these
conditions, we know that the equilibrium is unique and that it is
equal to the solution maximizing the sum of the individual utilities.
\subsection{The Relation Between Markets and Independent Controllers
Utilizing Global Data}
The performance measure for the system is given by
Eq.~(\ref{eq:stddev}). The best system is therefore the one that
minimizes this equation. Hence, the most straightforward move one can
think of to come to a market model, is to take {\em this} measure as
representing the utility function for the overall system. So, the
utility function for the individual agents is ideally
related to $[(T_{io}-T_{o}^{setp}) -
(\langle T_{i}\rangle - \langle T^{setp}\rangle)]^{2}$.
\footnote{Since utilities are expressions of preference orderings,
they are invariant under monotonic transformations.} However, this is
still a formulation containing global information.
Thus, we want to obtain a {\em purely local} reformulation, by getting
rid of the terms with $\langle T \rangle$ containing the global
information. We might replace them, though, by terms relating to the
changes in the local resource. In doing so, we take inspiration from
the standard controller equations Eq.~(\ref{eq:controller}) and
Eq.~(\ref{eq:avgcontr}), indicating that we get good results (for
unconstrained resources) with the update equation $ F_{io} =
F_{i-1,o}+\phi_{io}$, when $\phi_{io}$ has the form $\phi_{io} = \beta
(T_{io}-T_{o}^{setp})$. The intended interpretation of $\phi_{io}$ is
to represent the output that the local controller would have delivered
if acting independently with unconstrained resource. In the market
setting each agent updates its control signal $F_{io}$ through $F_{io}
= F_{i-1,o} + \Delta F_{io}$, where $\Delta F_{io}$ is determined by
the outcome of the market. Since the resource is only redistributed
among the agents, we have that $\sum_{o=1}^{N}{\Delta F_{io}} = 0$.
Accordingly, as a step in the design of a {\sc Market-B} scheme, based
on local data only, we employ the following definition.
{\bf Definition 1.} Assume as the utility function for the individual
office agents:
\begin{equation}
u(\Delta F_{io}) =
-\alpha _{o}^{2}(\Delta F_{io} - \phi_{io})^{2},
\label{eq:properUtility}
\end{equation}
where $\alpha_{o}$ is a strength parameter for each office
representing its physical properties such as $R_{o}$ and $C_{o}$. The
proper choice of $\alpha_{o}$ is discussed in Proposition 2 later on.
{\bf Proposition 1.} A general equilibrium market in which the agents
hold the utility function of Eq.~(\ref{eq:properUtility}) \emph{is
equivalent to} an integrating controller, the resource update
equation of which exploits global information and is described by:
\begin{equation}
\Delta F_{io}=\phi_{io}-
\frac{1}{\alpha_{o}^{2} \cdot \langle 1/ \alpha^{2} \rangle}
\langle \phi_{i} \rangle ,
\label{eq:generalDeltaFn}
\end{equation}
given that no agent is at its boundary.
{\bf Proof.} At equilibrium, all $u'(\Delta F_{io})$ will be equal,
and thus it will hold for every office that
$\Delta F_{io}-\phi_{io} = \frac{\alpha_{N}^{2}}{\alpha_{o}^{2}}
(\Delta F_{iN} - \phi_{iN})$.
Summing the equations yields
$\sum_{o=1}^{N-1}\Delta F_{io} - \sum_{o=1}^{N-1} \phi_{io} =
\alpha_{N}^{2} ( \Delta F_{iN} - \phi_{iN} )
\sum_{o=1}^{N-1}\frac{1}{\alpha_{o}^{2}}$.
Together with the resource constraint,
$\sum_{o=1}^{N}{\Delta F_{io}} = 0$,
this gives $\Delta F_{iN} = \phi_{iN} -
\frac{1}{\alpha_{N}^{2} \cdot \langle 1/ \alpha^{2} \rangle}
\langle \phi_{i} \rangle $.
For reasons of symmetry, this equation holds for all offices.
%$\Box$ % This symbol requires the latexsym package.
{\bf Corollary.} For the special case where all $\alpha_{o}$ are
equal, and $\phi_{io} = \beta (T_{io}-T_{o}^{setp})$,
Equation~(\ref{eq:generalDeltaFn}) becomes exactly the
\textsc{Control-B} scheme as captured by Eq.~(\ref{eq:avgcontr}).
Consequently, a computational market based on the utility function
$ u(\Delta F_{io}) =
-\alpha _{o}^{2}[\Delta F_{io} - \beta (T_{io}-T_{o}^{setp})]^{2}$,
will always lead to a resource allocation identical to that of the
global \textsc{Control-B} scheme.
In sum, we see that \emph{local data plus market communication is
equivalent to independent control utilizing global data}. Even though
our proof was based on the assumption that the agents are
never at their boundary values, it will be a very close approximation
in most practical applications. It should also be mentioned that
managing the boundaries is not required for a successful
implementation. As seen above, omitting the management of boundaries
in the current application leads to \textsc{Control-B}, which was
shown to have a very high performance.
\subsection{Finding an Optimal Utility Function}
In this section we show how an optimal utility function is constructed
in the {\em constrained} case, from an optimal controller for the {\em
unconstrained} case.
{\bf Proposition 2.} If $T_{io}$ is a linear function of
$\Delta F_{io}$,
\footnote{From the thermal model discussed in Section~\ref{sec:office}
(especially Eqs.~(\ref{eq:closedtemp}) and (\ref{eq:contrToPower})) we
note that this is indeed the case for a reasonably wide range.
Another, and general, reason that this assumption is adequate,
resides in the fact that linearization around a working point (here,
the minimum of $f$) is a commonly used and successful procedure in
control engineering. Accordingly, the proposition can be read as
giving the exact result, when we cut off the Taylor expansion after
the linear term. We mention in passing that the error made in $f$ due
to this cut-off is only of \emph{third} order with respect to the
resource.}
and if $\phi_{io}$ minimizes Eq.~(\ref{eq:stddev}) in the
unconstrained case, then in a market where the utility functions are
described by Eq.~(\ref{eq:properUtility}), with
$\alpha _{o}=\frac{\partial T_{io}}{\partial \Delta F_{io}}$,
the associated market equilibrium minimizes Eq.~(\ref{eq:stddev}) in
the constrained case, if the resource can be independently allocated
among the agents.
{\bf Proof.}
Minimizing Eq.~(\ref{eq:stddev}) boils down to minimizing
$f(T_{i1}, T_{i2}, \ldots\ ,T_{in}) =
\sum_{o=1}^{N}[(T_{io}-T_{o}^{setp}) -
(\langle T_{i}\rangle - \langle T^{setp}\rangle)]^{2}$,
since this is just a monotonic transformation. Due to the fact that
$\phi_{io}$ minimizes Eq.~(\ref{eq:stddev}), it holds that
$\frac{\partial f}{\partial \Delta F_{io}} = 0$
for $\Delta F_{io} = \phi_{io}$. This gives that $T_{io}(\phi_{io}) =
T_{o}^{setp} - (\langle T_{i}\rangle - \langle T^{setp}\rangle )$.
Thus, $f$ can be rewritten as
$\sum_{o=1}^{N}[T_{io} (\Delta F_{io}) - T_{io}( \phi_{io})]^{2}$.
Since $T_{io}$ is a linear function of $\Delta F_{io}$, we have that
$T_{io}(\Delta F_{io}) = T_{io}( \phi_{io}) + \frac{\partial
T_{io}}{\partial \Delta F_{io}}\cdot (\Delta F_{io} - \phi_{io})$, and
hence $f$ becomes $\sum_{o=1}^{N}\left(\frac{\partial T_{io}}{\partial
\Delta F_{io}}\right) ^{2}(\Delta F_{io} - \phi_{io} )^{2}$.
Thus $f = - \sum_{o=1}^{N}u_{o}$. Since we know (as pointed out in the
beginning of Section~\ref{sec:marketB}), that the equilibrium
maximizes the sum of the utilities we see that it minimizes $f$.
%$\Box$ % This symbol requires the latexsym package.
\paragraph{Discussion.}
Previously, we saw that the independent controller {\sc Control-B}
that incorporates global data, {\em viz.} the average temperatures,
performs very well. In this section we positively answered the
question if one can construct a market, {\sc Market-B}, that is based
on local data only and that performs as good or even better.
In this section a market approach based on general equilibrium theory
was used. This is of course not the only available mechanism for
resource allocation in MAS. It seems interesting to try out other
mechanisms, like the contract net protocol \cite{Davis:83a}, and see
if they perform better. However, proposition 2 tells us that, if we
treat this problem of building control as separable in terms of
agents, like done by Huberman \emph{et al.}, there is no better
scheme.\footnote{We note that, as mentioned earlier, the problem is
actually not really separable in terms of agents and therefore better
solutions may exist if this is taken into account. However, we believe
that for managing non-separability, centralized algorithms are likely
to be even more competitive compared to distributed ones. Another
observation is that in this paper we have only investigated the case
of using the current available resource as the interesting commodity,
as done by Huberman \emph{et al.}, and found an optimal mechanism for
that. At the same time, extending the negotiations to future resources
as well, could potentially increase performance, but this is a
different problem setting with different demands on available local
and/or global information items, such as predictions.}
For example, if we assigned all the resource to an auctioneer, that on
its turn would iteratively assign the resource in small portions to bidders
bidding with their true marginal utility, we would end up with
something close to the competitive equilibrium, but we can not do
better than \textsc{Market-B}. Furthermore, this would be an extremely
inefficient way to arrive at equilibrium compared to other available
methods \cite{Ygge:96a,Andersson:97a}. That is, we can use different
mechanisms for achieving the competitive equilibrium, but we can never
hope to find a mechanism that would do better than the
\textsc{Market-B} scheme.
\section{Discussion and Conclusion}
\label{sec:conclusions}
We believe that both the approach and the results, as presented in
this paper, pose a general challenge to the MAS community. Multi-agent
systems offer a very new way of looking at information technology,
with potentially a big future impact. They may lead to what Kuhn calls
a `paradigm shift' \cite{Kuhn:70a}. However, when new paradigms arise
on the scientific horizon, they must prove their value in comparison
and competition with existing, more established ones. The MAS paradigm
is no exception.
We have therefore deliberately played the role of the devil's advocate
in this paper. Any new paradigm in science sparks off enthusiasm. But
this tends to lead to a parochial view, on its turn bringing along
exaggerated claims and promises, and thus to wrong expectations from
society. Pride and prejudice are dangers lurking around the corner,
even in the field of MAS. These are not imaginary dangers, because the
history of Artificial Intelligence and computer science is full of
examples. Take, as an example, the field of knowledge-based systems.
Knowledge systems actually are a success story. They are now in
everyday use around the world. Yet, we are very far from the `copying
and automating human experts' image that was pictured to the public in
the early eighties. According to some, such ill-conceived expectations
contributed to the so-called `AI Winter' later in the decade. Still,
knowledge systems constitute a positive example, as they represent the
single most important commercial and industrial offspring from AI. But
their role has become much more modest, as intelligent support tools
or assistants, usually functioning as knowledge-intensive components
embedded within much larger conventional information systems.
So, the key question to be answered by the MAS community is: in what
respect and to what extent are multi-agent solutions better than their
more conventional alternatives? And the key message of this paper is
that arguing in favour of the multi-agent systems paradigm does
require much more careful analysis. As yet, there are hardly any
studies in the MAS literature of the kind carried out in the present
paper. But as we have shown in technical detail, old paradigms such as
conventional control cannot be {\em that} easily dismissed. Paradigm
shifts and scientific revolutions are brought about, not only through
noisy crowds (although these can indeed be very helpful), but by lots
of hard everyday technical work.
Abstract considerations alone, concerning what agents are, or on the
general nature of autonomy, rationality, and cooperation, are not
sufficient to achieve this. Therefore, we have taken a different
approach, one that is bottom-up and application-oriented. In this way,
we aim at obtaining experimental data points on the basis of which
convincing MAS claims can be established. The data point considered in
this paper is climate control within a large building consisting of
many offices. This is a quite prototypical application relating to the
general problem of optimal resource allocation in a highly distributed
environment. This class of problems has already received much
attention in the MAS area. Reportedly, this type of application is
very suitable for market-oriented programming \cite{Huberman:95a}. On
the other hand, we have devised some more conventional control
engineering solutions, as well as alternative market designs.
Important conclusions of our investigation are:
\begin{itemize}
\item The market approach by \cite{Huberman:95a} indeed outperforms a
standard control solution based on local, independent controllers. So,
the MAS approach indeed yields a working solution to this type of
problem.
\item However, if conventional control schemes are allowed to exploit
global information, as does the market design of Huberman {\em et
al.}, they perform even better.
\item We have proposed an alternative market design that uses local
data only, and still performs as good as a control engineering scheme
having access to global information.
\item So, our general conclusion is that {\em ``local data + market
communication = global information''}. The important difference is
that in computational markets this global information is an
{\em emergent property} rather than a presupposed concept, as it is in
standard control.
\end{itemize}
These results provide the opportunity to more clearly state what the
added value of market-oriented programming is in this type of
applications. There is a scientific role for debunking here. As we
have seen, one {\em can} model the situation in the more traditional
terms of control engineering. A similar argument regarding distributed
resource allocation could be construed, by the way, vis-\`{a}-vis
mathematical optimization ({\em cf.} our discussion in
\cite{Ygge:96a}).
In our analysis we have focused on the market approach. It is tempting
to ask whether things are different when a non-market MAS approach is
followed, say, using the contract net \cite{Davis:83a}. As we argued,
the answer in our opinion is a straightforward {\em no}. Arguing for
non-market approaches is not a way out, but a dead-end street. The
goal in the considered class of problems is to find the optimal
distributed solution. Alternative MAS approaches, market as well as
non-market ones, only change the multi-agent dynamics on the way to
this goal. This might be done in a better or poorer way, but it is not
possible to change this goal itself. The goal state in any MAS
approach is, however formulated, equivalent to market equilibrium, the
yardstick for having achieved it is given by some quantitative
performance measure as we discussed, and both are stable across
different MAS approaches.
The agent and market approach does give a highly intuitive and natural
picture of problems in distributed environments --- even when at a
strictly algorithmic level it effectively leads to the same end result
as alternative approaches. We do believe that this is a value in
itself: for conceptual modelling, understanding, explanation,
knowledge transfer. Moreover, models and pictures that have conceptual
simplicity are more easily generalized to more complicated situations,
e.g., to allocation of multiple resources in multicommodity markets
\cite{Wellman:93a}. Because of its focus on local information,
communication and action, the agent paradigm is more flexible than
centralized approaches. This does not show up very clearly in the
case analyzed here, because the underlying physics and mathematics
has been strongly simplified (for example, all offices and
thermodynamic processes are assumed to be equal). This will generally
not be true in reality, and that will necessitate a big modelling
effort in centralized approaches as standard control engineering.
For the present case, we have shown that the MAS approach offers
working solutions of equal quality (see the simulation experiments
and, for a formal and general result, our Proposition 1). As a point
in favour of a MAS approach, we note that it can treat resource
constraints relatively easily, see especially our Proposition 2.
So, when we have strong heterogeneity, large scale, and relative
independence, we believe that the agent approach starts to pay off.
This is visible for example in the application of power load
management we are working on ourselves \cite{Ygge:96a}. It does have
similarities with the application discussed in this paper, but for the
reasons mentioned the current industrial state of the art based on
central control approaches is quite limited. Notwithstanding this, it
does not diminish the need for thorough analysis --- of (market)
failures {\em and} successes.
\section*{Acknowledgments}
We thank Rune Gustavsson at the University of Karlskrona/Ronneby and
Hans Ottosson at EnerSearch AB for all their support. A special
acknowledgment goes to Olle Lindeberg whose very detailed comments on
the draft papers led to significant improvements in the simulations
and whose ideas also helped us in the design of the market in
Section~\ref{sec:marketB}. We also thank Bengt Johannesson, who, as a
part of his master's thesis, went through our paper in detail and
recreated all the simulations. We thank Arne Andersson, Eric Astor and
the SoC team at he University of Karlskrona/Ronneby for useful
comments and discussions of draft material.
\bibliography{ygge}
%\bibliographystyle{unsrt}
\bibliographystyle{named}
\end{document}