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.
