Home > Downloads




Market-Oriented Programming and its Application to Power Load Management

Abstract

Market-oriented programming is a new approach to design and implementation of resource allocation mechanisms in computer systems. It has its roots in different disciplines, such as economics and computer science (in particular the area of multi-agent systems). This thesis is divided into two different parts, focusing on: 1) central foundations and mechanisms of market-oriented programming, and 2) the use of market-oriented programming in practical applications.

Market-oriented programming is seen as a programming paradigm based on abstractions such as prices and demands. Concepts, terminology and theory from micro-economics form the foundations of the paradigm. Central aspects of these foundations are investigated and some new insights are presented. Furthermore, some relations between standard optimization/resource allocation approaches and markets are described, and novel theorems are introduced. A plethora of algorithms (some stemming from mathematical optimization and numerical analysis, and some new) for the main computational problem of market-oriented programming - the computation of general equilibrium - are described, analyzed and compared. Some issues of self-interested agents in market-oriented programming are also investigated.

A published, and generally recognized, market-oriented approach to the application building climate control is analyzed in some detail. A new approach to this application, based on market-oriented programming, is introduced and shown to be superior to the analyzed approach in many ways. The case study pinpoints a number of potential pitfalls as well as advantages of market-oriented approaches to this and other applications.

A second investigated application is power load management, i.e. the management of loads at the customers' side for obtaining more efficient energy systems management. The basis of the application is described and a new market-oriented approach is introduced and analyzed. The approach is shown to have a number of advantages compared to existing approaches to this problem.

The main conclusion of the thesis is that there are some potential pitfalls of market-oriented programming, but when used with care it provides a highly natural and efficient means for resource allocation in computer systems.

Introduction

Context and Main Research Issues

The research presented in this thesis has been performed in the research group Societies of Computation (SoC) at the University of Karlskrona/Ronneby, Sweden and I have been registered as a graduate student at Lund Institute of Technology and Lund University, Sweden. The work has been managed as a sub-project (sub-project 8) of the Information/Society/Energy/System project - the ISES project - of EnerSearch AB. The ISES project is a multi-disciplinary project with Ph.D. students and professors from, e.g., computer science, business administration and electrical engineering. EnerSearch AB is a research company owned by IBM Utility & Energy Services and Sydkraft AB. Sponsors of EnerSearch AB include ABB Network Partner, Electricite de France, IBM Utility & Energy Services, IT Blekinge, PreussenElektra AG, and Sydkraft AB. For more information refer to the EnerSearch web-site.

Today's energy utilities are facing major changes. Many countries are deregulating the electricity market (and other energy markets) and at the same time the possibilities to communicate with customers increase. Major enablers are concepts for global data networks (such as the Internet) and new communication technologies (such as power-line communication), see further Chapter 9. With this as a background the main question, put to the ISES project as a whole, is: "How can these new technologies increase the competitiveness of an energy utility?"

Of course, there are many aspects of a question of the above type, and nine different sub-projects deal with different issues. For example, one fundamental issue is if the customers are interested in interacting with the utility at all, and, if so, how. The main research issue of one ISES sub-project (sub-project 1) is to try to find efficient communication means by providing the customer with the right amount and form of information based on categorization of different customers' information acquisition and processing characteristics. Another sub-project (sub-project 5) deals with estimation of the potential gain of automating certain parts of the energy system.

The task that was assigned to sub-project 8 (which I have been working in) was to investigate distributed load management. As both computation and communication power is getting cheaper, the number of micro-processors residing close to the customer increases. Domestic appliances are evolving into "smart equipment" capable of doing quite advanced computation and communicating with the outside world. The research issue of the distributed load management project has been to investigate how all this "smart equipment" should be utilized and coordinated for efficient use of the energy system, i.e. to perform distributed load management.

The approach taken is to investigate the applicability of multi-agent systems, and market-oriented programming in particular, to load management. The main questions considered have been:

  • What are the basic principles and properties of market-oriented programming?
  • What is the relation between market-oriented programming and other (traditional) approaches, such as mathematical optimization and traditional approaches to resource allocation? Most importantly, what are the properties of the market outcome?
  • Can market-oriented programming be efficiently implemented? In particular, can it be efficiently implemented in a distributed environment?
  • Are there any existing market-oriented programming approaches to closely related applications?
  • What would a market-oriented programming approach to load management look like and what would the properties of such an approach be?

Main Contributions

This thesis contributes to results on general aspects of market-oriented programming as well as its use in particular applications.

