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.

While testing the max-sum algorithm against an example in a paper. I found a discrepancy between the papers value for a particular message and my codes value for a particular message. I checked the value manually on paper and it was the same as my codes. I then showed Gopal and he confirmed that the maths that I had used was sound. I am going to check that the paper has made mistake at my supervisors meeting today (just to make sure that I have implemented the max-sum algorithm correctly). TODO: Continue implementation of the max-sum algorithm, Lecture 12:00, version 2 of Gantt Chart

Implementation of MAX-SUM part deux

Finished implementing max-sum yesterday. Been testing it to make sure that it has no bugs. Once this is done, I will knock up a quick viewer to show the max-sum algorithm working visually. TODO: Finish testing max-sum, start implementation of the viewer

Things went wrong

On Friday I accidentally deleted my code I had been working on last week. Although I hadn't written much of the actual max-sum code, I had all the nice functions in place that handled the message passing etc so is a bit of a bore to write again (it is good practise though) Over the weekend I read a paper "Decentralised Coordination of Mobile Sensors Using the Max-Sum Algorithm" here is my take on it:

Uses max-sum to monitor and predict the state of spatial phenomena using a team of mobile sensors. Identifies that some centralised solutions exist (Gaussian Processing) however not acceptable in this setting for security reasons as provides central point of failure. To coordinate sensors, want to choose a move that maximises the total value obtained by the agents. (i.e. the agents that are connected to eachother and thus their utilities depend on eachother). Straight forward max-sum is not suitable in this setting as computation of messages is a bottleneck. Therefore introduces two techniques that prune the size of the joint action space (i.e. Utility) 1. Action pruning algorithm: pre run before the max-sum, prunes states that can never be maximised 2. Joint action pruning algorithm: speeds up computation of the messages from function to variable, uses branch and bound. TODO: Continue coding the max-sum algorithm, go to a lecture at 14:00 on sustainable energy.

Implementation of MAX-SUM

Yeh its a horrible day in Southampton (what a surprise!) This week I have been implementing the MAX-SUM algorithm in java to get a feel for how it works. Even though I studied it in my masters year, implementing it has definitely made me understand the fundamentals more thoroughly. There was one aspect that I couldn't at first get my head around. It was how you calculate the max of multiple agents utilities and q messages. As you increase the number of agents connected to each other, you increase the dimensions of the resulting cube of values which you must maximise across. (Hypercube territory) Thankfully Alex was able to explain it to me with code. TODO: Finished the implementation of the max-sum algorithm, add a viewer so can see if its working

4 day training reflection

The four day intensive course has given me a number of useful skills that I will be using for the next three years, and probably beyond. The things that were really useful to me was the chance to give three presentations and get feedback. Other helpful areas were how to get the most out of your supervisors and how to make my routine of how I read and analyse papers even more useful.

Doing this course has allowed me to network with a number of other PhD students across a range of disciplines. I even have an idea about a possible collaboration with a civil engineer called Andrew Hamilton who is looking at traffic control using emerging technologies. One of his emerging technologies involved cars talking to each other. Immediately I talked to him about agents and how they could play a role in this for coordinating traffic. We swapped emails and will be talking soon about how to solve this problem when we have both researched our respective areas more thoroughly.

However being on this course has meant that this week I have achieved nothing for my PhD. TODO (next week): Implement the MAX-SUM algorithm and clustering variables on a factor graph.

First monthly report

This month I have been conducting lots of reading in the area of energy, smart grids and agent based computing. I have been having weekly meetings with my supervisors where we discuss relevant areas I should be researching and directions that I should be taking. I have made a Gantt Chart of my expected work load from now until the hand-in date of my 9 month report. In the most recent meeting with my supervisors, we established a goal to work towards for the 9 month report: re-implement the work conducted in "The use of Constraint Programming for the Autonomous Management of Power Flows" using C-PLEX and try to make it decentralised by using some sort of coordination algorithm such as MAX-SUM. Work for the next month will consist of implementing the MAX-SUM algorithm and variable clustering to get an understanding of how the algorithm works, Researching and calculating DC power flow in electricity systems and investigating more thoroughly multi-agent based computing and micro-rids.

