Robots and software agents that reason about what they and others know usually represent uncertainty as a set of "possible worlds". Each world is a complete description of how things might be, and the agent knows something exactly when it holds in every world it cannot rule out. This is clean, but it scales badly. An agent that knows only "the cube is in box A or box B" has to carry both completed worlds, and nested uncertainty about what a human believes multiplies them. Existing planners respond in one of two ways. Some forbid disjunctive beliefs altogether. Others enumerate the worlds and hit limits within a handful of objects.
Philosophers of language have independently argued that uncertainty of this kind should not be split into complete alternatives. In possibility semantics, an agent's state is made of partial possibilities that can leave a question open. These possibilities are linked by a compatibility relation, and the propositions they support form an ortholattice: an algebra with "and", "or" and "not" in which the distributive law $A \land (B \lor C) = (A \land B) \lor (A \land C)$ may fail. The proposal is to make this semantic idea the data structure of an epistemic planner. We then test directly whether giving up distributivity buys compactness, or whether partiality alone does all the work.
Core Claim
The Orthologic of Epistemic Modals builds an epistemic orthologic in which "p, but it might not be p" is a contradiction, yet "it might not be p" does not entail "not p". It also gives a procedure for lifting any possible-worlds model into a possibility model. Compatibility and accessibility supplies the matching relational machinery. Its CA frames consist of a set of states, a compatibility relation and an accessibility relation for necessity. A symmetric compatibility relation produces ortholattices; a preorder produces distributive Heyting algebras. Both works are static. Neither defines how a state changes when an agent senses something, hears an announcement, or acts.
Our claim has two parts. First, sensing and public announcement can be defined as operations on finite CA frames that stay within the regular (closed) propositions. These operations agree with classical dynamic epistemic logic on goals that stay inside one epistemic level. The orthologic paper proves that non-classical behaviour appears only when an inference crosses between factual and modal levels, and this is why such agreement is plausible.
Second, on planning benchmarks, this representation lets one partial possibility stand in for a disjunctive belief that classical planners must either ban or split. As a result, the number of stored states grows more slowly than the number of Kripke worlds.
The second part is a hypothesis, not a promise. Its most important test is an ablation that keeps partiality but restores distributivity.
Research Program
The theoretical work defines three update operators on a CA frame $(X, \triangleleft, R_1,\dots,R_n)$. Here $X$ is a finite set of partial possibilities, $\triangleleft$ is the compatibility relation, and $R_i$ is agent $i$'s accessibility relation. Extending accessibility to several agents is itself new, since the CA-frame paper treats a single necessity operator.
The first operator, sensing a factual proposition $\varphi$, intersects with the regular set for $\varphi$ and re-closes. The second, announcement, restricts each $R_i$ in the style of a product update. The third, factual change, is defined through forgetting. Forgetting is the operation that Knowledge Compilation in the Modal Logic S5 and Knowledge Compilation in the Multi-Agent Epistemic Logic Kn use for state progression, but it has never been defined over ortholattices.
We will then prove one result: for goals and preconditions that stay within a single epistemic level, a plan that succeeds under the possibility representation also succeeds under the lifted classical Kripke model, and the reverse holds too. We will also map the complexity of plan verification for the case without factual change. This places the setting next to the classical map in Complexity Results in Epistemic Planning, which shows general epistemic planning to be undecidable and restricted fragments to range from NP to EXPSPACE.
Correctness of the operators will be checked mechanically before any planning experiment. Following the exhaustive approach of the CA-frames paper, which verified its representation results on all lattices up to size 16, we will enumerate small frames. On each one we will confirm that every update maps regular sets to regular sets and commutes with the lifting from Kripke models.
The engineering work replaces the world-set belief representation inside an AND/OR search planner with this structure. In the new planner, branching occurs only on sensing outcomes, not on unresolved disjunctions. All other components stay fixed: search, heuristics and the perspective-taking module used by Human-Aware Epistemic Task Planning.
Baselines
The naive reference point is explicit possible-worlds dynamic epistemic logic. Every valuation the agent cannot rule out is a separate world, and updates are product updates. This is the representation in the human-aware planner of Human-Aware Epistemic Task Planning, which reports "over 5,600 states in a 3-cube setup" and policies covering "up to 14 simultaneous possible worlds". We will reimplement it inside the same AND/OR search, so the only difference from our planner is the belief representation. Beating it means solving larger cube configurations in the same time, with fewer stored states per belief node.
The strongest existing method on standard benchmarks is the heuristic multi-agent planner of Heuristic Strategies for Accelerating Multi-Agent Epistemic Planning. Its variant with both the Enhancement and Belief Lock strategies "outperformed all others in 29 out of 33 hard instances" under a 3,600-second limit. Its enhanced breadth-first search cut time by over 80% relative to plain breadth-first search. We will give it and our planner the same instances, the same 3,600-second limit and the same hardware. Where possible, we will also add their search heuristics on top of our representation, so the comparison isolates representation rather than search. Beating it means solving more of the 33 hard instances, or solving the same ones with fewer explored belief states.
The classical compilation planner of Planning Over Multi-Agent Epistemic States is the third baseline. It is fast only because it bans disjunctive beliefs and bounds nesting depth. In its Corridor domain, total time rises from about 1.14s at depth 1 to about 38.80s at depth 3, driven by the growth in the number of fluents. We will run it on its own Corridor, Grapevine and Thief domains, plus variants we construct that require one disjunctive belief, which it cannot express. Beating it means flatter scaling in nesting depth on the original domains and coverage of the disjunctive variants.
Classical knowledge compilation is the direct competitor on compactness. Here we will implement the separability-based normal form of Knowledge Compilation in the Multi-Agent Epistemic Logic Kn. There is no reported result on Lacuna for an implementation of this normal form, because that paper is purely theoretical. We will therefore implement it ourselves with the same propositional base language, and compare representation size and progression time directly.
The ablation that isolates the key ingredient keeps everything about our planner fixed, but uses a preorder compatibility relation in place of a symmetric one. This yields partial states whose propositions form a distributive Heyting algebra rather than an ortholattice.
Why not just…?
Why not just ban disjunctive beliefs and compile to classical planning? That approach is the right choice when a domain never needs "the agent knows A or B". Its own results show the cost: fluent counts explode with nesting depth. It also cannot represent the cube-in-an-opaque-box situations that motivate the human-aware planner. The disjunctive Corridor and Grapevine variants show exactly where it stops applying, and the original domains test whether we lose speed where it does apply.
Why not just represent belief states as classical formulas, using the separability normal form or the S5 normal form of Knowledge Compilation in the Modal Logic S5? This is the real threat. A formula-based classical representation also avoids enumerating worlds. Its known weak points are the lack of tractable arbitrary conjunction and negation in the separability form, and the risk of size blow-up that the S5 paper acknowledges. Neither shows that it will lose in practice. We will compare sizes head-to-head. If it matches our representation, we will report that non-distributivity yields semantic fidelity but no computational gain.
Why not just use syntactic belief bases as in In Praise of Belief Bases? Belief bases solve a different problem: they ground explicit belief in stored sentences. Their implicit belief still follows the classical system KD, so the disjunction-splitting problem returns as soon as the planner must reason about consequences. We do not treat them as a competing representation for progression. They could, however, be layered on top of either approach.
Why not just speed up classical search with heuristics? Heuristics and representation are complementary, and Belief Lock assumes knowledge is never forgotten. Running the heuristics on both representations tells us whether our gains survive once search is already well optimized.
Proposed Experiments
The first decisive check is correctness. On every small frame we enumerate, the updates must preserve regularity and commute with lifting. Every plan our planner returns must also verify as successful under a classical dynamic-epistemic-logic checker on the original Kripke model. Any failure falsifies the first claim.
The main experiments cover three benchmark groups: the cube-sorting domain with the number of cubes and opaque containers increasing from 3; Gossip, Coin, Collaboration-and-communication and the 33 hard instances of Fang and Lin; and Corridor, Grapevine and Thief at depths 1 to 4. The metrics are instances solved within 3,600 seconds, wall-clock time, explored belief nodes, and stored states per belief node. A "stored state" means a possibility, a world, or a normal-form term, depending on the representation.
The decisive empirical check for the second claim is the comparison with the distributive ablation and with the classical normal form. If the ortholattice planner stores clearly fewer states than both as disjunctive uncertainty grows, then non-distributivity is doing real work. If the distributive ablation matches it, partiality is the source of the gain and orthocomplementation is incidental. If the separability normal form matches it, the contribution reduces to a correct dynamic semantics for epistemic modals. Each of these three outcomes is a finding worth reporting.
References
- The Orthologic of Epistemic Modals
- Compatibility and accessibility: Lattice representations for semantics of non-classical and modal logics
- Knowledge Compilation in the Modal Logic S5
- Knowledge Compilation in the Multi-Agent Epistemic Logic Kn
- Complexity Results in Epistemic Planning
- Human-Aware Epistemic Task Planning for Human-Robot Collaboration
- Heuristic Strategies for Accelerating Multi-Agent Epistemic Planning
- Planning Over Multi-Agent Epistemic States: A Classical Planning Approach
- In Praise of Belief Bases: Doing Epistemic Logic Without Possible Worlds