The Best-Partitions Problem: How to Build Meaningful Aggregations

The design and the debugging of large distributed AI systems require abstraction tools to build tractable macroscopic descriptions. Data aggregation provides such tools by partitioning the system dimensions into aggregated pieces of information. Since this process leads to information losses, the partitions should be chosen with the greatest caution. While the number of possible partitions grows exponentially with the size of the system, this paper proposes an algorithm that exploits exogenous constraints regarding the system semantics in order to find the best partitions in a linear or polynomial time. Two constrained sets of partitions (hierarchical and ordered) are detailed and applied to spatial and temporal aggregation of an agent-based model of international relations. The algorithm succeeds in providing meaningful high-level abstractions for the system analysis.