Advanced Topics¶

Tree Reorganization¶

EPOS is capable of randomly changing the relative position of agents in the tree hierarchy dynamically and on-the-fly during runtime. In other words, the reorganization means that each agent gets assigned a new set of children and a new parent. Note, however, that the overall tree topology is not changed, i.e. if the original hierarchy was balanced binary tree, EPOS ensures it remains balanced binary tree after the reorganization. The reorganization is employed as means of improving the learning capacity of the agents by allowing them to explore new combinations of plans.

When certain criterion is met, the reorganization is triggered. Consequently, a new random relative position of agents within the original tree topology is constructed and each agent receives a new set of children and a new parent. Implementation-wise, the criterion is always evaluated by the current root agent. The current root agent is the one that generates new random relative position of agents within the hierarchy and is the one that notifies the agents that the reorganization is taking place by first notifying its children which then propagate the notification down their subtrees. Note that the actual reorganization takes place during the top-down phase. When an agent receives a notification that the reorganization is taking place, it sends a request message to the current root, and it responds with a message containing the addresses of new children and a new parent. The reorganization also clears all current and previous selections, responses from subtree and indicator variables.

The reproducibility of experiments in terms of randomness in selecting new relative position of agents when the reorganization is triggered can be controlled via a random generator seed. It can be set via one of the following two ways (the example shows setting the seed to 0):

either setting strategy.reorganizationSeed=0, or
config.Configuration.java¶
```
public long reorganizationSeed = 0;
```

The class encapsulating the reorganization functionality is agent.ModifiableIeposAgent<V extends DataType<V>>. This class handles request and response messages exchanged to obtain a new set of children and a new parent. It also handles various reorganization criteria: Reorganization Criterion: Periodically, Reorganization Criterion: Convergence and Reorganization Criterion: Global Cost Reduction.

Reorganization Criterion: Periodically¶

The periodical criterion triggers the reorganization every X iterations. It can be enabled in two ways (the example shows the period of 3):

either setting strategy=periodically and periodically.reorganizationPeriod=3, or

config.Configuration.java¶

public ReorganizationStrategyType reorganizationType =
                                  ReorganizationStrategyType.PERIODICALLY;
public int reorganizationPeriod = 3;

Note that the period of reorganizations must be an integer value.

Reorganization Criterion: Convergence¶

Convergence is detected when the value of the global cost remains unchanged in two consecutive iterations. Note that the current root agent is the one that can check if the system converged. When the system converges, new combinations of selected plans cannot be explored, so the reorganization is triggered. The idea is to revert the state of the system to some previous, memorized state, that was far enough from this local minimum. Memorizing a state means that every agent memorizes its own selected plan. Intuitively, reverting the state and the new relative position of agents should be able to explore a new set of plan combinations, hopefully finding a combination that results in a lower global cost. A parameter called offset controls when the state is memorized. More precisely, if the value of the global cost is equal at iterations \(t-1\) and \(t\), then convergence is detected at iteration \(t\), the reorganization happens between iterations \(t\) and \(t+1\), and at iteration \(t+1\) the agents select the plans they have previously memorized. Finally, the new memorization occurs at iteration \(t+1+\) offset. Note that reverting to the previously memorized state discards local minimum found. Also, note that the value of the global cost at the iteration in which plans were memorized and at the iteration after the reorganization are equal.

The convergence reorganization criterion can be enabled in two ways (the example shows the offset of 3):

either setting strategy=convergence and convergence.memorizationOffset=3, or

config.Configuration.java¶

public ReorganizationStrategyType reorganizationType =
                                  ReorganizationStrategyType.CONVERGENCE;
public int reorganizationOffset = 3;

Note that the offset must be an integer value.

Reorganization Criterion: Global Cost Reduction¶

The Reorganization Criterion: Convergence has one main limitation: all progress EPOS made between the iteration at which the selections are memorized and the iteration at which convergence is detected is discarded after the reorganization. This criterion addresses this problem by allowing the system to trigger reorganizations before converging, hence decreasing the runtime. The idea is that the reorganization should be triggered when the system is too close to the the local minimum, which is measured by the reduction in the global cost in two consecutive iterations:

(1)¶\[\frac{G^{(t-1)} - G^{(t)}}{G^{(t-1)}},\]

where \(G^{(t-1)}\) and \(G^{(t)}\) represent the values of the global cost in two consecutive iterations \(t-1\) and \(t\). Intuitively, when the relative global cost reduction is low, the system is close to reaching the local minimum, but if it is high, the system takes long steps towards it. More precisely, the reorganization is triggered when the relative global cost reduction in Equation (1) drops below a certain threshold. At the iteration immediately after the reorganization, the agents make the same selections as at the iteration prior to the reorganization.

The reorganization criterion based on the global cost reduction can be enabled in two ways (the example shows the threshold of 0.5):

either setting strategy=globalCostReduction globalCost.reductionThreshold=0.5, or

config.Configuration.java¶

public ReorganizationStrategyType reorganizationType =
                                  ReorganizationStrategyType.GLOBAL_COST_REDUCTION;
public double convergenceTolerance = 0.5;

Note that the threshold must be a double value between 0 and 1. If the threshold is 0, no reorganization happens, since the relative global cost reduction can never be strictly lower than 0. If the threshold is 1, then reorganizations are guaranteed to happen since the relative global cost reduction is always lower than 1.

Reorganization Criterion: Never¶

By default, reorganizations are disabled. Externally, it can be done in one of the following two ways:

either setting strategy=never, or

config.Configuration.java¶

public ReorganizationStrategyType reorganizationType =
                                  ReorganizationStrategyType.NEVER;

Optimality¶

When running EPOS experiements it is important to compare them to other algorithms and evaluate how optimal the generated solution is. This can be done by comparing unfairness and global, local or global complex cost of the solution that EPOS converged to with other solutions. An example of optimality evaluation is to compare the EPOS solution with a random generated solution. A random generated solution can be created by selecting randomly a plan for each agent and then calculating all costs. Several random plan selections can be generated, so the EPOS solution can be compared to their average or max cost values. If the total agents and plan sizes are low (e.g. 5 agents with 2 possible plans each), the optimality of solutions can be evaluated by doing an exhaustive search on all possible plan selection combinations and calculating all costs for them. Sorting the plan selections according to their cost and plotting them in a double coordinate system with their indeces creates a solution landscape. Then the EPOS solutions can be placed on the solution landscape. This placement supports in determining whether the EPOS solutions are withing the top optimal solutions selected from the exhaustive search. Arguments regarding the optimality of EPOS solutions and the general ability of EPOS to find most optimal solutions can be supported by such analysis. An example of such analysis can be found in the figure below:

Optimality comparisons with exhaustive search and random plan selection are actively developed. Code and documentation will be updated soon!

How to run experiments with EPOS and COHDA¶

Current implementation of COHDA agents is deprecated. A new implementation will be presented in future version. Stay tuned!

How to run live¶

Under development. It will be populated in future versions.

How to write your own agent¶

Agent code is not yet finalized. Since the code keeps changing, please send us an email for detailed walkthrough for the current version of EPOS.