This week I am on the 4day intensive course that develops my skills in research and presentation.

A and E

Last night I took one one of my mates to A and E, nothing serious. Since there was a long waiting time, it gave me an opportunity to read quite a bit of hot air. It seems that nuclear power is the future for us if we want to have a 'sustainable' energy consumption for the next 1000 years. There are obviously a lot of problems to overcome first before but it is not totally infeasible. Over the next decades we sill see a rising demand for electricity. This will be due because of a shift to cleaner energy. Electricity is a high grade form of energy which if generated in the right way can be very clean. Therefore a shift to the electrification of certain service such as public transport and heating will be experienced. The book talks about the joys of heat pumps compared to conventional gas fired boilers. They are much more efficient at producing energy (in the form of heat) then gas or combined heat and power (CHP) and thus should be used in the future to provide living spaces with heating (and in the summer with air conditioning) Therefore I will be researching ways in which these micro generators can be incorporated into microgrids.

BAE Systems Report

Today I read the BAE Systems report on smart grids, here is a summery:

This report gives a detailed overview of smart grids and there applications. It begins with defining what a smart grid is and what it consists of. It then goes on to define how it could be used to manage the electricity in a static or deployable army base.

It identifies three aspects of the system that it would implement: demand side management (DSM), supply side managment (SSM) and Network management (NM). DSM is concerned with understanding and manageing consumer power demands in order to minimise peak power across many different consumers.SSM is Resposible for ensuring there is sufficient electrical power available to meet the total real-time consumers electrical power requirements. Needs to balance the generating of power across different generators and facilities. Uses predicted power estimates. NM manages the transmission and distribution of electrical power from the electricity generators to the consumers. This report provides the advantages of using a smart gird to manage the electricy on an army base.

Reading this report gave me some interesting areas that I could look into:

power dispatch and scheduling
network load balancing

All in all I want to look at power flow management and how this could be achieved in a microgrid environment.

monday morning

Today I spent most of my time finishing off the reading of "factor graphs and the sum-product algorithm". Oli and I also went through some more examples for the power systems lectures. TODO (for tomorrow): Read the BAE systems report on Smart Grids, Make a gantt chart for time up until the 9 month report, Go through the last question for power systems analysis.

maths

Over the past few days I have been reading two papers that contain quite a bit of maths. I have been going over both papers trying to understand what is going on. It is slow progress for me. The second of the two papers "factor graphs and the sum-product algorithm" is easier to understand and get a grasp of. So far essentially what the algorithm does is to construct a factor graph from a particular problem (which contains functions and variables) and then compute each variable as a product of all the factors. This is essentially computing a functions as a product of local functions (which take less operations to compute). This is what I understand is going on. Other then this, I have been working through a number of power analysis problems consisting of load factors, peak power, cost for generation etc.

maths

Today I have been trawling through the paper "The Generalized Distributive Law" to understand the maths behind the Max-Sum algorithm. The GDL is based on the "humble" distributive law [i.e ab + ac = a(b + c)] but generalised to other things, such as trees. The idea is that you decompose a problem into a set of smaller problems such that the complexity to solve the smaller problems is less than the complexity to solve the original function. Example f(x1, x2, x3), the complexity to solve this is dependant on all the variables, whereas if f(x1, x2, x3) = f(x1, x2) + f(x2, x3) the complexity is dependant on the maximum number of variables in the functions (in this case 2) therefore reducing the number of operations required to solve the problem. Ruben helped me to understand the basic concept of the GDL algorithm. The paper did contain some difficult maths which I got the general gist of, however I will need to go over this in more detail. TODO (tomorrow) : Read the second paper that Max-Sum is based on "Factor Graphs and the Sum-Product Algorithm"

monday morning

This week I shall be focusing on a lot of reading, surprise surprise! I was given another book to read by my supervisor Gopal called Perfect Power which details "how the microgrid revolution will unleash cleaner greener, and more abundant energy". TODO: Finish reading the current paper, and read another, go to the 14:00 lecture on sustainable energy, read some hot air, look at notes on conventional generation techniques.

interesting stuff

