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.