Dynamic Graph Reliability

Models, Algorithms and Evaluation

The Mission
In this game, you have to deal with the following: Input for the problem is a directed acyclic graph (DAG) G = (V,E). Two nodes are marked as s (start) and t (target), and an item must be moved from s to t. Additionally, there are probabilities p(v,e) for failures of edges given. The meaning for all edge/node-pairs (v,e) is that edge e leaves the graph with probability p(v,e) when the item enters the node v. Thus, the graph falls apart while the item is moving, and our decisions about the path of the item influences the probability of reaching the target-node.

One question is, what is the best choice for a successor v', when the item is in node v. Another closely related question is, what is the probability for reaching the target, when we follow an optimal decision-strategy or decision-policy.

We have developed a framework for testing such policies. A server is sending out queries, and another program, called the Engine, is supposed to answer these queries. Both are connected via a game client that also provides a graphical user interface (and not yet a visualization). Below you find more details about the model that is running on the server and about how to implement your own policy as an Engine. Two Engines for testing and presentation are available below.

 

The Model
In our model, we deal with nodes and directed edges. The nodes and edges form a directed acyclic graph on which an item moves from one node to another.
The server will keep an EventQueue that is sorted by time, from which it will generate queries to the Engine. Initially, the EventQueue keeps one event for each possible transition from a node to an edge and for each transition fron an edge to a node.
The server will the run the following loop until the end of the schedule has been reached:
  • Collect queries at current time from the EventQueue.
  • Send a query message to the Engine.
  • Receive a result message from the Engine.
  • Commit the answers from the result message, if possible.
  • Realize the probability distributions, which are associated to the current node.
  • Send message about committed decisions and sampled edge-failures.
Here are a few more details about how the server methods work:

Collect queries: only those queries will be collected, that could potentially be positively answered. E.g. if an edge is no outgoing edge from the current node, there will be no query concerning that edge.

Committing answers: unless the item has reached its final destination, for every query that was sent to the Engine, a new event is generated and added back into the EventQueue. This will be done in different ways, dependingon whether the query was committed or not.
The objective function: The objective function simply is 0 or 1, depending on whether the item has reached its target or not. If the item cannot reach the target any more, the game is over with value 0.

 

Connecting to the Competition Server
Via Internet, you can use a game client (with GUI) to connect to our server. If you aim at developing an intelligent controller for our simulation world, you have to write a stand-alone console program, which connects to our game client. Your controller - we call it the engine - can then be started with the help of the client program. If your engine follows the game dependent text protocol, it can participate. Your engine does only exchange messages with the client program, all communication between client and server via Internet is hidden for you and fully transparent. An easier way to develop a working optimization engine is to use an existing client-library.

 

Downloads


Link

Version

Description

GUI-0.8.4.zip

0.8.4 (09.09.2009)

Game Client and Graphical User Interface. Used to connect to the competition server, to connect an Engine, and for Visualization. The GUI is started with
'java -cp GUI-0.8.4.jar:Game_3u4.jar topsu.GUI' (unix) or 'java -cp GUI-0.8.4.jar;Game_3u4.jar topsu.GUI' (windows). It is recommended to create a folder 'Error' in the same directory where you start the GUI.

Two example engines (sources).
UCTengine.exe
YESengine.exe

1.0 09.09.2009

Two engines: UCTengine and YESengine. The YES engine is very simple and answers all queries with 1 (or YES). The UCT engine uses the simulation of the server for internal sampling and combines the sampling with a so called UCT algorithm, mainly known from computer-Go experiments. There are two makefiles 'makeYES' and 'makeUCT'. If you use cygwin for compilation, you might have to use the linker-switsch '-mno-cygwin'.

DGR1_micro.sql


Instance data for the DGR_micro1 example.

DGR1_datamodel.txt


SQL based data definition.


Contact

Ulf Lorenz (flulo'at'upb.de)
Andre Berger (berger'at'math.tu-berlin.de)
Ralf Hoffmann (rhoffmann'at'math.tu-berlin.de)

Index A – Z | Impressum | Webmaster | Modified: 10.05.2005