Privacy sensitive environment re-decomposition for junction tree agent organization construction

摘要

A number of frameworks for decentralized probabilistic reasoning, constraint reasoning, and decision theoretic reasoning assume a junction tree agent organization (JT-org). A natural decomposition of agent environment may not admit a JT-org. Hence, JT-org construction involves three related tasks: (1) Recognize whether a JT-org exists for a given environment decomposition. (2) When JT-orgs exist, construct one. (3) When no JT-org exists, revise the environment decomposition so that one exists and then construct it. Task 3 requires re-decomposition of the environment. However, re-decomposition incurs loss of JT-org linked privacy, including agent privacy, topology privacy, privacy on private variables, and privacy on shared variables. We propose a novel algorithm suite Distributed Agent Environment Re-decomposition (DAER) that accomplishes all three tasks distributively. For Tasks 1 and 2, DAER incurs no loss of JT-org linked privacy. For Task 3, it incurs significantly less privacy loss than existing JT-org construction methods. Performance of DAER is formally analyzed and empirically evaluated.