Abstract
This paper establishes a rigorous logical bridge between Fully Observable Non-Deterministic (FOND) planning and formal controller synthesis. By introducing "State Strong Fairness" (t-strong fairness) through Linear Temporal Logic (LTL), the authors prove that strong cyclic plans are equivalent to reactive controllers in fair environments. Furthermore, the paper demonstrates that FOND planning can be reduced to Recurrent Success LTS Control (RSGR), allowing the use of efficient synthesis algorithms for complex planning tasks.
Introduction
In the field of Artificial Intelligence, Fully Observable Non-Deterministic (FOND) planning describes scenarios where an agent's actions have multiple possible outcomes, all of which are observable after the fact. A classic example is a robot attempting to grasp a slippery object; the action may result in a successful pick-up or a failure where the object remains on the table. To navigate such uncertainty, the planning community has traditionally relied on "strong cyclic plans"—strategies that guarantee goal achievement provided the environment does not "conspire" against the agent indefinitely.
Despite the practical utility of these plans, the underlying assumption of "fairness"—the idea that an action will eventually succeed if attempted enough times—has remained largely informal. Meanwhile, the formal methods community has developed robust tools for reactive synthesis, where controllers are synthesized to satisfy temporal logic specifications against an adversarial environment. This paper unifies these two perspectives, providing a formal logical characterization of fairness and recasting FOND planning as a synthesis problem.
Formalizing Fairness: The t-strong Definition
A central contribution of this work is the identification of flaws in naive definitions of fairness. In simple terms, one might assume fairness means that if an action is tried, all its outcomes will eventually occur. However, the authors demonstrate that outcomes can be "coordinated" across different states to prevent an agent from reaching a goal, even under this simple definition.
To resolve this, the authors introduce State Strong Fairness (or t-strong fairness) using Linear Temporal Logic (LTL). This definition requires that if an action is executed infinitely often in a specific state, every possible outcome of that action from that state must occur infinitely often. This granular approach ensures that the environment cannot selectively "block" progress by alternating outcomes in a way that bypasses global fairness constraints. The authors use a running example of a "defective door" (involving key insertion and knob turning) to illustrate why this specific definition is required to avoid the traps of naive fairness.
Mapping Planning to Reactive Synthesis
The paper proves a fundamental equivalence: a policy is a strong cyclic plan if and only if it is a winning strategy in a synthesis game against a t-strong fair environment. This allows FOND planning to be treated as a Reactive Synthesis problem, where the agent plays a "game" against the environment to satisfy a goal formula.
To make this mapping computationally feasible, the authors introduce a reduction to Recurrent Success LTS Control (RSGR). While general LTL synthesis is 2EXPTIME-complete, many planning problems possess a "success/failure" structure. By identifying "intended effects" (e.g., the door actually opening when the key is turned), the authors can leverage GR(1) synthesis techniques. These techniques are significantly more efficient, operating in polynomial time relative to the size of the state space, and allow researchers to use highly optimized engines developed by the formal methods community.
Theoretical Results and Complexity
The authors provide two primary theorems that form the backbone of this unification:
- Soundness and Completeness: These theorems formally establish that strong cyclic plans are exactly the right solution concept for environments that satisfy the authors' definition of t-strong fairness.
- Complexity Realization: The reduction to RSGR matches the known exponential complexity of FOND planning (relative to the number of state variables) while providing a path to practical implementation through synthesis tools.
Unlike some specialized planning algorithms that might find a single valid path, the synthesis-based approach naturally generates maximal policies. These policies account for every possible starting state from which the goal is reachable, providing a more robust solution for dynamic environments.
Conclusion and Future Work
By providing a unified vocabulary (LTS, LTL, and CTL*), this research allows the planning and formal methods communities to share algorithms and theoretical insights. While the approach is currently limited by the "state space explosion" problem—where the state space grows exponentially with the number of variables—and the requirement for clearly defined "intended effects," it opens new avenues for research.
Future directions include exploring more nuanced fairness assumptions (such as biased outcomes) and extending the framework to fault-tolerant planning, where the system must survive even when environment assumptions are temporarily violated. This work represents a significant step toward more reliable and formally verified autonomous agents in non-deterministic worlds.
Summary updated