The area of market-oriented programming is rather new and stems from many different disciplines. Many of the contributions are integration and comparisons of results from different disciplines, such as economics, computer science (and in particular the area of multi-agent systems), mathematical optimization, numerical analysis, and control theory, whereas other contributions are new.

In more detail, the main contributions are:

  • A survey of market-oriented programming and clarification of basic concepts, such as relations between different tatonnement processes and price-oriented and resource-oriented market algorithms, and issues related to production in market-oriented programming. (Chapter 2.)
  • Novel theorems for how a general class of resource allocation problems can be decomposed into markets, both with perfect information and under uncertainty. (Chapter 3.)
  • A detailed study of algorithms for market-oriented programming. The study includes the introduction of new algorithms for market-oriented programming based on different standard algorithms from numerical analysis and mathematical optimization, the introduction of a new algorithm CoTree, particularly well suited for implementation in distributed environments, and some comparisons between existing market algorithms and the ones introduced in the thesis. (Chapter 4.)
  • The introduction of a novel algorithm for obtaining feasible solutions from intermediate results of a price-oriented algorithm. This is particularly useful when using market-oriented programming in time critical environments. (Chapter 5.)
  • Investigation of the potential gains and losses of speculation in market-oriented programming, both with perfect information and in the case where the agents hold biased information. (Chapter 6.)
  • Detailed studies of a published, and generally recognized, approach to market-oriented building climate control. The study includes analysis of critical factors for the success and pinpointing of drawbacks of the approach. Furthermore, a novel approach to the same problem is introduced which, in several respects, is superior to the original one. There is also some general conclusions regarding the applicability of competing multi-agent approaches to this problem. (Chapter 8.)
  • Introduction and evaluation of a novel approach to direct load management. The novel approach has a number of advantages compared to existing approaches, and the major concepts also seem highly applicable to indirect load management. (Chapter 9 - Chapter15 .)

Main Conclusions

The very general conclusion of the thesis is that market-oriented programming is a very useful approach for resource allocation in distributed systems in that it often can be efficiently implemented and that it often provides a straightforward way to decompose large problems, and that it relies on very natural abstractions, such as prices, supply and demand. In some more detail, the main conclusions are:
  • Market-oriented programming strongly rely on micro-economic theory and hereby it can take advantage of a significant amount of available terminology, theory and tools. Production in market-oriented programming introduces some issues (such as the risk of deadlock) which are not considered in standard economics, and which require special care. (Chapter 2)
  • Many general resource allocation/optimization problems can be decomposed into markets. (Chapter 3.)
  • Market-oriented programming can be efficiently implemented in many settings. However, we believe that algorithms for multi-commodity markets in distributed environments still can be significantly improved. (Chapter 4 and Chapter 5.)
  • The gains of speculation in one-shot markets where the utility functions are submitted at once are small already with a moderate number of agents. It is clear that for the application of load management when negotiating for an upcoming hour and when entire utility functions are submitted, it is sufficient to impose local optimization rather than competitive behavior. However, speculation when markets are iterated over time or when iterated algorithms are used for single shot markets (which typically are required on multi-commodity markets) is a complex issue, and the difficulties should not be underestimated. (Chapter 6.)
  • Even though market-oriented programming is appealing from many perspectives, comparisons with existing alternatives are important. Exaggerated claims about the benefits of market-oriented approaches will inevitably lead to backlashes. (Chapter 8.)
  • Market-oriented programming provides a very natural way to manage many large distributed resource allocation problems, and when properly used it leads to high quality outcomes. In particular, we have demonstrated that both the application of climate control and load management can be successfully managed with this approach. (Chapter 8 - Chapter 15.)

Publications/Contributors

