Research map / Learning theory and algorithms / Combinatorial and search optimization
On Action Theories with Iterable First-Order Progression
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.
Identifies situation calculus action theory classes (disjunctive normal and PANACK) for which first-order progression is iterable, i.e., remains first-order across action sequences.
Problem
Progression in the situation calculus generally requires second-order logic; existing first-order progression results (local-effect, normal, acyclic actions) hold only for single actions and are not iterable, since the progressed KB may violate the syntactic constraints needed for the next step.
Approach
Lifts Liu and Lakemeyer's first-order progression result for normal actions by allowing disjunctions in the KB (disjunctive normal action theories), and introduces PANACK action theories, which allow cyclic dependencies among non-local-effect fluents as long as they occur only in context conditions; both are shown to be iteratively first-order progressable.
Key results
- Disjunctive normal action theories are shown to be iteratively first-order progressable (Theorem 14).
- PANACK action theories, which strictly subsume disjunctive normal ones, are shown to be iteratively first-order progressable (Theorem 21).
- Example shows normal action theories (e.g., the Example 15 BAT) become non-normal after one progression step, so FO progression for normal actions is not iterable.
Surprising findings
- Normal and acyclic action progression, though first-order for single actions, can fail to be iterable: a BAT normal w.r.t. both actions becomes non-normal after progressing once.
Limitations
- Progression is FO only for the identified syntactic classes; general action theories still require second-order logic.
- PANACK restricts non-local-effect fluents to occur only in context conditions of SSAs.
- Work is theoretical; applications to planning and verification are left open.
Experimental setup
Baselines: normal actions (Liu and Lakemeyer 2009) acyclic actions (Liu and Claßen 2024) local-effect theories
Builds on: Lin and Reiter progression Liu and Lakemeyer local-effect and normal actions Liu and Claßen acyclic actions Ackermann lemma
Closest papers by meaning
- A Syntactic Approach to Computing Complete and Sound Abstraction in the Situation Calculus (AAAI 2025 · similarity 0.87)
- Situation Calculus Temporally Lifted Abstractions for Generalized Planning (AAAI 2025 · similarity 0.85)
- First-Order Automata (AAAI 2025 · similarity 0.84)
- DynaAct: Large Language Model Reasoning with Dynamic Action Spaces (NeurIPS 2025 · similarity 0.82)
- Towards Epistemic-Doxastic Planning with Observation and Revision (AAAI 2024 · similarity 0.82)
- A Modal Logic for Joint Abilities of Structured Strategies with Bounded Complexity (AAAI 2025 · similarity 0.82)
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.