Figure 13. Trees with extreme corresponding weights

Figure 13. Trees with extreme corresponding weights.

In the second step, the second priority of the power sellers are taken and the Residue is calculated and accumulated with that from the previous step. The steps are further carried until the Residue is greater than or equal to zero.

When the Residue is greater than zero, the prices of the current priority group are sorted in ascending order. Then, a clearing price is determined based on the intersection between the supply curve and the total demand curve. Figure 15 is used to give better explanation of the proposed algorithm.

Finally, the clearing price is used to select the power plants. The power plants, whose offered prices are lower than or equal to the clearing price, are selected to supply.

Priority	b1		b2		b3		b4
1	s3	0.89	s1	0.84	s5	0.88	s4	0.70
2	s2	0.80	s12	0.79	s10	0.85	s8	0.67
3	s6	0.75	s9	0.74	s7	0.76	s11	0.64

Figure 14. Results for extended tree similarity algorithm.
In Figure 15, the axis presents the capacity in megawatts (MW), whereas the ordinate describes the price in dollars/megawatts-hour ($/MWh). The offered capacities of the sellers from Priority 3 Figure 14 (s_6, s₉, s₇ and s₁₁) are aggregated to form the total supply curve. The total demand curve is derived from the summation of required capacities of buyers.

Further, a clearing price is determined based on the intersection between the supply curve and the demand curve, see Figure 15. All of the power plants whose offered prices are lower than or equal to the clearing price are scheduled to supply.

Price ($/MWh)

Q₁₁

Q₇

Clearing Price

P₁₁

Q₉

P₇

Q₆

P₉

P₆

-Q

Capacity

(MW)

Figure 15. Determination of the clearing price.

Begin

1. 
   For i = 1,…,n (n is the number of power distributors):
   

Calculate Total demand (required capacity) =

aggregation of the subdemands of power

distributor b_i

2. 
   For k=1,…,p (k is the priority index) do:
   

For i=1,…,n select the buyer-seller pair
(b_i, s_j,), where j = f(i), f(i) being the index of a seller that is paired with b_i; in our case these are pairs of power distributors b_i and power plants s_j, respectively.

1. 
   Calculate the Total supply (offered
   

capacity) = aggregation of the

subsupplies of power plant s_j

2. 
   Calculate Residue = Total supply – Total
   

demand

Accumulate the Residues as Residue

If Residue = 0

then the unit commitment is solved

If Residue < 0

then the unit commitment cannot be solved

If Residue > 0

 Sort in ascending order the prices of all s_j,

where j = f(i), i = 1,…,n

 Determine the clearing price

 Select the power plants with offered prices

lower than or equal to the clearing price

End

Figure 16. The Negotiation Algorithm.

5. Conclusion
The AgentMatcher architecture has been implemented to compute the similarity and pairing of the power buyer and seller agents. We have found that the proposed similarity based on weight variance selects a more preferred agent among agents having the same similarity value. A negotiation algorithm has been proposed and utilized to handle power transactions when a power distributor (buyer) has to deal with several power plants (sellers) because of capacity reasons.

The current tree similarity algorithm can only compute the similarity of pair of nodes by comparing their string attributes. We are extending the algorithm by considering all arc-labels in the negotiation. Also, we are modifying the similarity algorithm in different ways to take into account the semantic meaning of the string attributes.

Acknowledgements
This research work is partially funded by the CANARIE eduSource project and NSERC grants of Bhavsar and Boley. We thank Michael M. Richter for discussions and comments about the tree similarity algorithm. We also thank Alexander Chaudhry for proof reading.
References
[1] Bhavsar, V.C., Harold B., and Yang, L., “A Weighted-Tree Similarity Algorithm for Multi-agent System in E-Business Environments”, Proc. 2003 Workshop on Business Agents and the Semantic Web, Halifax, June 14, 2003, National Research Council of Canada, Institute for Information Technology, Fredericton, pp. 53-72, 2003.
[2] Boley, H., The Rule Markup Language: RDF-XML Data Model, XML Schema Hierarchy, and XSL Transformations, Invited Talk, INAP2001, Tokyo, October 2001. LNAI 2543, Springer-Verlag, 2003.
[3] Boley, H., “Object-Oriented RuleML: User-Level Roles, URI-Grounded Clauses, and Order-Sorted Terms”, Proc. Rules and Rule Markup Languages for the Semantic Web (RuleML-2003), Sanibel Island, Florida, LNCS 2876, Springer-Verlag, October 2003.
[4] Clayton, R.E., and Mukerji, R., ” System Planning Tools for the Competitive Market”, IEEE Computer Application in Power, Volume 9, No. 3, July, pp. 50-55, 1996.
[5] Dunn, W.H. Jr., Rossi, M.A., and Avramovic, B., ”Impact of Market Restructuring on Power Systems Operation”, IEEE Computer Application in Power, Volume 8, No. 1, January, pp. 42-47, 1995.
[6] Ede, S., Mount, T., Schulze, W., Thomas, R., and Zimmerman, R., “ Experimental Tests of Competitive Markets for Electric Power”, in 34th Hawaii International Conference on System Sciences, 2001.
[7] Foster, I., Kesselman, C., “The Grid: Blueprint for a New Computing Infrastructure”, Morgan Kaufmann Publishers, Inc., San Francisco, California, 1999.
[8] Lassila, O. and Swick, R.R., Resource Description Framework (RDF) Model and Syntax Specification. Recommendation REC-rdf-syntax-19990222, W3C, February 1999.
[9] Marsh, S., Ghorbani, A., and Bhavsar, V.C., “The ACORN Multi-Agent System”, Web Intelligence and Agent Systems: An International Journal 1, pp. 65-86, 2003.
[10] North, M. et al., “E-Laboratories: Agent-Based Modeling of Electricity Markets”, J. of Algorithms, Vo. 16, No. 1, pp. 33-66, 1994.
[11] Shasha, D., Wang, J., Zhang, K., “Treediff: Approximate Tree Matcher for Ordered Trees”, October 25, 2001.
[12] Sheble, G.B. and Fahd, G.N, “Unit Commitment Literature Synopsis”, IEEE Transactions on Power Systems, Vol.9, No 1, February 1994, pp.128-135.
[13] Tseng, C.L., Li, C. and Oren, S.S., “Solving the Unit Commitment Problem by Using A Unit Decommitment Method, Journal of Optimization Theory and Applications, Vol.105, No 3, pp.707-730, 2000.
[14] Wood, A.J., and Wollenberg, B.F., ”Power Generation, Operation, and Control”, John Wiley & Sons, Inc., New York, 1996.
[15] Wu, D.J., Kleindorfer, P. and Zhang, J.E., “Optimal Bidding and Contracting Strategies in the Deregulated Electric Power Market: Part I”, in 33rd Hawaii International Conference of System Sciences,2000.