Natural Language PDDL (NL-PDDL) for Open-world Goal-oriented Commonsense Regression Planning in Embodied AI
Authors: Xiaotian Liu
Armin Toroghi
Jiazhou Liang
David Courtis
Ruiwen Li
Ali Pesaranghader
Jaehong Kim
Tanmana Sadhu
Hyejeong Jeon
Scott Sanner
Venue: ICLR 2026 Poster (2026)
Keywords: Open-world Planning
Lifted Regression
Embodied Agents
Primary area: applications to robotics, autonomy, planning

Abstract: Planning in open-world environments, where agents must act with partially observed states and incomplete knowledge, is a central challenge in embodied AI. Open-world planning involves not only sequencing actions but also determining what information the agent needs to sense to enable those actions. Existing approaches using Large Language Models (LLM) and Vision-Language Models (VLM) cannot reliably plan over long horizons and complex goals, where they often hallucinate and fail to reason causally over agent-environment interactions. Alternatively, classical PDDL planners offer correct and principled reasoning, but fail in open-world settings: they presuppose complete models and depend on exhaustive grounding over all objects, states, and actions; they cannot address misalignment between goal specifications (e.g., “heat the bread”) and action specifications (e.g., “toast the bread”); and they do not generalize across modalities (e.g., text, vision). To address these core challenges: (i) we extend symbolic PDDL into a flexible natural language representation that we term NL-PDDL, improving accessibility for non-expert users as well as generalization over modalities; (ii) we generalize regression-style planning to NL-PDDL with commonsense entailment reasoning to determine what needs to be observed for goal achievement in partially-observed environments with potential goal–action specification misalignment; and (iii) we leverage the lifted specification of NL-PDDL to facilitate open-world planning that avoids exhaustive grounding and yields a time and space complexity independent of the number of ground objects, states, and actions. Our experiments in three diverse domains — classical Blocksworld and the embodied ALFWorld environment with both textual and visual states — show that NL-PDDL substantially outperforms existing baselines, is more robust to longer horizons and more complex goals, and generalizes across modalities.

