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.

Not for a while!

I haven't posted anything since March, so this blog post is well over due. I will begin to get back into blogging my Phd progress again so expect frequent updates! Since the last blog post I have fully implemented and tested the dynamic programming algorithm applied to electricity tree networks and have thoroughly tested the algorithm using the centralised algorithm I have previously mentioned. A brief overview of the algorithm is as follows:

1. Leaf nodes send messages to their parent describing their ability to generate power such that their loads are satisfied. Each message consists of the power travelling along the parents transmission line, the carbon intensity of the flow, and resulting carbon dioxide emissions.

2. When a node receives all of the messages from its children, it generates its own set of messages which it sends to its parent. A node calculates its ability to generate power and the carbon dioxide emissions that result from satisfying its own loads and all of its children's loads.

It should be noted that each node maintains a mapping from their generated messages to the amount of power they produce and the states that their children are in which result in the flow, carbon intensity and carbon dioxide emissions of the message. This represents the dynamic programming aspect of the algorithm

3. When the root node has received messages from all of its children, it calculates the best possible output it can be in such that it minimises the carbon dioxide emissions of the entire network. The root then calculates what flow will be travelling down each transmission line when outputting this optimal power and propagates this to its children. Each children will then look up what state it is in, and each of its children are in, when it has the specified power travelling along its parents transmission line. The children's optimal states are sent to its children, who in turn do the same calculation until the leaf nodes.


During the last three months I have been implementing the above algorithm and writing my nine month report. I had my nine month report viva on the 17th July 2011 at the University of Barcelona during the IJCAI-11 conference. I am pleased to say that I passed! Dr. Alessandro Farinelli was my examiner and gave me very good feedback regarding my motivation and direction of work. Particularly I needed to make clear the motivation for decomposing the problem and then using agents to decentralise the computation.

Having survived the first part of my PhD, I now have a clear plan for the direction of my work. Initially I will construct proofs for the completeness and optimality of my algorithm. Once this is complete I will refine the algorithm to work in cyclic networks and will then submit a paper to the AAMAS conference.

Implementation Details

I have been working on a tree message passing algorithm which uses dynamic programming to calculate optimal power flow in a tree network given an number of loads and generation units. Leaf nodes start by constructing a number of elements that contain a particular flow, carbon intensity and resulting carbon emission. They calculate it based on whether there is flow coming in from their parent, flow going out to their parent or whether there is no  resultant flow between them and their parent. The leaf nodes send these elements to their parents and the parents then construct their own set of elements by merging the results from their children. This continues all the way up to the root of the tree, at which point the root can calculate the optimum state it should be in to produce the minimum carbon emission. This optimum state is propagated back down the tree and each node uses backtracking to determine what state they should be in given and optimum state from their parent. Once messages have propagated to the leaf nodes the algorithm terminates and each node will be outputting a certain power that satisfies loads in the tree and minimises carbon emissions.

The algorithm has nearly been fully implemented, I just need to code the merging of the elements for the root node and the decisions it has to make. I also need to thoroughly test this.

Decentralised

I have come up with a simple strategy that coordinates generators in a decentralised way. The strategy will be applied to trees and works as follows:

Line A agent detects that it is overloaded, therefore it sends a message to the node receiving its flow that they need to increase their power output by x, and sends a message to the node sending their flow that they need to decrease their generation by x amount. In doing this the amount of power flowing down line A will be reduced by x and thus the line will no longer be overloaded.

Each subsequent node simply forwards the amount of power that is asked of them from a transmission line to all children.

A transmission line agent checks that the power required by one node from the other will not actually overload its transmission line, if it will then the transmission line changes the required power to be capped at the (maximumCapacity - currentFlow)

(i.e. Node 1 sends a message to Node 2 that it requires an extra 300kW, however the transmission line in between can only handle an extra 200kW therefore Node 2 will recieve a request for 200kW instead. )

Once the required power has been propagated down to the leaf nodes the nodes then send messages back to the root saying how much power they can produce and at what carbon intensity.

Finally messages are propagated back down to the leaf nodes starting from the root. At the root node it calculates how much power it needs to ask from each of its neighbours nodes in order to minimise carbon emissions, it only asks for the required power and doesn't care how it is broken down further between generators. Subsequent nodes repeat the process until all leaf nodes have received a message saying how much power is required from them. They all increase by the required amount.

