Made a new website

http://users.ecs.soton.ac.uk/sjom106/ check it out!

Summary of "Distributed Constraint Optimization with Structured Resource Constraints"

Read a very interesting paper today, here it is in a summary:


Presents a method for solving distributed constraint optimization problems applied to power networks using an extended DPOP. Represents the problem as a network of nodes which are either power sources or sinks (i.e. transformers which consume some power and pass the rest on to there various connected nodes). An edge between a node represents a transmission line and contains a maximum power constrain. The kirchhoff law is also applied to the entire network such that each transmission line must carry enough power for its directly connected sinks and all the sinks below it in the tree.

A number of feeder trees is used to present a network of this nature such that each feeder tree contains a power source as its root and consists of an acyclic tree with sinks at various levels. The idea is that it attempts to find a value for each agent such that sinks and loads are satisfied. It priovides two methods, one using resource quantification which descretizes resources (However this doesn't scale very well). The other uses resource abstraction which is a more general solution and scales very well. This solution uses partial feeder trees.

Two techniques for speeding the algorithm up are presented: inconsistent and dominated pruning. Inconsistent pruning uses the fact that the power at a parent should be greater then the power wanted by a child node. Therefore if a sink wants more power then its parent has this is inconsistent and thererfore this branch of the solution tree can be pruned.

Dominated pruning happens when more then one complete feeder tree exists that both have the same root and feed the same set of nodes. Thus the higher costing tree can be pruned. A set of results is presented which is benchmarked using the power network configuration made publicly available in [8]

TODO this week

I have just had the second ORCHID meeting. In it we covered all the research people have been doing since the last meeting. I spoke only briefly about max-sum and the areas I have been researching. I have also attended a library training course where we learnt about all the different resources available to us at Southampton. TODO (This Week) : Read DPOP Paper "Distributed constraint optimization with structured resource constraints", read other max-sum papers, research funding opportunities for internships abroad, research variable clustering (GDL paper), research pseudotrees.

This week I have been mostly..

This week I have focused my attention on the max-sum algorithm. I have implemented it in java and have created a simple visualisation to show it trying to perform graph colouring. I am still having problems with the implementation as it doesn't seem to converge to the correct solution. It will often reach the correct solution, but if left running will then converge to all nodes coloured one particular colour. I make sure each variable to function message is normalised before it is sent out and I also randomly allocate a variable state preference to each agent before the algorithm is run. In cyclic graphs (which will always be present when using agents) the max-sum algorithm does not guarantee convergence to an optimal solution, or a solution at all therefore I wonder whether I should implement the termination constraints and see if this makes any difference.

Today I have been reading a number of papers:
"The contract net protocol: High-level communication and control in a distributed problem solver" - presents an algorithm for task execution in a decentralised way using agents. A Manager agent will request a task to be completed, agents submit offers to complete that task with various constraints, the manger agent chooses the best offer, the offers owner becomes a contract agent and completes the task. Note this is a simple algorithm and there is no counter offers allowed.

"Intelligent distributed autonomous power systems (IDAPS)" - Presents IDAPS "Intelligent distributed autonomous power system" which is a form of microgrid.

I also attended the first Energy meeting where we discussed the particular areas we are all working in. These meeting will allow us to go into detail about particular problems that we have, or in order to get people interested in collaborating in a particular area. These meeting differ from the ORCHID meetings in that they are specifically in the area of energy and not the wider area of agents.

While testing the max-sum algorithm against an example in a paper. I found a discrepancy between the papers value for a particular message and my codes value for a particular message. I checked the value manually on paper and it was the same as my codes. I then showed Gopal and he confirmed that the maths that I had used was sound. I am going to check that the paper has made mistake at my supervisors meeting today (just to make sure that I have implemented the max-sum algorithm correctly). TODO: Continue implementation of the max-sum algorithm, Lecture 12:00, version 2 of Gantt Chart

Implementation of MAX-SUM part deux

Finished implementing max-sum yesterday. Been testing it to make sure that it has no bugs. Once this is done, I will knock up a quick viewer to show the max-sum algorithm working visually. TODO: Finish testing max-sum, start implementation of the viewer

Things went wrong

On Friday I accidentally deleted my code I had been working on last week. Although I hadn't written much of the actual max-sum code, I had all the nice functions in place that handled the message passing etc so is a bit of a bore to write again (it is good practise though) Over the weekend I read a paper "Decentralised Coordination of Mobile Sensors Using the Max-Sum Algorithm" here is my take on it:

Uses max-sum to monitor and predict the state of spatial phenomena using a team of mobile sensors. Identifies that some centralised solutions exist (Gaussian Processing) however not acceptable in this setting for security reasons as provides central point of failure. To coordinate sensors, want to choose a move that maximises the total value obtained by the agents. (i.e. the agents that are connected to eachother and thus their utilities depend on eachother). Straight forward max-sum is not suitable in this setting as computation of messages is a bottleneck. Therefore introduces two techniques that prune the size of the joint action space (i.e. Utility) 1. Action pruning algorithm: pre run before the max-sum, prunes states that can never be maximised 2. Joint action pruning algorithm: speeds up computation of the messages from function to variable, uses branch and bound. TODO: Continue coding the max-sum algorithm, go to a lecture at 14:00 on sustainable energy.

Implementation of MAX-SUM

Yeh its a horrible day in Southampton (what a surprise!) This week I have been implementing the MAX-SUM algorithm in java to get a feel for how it works. Even though I studied it in my masters year, implementing it has definitely made me understand the fundamentals more thoroughly. There was one aspect that I couldn't at first get my head around. It was how you calculate the max of multiple agents utilities and q messages. As you increase the number of agents connected to each other, you increase the dimensions of the resulting cube of values which you must maximise across. (Hypercube territory) Thankfully Alex was able to explain it to me with code. TODO: Finished the implementation of the max-sum algorithm, add a viewer so can see if its working

4 day training reflection

The four day intensive course has given me a number of useful skills that I will be using for the next three years, and probably beyond. The things that were really useful to me was the chance to give three presentations and get feedback. Other helpful areas were how to get the most out of your supervisors and how to make my routine of how I read and analyse papers even more useful.

Doing this course has allowed me to network with a number of other PhD students across a range of disciplines. I even have an idea about a possible collaboration with a civil engineer called Andrew Hamilton who is looking at traffic control using emerging technologies. One of his emerging technologies involved cars talking to each other. Immediately I talked to him about agents and how they could play a role in this for coordinating traffic. We swapped emails and will be talking soon about how to solve this problem when we have both researched our respective areas more thoroughly.

However being on this course has meant that this week I have achieved nothing for my PhD. TODO (next week): Implement the MAX-SUM algorithm and clustering variables on a factor graph.

First monthly report

This month I have been conducting lots of reading in the area of energy, smart grids and agent based computing. I have been having weekly meetings with my supervisors where we discuss relevant areas I should be researching and directions that I should be taking. I have made a Gantt Chart of my expected work load from now until the hand-in date of my 9 month report. In the most recent meeting with my supervisors, we established a goal to work towards for the 9 month report: re-implement the work conducted in "The use of Constraint Programming for the Autonomous Management of Power Flows" using C-PLEX and try to make it decentralised by using some sort of coordination algorithm such as MAX-SUM. Work for the next month will consist of implementing the MAX-SUM algorithm and variable clustering to get an understanding of how the algorithm works, Researching and calculating DC power flow in electricity systems and investigating more thoroughly multi-agent based computing and micro-rids.

This week I am on the 4day intensive course that develops my skills in research and presentation.