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.

Direction of research: Distributed Optimal Power Flow

I have just read the following papers on distributed optimal power flow:

1. Kim BH, Baldick R. Coarse-grained distributed optimal power flow. IEEE Transactions on Power Systems. 1997:932-939.

This paper provides a distributed approach to optimal power flow based on an objective function. It involves splitting the network into a variety of regions each with its own set of buses and transmission lines. Regions which have a transmission line between them share variable values by using a dummy bus. The variables are then duplicated for that dummy bus and each region uses their version of the variables to solve their power flow. For each iteration, regions exchange their shared variables and update them until convergence is experienced.

The distributed equations involve using lagrangians to solve and update the shared variables. This paper provides some very good reasons for decentralised power flow and promising test results. As future work it suggests a number of possibilities which could be used. For example make use of previous iterations to avoid having to refactorise certain equations.

2. Baldick R, Kim BH, Chase C, Luo Y. A fast distributed implementation of optimal power flow. IEEE Transactions on Power Systems. 1999:858-864.

This paper is a fast implementation of [1] using techniques from:

3. Wu Y-C, Debs AS, Marsten RE. A direct nonlinear predictor-corrector primal-dual interior point algorithm for optimal power flows. IEEE Transactions on Power Systems. 1994:876-883.

This is one direction that my research is heading. I am very interested in distributed optimal power flow and how this can be used in conjunction with reducing overloaded lines within a network whilst minimising carbon emissions.

Simplex Methods

This week I have been researching the Simplex method and how it can solve linear programming problems. I have specifically been looking at whether a decentralised version exists that could be applied to the generator coordination domain. However so far I think the decentralised version still requires all nodes to know the global objective function and thus still contains centralised elements. I am also looking at whether a message passing algorithm can be applied in order to coordinate generators, however so far I have concluded that each generator must know about all the loads within the network in order to collectively coordinate their outputs. This week I have also applied to IBM and Google for summer internships. I have had two telephone interviews with Google where they asked me some technical questions regarding algorithms.

Video Demo

I've created a short video of my centralised demo. It doesn't have any audio or captions explaining what's going on because I would normally use it during presentations where I explain what's happening.Here's an explanation: To start with the network is working normally, loads and output are balanced and no transmission lines are overloaded. The green node is a generator that has been nominated to follow the load within the network and will ramp up/down accordingly. As the red nodes's load increases the nominated generator will ramp up its output to compensate, however this overloads two transmission lines on the network. In order to reduce the overload, the generators must be coordinated such that they reconfigure there outputs. The objective function is minimising carbon emissions but it is also making sure that the distance between a generators current output and the output it is changing to is minimal.

Tree based power flow

Read Kho J, Tran-Thanh L, Rogers A, Jennings NR. An Agent-Based Distributed Coordination Mechanism for Wireless Visual Sensor Nodes Using Dynamic Programming. The Computer Journal. 2010;53(8):1277.

Contains an algorithm that calculates the sampling, forwarding and routing actions of each node within a network such that maximum information of data is collected. Two algorithms are presented, one which assumes fixed path for data from a node to the base station (i.e underlying tree structure) and one which has flexible routing.

In both cases dynamic programming is used to propagate message from the nodes in the network to the base station. In the tree algorithm messages are propagated from the root (base station) to the leaves and then back to the root again:

1. Starting from the root, node sends to all its children the energy it uses to forward data and its own energy budget (i.e. how much energy it can use). When a node receives this information from its parent it sends its own information to all of its children.

2. Each node sends its D message to its parent, expressing it utility calculated based on its own ability to send data and in conjunction with its children.

3. base station calculates the optimal coordination for the sensors based on whether they forward some of their data or their childrens data. Corrdination message propagates through the network.

Using this as a starting point for calculating flow within the network. I am going to start with a simple tree network of 4 nodes and assume there are no transmission line limits. Need to express a nodes ability to either use power from elsewhere or use its own power to satisfy a load. 

One step forward, two steps back

Today I had a supervisor meeting with Alex and Gopal. In it I explained my simple decentralised message passing algorithm for determining which generators need to ramp up in order to reduce an overloaded line. As in the scenario I described in my previous blog post. However Alex pointed out that the way in which I allocate power does not take into account when a load overloads a line but the load is not directly connected to the line that gets overloaded. In this case a node nearer the load may be able to satisfy it however in my model I had assumed that load was situated at the root of the tree.

Therefore I have turned my attention to solving the decentralised power flow in a tree using dynamic programming. Is there an allocation of generator outputs that satisfy the thermal limits of the transmission lines and satisfy the loads within the tree using a decentralised dynamic programming algorithm. As a starting point I am going to read the following paper which does a similar thing for sending information around a tree using sensors:

Kho J, Tran-Thanh L, Rogers A, Jennings NR. An Agent-Based Distributed Coordination Mechanism for Wireless Visual Sensor Nodes Using Dynamic Programming. The Computer Journal. 2010;53(8):1277.

Initially from the dynamic programming explanations I think each generator will represent a stage and the state of each stage will be a continuous variable representing the generators output. The decision variable for each stage will represent the optimal output for each generator such that carbon emissions are minimised, the flow within the network is satisfied and the transmission lines are not overloaded.

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.

This Week

This week I will be focusing on researching ways to implement a decentralised approach to the problem of generator coordination within a network. I will also be polishing my demo so that it can be displayed at the next energy meeting where I will be giving a presentation on my work so far.

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.

Back in Southampton

Back in Southampton now here is a summery of what I have been doing:
I have been focusing my attention on achieving a good understanding of how the electricity system works by reading a variety of books including 

1. Galvin R, Yeager K, Stuller J. Perfect power: how the microgrid revolution will unleash cleaner, greener, and more abundant energy. 1st ed. McGraw-Hill Professional; 2008.

2. Weedy BM, Cory BJ. Electric Power Systems. 4th ed. John Wiley & Sons; 2004.

3. Gonen T. Electric power distribution system engineering. 2nd ed. McGraw-Hill New York; 2007.

4. Chard FDLC. Electricity Supply: Transmission and Distribution. 1st ed. Longman Group Limited; 1976.

I have also been studying the paper:

1. Davidson EM, Dolan MJ, McArthur SDJ, Ault GW. The use of constraint programming for the autonomous management of power flows. In: 15th International Conference on Intelligent System Applications to Power Systems (ISAP 2009).; 2009:1-7.

with the intention of first recreating the results found in the paper and then applying a decentralised way to calculate power flow analysis. By the end of January the goal is to have a mathematical model of the various constraints and equations used and a set of experiments and results written up in a small two column style paper.