Similarly the subtree that is required to decrease its power output by x amount perform the same steps however the transmission lines do not need to intervene in changing the required decrease in power.

Demo

I have now created a demo which visualises an electricity network with a number of generators and loads. When the demo is run, a load increases on the network, which is then satisfied by a generator ramping up to compensate. However doing this overloads two of the lines on the network. It then attempts to coordinate generators so that the lines are no longer overloaded. The objective function in use is a combination of minimising  the sum of carbon emissions and minimising the change of generators output.

Java implementation of CPLEX

I have written some code in Java which uses CPLEX to solve the same problem that I specified in my last post. The reason for using Java and CPLEX to specify the problem is that an actual simulation can be conducted that uses multiple CPLEX models to demonstrate the centralised approach to generator coordination. The simulation scenario is as follows:

1. Network is balanced, all thermal limits are satisfied. Carbon emissions are minimised. One generator/Node is nominated to follow loads within the network.

2. Load at a substation increases/line failure

3. This causes nominated generator to balance the demand

4. However in doing so this overloads a line.

5. Run the CPLEX code to optimise the thermal constraints within the network and also reduce the distance between the new power output of a generator and its previous power output when the network was overloaded.

6. network solution is achieved, network is restored back to fully working order.

This benchmark will be used to test the centralised, and eventually, decentralised approach.

Programming

Last week I took 'time out' from my PhD to code a BAE Logistics simulator. I made some quick skeleton code with basic functionality to show BAE so that they could come up with a proper set of requirements. I will finish the coding in the coming weeks but will only be working on it part time.

Since the coding I have been working on my PhD again. I am currently testing some CPLEX code I have written. It works out the generator output that minimises the carbon emissions of the generators, subject to thermal limits of the power lines. The plan is to code in some sort of ordering on the generators such that generators that have been connected to the power grid the longest are curtailed last. I am also looking at refining my mathematical model of the problem, however I am having difficulties with specifying an ordering on a set in mathematical form. I have taken a few abstract set theory books out of the library, so hopefully they will help

Need to get back into the habit of blogging!

I have been familiarising myself with a few techniques that are used in the paper "The use of constraint programming for the autonomous management of power flows":

• back tracking search - Search the tree by starting at the root and traversing in a depth first manner. At a particular node C, checks whether a valid solution can be computed from C, if not whole subtree is pruned. Obviously the hard part using a good approximation function that can calculate whether a valid solution exists.
• best first - explores the tree by expanding the most promising node chose according to a specific rule. A* search is an example.

I have implemented the DC power flow equations in matlab, they use considerably less code then the java implementation. Hopefully this matlab implementation will be used by CPLEX, a constraint optimisation solver, so that it can calculate the flow, however I am still working on expressing the problem in CPLEX language. 

In parallel to this I have been describing the model and the problem in mathematical terms, I have written a one page mathematical explanation of the constraints, the network and the variables defining their domains and bounds. This in theory will allow me to then translate it into any coding environment in order to implement it.

A selection of papers that I have read:

1. Dam KH van, Houwing M, Lukszo Z, Bouwmans I. Agent-based control of distributed electricity generation with micro combined heat and power: cross-sectoral learning for process and infrastructure engineers. Computers & Chemical Engineering. 2008;32(1-2):205-217. 

2. Taylor P, Xu T, McArthur S, et al., others. Integrating voltage control and power flow management in AuRA-NMS. In: SmartGrids for Distribution, 2008. IET-CIRED. CIRED Seminar.; 2008:1-4.

3. Pipattanasomporn M, Feroze H, Rahman S. Multi-agent systems in a distributed smart grid: Design and implementation. In: Power Systems Conference and Exposition (PSCE 2009).; 2009:1-8. 

4. Dolan MJ, Davidson EM, Ault GW, McDonald JR. Techniques for managing power flows in active distribution networks within thermal constraints. In: Electricity Distribution-Part 1, 2009. CIRED 2009. 20th International Conference and Exhibition on.; 2009:1-4.

I have implemented the same network as the one in the paper "The use of constraint programming for the autonomous management of power flows". However it does not specify any of the loads, and therefore I will not be able to recreate the exact experiments without them.

Next week I am putting the PhD on a one week hold to code full time on a project for BAE systems.

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