Moving forward

I have now constructed proofs for the completeness and correctness of my algorithm:

Proposition 1: The Algorithm is Complete

(Will not ignore any state and will always return an optimal one)

Proof

There are no cycles in the problem, all messaged constructed and sent to node i come from disjoint parts of the constraint graph. To construct messages, each node iterates through all possible states of itself and its children. Each message contains the minimum carbon dioxide emissions that would result when the current node’s loads, and all of its children’s loads, are satisfied. The root node then chooses its own state, and the states of its children, that result in the minimum carbon emission of a feasible solution. Therefore, at each node, all feasible states are evaluated and the root node chooses the optimal set of states which minimises carbon dioxide emissions. Hence, the proposition holds.

Proposition 2: The Algorithm is Correct

(Will not return any invalid solutions)

Proof

This proof follows on from proposition 1. If at each node, only the feasible states are evaluated (i.e. the states that conform to the constraints of the generators and the transmission lines), then each message constructed will contain the minimum carbon dioxide emissions that result from a feasible set of states. Therefore, any solution calculated by the algorithm will be valid as it has explicitly conformed to the constraints of the network. Hence, the proposition holds.

The Next Steps

In order to present a worth while paper at AAMAS, I need to relate my algorithm to existing work and test it against existing algorithms. Therefore, I have applied the MAX-SUM algorithm (on paper) to a tree electrical network and it is able to determine the flows and generator outputs such that the carbon dioxide emissions are minimised. Both my algorithm and the MAX-SUM algorithm are doing essentially the same thing when passing messages. However, the hypothesis is that my algorithm should be faster because it incorporates a number of steps in the messages which it sends and doesn't iterate through every possible state; only the states that are valid.

In order to compare MAX-SUM and my tree algorithm, I have had to modify my tree algorithm slightly. The MAX-SUM algorithm uses a state utility which calculates the carbon dioxide emission when power is produced (and not consumed). Therefore, my tree algorithm has been modified (on paper) to construct messages with a carbon dioxide emissions value calculated when the power is produced. I will now code both of these algorithm and run comprehensive tests.

In other news I have changed the layout and look of my website, please have a look here.

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...

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.

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.

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"