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.

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.