Read a few papers today and had some possible ideas about what to investigate: one paper Coalition formation in transmission expansion planning uses coalition formation to determine the optimal number of transmission lines to add to an existing network in order to supply forecasted load. This same technique could be applied to mircorgenerators to determine how many should be added to the network and in what locations in order to meet various flows. This could be based on certain factors like average power output or efficiency or something. I also talked to Harry in the labs today, he suggested Power Matcher (which I already new about) and also IDAPS which I had forgotten about, so will look at the various papers produced on these implementations in due course.

interesting lecture

Had a lecture on power systems analysis today. It was quite interesting and gave me a few ideas of what could be done. For instance load factor (average power / peak power) could be taken into consideration when controlling a microgrid. The idea is that you want the load factor to be as close to 1 as possible, that way the fluctuations between supply and demand is reduced meaning that high cost generators, which allows peak demand to be satisfied, do not have to be used as much! This is difficult to achieve in a microgrid that contains alot of renewable generators and many loads, but this could be solved using agents. I am interested in this and will look into this area of agent based microgrid management. TODO: Print off some more papers to read, read one paper and make notes, explore load factor and load loss factor, read notes on power systems analysis, go to lecture at 12:00 (sustainable energy), read some hot air (for background knowledge).

computer set up

Finally set up the new computer, its a beastly quad core with 12 GB of RAM and two 22" monitors, veeeerrrry nice! TODO: Read two papers and make comments, download and print some of the papers suggested by Gopal, read some Hot Air.

the start of the week

Tried to go to the conventional generation technologies lecture today at 9am but the lecture was full and there were no chairs. Sorted out my ID card and now in the office getting ready to read a bunch of stuff. TODO : Read some more hot air, Read one paper and make notes, Go to the lecture at 14:00. Over the weekend I have been thinking about what sort of area of smart grid I want to look at. I definitely want to look at integration of microgenerators in a microgrid environment. I need to find the papers that I read for my 4th year research project and make notes on them.

induction

Today is the first part of my induction to the university and postgraduate research. It involves some talks by various important people and a tour of the university campus (in case I have forgotten where everything is :p) TODO: Other then that I am going to read two papers today, they are Multi-Agent Systems for Power Engineering Applications Part I and II (written by the IEEE Power Engineering Society's (PES) Intelligent System Subcommittee). These should give a great deal of background knowledge about how to apply agents to the smart grid environment. I will also be reading my daily dose of "Sustainable Energy - without the hot air" I suggest anyone and everyone to read this, available online http://www.withouthotair.com/

lectures

I have a couple of lectures today, one was at 9:00 (power systems) and the other is at 12:00 (sustainable energy). Both should provide a good background knowledge to the area of Smart grids and energy. TODO: Read and provide comments on two papers, go to the lecture at 12, read some more of hot air, hand in demonstrator form and hopefully set up the new pc.

an interesting fact

One for the people against wind turbines because of bird deaths -
Annual average number of birds killed by wind turbines in denmark = 30,000
Annual average number of birds killed by cats in Britain = 55,000,000
Anyway I digress:
Today I read two papers on the AuRA-NMS which is currently being developed by a number of different Universities and companies. They have come up with a framework that can control a number of things using agents such as power flow and voltage levels, and integration of generators. I have also read a large amount of the book I mentioned previously, it is very interesting. From what I gather so far, the most feasible microgenerators that could be installed on every home and actually produce enough electricity to be worthwhile is photovoltaic panels. Also thermal panels which heat water are another viable way to decrease demands for electricity due to heating. Ways in which these technologies could be integrated and controlled by agents in a distributed system is of some interest to me.

tasks for the day

Got into the office about half an hour ago and have been getting ready to read all day. Got a selection of papers and a book on sustainable energy (without the hot air), so should be good! Hopefully the computer will come today so I can set up my working environment properly. Still, early days!

officially started

So I have now left the world of the intern and entered the realm of the postgraduate researcher! Had my first kickoff meeting today with Alex and Gopal, very daunting but expected. I have some papers to read on multi-agent based systems and energy, gonna get cracking with them over the next couple of days! My computer has apparently arrived but not yet with me, fingers crossed I get it soon.