Published as a conference paper at ICLR 2026
NATURAL LANGUAGE PDDL (NL-PDDL) FOR OPEN-WORLD GOAL-ORIENTED COMMONSENSE REGRESSION PLANNING IN EMBODIED AI
Xiaotian Liu' Armin Toroghi', Jiazhou Liang', David Courtis', Ruiwen Li', Ali Pesaranghader', Jachong Kim², Tanmana Sadhu², Hyejeong Jeon', Scott Sanner 'University of Toronto, LG Electronics, Toronto AI Lab, 'LG Electronics, *Vector Institute of Al Ixtaatilnt.Lia..mmmi.oooooo lii.iig..n david. court david.courti s) @mail utoronto.ca.
ruiienn.L@@allmmiuuuttrrootttte ca. huui.eeearannhhdddee.ejeoogggg kim, tanmana. sadhu, jeon 01ge com,
ABSTRACT
Planning in open-world environments, where agents must act with partially ob- served states and incomplete knowledge, is central challenge in embodied AI. Open-world planning involves not only sequencing actions but also determin- ing what information the agent needs sense to enable those actions. Existing approaches using Large Language Models (LLM) and Vision-Language Models (VLM) cannot reliably plan over long horizons and complex goals, where they often hallucinate and fail to reason causally over agent-environment interactions. Alternatively, classical PDDL planners offer correct and principled reasoning, but fail in open- world settings: they presuppose complete models and depend on haustive grounding over all objects, states, and actions; they cannot address mis- alignment between goal specifications (c.g., "heat the bread") and action speci- fications (e.g.. "toast the bread"); and they do not generalize across modalities (e.g., text, vision). To address these core challenges: (i) we extend symbolic PDDL into flexible natural language representation that we term NL-PDDL, improving accessibility for non-expert users as well generalization over modali- ties; (ii) we generalize regression-styl planning to NL-PDDL with commonsense entailment reasoning determine what needs to be observed for goal achieve- ment in partially-observed environments with potential goal-action specification misalignment; and (iii) we leverage the lifted specification of NL.-PDDL. to facil- itate open- world planning that avoids exhaustive grounding and yields a time and space complexity independent of the number of ground objects, states, and ac- tions. Our experiments in three diverse domains - classical Blocksworld and the embodied ALFWorld environment with both textual and visual states show that NL-PDDL substantially outperforms existing baselines, is more robust to longer horizons and more complex goals, and generalizes across modalities.
INTRODUCTION
Open-world planning where the agent operates under partial observability and incomplete knowl- edge. is essential for embodied agents to perform real-world tasks. Such embodied environments are inherently open-world and involve reasoning over multitude of objects, posing challenges for planning. For example, we consider Figure [ where the agent is asked to "toast the bread and leave on a plate". To efficiently identify the sequence of actions that achieve this goal given only partial observations of the state and an incomplete environment model, the agent must find the relevant
* "quual contribution
In this work, we characterize open-world by partial observahility and incomplete domain knowledge, dis- tinguishing it from open-world games, which refers open-ended tasks in expansive environments.

---

Published as a conference paper at ICLR 2026
Gool
Iotiial Stnte
"aated"""Oyyiiee plate' (a(leed"( (ty)"
"Ploas Heat bread frrees
Action: "pick up [Do]" Any flocnt
POOL
Actions "put To on bY
(Brood) in (25) ((Brad) on (B)) (Po/Bread, 9r/3y)
"[ttrad) basse iith a plate x ([lmma)) is Ob?!
Aution: "buil (2o) using (?r) v. Any Alunnt
Agent's Actions
sada plss
Regresslon Step!
Appel Regresfor
"pot (2o) on (tel", (Te Voluet in: "roppcdr)) Iraconditine:
Uread heated w'Or)) plate The agent holée (Itread)
Fiftere
Action: "tnart (Tt) using (r)) ((tread) is trasted - "[lieed)) is hosted' (Pay Bread)
"Te spoatt sopaaiiiiae lo wayg?"
Action: "pick up (to)'
Artion: "put (1o) on (11) + Any fluent
"Tee heaat owr
Nu
"pick (ha)
Seader
Regression Step
Irscenditina:
"Th sparz nar Dhe
(22) can toast (20g is W in The agent holds (Bread)"
Action "pic up Boj"
"bail (hw) (Pr)", Phiiie 1-W 'moop??
agent possesses (Besad)) > "The agent holds (Bready'
Og
(Pu Becod)
tantee (Ne
Regression Step
Elfeets
"Vaal shalla"
22) can toest (Bread) The agent near (Braad) 4 E2) is plats
EL "piek up
"Inast (Po) Chej" (Phot Vaytow Yags
Progeditios:
sesting
"he tprk
Adl
"Colatraand"
"put
Figure I: Overview of the NL-PDDL framework: (Agent's Actions) The specification of actions available to the agent are provided in natural language (NL) variant of PDDL that we introduce. (Goal) The user provides NL instructions that are automatically translated into an NL-PDDL goal specification. (Initial State) The initial state given as an image. (Planning Goal) Open-world first-order planning proceeds top-down: starting from the goal, regressed subgoals are generated that must hold before each action can be applied (c.g., the goal (bread) is heated regresses to the action toast (bread) using (toaster), which generates subgoals the agent holds the (bread) and toaster is available). At each step, LLM-based entailment connects subgoals with the NL effects of candidate actions and reasons about object affordances (e.g.. toaster can toast bread, but a pot of water canmot). (Selected Plan) A VLM grounds the NL object names in a regressed subgoal to their corresponding entities in the initial state image that are then used to instantiate an actionable plan,
objects (e.g., bread, toaster, and plate) while judiciously ignoring irrelevant ones. It must also use its commonsense knowledge to reason that a toaster can heat bread, but pot of water cannot.
The breakthrough of foundation models such as Large Language Models (LLM) and Vision- Language Models (VLM) has led to their increased usage in planning (Yao al. 2023b; Li al.
2024| Kong et al.) 2024); yet, they come with critical limitations (Shojuce et al. [025] Kambham pati al.] 2024). These models struggle generate reliable long-horizon plans with sound causal reasoning about the interactions between the agent and its environment as they lack a mechanism to track state changes and project how actions alter the world (Valmeekam et al. (024). Moreover, they fail on complex goals involving multiple logical constraints (Goebel & Zips| (0225). and their black-box nature makes it hard to interpret or verify their generated plans (Aghzal et al. 2025).
In contrast, classical planners, such as those based on the Planning Domain Definiion Language (PDDL) McDermott et al., 1998), have traditionally served the role of planning in AI. While ver- ifiably correct, these methods often presume all objects and relations are known in a perfect model that can be exhaustively grounded. These methods also cannot bridge misalignments between goals and action specifications (e.g., reasoning that the action "toast the bread" is able to achieve the goal "heat the bread"s a rev). Such limitations are too restrictive for the the open-world world setting we address here.
To overcome the limitations of existing methods, we introduce NL-PDDL, a planning framework that combines the expressive flexibility of natural language (NL) with the formal guarantees of symbolic planning. An overview of the NL-PDDL workflow is provided in Figure and its caption. Concretely, we make the following key contributions open-world planning in embodied Al:
2

---

Published as a conference paper at ICLR 2026
We extend classical PDDL into NL-PDDL, flexible representation that lets users specify goals and actions abstractly in NL. This flexibility reduces the specification burden (vs. rigid PDDL schemas) and tolerates semantically incomplete and syntactically imperfect domain and state de- scriptions while maintaining sound plan generation.
We propose an open- regression-style NI.-PDDL. planner that uses LLM-bbased common- sense entailment over regressed subgoals to both infer the observations needed to achieve target (e.g., heat bread - find toaster) and resolve misalignments between (sub)goals and action effects.
We avoid exhaustive grounding via lifted regression (Reiter 1991). Instead of reasoning about specific objects (e.g.. pan3, toasterl), lifted regression leverages the variables inherent in NL- PDDL (e.g.. "there exists some x that can toast bread"). Lifted plans are instantiated only when suitable objects are found, making planning complexity independent of the number of objects and abstractly capturing a lifted conditional plan of all initial state conditions that can achieve a goal.
Across three diverse planning domains Blocksworld (Valmeekam et al. 2022), ALFworld, and ALFworld- Vision (Shridhar et al., (022)) we show that lifted regression planning in NL-PDDL achieves higher plan-success rates than strong baselines, remains robust as plan horizons increase, and generalizes across both text and vision modalities.
2 METHODOLOGY
In this section, we present Natural Language PDDL (NL-PDDL),, framework for open-world, goal-oriented planning by leveraging regression-style reasoning enhanced with L..M-based com- monsense reasoning. While classical PDDL provides a sound framework for long- long-horizon planning, it cannot facilitate commonsense reasoning unless such knowledge is explicitly encoded by a domain designer. For example, classical PDDL solver cannot infer that is oooassa ed (bread) implies isHeated (bread) even though it is intuitively clear to humans that "if bread is toasted, it is likely heated". NL-PDDL builds on the formal framework of classical PDDL but replaces sym- bolic predicates, variables, and objects with typed NL counterparts, enabling seamless integration of LLMS perform commonsense entailment inferences during planning. For a formal review of PDDL and first-order regression planning extended here, we refer the reader to Appendix B
Natural Language Representation of PDDL. In classical PDDL, predicates, objects, and variables are represented with rigid symbols. NL-PDDL replaces these symbols with typed NL counterparts. For instance, the symbolic predicate isToasted (bread) becomes "the (bread) is toasted"' "bread" "food", while "the (?o:food) is toasted" denotes its lifted form. Here, 2o:food indicates that (?o) is of type food.
NL--PDLL Problem Definition. NL.-PDDL problems are defined like classical PDDL problems, but aimed at open-world planning. We define an NI.-PDDI. problem as a tuple P (G, A, F, h), where G is conjunctive formula expressing the agent's goal, and F is the set of lifted NI. predicates in the domain. A is the set of actions (y)), i.c., parameterized first-order operators. Each a(y)) e A is defined by: preconditions a(y). .re S F, which must hold for the action to execute; add effects (dd) S F., which become true after the action is executed; and delete effects a a(ū) del which no longer hold after execution. The planning horizon h e N is the maximum length of feasible plans. The goal in NL-PDDL is to construct a conditional plan II that maps subgoal formulas to action sequences that can achieve them:
II= [(11
(a (IT.), a 1i (I )),,,, (vx((T))) (a (a ,..., ti (xkins) }>)}
(1)
where each (x,) is a first-order formula representing a subgoal, and (I
the corresponding sequence of actions (i.e., plan) with length n, & h, and each o xú As an example, the plan derived by NL-PDDL for the problem in Figure Tis presented in Figure 2
2.1 FIRST ORDER REGRESSION IN NL-PDDL
Effect Axioms. Following the methodology for first-order regression defined in Appendix B we first need to transform our NL-PDDL description into the effect axioms that are used to perform regression planning. Specifically. following the notation of Appendix B we build axioms of the
form of Equations and 9 and provide concrete example of Prases. Ouen: (2o, ?r) for action "toast
3

---

Published as a conference paper at ICLR 2026
II ==1 [(
1/ : "(Rread) is heated x((y)) is plate"> (BBradd on (2g)"
(0)
2 : ((eead) hested""A11y) "The agent holds (Beeady"
[pot (Bread) (29)*
Va *(2r) can toast (Bread) (Bread)"x""()) is plate"> "The agent holds (Bread))
Toast (Breaad) using (76)
[put (Bread) on (?v)*)
9/4 ?(2r) (Bread) (²)) plate""" The
(Bread)"
"pick up (Bread)"
Tnast (Bread) using (?r)
}]
*put (Bread) on (?9)
Subgoals
Action Sequenoes
Figure 2: The conditional plan derived by NL-PDDL for the problem in Figure
(2oxobject) using (Proobject)" and predicate "(?o) is toasted" from the NL-PDDL description in Fig-
ure 3
Running Example (continued):
Predicate
Astion toast (fo: object) using (?r object]"
Positive effect axiom for
"(oo: object) toasted
with respect
Adtion Toast (?0) using (?r)"
Precondttion
Nadialaa Predicate
((rr) toast (2o)*
"the agent holds (?o)"
(20) is toasted
Poeetet Sueu (?o, ?r)
Prodicate
Astion put (Yo object) on (Yr receptacle]"
Negative effect axiom for "the agent holds (To object)" with respect
Procondllon
state
toast (2o) using (?r)"
"the agent is near (?r)"
"the agent holds (2o)"
"the agent holds (7o)"
Ppue. Opez (?o, ?r)
Figure 3: Example of positive and negative effect axioms based on the NL-PDDL problem in Fig- ure
In English, this says object "(?o)" is toasted in the next state if the agent holds it, and the agent toasts "(?o)" using object "(?r)" " that can toast "(?o)". To illustrate negative effect axioms, construct "paan oza (?o, ?r) for action "pul(?o) Figure 3 In English, this says if the agent holds an object "(?o)", is near receptacle "(?r)", and puts "(?o)" on "(?r)", ", then the agent no longer holds "(?o)" in the next state.
(?r)" and predicate "the agent holds( (o)" in
These positive (negative) effect axioms are only constructed for predicates and actions if the pred- icate is in the add (delete) effect of the action in the NL.PDDL description. Cases that a predicate appears in the effects of multiple actions are handled via disjunction (see Appendix for details).
Successor State Axioms. As described in Appendix B successor state axioms (SSAs) are the workhorse of lifted regression planning in that they allow the replacement of a predicate in post- action state with the necessary subgoals required to achieve it. Let Fy, (v7) denote the value of predicate F(yP) in the next state after executing action a; (g)) The SSA for F(yP) defined as:
F. = = = (T)
(F(z) FF (7))
(2)
In English, an SSA states that a predicate F is true in the successor state iff it was made true by a positive effect, it already true and not made false by negative effect. We construct the SSAs for each predin-ee pair. While we leave complete formal details to Appendix [ due to space limitations, we provide the SSA for predicate Proasted (2o) and action Ohoase (?o, ?r), and for predicate Photos( (?o) and action (?o. ?r) in Figure 4 as examples to illustrate the process of SSA. After constructing the SSAs, NL-PDDL recursively regresses each subgoal through applicable actions to construct the conditional plan II. We explain the regression procedure in the next section.
2.1.1 REGRESSION OF POTENTIALLY MISALIGNED PREDICATES IN NL-PDDL
In regression planning with classical PDDL, goal predicates are only matched to action effects that share the same predicate names. In NL, such exact matches rarely occur due to variability in phras-
2 All unquantified variahles assumed be universally quantified.
4

---

Published as a conference paper at ICLR 2026
Running Example (continued):
Preicale
Soler
Successor state axiom
for
(oo object) toasted"
and
toast
object) using (?h oboject)"
Naslasaa Predicrr
Prodissa
Actin
Procendion
toasted"
(Po) toasted"
'taat (Po) using, (?r))
(Tr) toast (Po)"
"the agent near (?r))
Pleasi Rove (?o, 3r)
Fredecil
Action
Successor state axiom
for
The agent holds (?o object)"
and
put (To: object) on (Tr: receplacle]"
Stal Fredicate
Prodkate
Adloo
Drecoditon
"the agent holds (2o)
the agent holds (2o)
A -(a
put (2o) on (2r)"
^
"the agent is near (?r))
"the agent holds (2o)
Paess Opa (?o, ?r)
Figure 4: Example successor state axioms induced from the corresponding positive and negative effect axioms.
ing, instead an action effect may entail goal literal, e.g., "the bread is toasted" entails (-) "the bread heated" this section, we extend lifted regression planning using LLM entailment (HLLM)
Regression of Positive NL Predicates. Let ( be a predicate in the next state. We aim to regress it through an action d; to derive pre-action conditions such that if they hold, executing a; results in next state that entails P' (z7) To this end, we first identify predicate F T2 that can be unified with P' In PDDL, unification makes the two predicates syntactically identical through variable substitution, but NL-PDDL allows more general form of unification based on commonsense entailment: predicates F(=) and (z() are unifiable iff they have equal arities and substitution 9 exists that induces an injective mapping between their variables such that:
(i) For every pair of corresponding types t2 T, and to T. mapped by 0, to FLLM tz. (ii) After applying the substituted predicate F()) entails the substituted goal predicate P'(x)) i.e., F(Z)0 FLM P'(
A legal typed unification results in substitution @ that is mapping of variables to terms (e.g.. 0 = {a/u), so that F(x)0 F(y)), which then permits a misaligned regression to proceed. Formally, let F (z) E & denote the SSA formula for F=) with respect to a; under the unifier 0:
Regr, (P)))) F. (=)0.
(3)
With Regr,, we can now formally regress predicate through an action with misaligned effects:
Running Examplec
grad
Action
Regr.
"(breed: food) heated"
"Inasi (Po: alyec) iiing (Bo objject"
120) can (oa) A "the agent holds (Po)"
= (7o/ "uroal""
Onilication
- (2o/ "oreal?
Condition i): Type Consistency
"food" iuse "object"
(brend) Freas '(besad) hoated"
'[ho: object is westtd"
Condition
Figure 5: An example of regression step of a positive predicate with goal-action misalignment.
In the example of Figure to identify the subgoals necessary for the predicate "(Brea:.fod)) is heated" to hold after an action is executed, aim to find predicate unifiable with it. The predicate "(?o:object) is toasted" qualifies, with = { ("?"" ""bread"", because (i) type consistency holds ("food" FLLM "object")) and (ii) after substitution, ("bread is toasted" I LLL "bread is heated"). This allows us to derive the regressed subgoal condition (given by the SSA) that can achieve "(bread) heated". which is how subgoal 4/s is derived from the the conditional plan example of Figure
"This relaxation from syntactic equivalence to entailment based unification allows, for example, unify- ing "(?x:food) is on (?y:plate)" with "(Py:receptacle) is under (?x:object)". as they are both binary and with 0 (?x/?y,?pp ?y.??,] we have "food" "uM "object", "plate" " "LLM" "receptacle" ", and "(2x) is on (?y)" "(?y) under (?x)"
5

---

Published as a conference paper at ICLR 2026
Regression of Negative NL predicates. As for negative predicates, regress negated predicate -P through an action a; to derive preconditions that ensure (F) holds after ag is executed. Thus, we identify predicate e that can be unified with P( Let 0 be the unifier inducing an injective mapping between predicate variables such that:
(i) For every pair of corresponding types t T2 and t, Tg mapped by 0, tx FLMM iz. After applying 0, the substituted goal predicate entails the substituted precondition predi- cate, i.e., (T) FLLM F(Z)0.
Critically note that the direction of entailment in check (ii) for negative NL predicates reverses from the case for positive NL predicates. Let F., (2) Φ be the SSA formula for F2)2), with respect to ai. Applying 0 to this formula and negating the result gives the regressed condition for-P" (P with respect a,;
Regr, (-P(()))))) -F,
We provide worked example illustrating the regression of a negative NL predicate in Figure To identify the subgoals necessary for the predicate - "the agent (rratfo) to hold after an action executed, we aim to find predicate that is unifiable with it. The predicate -the agent holds( ?o:object)" qualifies for this, under the substitution 0 = ( ("re"/"breadd", be- cause (i) type consistency condition holds ("food" FLLM "object"), and (ii) once the substitution is applied, ("the agent possesses (bread)"Huu "the agent holds (bread)") "). Note that the direction of the entailment condition (ii) the opposite the case of positive predicates. The post-action predicate - "the agent possesses<beaad
thus be unified with the post-action predicate ""hhe agent holds( Pozobject)" ", which turn equivalent to its SSA with the action "pick up (?o)", which yields the new subgoal.
Misa igned Goal Predicars
Action
SBA ugant's anpay" A
Rege
agase
Ytick up obyect)
)=
agent nearPuy"
(Pay "lovad")
feody"
Unification
Onliccaton Cleck
0= (7o/ bired")
Candition 0): Type Conuistrry
"lodd Hrase "object"
Prodkate from S5A5
The agent presessem@rreedy uae the agen holds Cready
apei object y
Candition iij: Predicats Entaihuent
Figure 6: An example of a regression step of negative predicate with goal-action misalignment.
NL Regression with Multiple Entailments. A predicate P'(E) T may be semantically tailed by multiple other predicates. For example, the goal "(?o) is cooked" may be entailed by either "(?o) is toasted" "(2o) is boiled".. In such cases, we aggregate all entailing predicates.
Let F = (Z)), Fm (mm)
(..).) E F A (( FLLM P'(E) } be the set of all predicates that entail P'( The aggregated regression (T with respect to action a; is:
m
Regr, (P))))
V (T), where Fje E Rt..
The same construction applies to negated predicates, with entailment checked in the reverse direc- Fm (Tm) (., E F ^ (E FLLM F.().) } be the set of
tion. Let FF all predicates entailed by P'( The aggregated regression of (P) with respect to a; is:
Regr, (-P a;) =
A F (2),( j=1
where Fj FF.
(6)
In practice, multiple entailments can induce cross- cross-product explosion during DNF expansion, in- creasing regression path and prolonging regression time.
2.1.2 REGRESSION OF FORMULAS
Full first-order formulas can now be regressed using Algorithm I the formula is rewritten in Dis- junctive Normal Form (DNF), the predicates in each disjunct regressed following the process in

---

Published as a conference paper at ICLR 2026
Algorithm REGRRSSSFORMULAA(S (z(3)), J)
Input: in DNF: a: (
2: Output: 1 = Regr, (W) (8), a.) in DNF
3: d - Ø
4: for each disjunct C' v/ do
5:
D D
each literal (z;)) in do Construct: F
7:
( (z) (
9:
D D F
10:
Convert ToDeeF)
11: end for
12: 2
D
13:
end for
14:
return
Instruction: apple put
bable
Pick up apple
apple with microsvve
Pick up apple
to
Figure 7: An Example of a Visual ALFWorld Task.
Section 2.1.1 and the results are incrementally combined in DNF. The general regression process in the NL. PDDL. framework summarized in Appendix D
EXPERIMENTS
We pose the following research questions:
RQI: Overall Planning Performance. How does NL-PDDI perform in terms of success rate and computational cost across modalities (e.g., text, images), compared to baselines?
RQ2: Reasoning over Language Misalignment. How well does NL-PDDL handle planning tasks where NL descriptions of the action specifications and the goal are misaligned?
RQ3: Effect of Task Complexity. How does NL-PDDL compare to baselines as task complexity increases, measured by optimal plan length and the number of constraints in the goal?
3.1 EXPERIMENTAL SETUP
Open- Open-World Tasks. We conduct open-world planning experiments ALFWorld Text (Shridhar al. 202T) and ALFWorld Vision (ef. Figure 7 evaluate performance across modalities. Agents must operate under partial observability and incomplete task-relevant knowledge to complete com- mon household tasks in virtual home environments. It supports a rich space of interactions, requiring the agents to reason about object relations and action affordances without hardcoded annotations. Following prior work YYang et al.) 2024 Shridhar et al.) [021] Yao et al.) 2023b Wang et al.) 2023), evaluate NL--PDLL We also extend both AI. A.Fld benchmarks by introducing misaligned language descriptions of the agent's s action model and goals (cf. Appendix
135 out- auntof-distribution tasks with 50 movement budget (cf. Appendix
Closed World Tasks. Blocksworld a widely used closed-world planning domain in which the task rearrange colored blocks, initially stacked or on table, achieve a given goal. We adopt

---

Published as a conference paper at ICLR 2026
Table 1: (RQ1) Performance of different methods in two open-world datasets without misalign- ment between goal and model. Reporred performance in the original work.
Open-
Misalignment
Methods
Tok.
Expert Trajectory
Tine-innng
GPT-4o
1,358,934
K
21%
Direct
Deminni-2.0-Flor
1,176,406
0
X
16%
LLM-based Planner
LLaMA-3.1
1,193,640
0
X
19%
ReAct examples)
5,307,266
ReAct (w model)
4,242.560
0
X
34%
ALFWorld
LLM. based Plunner
Retlexion-3'
Reflexion 10 DEPS
NA
NA
0
X 91%
X 83%
Text
NA
Finc-tuned LM
BUTLER
NA
100,000
2618
Ours
NL-PDDL
443,407
0
X
94%
GPT-4o
L823,539
VLM-buse Planner
Direct
Gemini-2.0-Flssh
1,440,225
0
X
2%
LLaMA-3.1
1,505,371
0
X
2%
LdaMM-Adapeer
170,000
ALFWorld Vision
Fine-tuned
InstructBLII
NA
170,000
EMMA-3
NA
15,237
/
37%
EMMA-10 10¹
NA
15,237
/
82%
Ours
NL-PDDL
679,148
0
84%
Table 2: (RQ1) Performance comparison across closed-world Blocksworld variants without mis- alignment. Direct L.LM-based planners fail generate valid plans for Mystery and Randomized Blocksworld. NL-PDDI. demonstrates consistent and robust performance across all variants.
Closed-World Without Misalignment
Mystery
Randomized Blocksworld
Method
Blocksworld
Blocksworld
Tok.
SR (%)
Tok.
SR (%)
Tok.
SR (%)
GPT140
834,890
0%
835,974
0%
Gemini-2.0
834,060
1%
835,824
0%
LLaMA 3.1
963,565
44%
841.791
0%
842,622
0%
Fast Downward
N/A
100%
100%
N/A
100%
NL-PDDL
70%
70%
70%
variant introduced in Valmeekam et al. (2022) by converting goal specifications into NL descriptions for NL-based planners. We include two additional variants to probe brittleness to surface form and lexical priors by replacing object and goal names in the NL descriptions with random English words (Mystery Blocksworld) and random strings (Randomized Blocksworld). Beyond these, we introduce Misalignment Blocksworld, where the NI. descriptions of action model and goals contextually meaningful but intentionally misaligned, to assess the commonsense entailment capabilities of plan- ners (cf. Appendix for details).
Baselines and Evaluation Metrics. We compare NL-PDDL with SOTA baselines in open- and closed-worid domains. In the open-world settings (i.e., ALFWorld Text and Vision), compare with (i) Direct LLM/VLLM-base
planners: GPT-4o (Hurst et al. 2024). Gemini-2.0 Flash (Team) al. (023). and LLaMA-3.1 (Grattafiori
2024). (ii) Reflective LLM-based planners: Re- Act Yao et al. 2023b). Reflexion (Shinn et al. 2023). and DEPS (Wang et al., (2023). and (iii)
Fine-tuned L.M//VMMs: BUTLER (Shridhar al., (02T), LLaMA-Adapter (Gao al. 2023).
InstructBL.IP (Dai et al. 2023), and EMMA (Yang et al. (024), all trained on ALFWorld expert demonsrations. In the closed-world setting, we compare against Direct LLM-based planners and the classical Fast Downward (Helmert) 2006) planner, which serves as upper bound on planning performance. The detailed implementation of NL-PDDL on the ALFWorld and Blocksworld bench- marks is included in Appendix H Methods are evaluated under a feasible maximum runtime. For evaluation, we consider two aspects: task Success Rate (SR), and associated cost, as captured by the # Tokens Usage (# Tok.) in L.M.M
8

---

Published as a conference paper at ICLR 2026
Table 3: (RQ2) Performance across settings with misalignment in open-world ALFWorld (Tex- V/Vision) and closed-word -ooldd Misalignment Blocksworld. Reported methods are omitted since prior works did not consider misalignment.
Open-World World With Misalignment
ALFWorid Text
ALFWorld Vision
Blocksworid
Culegury
Method
TTok
(%%
Tok.
(S3)
#Tok
(%)
GPT-4o
1,440,470
175:
1,811,004
(11))
937,905
(179)
Direct LLM
Gemini-22 2.0 Flash
1,251_535
15% (119))))))
1,262,016
5% (13%)
939,950
23%
LLaMA-3.1
1,310,664
15% (1488
1,800,922
2% (016)
950,490
42% (1.9)
examples
5,215,612
79% (1129))
N/A
N/A
NiA
NIA
ReAct
model
4,428,914
23% (L1115)
N/A
N/A
N/A
N/A
Classical Planner
Fast Downward
NIA
N/A
NZA
N/A
0%
Ours
NL-PPDLL
501,049
91% (1316)
745,365
80% (_416)
11,656
70%
Blocksworld
Mystery Blocksworid
Randomized Blockowerdd
Misal Misalignment Blocksworld
100
Surress hate- (KG
GPT-4o
Gemini 2,0 Flash
10c
10e
10
LLaMA-3.1
Dapth
Depth
Dopth
Dopth
RoAct (wi mami))
ALFWorld Toxt
AtPWorrd Vision
ALFitorid Text (misalign))
ALFWorld Visian (misalign)
ReAct (wl Modell
1.00
+
NL-POOL (Ours)
Sucress Pate (66)
80
20
Constraints
Goal Constraints
Goal Constraints
Goal Constraints
Figure 8: (RQ3) SR by goal complexity and optimal plan depth ALFWorld and Blocksworld
across planners
RESULTS AND DISCUSSION
RQ1. In open-world tasks (cf. Table NL-PDDL achieves superior SR on both ALFWorld Text and Vision compared to all baselines. On ALFWorld Text, NL-PDDL achieves 94% SR with only 443K tokens, whereas ReAct consumes over ten times more tokens while reaching lower SR. Although Reflexion-10 10 achieves performance comparable to NL-PDDL, it depends on repeating trials of the same task, which infeasible for many embodied AI applications. Impressively, NL-PDDL even outperforms all fine-tuned VLMs that rely on thousands of expert trajectories in visual ALFWorld. Our results highlight its generalizability across different modalities for open- world tasks. In cloled-world tasks (cf. Table 2). NL-PDDL demonstrates robust performance with a consistent 70% SR at tokens. contrast, direct LLM-based planners entirely fail to solve the Mystery and Randomized variants, performing with less than 1% SR despite substantial token usage. Fast Downward, a closed-world planner, achieves a 100% success rate on the three Blocksworld domains. However, it is brittle under goal-as coal-action misalignment,
demonstrate in RQ3.
RQ2. In Table 3 we evaluate the performance of different methods on open- and closed world tasks with misalignment between the NL descriptions of action models and goals. NL-PDDL demonstrates clear robustness in the face of such misalignments. In open-world tasks, NL-PDDL maintains a 91% SR on ALFWorld Text and 80% ALFWorld Vision. By contrast, ReAct, whether explicitly prompted to focus on action models supported with few-shot examples, suf- fers notable degradation, underscoring its sensitivity misalignment. The closed-world Misalign- ment Blocksworld variant highlights the gap: Fast Downward, though highly effective in purely symbolic and aligned settings, does not perform commonsense entailment and fails under goal- action schema misalignment; in contrast, NL-PDDL maintains performance comparable to other Blocksworld variants, evidencing robust misalignment handling.

---

Published as a conference paper at ICLR 2026
We evaluate planner performance relative optimal plan depth. NL-PDDL achieves per- fect success up to depth 6, with performance declining to 84% at depth and fails beyond depth 10 under the runtime limit. By contrast, LLM-based planners exhibit consistent deterioration across all depths. NL--PDDL's decline stems from scalability limitations under the predefined maximum runtime, while L.LM-based planners fail due their inability to reason The Fast Downward planner maintains perfect performance when the action model and goals are fully aligned, but fails on the Misalignment Blocksworld where commonsense entailment reason- ing is required. In open-world tasks where optimal depth is inconsistent, we measure NL-PDDL's performance against goal complexity. NL-PDDL remains stable, showing only a 3% average drop across ALFWorld Text and Vision, while LLM/VLM-basee planners degrade much more sharply, underscoring their sensitivity to increasing goal complexity. Together, these results demonstrate the robustness of NL-PDDL with respect to goal complexity across open- and closed-world tasks.
RQ3.
extended horizon.
5 RELATED WORK
Eliciting Stronger Reasoning from LLMs: As L.MSs scale, they remain prone to hallucinations and logical fallacies (Tonmoy et al., 2024 Zhang et al. 2025 resulting in new prompting strategies
to mitigate these concerns. Step-by-step methods (Wei al.
2022 Kojima et al., 2022 Yao al.)
2023a) encourage incremental reasoning by breaking problems into sub-steps or branching search trajectories. Reflective methods such as ReAct (Yao et al. 2023b) and Reflexion (Shinn et al. 2023)
add self-reflection, critiquing, and revision. Yet these methods often fail on tasks with several logical constraints or long- long-horizon dependencies (Valmeekam et al., 20236 2022) Song et al.] 2025): : are
sensitive prompt design and few-shot examples, iteration dependent (Pan al. 2023); and remain unverifiable since the LLM acts as a black box without guarantees of soundness (Shanahan 2024).
Planning with LLMs and Symbolic Planners: A separate body of work integrates LLMs with classical planners. One approach treats LLMs as planners that generate action sequences from sym- bolic task descriptions (Silver al., 2022 Song al. 2023 Silver et al. (024).. Another uses LLMs as translators, converting NL problems and domains into structured formats for symbolic solvers (Guan al., 2023; Kambhampati al., 2024, Oswald al. 2024] Yang et al., 2023). Both approaches face limitations; LaM-as-planne approaches are unreliable due to reasoning errors and hallucinations, while translator based methods often introduce faulty predicates, actions, or logical mappings of NI. descriptions that cause downstream planning failures. Translation also imposes an expressivity bottleneck, restricting applicability to problems encodable in symbolic form. Finally, most assume closed-worke settings, making them inappropriate for open-world planning.
Our Point of Departure: We introduce a novel NL-PDDL hybrid natural language variation of PDDL to facilitate the of powerful commonsense (V)LLM reasoning during planning, and blend with symbolic lifted regression over NL-PDDL to address open- open-world, nonghooizon planning.
We further discuss NL-to-PDDL translation approaches and clarify their distinctions from NL-
PDDL in Appendix
CONCLUSION
We proposed NL-PDDL, framework for open-world planning that extends symbolic PDDL to support NL, improving accessibility for non-experts. NL-PDDL facilitates the integration of LLM commonsense knowledge into open- open-world regression planning to address goal-action misalignment, while retaining soundness and verifiability. Empirically, we showed that lifted regression planning in NL-PDDL achieves higher plan-success rates in contrast to existing strong baselines, remains robust as plan horizons increase, and generalizes well across both text and vision modalities.
ACKNOWLEDGMENTS
This work was supported by LG Electronics, Toronto AI Lab Grant Ref No. 2024-0565 and by the Institute of Information & Communications Technology Planning & Evaluation (IITP) grant funded by the Korean Government (MSIT) (No. RS-2024-04458882, National AI Research Lab Project).
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Mohamed Aghzal, Erion Plaku, Gregory J Stein, and Ziyu Yao. A survey on large language models for automated planning. arXiv preprint (rXXi::5522.22.333 2025.
Pierre Carbonnelle. pydatalog: Logic programming in python. https://sites.... httpp:://g..hub..ccoom/crrbbm//
e.
com/ wwt.tteeytllllg///aoaaaa 2024.
og.
Wenliang Dai, Junnan Li, Dongxu Li, Anthony Tiong, Junqi Zhao, Weisheng Wang, Boyang Li, Pascale N Fung, and Steven Hoi. Instructblip: Towards general-purpose vision-language models with instruction tuning. Advances in neural information processing systems, 36:49250-49267, 2023.
Peng Gao, Jiaming Han, Renrui Zhang, Ziyi Lin, Shijie Geng, Aojun Zhou, Wei Zhang, Pan Lu, Conghui He, Xiangyu Yue, al. Llama-adapter v2: Parameter-efficint visual instruction model. arXiv preprint 2tt1::20341501100 2023.
Kai Goebel and Patrik Zips. Can llm-rensoning models replace classical planning? benchmark study, arXiv preprint arXiv:2507.2358) 2025.
Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. The Ilama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024.
Lin Guan, Karthik Valmeekam, Sarath Sreedharan, and Subbarao Kambhampati. Leveraging pre- trained large language models to construct and utilize world models for model-based task plan- ning. Advances in Neural Information Processing Systems, 36:79081-79094, 2023.
Patrik Haslum, Nir Lipovetzky. Daniele Magazzeni, and Christian Muise. An Introduction to the Planning Domain Definition Language, volume 13 of Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool, 2019.
Malte Helmert. The fast downward planning system. Journal of Artificial Intelligence Research, 26: 191-246, 2006.
Yongfeng Huo, Jing Tang, Yinghui Pan, Yifeng Zeng, and Langcai Cao. Learning planning domain model from natural language process manuals. IEEE Access, 13219-14333,,, 2020.
Aaron Hurst, Adam Lerer, Adam P Goucher, Adam Perelman, Aditya Ramesh, Aidan Clark, AJ Os- trow, Akila Welihinda, Alan Hayes, Alec Radford, et al. Gpt-4o system card. arXiv preprint arXiv:2410.21276, 2024.
Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Mudit Verma, Kaya Stechly, Siddhant Bhambri, Lucas Paul Saldyt, and Anil B Murthy, Position: Llms can't plan, but can help planning in Ilm-modulo frameworks. In Forty-first International Conference Machine Learning, 2024.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35:22199 22009922221222222 2022.
Xiangrui Kong, Wenxiao Zhang, Jin Hong, and Thomas Braunl. Embodied ai in mobile robots: Coverage path planning with large language models. arXiv preprint arXiv:2407.02220, 2024.
Manling Li, Shiyu Zhao, Qineng Wang. Kangrui Wang, Yu Zhou, Sanjana Srivastava, Cem Gokmen, Tony Lee, Erran Li Li, Ruohan Zhang, et al. Embodied agent interface: Benchmarking 1lms for embodied decision making. Advances in Neural Information Processing Systems, 37:100428- 100534, 2024.
Drew McDermott, Malik Ghallab, Adele Howe, Craig Knoblock, Ashwin Ram, Manuela Veloso, Daniel Weld, and David Wilkins. PDDL The Planning Domain Definition Language Version 1.2. Technical Report CVC TR-98-003/DDC 1165, Yale Center for Computational Vision and Control, Yale University, 1998.
11

---

Published as a conference paper at ICLR 2026
Shivam Miglani and Neil Yorke- Smith. Nitopddl: one-shot learning of pddl models from natu- ral language process manuals. In Proc. of the ICAPS Workshop on Knowledge Engineering for Planning and Scheduling (KEPS). ICAPS, 2020.
Christian Muise, Florian Pommerening, Jendrik Seipp. and Michael Katz. Planutils: Bringing plan- ning to the masses. In ICAPS 2022 System Demonstrations, 2022.
James Oswald, Kavitha Srinivas, Harsha Kokel, Junkyu Lee, Michael Katz, and Shirin Sohrabi. Large language models as planning domain generators. In Proceedings of the International Con-
ference on Automated Planning and Scheduling, volume 34, pp. 423-431, 2024.
Liangming Pan, Alon Albalak, Xinyi Wang, and William Yang Wang- Logic-Im: Empower- ing large language models with symbolic solvers for faithful logical reasoning. arXiv preprint arXiv:2305. /2295, 2023.
Raymond Reiter. Equality and domain closure in first-order databases. Journal of the ACM (JACM), 27(2):235-249 1980.
Raymond Reiter. The frame problem in the situation calculus: simple solution (sometimes) and a completeness result for goal regression. Artificial intelligence and mathematical theory of computation: papers in honor of John McCarthy, 50:359-380, 1991.
Murray Shanahan. Talking about large language models. Communications of the ACM, 67(2):68-79 2024.
Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems, 36:8634-8652, 2023.
Parshin Shojace, Iman Mirzadeh, Keivan Alizadeh, Maxwell Horton, Samy Bengio, and Mehrdad Farajtabar. The illusion of thinking: Understanding the strengths and limitations of reasoning models via the lens of problem complexity. arXiv preprint arXiv:2506.0m 06941, 2025.
Mohit Shridhar, Xingdi Yuan, Mlec-Alex Cote, Yonatan Bisk, Adam Trischler, and Matthew Hausknecht. Alfworld: Aligning text and embodied environments for interactive learning. In International Conference on Learning Representations, 2021.
Tom Silver, Varun Hariprasad, Reece S Shuttleworth, Nishanth Kumar, Tomás Lozano-Pérez, and Leslie Pack Kaelbling. Pddl planning with pretrained large language models. In NeurlPS 2022 foundation models for decision making workshop, 2022.
Tom Silver, Soham Dan, Kavitha Srinivas, Joshua B Tenenbaum, Leslie Kaelbling, and Michael Katz. Generalized planning in pddl domains with pretrained large language models. In Proceed- ings of the AAAI conference on artificial intelligence, volume 38, pp. 20256-20264, 2024.
Pavel Smirnov, Frank Joublin, Antonello Ceravola, and Michael Gienger. Generating consistent pddl domains with large language models. arXiv preprint arXiv:2404.07735 2024.
Chan Hee Song, Jiaman Wu, Clayton Washington, Brian M Sadler, Wei-Lun Chao, and Yu Su. Lim-planner: Few-shot grounded planning for embodied agents with large language models. In Proceedings of the IEEE/CVF international conference computer vision, pp. 2998-3009 2023.
Peiyang Song, Pengrui Han, and Noah Goodman. A survey on large language model reasoning failures. In 2nd Al for Math Workshop@ ICML 2025, 2025.
Gemini Team, Rohan Anil, Sebastian Borgeaud, Jean- Caan-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, Katie Millican, et al. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.11800 2023.
SM Tonmoy, SM Zaman, Vinija Jain, Anku Rani, Vipula Rawte, Aman Chadha, and Amitava Das. A comprehensive survey of hallucination mitigation techniques in large language models. arXiv preprint 43111:2401.01313, 6, 2024.
12

---

Published as a conference paper at ICLR 2026
Karthik Valmeekam, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati. Large lan- guage models still can't ' plan (a benchmark for Ilms on planning and reasoning about change). In NeurlPS 2022 Foundation Models for Decision Making Workshop, 2022.
Karthik Valmeekam, Matthew Marquez, Alberto Olmo, Sarath Sreedharan, and Subbarao Kamb- hampati. Planbench: An extensible benchmark for evaluating large language models on planning and reasoning about change, 2023a. URL
Karthik Valmeekam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati. On the planning abilities of large language models-a critical investigation. Advances in Neural Informa- tion Processing Systems, 36:75993-76005. 2023b.
Karthik Valmeekam, Kaya Stechly, and Subbarao Kambhampati. Lims still can't plan; can lrms? a preliminary evaluation of openai's 's ol on planbench. arXiv preprint arXiv:2409. /3373, 2024.
Zihao Wang, Shaofei Cai, Guanzhou Chen, Anji Liu, Xiaojian Ma, and Yitao Liang. Describe, explain, plan and select: Interactive planning with large language models enables open-world multi-task agents, arXiv preprint arXiv:2302.01560 2023.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837, 2022.
Yaqi Xie, Chen Yu, Tongyao Zhu, Jinbin Bai, Ze Gong, and Harold Soh. Translating natural lan- guage planning goals with large-language models. arXiv preprint arXiv:2302.05 128, 2023.
Yijun Yang, Tianyi Zhou, Kanxue Li, Dapeng Tao, Lusong Li, Li Shen, Xiaodong He, Jing Jiang, and Yuhui Shi. Embodied multi-modal agent trained by an Ilm from a parallel textworld. In Proceedings the IEEE/CVF conference on computer vision and pattern recognition, pp. 26275- 26285, 2024.
Zhun Yang, Adam Ishay, and Joohyung Lee. Coupling large language models with logic program- ming for robust and general reasoning from text. arXiv preprint arXiv:2307. 07666,,,,,, 2023.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimban. Tree of thoughts: Deliberate problem solving with large language models. Ad- vances in neural information processing systems, 36: 1809-11822, 2023a.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. In International Conference on Learning Representations (ICLR), 2023b.
Yue Zhang, Yafu Li, Leyang Cui, Deng Cai, Lemao Liu, Tingchen Fu, Xinting Huang, Enbo Zhao, Yu Zhang, Yulong Chen, et al. Siren's song the ai ocean: A survey on hallucination in large language models. Computational Linguistics, pp. 1-46, 2025.
A ETHICS, REPRODUCIBILITY, LLM USAGE STATEMENT
A.1 ETHICS STATEMENT
We adhere to the ICLR Code of Ethics. This work does not involve human animal subjects, and no identifiable personal information was used in developing this paper. Therefore, there are no privacy or security concerns. We are committed maintaining integrity and transparency throughout the research process.
A.2 REPRODUCIBILITY STATEMENT
We have made every effort to ensure that the methodology presented in this work is reproducible. All code used in this study has been released in anonymous repository to support reproducibility and verifiability. Full descriptions of the methods and experimental setup are provided both the main text and the appendix to facilitate transparent evaluation and replication of our results.
13

---

Published as a conference paper at ICLR 2026
A.3 THE USE OF LARGE LANGUAGE MODELS (LLMS)
Large Language Models (LLMs) were used to aid or polish the writing of this paper. Specifically, we employed LLMs to improve the readability and clarity of the manuscript.
B FUNDAMENTALS OF REGRESSION PLANNING IN PDDL
In this section, review PDDL and its representation of planning problems, then introduce the first- order regression approach to planning. The corresponding operations for our proposed NL-PDDLL presented in Section 2.1 of the main paper.
B.1 PDDL PLANNING REPRESENTATION.
planning problem is defined as the tuple P (F, O, A, 80, G)2 where:
F is the set of first-order predicates that describe properties of objects relations be- tween them, whose truth values may change as actions are applied, such as boiled (x), can toast(a2 y). etc.
O is the set of objects in the domain, which serve as the constants over which predicates and actions are instantiated, (c.g., potato, plate, etc.).
the set of actions (z))), i.e., parameterized first-order operators. Each action schema is defined by:
Preconditions: Denoted by (;)))rre C. F is the set of predicates that must hold for the action to be applicable.
Add effects: Denoted by (a)))addd F is the set of predicates that become true once the action is executed.
Delltee effects: Denoted by dy.))edel is the of predicates that are no longer true after the action is executed.
For instance, the action pickup (?o) has the preconditions hand and near (?o), the add effect possess (?o), and the delete effect hand_emptt
50 is the initial state, given set of ground predicates that hold true before any action is executed.
G is the goal condition, specified as a set of predicates that must be satisfied in a terminal state.
In classical planning, problems are often specified the Planning Domain Definition Language (PDDL), which is divided into parts: the domain and the problem instance. The domain defines the agent's action model together with the set of predicates F and the set action schemas A. The problem instance specifies finite object O, initial state 8q and G given predicates.
of ground
The objective of solving planning problem is find conditional plan, i.e., finite sequence of actions (1),... ...., (*)), such that, starting from so. executing each action in sequentially results in state s, that satisfies the goal G. Here, the superscript (i) in ( indicates that is the action executed at the i-th step of the plan, i... represents the horizon index the action within the sequence.
14

---

Published as a conference paper at ICLR 2026
Example.
We represent the planning problem
P -
80. G).
predicates F.
F (hand empty, near(æ), possess())) on(2, y). (x) can bake(æ, y). full.of.water((), baked(z), bciled(x))
Objects O.
0 { bread, plate, toaster, pot }-
Actions A. pickup(2o):
pre: (hand_empty, , near (?o)
add: (possess
del: (hand.empty)
puton(?o, ?r):
pre: (possess (?o), near (?x)
add: (hand_empty, on (?o, ?r)
del: (possess (?o)
toast(?o, ?r):
pre can-toast (?o, ?r), possess (?o)
add: {i sHot (?0)
del: Ø
Initial state 8g+
Sa (hand empty, near (potato), near (plate), near (oven) near (pot), boiling.device (pot), can.toast (bread, toaster), full.ff (pot)
Goal G.
G heated (bread), on (bread, plate) }.
B.2
FIRST ORDER REGRESSION
First-order Regression addresses open-world planning by lifting object representations into variables and reasoning backward from goals. First-order regression allows the agent to generate lifted plans without requiring prior knowledge of the full object set O or complete initial state Sp- In this approach, beginning from the goal, the objective applicable actions, in order to compute the subgoals that must hold in earlier states. By repeating this process, the agent constructs sequence of actions that achieves the original goal while remaining fully symbolic and lifted, enabling reasoning over unknown partially observed objects.
iteratively regress the target formula through
In this section, we introduce the procedure for translating a PDDL problem into first-order repre- sentation and explain how regression is performed using the Successor State Axioms (SSAs).
B.2.1 PDDL TO FIRST-ORDER LOGIC DOMAIN THEORY
To axiomatize a PDDL domain theory, we begin by defining positive and negative effect axioms, which specify how predicates change result of actions.
Positive effect axioms: state which actions A can explicitly make each predicate F(F) true.
Negative effect axioms state which actions a A can explicitly make the predicate F(ā) false.
15

---

Published as a conference paper at ICLR 2026
These axioms essential for accurately regressing goal through action: to determine the conditions that must have held before the action, one needs to know exactly how each action modifies the state. To obtain these axioms, make the following assumptions.
No new variables outside of action parameter are introduced in preconditions and effects.
No quantifiers are used in the action's preconditions and effects.
All unquantified variables are implicitly universally quantified.
We assume positive and negative effect axioms can be specified by considering all of the ways in which each action can affect each predicate. Let F(UF) be a predicate in the current state, Y a. (7. is first-order formula such that, if it holds in the current state then ("(FF) holds after executing (z)) Similarly, let FF (77 8) be a first-order formula such that, if it holds in the current state s, then (yF) holds after executing (z)) We write TF (7) and YF, (77) shorthands for the state-dependent conditions TF.a, (J7, 8) and Tra (T, 8) the current state, respectively, and define the normal form of effect axioms as following:
Vg: T [T (V) F., (F)],
T (g) -F (iF))
Here, T indicates that each variable in is assigned its type by corresponding element in T. Given a PDDL problem p with an action set A. we can derive effect axioms in the aforementioned normal form, action by action. Consider an action a()) A, and let F(īr) be predicate in its pos- itive effect set, i.e,, F(ūr) e ady).add. The predicate parameters ÜF correspond to permutation of subset of the action parameters V. We use U.P F to denote the remaining action parameters that do not appear in Är which are existentially quantified. With this setup, we construct the following implication:
for each F(FF) avV).add: VT:T. T, la= az(
Pre,( Fd, (Ur).
(a) (7). (g))
Ea;
F. (1)
(8)
Similarly, for the predicates in the delete effects of the action, we have: for each F(FF) E a,()).del: Vg T, [a az(,7) ^
Pre, Pre,(17)1 -F (Ur).
Pre, (aa
FF (
We can combine multiple predicates with the same name via disjunction. The detailed methodol- ogy is outlined in Appendix
Positive effect axiom.
For isHott?o) with respect to the action toast(?o, ?r):
Vbo:object, Pr troobject,
toast(?o, ?r) a can_toast (?o, ?r) ^ possess(?o)
Tasoo, coaet (?0,2x)
isHot (20)).
Negative effeec axiom.
For possess(?o) with respect the action puton ?r):
V?o:object, Pr:receptacle,d
putonnoo, ?r) near(?r) ^ possess(?o)
Sposseas, sutan (20,24)
possesss' (3o) (Bo))
16

---

Published as a conference paper at ICLR 2026
Succesor State Axioms When PDDL problem is transformed into the above nonmal form, Reiter 1991) showed that, under the assumptions of the Unique Names Axioms (Reiter 1980) and the Explanation Closure Axioms (Reiter 199I),
construct Successor State Axioms (SSAs) that
capture how predicate may change or persist as the agent interacts with the environment. Let Fo, (yF) denote the value of a predicate F(yr) in the next state after executing action az(ū)) The SSA for F F(FF) is defined as:
Vz: F (F. FF. (77)
(F(NF) A FF,, (7))
(10)
Intuitively, SSAs state that a predicate F" ("((F) in the next state can be true either because it is made true by an action (y)), as specified by F (7), or because was already true in the previous state, F F(VF), and the action does not make it false, i.e., FF,, (7).
A to:object, re:eeccpaacle, possess' (2o) pickup(?o) hand empty near(?o))
"paasess, (?o)
possess(20) (aa = putpoon(2o,; near(?r)))
"poesses, poron (to, 2x)
First-Order Regression Let v/ denote first-order state description that holds after executing an action a,. The regression operator Regr(v) (v',,, aa) "backprojects" vi to compute logical formula du that must hold before the execution of ag Fortunately. SSAs provide a logically equivalent pre-action condition for each predicate F", (z) E vb with respect to an action a; A. Regression of the entire formula is performed by recursively replacing each post-action predicate F((Z) with its corresponding precondition formula Fx (I), defined by the appropriate SSA.
Regr(F Fd, (I)
(11)
Regr(isHot (?0), toast (?o, ?r)) = can_toast (?o, ?r) A possess (?o)
SSAs lay the foundation of lifted regression planning, since using SSAs, a predicate in a post-action state with the subgoals that are required to hold before the action is executed to achieve the predicate. We provide examples of this functionality in Section 2.1
able to replace
C COMBINING EFFECT AXIOMS
Combining Effect Exioms(Appendix For predicates that appear in multiple action effects, need to combine them into a single effect axiom. For instance, we have two antecedent condition formulae Ci (#1, 71) and (2 (22 where:
Vi : Tr, Ø1 Ty [C1 F(
(12)
VT. : Tz,, T2 Ty, [C2(2e, 12) F.
(13)
let 0 = (. Z1, 4 3 be the most general unifier (MGU) of C1 and C22 i.c. the substitution that unifies the variables of C2 with those of the Cj without introducing unnecessary restrictions. We then apply 0 to C2 Ø2), i.e. SUBST((, C2(22,)T) C2 VT). and form the following implication:
Vo TT vi Ty (Ci(Z), 7)) v (2(71,71) Tr. (
(14)
where SURST((0,) denotes the formula obtained by applying substitution p.
17

---

Published as a conference paper at ICLR 2026
Va: A, 20 object, ?r object (a bake(?o, 3r) a baking.devica((f)) ^ can_bake(2o, ?r) ^ possess(?o))
(3=boil(oo,22) ?r) a boiling. A ofll ^ possess(?o))]
= isHot (?o)
D NL-REGRESSION ALGORITHM
Algorithm 2 presents the regression process in the NL-PDDL framework. Starting from G, standardize actions and regress the current subgoal v through them. The result is simplified and if valid, the action is appended to the plan, forming (1,, a). This process is repeated to depth h, yielding the final plan which consists of all such pairs (+), ā) where v is logically equivalent to the original goal G.
Algorithm NL-REGRESSION ALGORITIIM
I: Input: T' = (G, h, F)
2: Output: C (6, a)) with each & in DNF
3:
(7) (7) P(x) E F, a,) E A}.
F2,
4: Frontier - (G. []. 0))
5: - [T,(G, [], )
while Frondier Ø
7: Extract (ø', a, d) from Frontier
8: if > h then
9:
continue
10:
end if
11:
for each (17) E A
12:
(1( < STANDARDIZE((;
//See Appendix E.
13:
REGRESSFORMULAN (;()), F)
14:
if evaluated to False then continue end
16:
17:
3 SIMPLIFY(()
ISeee Appendix E.2
18: a' - a (t)
19:
Frontier Prontier (1), d' d d+1)) T ((b, d')}
20:
21:
end for
22:
end while
23:
return
E OPERATIONS IN FIRST-ORDER REGRESSION
E. STANDARDIZATION
Let be a first-order formula. The standardization of denoted STANDARDIZE((p). is obtained by renaming the bound variables in y with fresh variables so that no two distinct quantifiers yp bind the same variable symbol.
Formally, if .1...., Ty are the bound variables in y,, then
STANDARDIZE(()) =
where p is a bijective renaming function mapping each x; to fresh variable af such that ay & Var(yp) for all i. Here, Var(yp) denotes the set of variables occurring in the formula 42.
18

---

Published as a conference paper at ICLR 2026
E.2 SIMPLIFICATIONS
Regression typically generates a large, expanded DNF formula. To keep the resulting plan compact and interpretable, we apply a set of simplification rules that maintain logical equivalence while eliminating redundancy. These simplifications enable the planner to express subgoals clearly and prevent repeated formulas from arising during regression.
E.2. EQUALITY-BASED QUANTIFIER ELIMINATION
We eliminate quantified variables that equal to object by replacing them with the object, i.e.,
3x : [x x= F(x)) F(x*)
where x* is an object. This transformation preserves logical equivalence while eliminating redun- dant quantification. It is often applied during regression, where triggered by the need unify variables between predicates and action parameters. This rule is especially valuable when the re- gressed formula includes equality constraints that enforce correspondences between variables.
E.2.2 CONTRADICTION EVALUATION
Contradictions often arise within regressed formulas and can be simplified (false). We consider two main cases:
Conjunctive Formulas. A conjunction that contains mutually exclusive literals or unsat- isfiable equality conditions simplifies to false. For example:
F(r) A -((x) - 4, r y A xナ
These situations typically occur when inconsistent conditions are introduced through gression or substitution.
Disjunctive Formulas. In disjunctions, the false literal 1 can be eliminated since it does not affect the overall satisfiability:
F() = F(x) ....
E.2.3 No NO-OP ASSUMPTION.
We assume that the domain does not contain no-op actions. A no-op action is an action that leaves the state unchanged, so we assume that every action makes a meaningful change to the state. Hence, any disjunct the regressed formula that is logically identical to the original goal can be safely eliminated.
Regr(G(x))
VUPNE v G(æ)
VUDNNF
This guarantees that plans are constructed only from informative regressions.
E.2.4 DNF SUBSUMPTION.
Let be a DNF formula:
VC,,
in which each clause C. is conjunction of literals. We say clause C2 subsumes another clause Cj
C Cg. Cy.
In this simplification technique, we eliminate any clause Cj for which there exists another clause C; such that C. Cy. Formally, if
3i such that C₁ Cj+
19

---

Published as a conference paper at ICLR 2026
the formula
Φ = Va
simplified to
6' = VC such that kj,k k) - C+)
For example, with DNF subsumption, we have
[Fi(5)) F2(15) A (Fi A F2(2%) A Fa(25) = (ii A F2(x2))
This simplification allows the planner to just maintain the most general subgoal formulas while preserving correctness.
E.2.5 DUPLICATE DETECTION.
To prevent inefficiency during plan generation, process called duplicate detection ensures the plan- ner doesn't repeatedly visit the same subgoal. Exploring logically equivalent but distinct branches would lead to wasted computation and overly complex policies.
regressed formula marked as duplicate if is structurally identical one already seen, ignor- ing differences in how variables are named or how the conjuncts are ordered.
To enable this duplicate detection, every conjunctive formula standardized by performing the following steps:
Canonicalizing order: Sorting all predicates and their arguments into a fixed, canonical sequence.
Consistent variable mapping: Assigning variables consistently across the formula (e.g., uniformly replacing x, y, with 01, U2, 0g in corresponding positions).
Flattening: Removing nested conjunctions where possible.
E.2.6
DOMAIN AXIOMS.
We enforce Nommin--peciffic integrity constraints for the Blocksworld domain to ensure all regressed formulas remain physically consistent.
Single-Object Holding.
The agent cannot hold two distinct blocks simultaneously:
4b,, b2, bj * b2 -(Holding(bi) Holding(b2)).
Hand Consistency. The agent's hand cannot be both holding a block and empty:
Ab. - ((Holding(b) HandEmpty).
Any clause violating these axioms during regression is simplified to 1. and removed from the DNE.
F ALFWORLD DETAILS
F.1 ALFWORLD TASKS
ALFWorld simulates a typical household environment and focuses on daily embodied AI tasks. Table 4 lists the supported task types along with their corresponding goal templates.
Pick & Place (e.g., "put a plate the coffee table"") the agent must find object of the desired type, pick it up, find the correct location to place it, and put it down there.
Examine in Light (c.g., "examine a book under the lamp") - the agent must find an object of the desired type, locate and turn light source with the desired object in-hand.
20

---

Published as a conference paper at ICLR 2026
Table Task-types and templated goal descriptions in ALFWorld.
Task-type
Templates
Pick & Place
(a) put [obj) in {recep).
(b) put some {obj} on {recep).
Examine Light
(a) look {obj} under the (lamp).
(b) examine the {obj} with the {lamp).
Clean & Place
(a) put clean {obj) in (recep).
(b) clean some {obj} and put in {recep).
Heat & Place
(a) put hot {obj] in {recep].
(b) heat some (obj) and put it in (recep).
Cool & Place
(a) put cool {obj} in {recep}.
(b) cool some [obj} and put it in {recep).
Pick Two Place
(a) put two {obj} in {recep}.
(b) find two {obi} and put them (recep).
Clean & Place (e.g.. "clean the knife and put in the drawer") the agent must find an object of the desired type, pick it up, go to a sink or a basin, wash the object by turning on the faucet, then find the correct location place it, and put it down there.
Heat & Place (e.g., "heat a mug and put on the coffee table") - the agent must find an object of the desired type, pick it up. go to microwave, heat the object by turning the microwave, then find the correct location to place it, and put it down there.
Cool & Place (c.g., "put cool bottle on the countertop") the agent must find object of the desired type, pick it up, go to a fridge, put the object inside the fridge and cool it, then find the correct location to place it, and put down there.
Pick Two & Place (c.g., "put two pencils in the drawer") - the agent must find an object of the desired type, pick up. find the correct location place it, put it down there, then look for another object of the desired type, pick it up, return to the previous location, and put it down there with the other object.
F.2 EXAMPLE TRAJECTORY
You are in the middle of room. Looking quickly around you, you see drawer 15, a drawer 19,
a drawer 7, an armchair 1, and a drawer 10.
Your task is to: find two remotecontrol and put them in armchair. go sidetable
You arrive loc 34. the sidetable you take remotecontral from si dideaable
remotecontrol
You pick up the remoteconzzol 1 from the sidetable 2.
> go to armchair 1
You errive at loc 1. On the armchair 1, you see nothing.
> put remotecontrol 1 in/on armchair 1
You put the remotecontrol 1 in/on the armchair 1.
> go to sofa 1
loc 2. On the sofa 1, you see a newspaper 1, a pillow and a remotecontrol 2.
You arrive
take remotecontrol from sofa 1
You pick the remoteconsrol from the sofa 1.
go armchair 1
You arrive at loc 1. On the armehair 1, see remotecontrol 1. > put remotecontral 2 in/on armchair 1
You won!
21

---

Published as a conference paper at ICLR 2026
G ENTAILMENT DETAILS
G.1 1 ENTAILMENT DESIGN
In this section we outline how we misaligned the action model and the goal for both AFLWorld and Blocksworld domain.
ALFWorld Entailment Predicates Instead of using symbolic predicates such as, we define each action effect and precondition directly in NL and allow multiple entailed variants. Hard string match- ing is replaced with entailment sets as follows:
handEmpty ("the agent's hand is empty", "the agent is not holding anything")
in(o, r) ("o o is in r", "o inside r", "o stored in r"}
hot(o) ( is heated", "o is hot", "o baked")
washed(() o) ("o washed", "o clean", "o is cleaned")
co)led(o) t is chilled",, "o is cool", "o is cooled")
holding(o) o) { the agent holding o", "the agent possesses o", "the agent has o in possessing") on(r) ("r is turned on", "r is on", "r is switched on")
Blocksworld Entailment Predicates). We express each predicate directly in NL and allow multi- ple entailed variants rather than relying on canonical symbols. The entailment sets are:
handEmpty {"the agent is not holding any objects", "the agent not holding anything")
clear(b) (
["block b has nothing top of it", "no block is on 8*}
onTable(b)) ("block b sits directly on the table", "b on the table")
on(b1, b2) ("block b is directly above block b2", "bi on b2")
holding (): [he agent possesses block 6", "the agent is holding b"}
G.2 NATURAL LANGUAGE DESCRIPTION ACTION MODELS
We convert each action schema into natural language description that specifies its preconditions and effects. These NL descriptions are provided to all LLM- and VLM-based models. To test alignment, we intentionally modify the descriptions use phrases that entail the goal but do exactly match the goal string, thereby requiring explicit entailment reasoning. Below we provide examples of the NL descriptions of both the ALFWorld and Blocksworld action models.
Natural Language ALFWorld Action Model
The pickup action requi the agent's s hand to be empty and results in the agent helding the target object. The put actien requires the agent to already be holding an object and allows the object to be placed inside or on top another receptacle, after which the agent's hand becones empty. The heat action requires the agent to holding an object and to at a heating device, producing The wash action requires the agent washing devi resulting in the object bacoming in washed. The chill action requires the agent to be holding the object and to be at chilling device, resulting in the object becoming chilled. The light action requires the agent to be holding the object and to be at a lighting device, producing the effect that the object becomes illuminated. Finally, device atate can be toggled by turn on and turn off, which require the agent to be at the device and result it being switched on or off
effect
or baked. holding the object and be
object becomes
Natural Language Blocksworld Action Model
22

---

Published as a conference paper at ICLR 2026
The pickup action requires the agent's hand to be empty and results in the agent helding the target object. The put acticn requires the agent to already be holding an object and allows the object to be placed inside or on top of another receptacle, after which the agent's s hand becones empty. The heat action requires the agent to be holding an object and to be at a heating device, preducing
effect that the object becomes holding the object and be
or baked.
The wash action requires the agent washing devi ce, resulting in the object bacom ng washed. The chill action requires the agent to be holding the object and to be at chilling device, resulting in the object becoming chilled. The light action requires the agent to be holding the object and to be at a lighting device, producing the effect that the object becomes illuminated. Finally, device atate can be toggled by turn on and turn off, which require the agent to be at the device and result in it being switched on or cff
H DESIGN DETAILS OF NL-PDDL ALFWORLD AND BLOCKSWORLD IMPLEMENTATION
H.1 ALFWORLD
In addition to the core NL-PDDL planner, our ALFWorld agent consists of VLM-based obser- vation parser, a knowledge base (KB), and an LLM-based object grounder. The observation parser extracts list of object names from either text image input. We use Gemini-2.0-Flaah (Team) jet al. 2023) for image observations parsing. After obtaining the object names, we use GPT-4o to instantiate these into Predicaiss and update the agent's ' KB. The KB is implemented using Py- Datalog (Carbonnelle) 2024). Whenever new knowledge is acquired, the agent queries subgoals generated by the NL-PDDL regression planner to determine feasible plan to execute.
Observation Parser The observation parser is responsible for extracting candidate object names and their types from either textual descriptions or visual observations. In the ALFWorld Text setting, object names are directly provided in the environment description, extract object references. In the ALFWorld Vision setting, the parser receives RGB frames from a simulated first-person camera. Here, of open-vocabulary object detection, to generate bounding boxes around objects of interest. Gemini prompted with relevant object descriptions ge.g., "Find a cup", "Find something that can wash the cup")) derived from subgoals generated by the NL-PDDL planner, and it returns a list of detected objects with bounding boxes, labels, and confidence scores. The resulting object list serves as the input to the grounding stage but does not by itself produce predicates or symbolic facts.
simply parse this list to
Gemini-2.0-Flaan (Team al. 2023 a VLM capable
Object Grounder The object grounder bridges the gap between raw object names and the struc- tured predicates required by the NL-PDDL planner. Given the list of parsed object tokens and their textual or visual context, we use GPT-4o to generate grounded natural language predicates that align with our lifted planning formalism. For example, given the input "mug is cleaned," the grounder infers the predicate clean (mug_1). The grounder also infers action-relevant relations such canCles (sink_l, apple_1) when provided with relevant context. This ensures that grounded facts are consistent with both the agent's 's environment and the symbolic schema expected by the planner.
Knowledge Base The knowledge base (KB) stores grounded predicates and supports logical rea- soning over them. We implement the KB using PyDatalog (Carbonnelle)) 2024), a lightweight logic programming library for Python that supports declarative predicate logic, variable binding, and rule- based inference. During plan execution, the planner queries the KB to check whether a lifted subgoal can be satisfied with the current facts. If the KB entails subgoal, we bind the variables in both the subgoal and the associated actions, and then execute the corresponding plan. This allows the planner to maintain consistency between abstract subgoals and grounded execution.
23

---

Published as a conference paper at ICLR 2026
H.2 BLOCKSWORLD
For the Blocksworid domain, we convert the original PDDL goal into corresponding NL-PDDL formulation. We follow the methodology Valmeekam al. (2023a) to ensure consistency be- tween symbolic and natural language representations. The lifted regression planner then produces a sequence of subgoals with a fixed horizon of 10, which are grounded and validated sequentially. Each subgoal and the agent's 's initial state translated into PyDatalog and checked for logical con- sistency with the original PDDL specification. Once all subgoals are validated, we use the standard PDDL validator from Muise et al. (2022) ensure correctness of the complete plan.
H.3 LLM PROMPT FOR TYPE CONSISTENCY CHECK
ROLE:
You are helper agent in common household setting.
You checking TYPE ENTACIMENT between two predicates' term types. INSTRUCTTON:
1. If the candidate's cerm type set implies or matches the target/s term type set for each corresponding term, answer YES.
2. Consider synonyms and common-sense subtype relations (e.g., 'vegetable' entails foodd).
3. If information is unknowt, conservative and very likely.
unless it's Candidate term types: [Sndsssllmmed_pppa___sssss
INPUT:
Target term types: in mot_ll___mmde__peess
OUTPUT FORMAT:
Line 1: exactly YES or NO.
Line 2: Reason,
RESPONSE:
ROLE:
You helper agent in househald setting.
QUESTION:
is true, can you imply Predicate 1 "(Smisaligned geaaaaalggee__gal__reeeeeee gta.__predicatee1..... is true?.
if you know Predicate 2 [
Respond with exactly "YES" if you think the statement is ganerally implied
Respond with "NO" if you think the statement is generally false
TNPUT:
Predicate
Predicate "[aattion_mddeepprredcaaaatt
INSTRUCTION:
1. Use the definition of the predicates to determine if Predicate implies Predicate 1.
2. You know the following background to determine the specific information of the objects within Predicate and Predicate 2: $goal predicates$
3. When determinirg the response, consider meaning the Predicate and Predicate with type of specific object each refers to contexts.
4. Pe creative and think outside the box. IF there is typo between the two predicates, you should say Yes.
OUTPUT FORMAT:
Tine 1 exactly YES or NO.
Line 2: Reason.
RESPONSE:
I WORKS ON TRANSLATING NL TO PDDL
PDDL has long been established as the primary standard for defining planning domains and prob- lems in Al (Haslum al. 2019). However, authoring accurate PDDL. domains and problem speci-
24

---

Published as a conference paper at ICLR 2026
fications is resource-intensive process that requires human expertise. To facilitate this process, growing body of work has explored translating NL descriptions of planning domains and problems into PDDL.
Early efforts include NLtoPDDL Miglani & Yorke-Smith (2020), a pipeline that leverages read- ily available NL data by combining pre-trained contextual embeddings with Deep Reinforcement Learning (DRL) techniques previously used to extract structured plans from NL. Another example FPTCP Huo al. (2020), which constructs a ternary template of NL sentences extract actions and their associated objects in a human-in-the-loop framework.
With the emergence of large language models (LLMs), their strong language understanding and commonsense reasoning abilities have been used to further facilitate PDDL construction from NL. For instance, Xie al. (2023) uses the in-context learning capabilities of LLMs translate NL domains and problems into PDDL via few-shot examples, demonstrating that using LLMs solely for translation and delegating the planning step PDDL solver yields superior results compared to direct LLM-based planning. Similarly, [Smirnvv et al. (2024) employs LLM to generate PDDL plans, but also introduces LLM-based consistency checks and error-correction loops to improve plan quality. More recently. advanced approaches such as Ada ? have been proposed. Rather than translating a pre-existing instruction or domain manual into a single PDDL file, Ada interactively learns adaptive planning representations. In this framework, high-level action abstractions and low- level controllers are jointly adapted to a given domain of planning tasks, guided by NL inputs.
Although these seminal works significantly improve the usability of PDDL,, they all limited to translating NL inputs into PDDL and then relying on an existing PDDL planner-a process that can be error-prone due to the inherent limitations of LLMs and the auxiliary techniques involved. In contrast, NL-PDDL directly extends the PDDL framework to natively support NL specifications, thereby eliminating the need for NL-to-PDDL translation. Moreover, prior approaches primarily focus on generating and refining closed-words domains, whereas NL-PDDL supports open- open-world planning with incomplete domain knowledge.
J NUMBER OF UNDEFINED PREDICATES IN ALFWORLD
In practical scenarios, misalignment between an agent's action model and the underlying task goals is common. Consequently, it is essential for symbolic planner to incorporate LLM-based reasoning when necessary- a capability that NL-PDDL is explicitly designed to provide.
As shown in Table In the ALFWorld domain, total of 583 unique predicates appear across all tasks, with an average of 52.26 predicates per task. Yet the action model defines only 22 predi- aptes-aaproximatell 3.7% of all predicates observed in experiments. The remaining predicates arise dynamically from the user's instructions and the agent's interaction with the environment.
Because these predicates not predefined, existing symbolic planning approaches that require a fixed, closed-world predicate set become infeasible. In contrast, NL-PDDL is the only formal framework that removes the need for predefined predicate vocabulary by leveraging LLM-based entailment reasoning to interpret and ground predicates on demand.
Table 5: Predicate statistics for the ALFWorld domain.
Statistic
Value
Total Number of Predicates
583
Predefined Predicates
22
Predicates per Task
52.26
K ENTILAMENT CHECK
We conducted an additional ablation study (cf. T to evaluate the correctness of the LLM when performing predicate-level affordance reasoning over natural-language predicates. We randomly selected 20 predicates from ALFWorld and asked a human annotator to manually provide three sentences that should be entailed by each predicate and three sentences that should not be entailed.
25

---

Published as a conference paper at ICLR 2026
This yielded 120 coaauleenn-noneentalie pairs in total. We then evaluated all pairs using the NL-PDDL entailment procedure to assess the model's ' precision and robustness in predicate-level reasoning.
Table 6: Classification statistics for the ALFWorld predicate evaluation.
Metric
Number of Instances
True Positive
60
True Negative
58
False Positive
0
False Negative
Total Accuracy
98.3
L LLM CALLS AND LATENCY
We randomly select 20 goals from Misaligned BlockWorld and Misaligned ALFWorld for each depth and report the mean and 95% confidence interval of the total number of LLM calls in Table These totals include both local cache hits (i.e., we store all previously encountered LLM entailments in global cache shared across goals) and actual API calls.
Table 7: LLM call and entailment statisties across domains.
Domain
ALFWorld with Misalignment
Misalignment BlocksWorld
LLM API Call
50.4 + 12.9
73.2 1: 23.4
Total Entailments Reasoning
221.5 155.6
1263 1 435.7
Avg Latency per Call
1.8648 sec
1.2443 sec
26


Reviews:
[{"review_id": "r9FtKmXkSc", "reviewer": "Reviewer_SAUU", "summary": "This paper proposes NL-PDDL, an extension of classical PDDL for open-world goal-oriented planning in embodied AI. NL-PDDL represents goals and actions through typed natural language constructs to integrate LLM commonsense reasoning during planning. The framework avoids exhaustive grounding and leverags entailment-based unification to tackle misalignment between natural language goal specifications and action models. Experimental evaluation is conducted on ALFWorld (text and vision variants) and Blocksworld, comparing against SOTA LLM, VLM, and symbolic planning baselines across modalities, goal complexities, and specification alignments.", "questions": "N/A", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The idea of extending PDDL into a natural-language variant and embedding LLM-based entailment checks into the planning loop is natural and intuitive. This combines sound symbolic reasoning with the flexibility of language-based commonsense, addressing issues where classical PDDL or direct LLM planners individually fail.\n\n2. The results on well-known datasets show that this form of representation works relatively well for autoregressive models. If this paradigm is proven to be more suitable for training, it could become a general paradigm.", "weaknesses": "1. There are some very relevant works that should be cited and compared, e.g. Ada (Learning adaptive planning representations with natural language guidance), and other works that translate between natural language and PDDL, or have LLMs generate PDDL for planning purposes, such as:\na. NLtoPDDL: One-Shot Learning of PDDL Models from Natural Language Process Manuals\nb. GPTPDDL (Translating Natural Language to Planning Goals with Large-Language Models), \nc. Generating consistent PDDL domains with Large Language Models, \n..... and many more", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "W2AgrqG5Tl", "reviewer": "Reviewer_qrc8", "summary": "Paper proposes NL-PDDL, a hybrid framework that integrates natural-language representations with symbolic regression planning to enable open-world, goal-oriented reasoning for embodied AI. The authors extend classical PDDL by allowing goals, predicates, and actions to be expressed in natural language, while preserving logical structure for verifiable planning. A lifted regression algorithm combines symbolic reasoning with LLM-based commonsense entailment, enabling the planner to infer semantically aligned actions and to reason under partial observability without exhaustive grounding. Experiments demonstrate higher plan-success rates compared with baselines. The work aims to bridge the interpretability of symbolic planners with the flexibility of language models for open-world embodied reasoning.", "questions": "1.Efficiency and scalability\nHow many LLM entailment calls are typically made per plan? What is the average planning latency compared to other planners? \n\n2.Execution interface:\nHow do NL-PDDL actions interface with a robot's control stack or low-level skill library? Can the planner adapt its decomposition granularity based on the robot's available primitives?\n\n3.Entailment completeness:\nHow is the predicate set constructed, and how large is it in your experiments?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.Paper conducts experiments on 3 benchmarks demonstrate the effectiveness of the proposed approach.\n\n2.By leveraging lifted regression, NL-PDDL maintains scalability with respect to the number of objects, a property desirable for open-world and partially observable environments.", "weaknesses": "1.Unclear LLM-call efficiency and runtime impact\nThe regression algorithm requires repeated LLM entailment checks for each predicate and clause. Although the paper reports token counts, it omits time latency and number of LLM calls per plan. It could difficult to assess whether the approach is practical for deployment or real-time settings without this.\n\n2.No clear bridge from symbolic plan to robot execution\nWhile the framework grounds entities in images via a VLM, it stops short of showing how regressed NL-PDDL actions map onto executable robot actions. The granularity of generated subgoals may not align with the level of abstraction supported by downstream policies.\n\n3.Incomplete treatment of entailment aggregation\nThe “aggregate all entailing predicates” step depends on the finite predicate set and LLM entailment checks, but how to prove the sufficiency of this set.\n\n4.No real-world or hardware validation\nAll experiments are performed in simulated domains and lack of real robot experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "m04KrfFcCL", "reviewer": "Reviewer_DC4D", "summary": "To address the open-world embodied AI tasks with partial observability and incomplete knowledge, this paper proposes NL-PDDL, which combines the strictness of symbolic planning with the semantic flexibility of LLMs. NL-PDDL first extends PDDL into a natural language form for representation, enabling LLM-based commonsense entailment reasoning, and finally employs lifted regression planning. The method maintains robustness under goal-action specification misalignment and generalizes across both textual and visual modalities.", "questions": "1. Given that NL-PDDL relies on natural language representations, could semantic ambiguity or variability in NL descriptions cause the LLM-based entailment reasoning to produce incorrect unifications? For instance, if the entailment check between goal predicates and action effects yields false positives or false negatives due to ambiguous phrasing, would this result in invalid plans or missed valid action sequences during lifted regression?\n\n2. Could NL-PDDL be integrated as a verifiable planning component within broader LLM-based planning frameworks? Would this hybrid architecture improve both the correctness guarantees and the adaptability to novel scenarios beyond the predefined PDDL domain specifications?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Maintain the verifiability of symbolic planning.\n2. Handle semantic misalignment through LLM.\n3. Lifted representation avoids exhaustive grounding.\n4. Works across textual and visual modalities", "weaknesses": "1. Limited novelty compared to prior work. I believe NL-PDDL lacks sufficient innovation. LLM-Regress [1] already proposed combining lifted regression with LLM for open-world planning. What advantages does NL-PDDL offer over this approach? From both the methodology and experimental results, NL-PDDL's advantages are not prominent. LLM-Regress achieves higher success rates and lower token consumption on ALFWorld.\n\n2. Scalability and applicability limitations. NL-PDDL is not a general, scalable approach for open-world planning, as PDDL cannot fully model all problems in open-world settings. In addition, with increasing problem complexity, a sharp performance degradation of NL-PDDL (Figure 7) is observed. This instability may limit the method's practical applicability.\n\n3. Inability to learn. NL-PDDL lacks learning capability, relying entirely on predefined domain specifications and LLM commonsense without the ability to improve from experience or adapt to new domains automatically.\n\n[1] Liu X, Pesaranghader A, Li H, et al. Open-world planning via lifted regression with LLM-inferred affordances for embodied agents", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)