Research Methodology Assignment: Introduction

By the year 2050 the UK government has made it mandatory that we reduce our carbon emissions by 80%. In order to meet this target, lower carbon technologies such as the electrification of heating and transport will need to be introduced. Unfortunately this rising demand for electricity cannot be sustained with the current electricity infrastructure. Therefore a smart grid capable of incorporating an increasing number of generators is required.

These generators need to be coordinated efficiently in order to supply loads within the network whilst satisfying thermal limits of the transmission lines. The proposed solution is to model the network as a constraint satisfaction problem and then solve using constraint programming. However this is a centralised approach and therefore will have scaling issues when applied to a larger network.

To address these shortcomings we propose a decentralised message passing algorithm, max-sum, which scales well with the size of the network; since the size and number of messages sent, is only dependant on a local neighbourhood. Max-sum has been extended to incorporate thermal constraint satisfaction and to give priority to generators that use renewable resources while curtailing non-renewable generators.

The rest of this paper is organised as follows...

Electricity

This week I will be learning all things to do with electricity. I have also written an introduction for my Research Methodology course, here it is:


By the year 2050 the UK government has made it mandatory that we reduce our carbon emissions by 80%. In order to meet this target, lower carbon technologies such as the electrification of heating and transport will need to be introduced. Unfortunately this rising demand for electricity cannot be sustained with the current national electricity structure. A more dynamic two-way electricity network is needed that incorporates decentralised generators, renewable resources and storage devices managed in an efficient manner.

However incorporating these devices will be difficult without revised management techniques. The proposed solution is to split the national electricity structure into multi-agent managed micro-grids which are able to run as isolated electricity networks capable of meeting electrical demand efficiently. One aspect of the management system involves decentralised generator coordination to determine the output of each generator needed to satisfy the loads on the network when thermal constraints apply.

Previous work in this area has used constraint optimisation techniques to find an optimal solution; however this is in a centralised manner, therefore posing potential security and reliability issues due to the central point of failure. DPOP, a coordination algorithm that uses message passing, has been applied to this setting and is almost completely decentralised. However the size of the messages increases exponentially with the size of the network and thus this technique does not scale well.

We propose an extension of the novel algorithm called MAX-SUM which uses message passing to coordinate renewable and non-renewable generators within a micro-grid. Specifically the MAX-SUM algorithm has been extended to incorporate thermal constraint satisfaction and to give priority to generators that use renewable resources while curtailing non-renewable generators. The extended MAX-SUM algorithm coordinates in a decentralised manner, with the size and the number of messages dependant only on a local neighbourhood therefore scaling well.

Power Flow Analysis

Since last time I have finally implemented a properly working max-sum algorithm. I have also applied to work for Google on a summer internship in either north America or Sydney, Australia so fingers crossed. TODO: For the remainder of the week I plan to research the background of power flow analysis and how to do AC and DC power flow of electricity networks.

Made a new website

http://users.ecs.soton.ac.uk/sjom106/ check it out!

Summary of "Distributed Constraint Optimization with Structured Resource Constraints"

Read a very interesting paper today, here it is in a summary:


Presents a method for solving distributed constraint optimization problems applied to power networks using an extended DPOP. Represents the problem as a network of nodes which are either power sources or sinks (i.e. transformers which consume some power and pass the rest on to there various connected nodes). An edge between a node represents a transmission line and contains a maximum power constrain. The kirchhoff law is also applied to the entire network such that each transmission line must carry enough power for its directly connected sinks and all the sinks below it in the tree.

A number of feeder trees is used to present a network of this nature such that each feeder tree contains a power source as its root and consists of an acyclic tree with sinks at various levels. The idea is that it attempts to find a value for each agent such that sinks and loads are satisfied. It priovides two methods, one using resource quantification which descretizes resources (However this doesn't scale very well). The other uses resource abstraction which is a more general solution and scales very well. This solution uses partial feeder trees.

Two techniques for speeding the algorithm up are presented: inconsistent and dominated pruning. Inconsistent pruning uses the fact that the power at a parent should be greater then the power wanted by a child node. Therefore if a sink wants more power then its parent has this is inconsistent and thererfore this branch of the solution tree can be pruned.

Dominated pruning happens when more then one complete feeder tree exists that both have the same root and feed the same set of nodes. Thus the higher costing tree can be pruned. A set of results is presented which is benchmarked using the power network configuration made publicly available in [8]

TODO this week

I have just had the second ORCHID meeting. In it we covered all the research people have been doing since the last meeting. I spoke only briefly about max-sum and the areas I have been researching. I have also attended a library training course where we learnt about all the different resources available to us at Southampton. TODO (This Week) : Read DPOP Paper "Distributed constraint optimization with structured resource constraints", read other max-sum papers, research funding opportunities for internships abroad, research variable clustering (GDL paper), research pseudotrees.

This week I have been mostly..

This week I have focused my attention on the max-sum algorithm. I have implemented it in java and have created a simple visualisation to show it trying to perform graph colouring. I am still having problems with the implementation as it doesn't seem to converge to the correct solution. It will often reach the correct solution, but if left running will then converge to all nodes coloured one particular colour. I make sure each variable to function message is normalised before it is sent out and I also randomly allocate a variable state preference to each agent before the algorithm is run. In cyclic graphs (which will always be present when using agents) the max-sum algorithm does not guarantee convergence to an optimal solution, or a solution at all therefore I wonder whether I should implement the termination constraints and see if this makes any difference.

Today I have been reading a number of papers:
"The contract net protocol: High-level communication and control in a distributed problem solver" - presents an algorithm for task execution in a decentralised way using agents. A Manager agent will request a task to be completed, agents submit offers to complete that task with various constraints, the manger agent chooses the best offer, the offers owner becomes a contract agent and completes the task. Note this is a simple algorithm and there is no counter offers allowed.

"Intelligent distributed autonomous power systems (IDAPS)" - Presents IDAPS "Intelligent distributed autonomous power system" which is a form of microgrid.

I also attended the first Energy meeting where we discussed the particular areas we are all working in. These meeting will allow us to go into detail about particular problems that we have, or in order to get people interested in collaborating in a particular area. These meeting differ from the ORCHID meetings in that they are specifically in the area of energy and not the wider area of agents.