Home > Downloads




The DiMalloc Project

Overview

The DiMalloc project (acronym for techniques for DIstributed Markets, negotiation, and resource ALLOCation) focus on market mechanisms for resource allocation in computer systems, with energy systems management as main application.

DiMalloc is sponsored by NUTEK (as part of the PROMODIS program) and EnerSearch AB.

The project was started July 1st, 1998 and the first phase consists of 18 months.

Participants

Project leader: Prof. Arne Andersson, Computing Science Department, Uppsala University
Senior researcher: Dr. Fredrik Ygge, EnerSearch AB.
PhD students: Per Carlsson, Computing Science Department, Uppsala University and Department of Computer Science, Lund University.
Maria Karlsson, Computing Science Department, Uppsala University and Department of Mathematics, Statistics and Computer Science, Växjö University.

The participating organizations are EnerSearch AB, Uppsala University, Lund University, and the University of Karlskrona/Ronneby.

Main Scientific Content

The interest in automated negotiation among different parties represented by computational agents is continuously increasing. We study such negotiations from mainly two aspects; (i) how markets can facilitate efficient resource allocation in distributed environments, and (ii) fundamental properties of market protocols. These two aspects are discussed further below. Both aspects are of vital importance for tomorrow's energy utilities. The research includes theoretical studies as well as field tests in close cooperation with EnerSearch AB and its owners.

Efficient Market Protocols and Resource Allocation Algorithms

On a deregulated market, many energy utilities have declared an interest in providing services rather than merely pure energy. One such service could be to provide a comfortable indoor temperature in a public building. As prices vary significantly during a day (cf. the balance services of Nord Pool, the major market place for electricity in the Nordic countries), it is important to consider energy costs while providing the services. Furthermore, for the same reason it often makes sense for the utility to establish contracts with customers allowing the utility to temporarily control loads at the customer site for some compensation to the customer. As energy utilities typically support a large number of customers (up to some millions), the management of the energy system is a complicated optimization problem, both from a performance point of view (in terms of communication and computation) and from a software engineering point of view. The situation is further complicated by its dynamic nature; customers may leave and new customers may enter.

We have already developed new efficient algorithms for settings of this kind as well as a conceptual framework where the energy system is modeled as a multi-agent system. Some initial field tests have already been performed and others are currently under implementation.

The main research issues of this project are:

  • further development of algorithms for distributed markets and distributed resource allocation in general;
  • further development/incorporation of more complicated load models;
Knowledge transfer of current state of the art and new results to the industrial partners will be fascilitated through publication of reports and papers, and through seminars and/or workshops.

The following demonstrators/prototypes are planned:

  • field tests of the developed methods;
  • building of prototypes of tools for integration of the load management system into the control rooms of power utilities;

Self-Interested Agents in Market Negotiations

Another important field of study is negotiation protocols for markets with divisible goods, such as electricity. Interesting properties of such protocols is how vulnerable they are to manipulation (i.e. "false" bids) and how efficient the outcome is. For example, the major current electricity spot-market for Nordic countries (Nord Pool) is based on bids treating each of the coming 24 hours separately. Practically, this means that when a utility makes a decision for the amounts to buy or sell at different prices at a future hour, this bid has to be based on some predictions of other prices, i.e. the decision of whether or not to start a spare plant is typically based on some expectation on the average price the coming day. Presumably the efficiency of the market can be improved by letting the utilities use more expressive bids, containing dependencies between the different hours. Furthermore, the integration of production costs and more advanced pricing mechanisms for transmission and distribution may also increase the efficiency of the energy system. At the same time, aspects related to the vulnerability to manipulation of such more extended protocols have to be well understood. Our aim is to compare and analyse the use of different market protocols for these (and other) applications and to investigate how agent-based electronic markets can help in this respect. One advantage of agent-based markets is that they can use protocols that are not manually practical (e.g. relying on very fast iterations and/or negotiating with a large number of different agents before closing a deal).

A clear goal for our future work is to contribute to, and possibly develop, better market systems - for electricity trade and trade with other goods.

In particular, we believe that the expertise we will develop in designing and understanding market protocols will be essential for Swedish power utilities on a future deregulated (international) electricity market.

In this phase this part of the project is a pure research activity and the construction of demonstrators and/or prototypes will depend on the characteristics of the research results. Knowledge transfer of current state of the art and new results to the industry will be fascilitated through publication of papers and report and seminars and/or workshops.


A progress report to NUTEK, one of the main sponsors, is found here.