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.

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.