Most of the material in this thesis has been presented at different conferences, workshops, and seminars, and published in different books, proceedings or technical reports. Here is a complete list of the publications that contain some material published in the thesis, and some comment on the respective paper's connection to the thesis. The list is given in chronological order.
  • Staffan Hägg, Fredrik Ygge, Rune Gustavsson and Hans Ottosson, DA-SoC: A Testbed for Modelling Distribution Automation Applications Using Agent-Oriented Programming, Proceedings of Modelling Autonomous Agents in a Multi-Agent World (MAAMAW '94), Odense, Denmark, 1994.

    In this paper an early version of the basic architecture used in Chapter 10 was presented, though the work was at a very early stage.

  • Staffan H ägg and Fredrik Ygge, Agent-Oriented Programming in Power Distribution Automation - An Architecture, a Language, and their Applicability, Joint licantiate thesis, Department of Computer Science, Lund University, CODEN: LUTEDX/(TECS-3056)/1-183/(1995), 1995.

    The thesis discuss the use of market-based approach to load management in quite general terms.

  • Fredrik Ygge and Eric Astor, Interacting Intelligent Software Agents in Demand Management, Proceeding of Distribution Automation/Demand Side Management (DA/DSM) '95, PennWell Conferences and Exhibitions, 1995.

    Some important difficulties and opportunities related to market-oriented approaches for load management were discussed in this paper. It is one step in the direction towards the current market-oriented approach to load management.

  • Fredrik Ygge, Rune Gustavsson, and Hans Akkermans,Homebots: Intelligent Agents for Decentralized Load Management, Proceeding of Distribution Automation/Demand Side Management (DA/DSM) '96, pp. 597 - 610, PennWell Conferences and Exhibitions, 1996.

    The paper presents a two-commodity approach (with only one explicit commodity) to load management. Even though without technical detail, different load management scenarios are demonstrated.

  • Elmar van Dijk, Rolf Raven, and Fredrik Ygge, SmartHome User Interface: Controlling Your Home Through the Internet, Proceeding of Distribution Automation/Demand Side Management (DA/DSM) '96, pp. 675 - 686, PennWell Conferences and Exhibitions, 1996.

    The paper describes the integration of domestic appliances and the Internet, and is relevant for Chapter 9.

  • Hans Akkermans, Fredrik Ygge, and Rune Gustavsson, HOMEBOTS: Intelligent Decentralized Services for Energy Management, In J. F. Schreinemakers (Ed.), Knowledge Management: Organization, Competence and Methodology, Ergon Verlag, Wuerzburg, D, 1996.

    This paper has many similarities with (iv) above, but is written more for an audience with a knowledge management background.

  • Fredrik Ygge and Hans Akkermans, Power Load Management as a Computational Market, Proceeding of the Second International Conference on Multi-Agent Systems (ICMAS) '96, pp 393 - 400. AAAI Press, 1996.

    A two-commodity (with only one explicit commodity) approach to load management was presented in some detail in. The paper is an important base for both Chapter 4 and Chapter 9 - Chapter 15.

  • Fredrik Ygge, A Framework for Computational Markets, Term paper for the course: Graduate Course on Patterns and Frameworks, January 1997, available from this page.

    This paper describes how OOP concepts, such as design patterns and framework, can be utilized for the implementation of computational markets. The paper is relevant for some discussion in Chapter 2.

  • Fredrik Ygge and Hans Akkermans, Making a Case for Multi-Agent Systems, Proceedings of the Eighth Modelling Autonomous Agents in a Multi-Agent World (MAAMAW '97), pp. 156-176. Springer Verlag, 1997.

    Chapter 8 is based on this paper.

  • Tuomas Sandholm and Fredrik Ygge, On the Gains and Losses of Speculation in Equilibrium Markets, Proceedings of the Fifteenth International Conference on Artificial Intelligence (IJCAI '97), Morgan Kaufmann, 1997.

    This paper essentially constitutes Chapter 6.

  • Hans Akkermans and Fredrik Ygge, Smart Software as Customer Assistant in Large-Scale Distributed Load Management, Proceeding of Distribution Automation/Demand Side Management Europe (DA/DSM) '97, PennWell Conferences and Exhibitions, 1997.

    The scheduling problem is introduced together with other important considerations, such as the transformation between customer preferences and utility functions in a form useful on computational markets. It also describes achieved results in a rather non-technical way. The paper serves as background for Chapter 9 - Chapter 15.

  • Fredrik Ygge, Power Load Management as a Multi-Commodity Market, University of Karlskrona/Ronneby Research Report 1997:15, ISSN: 1103-1581. Date: 18 November 1997.

    This report is a first draft of Chapter 9 - Chapter 15.

  • Fredrik Ygge and Hans Akkermans, Duality in Multi-Commodity Market Computations, C. Zhang and D. Lukose, editors, Proceeding of the Third Australian Workshop on Distributed Artificial Intelligence, pages 65 - 78, Perth, Australia, 1 December 1997.

    Introduction of the multi-commodity resource oriented algorithm (Chapter 4) and the Proportion algorithm (Chapter 5).

  • Arne Andersson and Fredrik Ygge, Managing Large Scale Computational Markets, Proceedings of the 31st Hawaiian International Conference on System Sciences, VOL VII - Software Technology Track, pages 4 - 13, Big Island Hawaii, 6-9 January, IEEE Computer Society, 1998.

    Introduction of the CoTree algorithm (Chapter 4).

  • Hans Akkermans, Rune Gustavsson and Fredrik Ygge, Pragmatics of Agent Communication, Proceedings of KAW'98, Banff, Canada, 18 - 23 April, 1998. (In press.)

    This paper focuses on agent communication and the market-oriented load management approach in this thesis is used as an example. The communication diagram style has (with some modifications) been used in Chapter 9.

  • Fredrik Ygge and Hans Akkermans, On Resource-Oriented Market Computations, Proceedings of the Third International Conference on Multi-Agent Systems, (ICMAS 98), Paris, France, August, 1998. (In press.)

    A revised presentation of the resource-oriented multi-commodity algorithm introduced (xiii) above.

  • Fredrik Ygge and Hans Akkermans, Market Computations in Time-Critical Environments, Submitted.

    A revised presentation of the Proportion algorithm introduced in "Duality in Multi-Commodity Market Computations" above.

  • Fredrik Ygge, Hans Akkermans and Arne Andersson, A Multi-Commodity Market Approach to Power Load Management, Submitted.

    A revised and compressed version of the report "Power Load Management as a Multi-Commodity Market". Furthermore, it introduces the theorems presented in Chapter 3.

All co-authors to the above papers are of course important contributors to this thesis. In addition, a note should be added on the LoadSched algorithm. This algorithm has been developed by Arne Andersson and Eric Schenk in cooperation with the author. The use of the term "we" in the thesis refers to me and the co-authors of the different parts. It should be kept in mind, though, that all co-authors have not been able to proof read all material and there is no claim that all of them agree to everything in the thesis.

Outline of the Thesis

The thesis is divided into two parts. Part 1 deals with general issues related to market-oriented programming and Part 2 describes the application of market-oriented programming to two important applications.

Chapter 2 aims at clarifying the foundations of market-oriented programming and to serve as an introduction to the other chapters in Part 1. Basic terminology and concepts from economics are presented and some differences between economics and market-oriented programming are described. The chapter also gives an introduction to how general equilibrium theory can be applied to actual resource allocation. The next chapter, Chapter 3, formally describes how general resource allocation problems can be modeled as markets. Thus, this chapter shows some fundamental relations between economics and mathematical optimization/numerical analysis. The problem of actually computing a market outcome is treated in Chapter 4. Here a large number of algorithms with different properties are described and compared. One of the conclusions of Chapter 4 is that a wide class of algorithms (price-oriented algorithms) have a property which makes them useless as any-time algorithms. In Chapter 5 we introduce a novel approach to overcome this problem. Chapter 6, deals with the issue of speculation in equilibrium markets. That is, can agents gain (or lose) by revealing false preferences? The final chapter of Part 1, Chapter 7, gives a general summary of Part 1.

The first chapter in Part 2, Chapter 8, studies an existing market-oriented approach to building climate control in some detail. The remaining chapters of Part 2, Chapter 9 through Chapter 15, are dedicated to power load management. Chapter 9 gives a short introduction to load management and describes different issues important for future energy utilities. In Chapter 10 a multi-agent architecture for load management is introduced. The architecture is then demonstrated on a specific load management example in Chapter 11. The issue of scheduling loads is discussed in Chapter 12. Another example is then given in Chapter 13. Different general issues of simplifications and generalizations, for, e.g., the incorporation of more complex load models, are treated in Chapter 14. The final chapter of Part 2, Chapter 15, contains a summary discussion and conclusions regarding the market-oriented approach to load management.

Finally Chapter 16 presents the conclusions of the thesis.

A word (or words) marked >like this appears in the glossary. Terms appearing in the glossary are not marked this way every time they occur, but rather when it is assumed to help the reader.

Conclusions

Market-oriented programming is seen as a new paradigm for design and implementation of resource allocation mechanisms in computer systems. This thesis presents some fundamental issues related to market-oriented programming and its application to building climate control and power load management.

As shown in this thesis market-oriented programming has a multi-disciplinary flavor. The approach stems mainly from economics and computer science (in particular the area of multi-agent systems), but also other disciplines such as traditional mathematical optimization, resource allocation and numerical analysis, are of big importance. In this thesis we have showed how market-oriented programming can benefit from the use of methods and abstractions from other disciplines and what the relation between market-oriented programming and some of these disciplines are. For example, in Chapter 3 we formally showed how a general class of optimization problems could be transformed into corresponding market formulations.

One of the basic ideas in market-oriented programming is to use abstractions from micro-economic theory for design and implementation of resource allocation mechanisms. Thus, even though market-oriented programming and micro-economics have much in common the objectives of the two different disciplines are in many way different. The aim of micro-economics is to develop methods that describes and formalizes human behavior. In market-oriented programming the aim is, as stated above, to use the developed abstraction to design and implement systems. This means that some questions are fundamentally different whereas others are of common interest.

Even though the close relation to micro-economics provides us with very useful theory and appealing concepts for market-oriented programming, there are some potential problems. One is related to production. In standard micro-economics the ordering of production is not considered. In market-oriented programming, however, this can be a critical issue. As was discussed in Chapter 2, different production dependencies can lead to dead-lock situations.

Another, and probably more important, danger is related to the association between human agents and computational agents. An important conclusion of this thesis is that the metaphor must not be taken too far. It is appealing to use metaphors such as the "invisible hand", developed for the human society, also for computer systems. However, as we have described in this thesis, things are not that easy, and nice abstractions are of little help if they are not used properly. For market-oriented approaches to be generally accepted, in-depth studies of advantages and weaknesses of multi-agent systems solutions versus conventional ones in practical applications are needed. In Chapter 8, we offered one such study. Climate control in large buildings is one application area where multi-agent systems, 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. The chapter gives a detailed analysis and comparison, so as to learn about differences between standard versus multi-agent systems approaches, and yielding new insights about benefits and limitations of market-based approaches.

A key question is: in what respect and to what extent are multi-agent (and market-oriented) solutions better than their alternatives? We believe that the building climate control 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 power load management applications presented in Chapter 10 -- Chapter 15, the file allocation problem of Kurose and Simha, and the flow problems investigated by Wellman).

We have therefore shed light over some potential dangers. In some detail we have demonstrated that the suggested market-oriented approach indeed outperformed standard local controllers. On the other hand we also demonstrated that traditional controllers having access to the same data perform even better. A positive result was, however, that we demonstrated how proper utility functions and market mechanisms can provide an optimal scheme from agents using only local data and communicating through prices and demands only.

On the positive side we also have that 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 modeling, understanding, explanation, and knowledge transfer. Moreover, models and pictures that have conceptual simplicity are more easily generalized to more complicated situations. 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 building climate control application, because the limited scope of this resource allocation problem. For example, here the temperature was a uniform performance measure and all thermodynamic processes are assumed to be equal. This will generally not be true in reality, and that will necessitate a big modeling efforts in centralized approaches as standard control engineering. For the present case, we have shown that the multi-agent systems approach offers working solutions of equal quality.

In Chapter 3 we showed that the market-metaphor does not only result in optimal solution for the particular example of building climate control, but for very general classes of resource allocation/optimization problems, also in the presence of uncertainty. This formed the basis for our market-oriented load management design of Chapter 10.

The applicability of market-oriented programming to load management was discussed in Chapter 9-- Chapter 15. We introduced a novel approach to load management based on local agents Homebots communicating through market mechanisms. The approach was also demonstrated on a number of examples. Our conclusion is that the approach is highly applicable to load management and that it has a number of advantages compared to traditional approaches. Main features of the approach is that it:

  • provides an integrated load management strategy for many different types of loads and customer contracts,
  • obtains a high quality solution (often the market outcome is a close approximation of the true theoretical optimum),
  • enables natural decomposition of the problem from a software engineering perspective as well as from a computational perspective,
  • gives the utility a view of the system based on the most natural abstractions -- prices and demand, and
  • provides a local estimate of the value of the customer contract, i.e. gives an on-line cost/benefit analysis.
Having concluded that it is possible to design a load management system as a market-oriented multi-agent system, and that the market outcome is of very high quality the remaining question is if this market-outcome can be efficiently computed or not. This issue was dealt with in detail in Chapter 4 and Chapter 5. The investigation showed that there is a plethora of available algorithmic families from numerical analysis and mathematical optimization that are highly applicable to this setting. We also introduced a novel algorithm CoTree, particularly well suited for implementation in distributed environments.

In concluding the conclusions, if there should be one single conclusions for the thesis as a whole it should be this: Market-oriented programming is very useful for the design and implementation of resource allocation mechanisms in computer systems and highly applicable to applications such as power load management, but it should be used with great care and expectations should be well balanced.