Privacy Sensitive Environment Decomposition for Hypertree Agent Organization Construction

Abstract

Cooperative multiagent systems form an active area of research and practice in AI and software engineering. Decentralized probabilistic reasoning, constraint reasoning, and decision-theoretic reasoning are essential tasks of cooperative multiagent systems. Several frameworks for these tasks organize agents into a junction tree (JT). The JT agent organization has several computational advantages, including agent privacy during inference. During construction of the JT, however, existing frameworks utilize construction algorithms that leak the agent privacy. One exception is the HTBS algorithm, which constructs a JT if one exists without disclosing such private information. A limitation of the HTBS algorithm is that if no JT exists in the given agent environment decomposition, it only recognizes the non-existence. A novel algorithm suite DAER (Distributed Agent Environment Re-decomposition) is proposed to overcome this limitation by re-decomposing the environment to construct a JT. DAER has been evaluated in comparison with existing algorithms demonstrating significantly lower privacy loss.