AgentMatcher architecture, unit commitment, multi-agent system, intelligent agent,

## 1. Introduction

Electricity markets are complex and operate under a variety of rules in different schedules. Electricity markets all over the world are being deregulated these days. Many electricity markets are undergoing a transition from monopoly-like structures to market structures, which are usually identified as power grid virtual markets [5, 6, 15]. In these virtual markets, the price of electricity fluctuates according to the current supply and demand. Therefore, the amount of transactions among sellers and buyers has increased significantly. Transactions consist of determining the most economical power plants to satisfy electricity demands and operating constraints.

Optimizing transactions is regarded as one of the major problems in power system operation, and is referred to in the literature as the unit commitment problem [14]. The unit commitment is a complex, large scale, mixed-integer, and non-linear optimization problem. Since it is a combinatorial problem, it has non-polynomial (NP) time complexity [13].

Besides the complexity of the solutions, power grid transactions are often handled from several wide areas having interconnection of electricity networks. In this regard, best solutions for the transactions can be obtained by using computational grids. The computational grid has evolved from systems sharing distributed resources to service oriented architectures for transparent and reliable distributed systems, which have high-end computational capabilities [7].

The unit commitment problem has been solved using several optimization methods [4, 12], which can be categorized into three types: (1) mathematical methods, such as integer and mixed-integer programming, branch-and-bound methods, Lagrangian relaxation, augmented Lagrangian, and dynamic programming; (2) heuristic methods, which include genetic algorithms, genetic programming, simulated annealing, fuzzy logic; and (3) artificial intelligent methods, which involve artificial neural networks, expert systems, and multi-agent systems.

Since only few knowledge-based methods have been implemented in solving the unit commitment problems, this paper proposes the application of AgentMatcher architecture for computing similarity, pairing, and negotiating between power sellers and power buyers in virtual markets. The AgentMatcher architecture has been developed for e-business and e-learning applications [1].

The paper first provides some background on the AgentMatcher architecture, reviews the similarity algorithm and describes the pairing process. Then, the similarity based on weight variance, which is the extension of the similarity algorithm, is proposed in Section 3. Section 4 discusses the unit commitment problem and also proposes the negotiation algorithm. Finally, the conclusions are presented in Section 5.

## 2. AgentMatcher

In a multi-agent system architecture like ACORN [9], buyer and seller agents can carry the information for buyers and sellers. Buyer agents and seller agents need to communicate with each other through a middle agent to finalize their transaction. In this paper, the sellers are power plants and the buyers are electricity distributors, which will sell the electricity to consumers, such as hotels, shopping malls, industries, public buildings, and houses.

In order to implement the complete transaction, we propose an architecture called AgentMatcher that is composed of three components; the similarity computation of agents, the pairing process of the buyer and seller agents based on their similarity values, and the negotiation process. Thus, the AgentMatcher architecture covers the whole process after the buyer and seller agents enter the market place until they finish their negotiation.

**2.1. Architecture **

The matchmaking scenario of e-learning proposed in [1] could be adopted to our power plant application. Buyer and seller agents enter the power grid market to conduct their transaction as shown in Figure 1.

After power plant agents and power distributor agents enter the power grid market, similarity values are computed for every pair of agents. These similarity values are the prerequisites for pairing.

During the pairing process, our algorithm recommends an appropriate power plant for every power distributor. The results of this pairing process are the prerequisites for negotiation.

Power Distributor 1

Power Plant 1

Virtual

Power Grid
Market

.

Power Plant 2

Power Distributor 2

.

.

.

.

.
Power Plant m

Power Distributor n

**Figure 1. A virtual power grid market.**

Whenever the power plant and power distributor decide to negotiate with each other, the negotiation between them could be conducted based on the negotiation algorithm described in Section 4.

In this paper, when many buyers and sellers are in the market place, we use s_{i} (1im) and b_{i} (1jn) to represent different sellers and buyers, respectively.