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.