Timely Common Knowledge Characterising Asymmetric Distributed Coordination via Vectorial Fixed Points

Coordinating activities at different sites of a multi-agent system typically imposes epistemic constraints on the par-ticipants. Specifying explicit bounds on the relative times at which actions are performed induces combined tempo-ral and epistemic constraints on when agents can perform their actions. This paper characterises the interactive epis-temic state that arises when actions must meet particular temporal constraints. The new state, called timely common knowledge, generalizes common knowledge, as well as other variants of common knowledge. While known variants of common knowledge are defined in terms of a fixed point of an epistemic formula, timely common knowledge is defined in terms of a vectorial fixed point of temporal-epistemic for-mulae. A general class of coordination tasks with timing constraints is defined, and timely common knowledge is used to characterise both solvability and optimal solutions of such tasks. Moreover, it is shown that under natural conditions, timely common knowledge is equivalent to an infinite con-junction of temporal-epistemic formulae, in analogy to the popular definition of common knowledge. Categories and Subject Descriptors [Artificial intelligence]: Knowledge representation and reasoning — Reasoning about belief and knowledge, Tempo-ral reasoning, Causal reasoning and diagnostics; [Artificial intelligence]: Distributed artificial intelligence — Cooper-ation and coordination, multi-agent systems; [Real-time systems]: Real-time system specification; [Distributed computing methodologies