Abstract
This research addresses the challenge of synthesizing robust policies for high-level agent programs (Golog) that must satisfy temporal goals (LTLf) in nondeterministic environments. By restricting the logic to a specific decidable fragment ($C^2$), the authors transform the problem into a finite game, allowing agents to find winning strategies despite unpredictable environmental actions. The framework is evaluated on robotic planning domains, demonstrating feasibility for problems with an unbounded number of objects.
Introduction
In classical AI planning, environments are often assumed to be predictable or follow simple rules. However, real-world robotics involves two major hurdles: nondeterminism, where actions can fail or the environment changes independently, and first-order complexity, involving an unbounded number of objects and incomplete initial information. This paper, presented at AAAI-25, bridges the gap between high-level Golog programming and robust policy synthesis, allowing programs to be "realized" as policies that succeed regardless of environmental interference.
Methodology
The proposed framework treats the agent and environment as two players in a game. To make first-order synthesis computable, the authors introduce several key technical innovations:
- Action Partitioning: Actions are divided into controllable (agent) and environment actions. Unlike strict turn-taking models, the environment is permitted to perform multiple consecutive actions.
- Finite Game Arena: Since first-order logic can describe infinite states, the authors use "types" and "characteristic graphs" to create a finite abstraction. They restrict the logic to the $C^2$ fragment (two variables and counting) and acyclic basic action theories to ensure decidability.
- LTLf Tracking: Goals are defined using Linear Temporal Logic on finite traces (LTLf). The algorithm uses a "Next Normal Form" (XNF) to split temporal formulas into current requirements and future obligations.
- Incremental Construction: To mitigate state explosion, the game arena is built on-the-fly, exploring only the state space necessary to find a winning strategy.
Experimental Evaluation
The researchers evaluated their approach using the vergo Golog interpreter on two benchmark domains: a Dishwasher Robot (moving dishes between rooms) and a Warehouse Robot (moving fragile boxes).
Key Results and Scaling Challenges
The system successfully synthesized policies for domains with an unbounded number of objects. However, the experiments revealed distinct scaling characteristics. As shown in the performance data for the Dishwasher domain, the number of objects (dishes) has a significantly larger impact on synthesis time and state space size than the number of locations (rooms).
While the Dishwasher domain instances were often solved in seconds, the Warehouse domain proved more challenging, sometimes requiring hours. This disparity is attributed to the Warehouse domain's requirement for more complex first-order reasoning compared to the simpler "local-effect" logic of the Dishwasher domain.
Discussion and Future Work
A significant insight of this work is the use of Golog programs as "partial strategies." Instead of planning from scratch, the synthesis engine resolves the nondeterminism within a provided program template to satisfy the LTLf goal.
Despite its success, the current approach faces limitations regarding "object permutation," where the search space grows because the system treats identical objects as unique entities. Future work will focus on symmetry breaking to improve speed, expanding the supported logic fragments, and integrating modern planning heuristics to scale to larger, more complex environments.
Summary updated