Research map / Multi-agent systems and games / Human-AI and goal-conditioned
LTLf Synthesis on First-Order Agent Programs in Nondeterministic Environments
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes synthesis of policies for first-order Golog programs under environment nondeterminism with LTLf goals, via a finite game arena built from characteristic graphs, types and XNF, and evaluates it on dishwasher and warehouse robot domains.
Problem
Program realization for high-level Golog agent programs when environment actions can interleave arbitrarily and influence outcomes, with temporal (LTLf) goals over first-order, possibly infinite domains with incomplete initial knowledge.
Approach
Partition actions into agent and environment actions and synthesize a terminating policy satisfying an LTLf goal by constructing a finite game arena over types of worlds, characteristic graphs of the program, and XNF-based LTLf tracking, then solving the game with a fixpoint algorithm (decidable for C2 acyclic BATs without pick operators).
Key results
- Provides a sound and complete algorithm that returns a terminating, winning strategy when one exists, for acyclic C2 BATs without pick operators.
- Implemented in the Prolog-based Golog interpreter vergo and evaluated on dishwasher and warehouse robot domains.
- Construction is incremental, materializing only reachable and relevant parts of the arena.
Limitations
- General synthesis problem is undecidable; decidability requires C2, acyclic BATs and no pick operators.
- Evaluation limited to two hand-crafted domains (dishwasher and warehouse robot).
Experimental setup
Metrics: runtime
Builds on: Golog situation calculus LTLf synthesis characteristic graphs FOND planning
Closest papers by meaning
- Situation Calculus Temporally Lifted Abstractions for Generalized Planning (AAAI 2025 · similarity 0.87)
- EnCompass: Enhancing Agent Programming with Search Over Program Execution Paths (NeurIPS 2025 · similarity 0.87)
- Abstraction of Situation Calculus Concurrent Game Structures (AAAI 2024 · similarity 0.87)
- Natural Strategic Ability in Stochastic Multi-Agent Systems (AAAI 2024 · similarity 0.86)
- A Syntactic Approach to Computing Complete and Sound Abstraction in the Situation Calculus (AAAI 2025 · similarity 0.85)
- Adaptive Reactive Synthesis for LTL and LTLf Modulo Theories (AAAI 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.