pydcop.distribution.gh_secp_fgdp

GH-SECP-FGDP : Greedy Heuristic for the SECP Factor Graph Distribution Problem

To minimize the communication load, we place each pair (yj , φj) on an agent ai with i chosen such that xi ∈ Sφj , meaning that xi is one of the variables influencing yj . Similarly, a factor rk is hosted on an agent ai such that xi ∈ Srk . Intuitively this means that the factor representing a rule is always hosted on a agent affected by this rule. As to ensure a balanced computation load, yj ’s, φj ’s and rk ’s are fairly distributed among the candidate agents.

When implementing this heuristic, we use a greedy approach to select one agent among the set of valid agents for a given computation: we select the agent, with enough capacity, that is already hosting the highest number of computations that share a dependency with the computation we are placing. In case of tie, we chose the agent with the highest remaining capacity. By grouping interdependent computations, this approach favors distributions with a low communication cost.

• actuator variable and cost factor are placed on the corresponding device/ agent, which is the agent where the hosting cost is 0

• variable and factor for physicals model are hosted on the same agent. We select that agent by looking at the model’s factor and look for the the agent with enough capacity that already host the highest number of neighbors

Notice that * the communication load is not used in this distribution method * the computation footprint is required

This distribution method is designed for SECP and makes the following assumptions on the DCOP (which are always satisfied if the SECP has been generated using ‘pydcop generate’ command): * variables that represent an actuator are assigned to an agent, with an hosting cost of 0 * If external cost constraints are used for actuators, they must be named after the

actuator’s name. E.g. (l0, c_l0)

• Physical model factor are named after the physical model variable name, e.g. (m1, c_m1)