{"id":"4c0d4647-c6bc-4fdc-90cf-54c31dd6577c","arxiv_id":"2412.05528","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A non-exhaustive survey that explains classical AI planning, structure-exploiting solvers, and learning approaches for planning and generalization.","lead":"This paper is a survey and primer on AI planning (AP), introducing its symbolic problem representations, solution techniques, and learning-based extensions for a broad AI audience. It is aimed at researchers in reinforcement learning and adjacent fields who want to understand what AP offers.","discovery_kind":"review","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the reader's EXPSPACE concern does not land, since Sec. 3.1 presents lifted STRIPS with unbounded arity, for which EXPSPACE-completeness is the standard result.","rationale":"The reader and I focused on the same sentence in Sec. 3.2, but I conclude that the concern is a false positive. The paper's formalism is explicitly lifted: states are sets of ground propositions, but actions are schemata with arguments, and the input includes predicates and objects. Complexity must therefore be measured in the size of that compact lifted description, not in the size of the exponentially larger ground encoding. In the propositional STRIPS setting, where the input is already ground, plan existence is PSPACE-complete (Bylander 1994). But when action schemata with unbounded arity are part of the input, the number of ground actions can be exponential in the input size, and the decision problem becomes EXPSPACE-complete; this is precisely the Erol, Nau, and Subrahmanian (1995) result the paper cites. The reader's claim that EXPSPACE requires functions or quantifiers is not supported: the succinct grounding mechanism itself supplies the exponential blowup. No other load-bearing technical inaccuracy surfaced in my read. Some statements are broad survey-level claims, but they are not internally inconsistent and are generally accompanied by citations or pointers to more comprehensive treatments. Because the only concrete red flag raised by the reader does not survive scrutiny, I see no reason to move the verdict; retaining the conditional as an invitation to verify the cited theorem is harmless, but it is not forced by a substantive error.","tokens_in":21447,"tokens_out":12191,"duration_ms":119792,"concrete_test":"Retrieve Erol, Nau, and Subrahmanian (1995) and check the exact theorem the survey cites: verify that it covers function-free, quantifier-free STRIPS with lifted schemata of unbounded arity, where grounding can be exponential in the input size. If the theorem covers that formalism, the reader's PSPACE objection is a ground-size artifact and Sec. 3.2 stands; if it requires conditions absent from Sec. 3.1, revise the sentence. A useful sanity bound is: with one binary predicate and n objects there are n^2 grounded propositions (polynomial for fixed arity), but arity is not fixed in the formalism, so exponential grounding and EXPSPACE-completeness are consistent.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After checking the argument, I do not find a load-bearing concern. The central claim—that structured symbolic models are a distinctive and useful AP contribution—is a survey framing supported by the cited literature and by the formal development in Secs. 2–3. The reader's weakest-assumption candidate (Sec. 3.2's EXPSPACE-completeness) does not land: the paper defines lifted action schemata over predicates and objects, not ground propositional STRIPS. For lifted STRIPS with unbounded predicate/action arity, the ground instance can be exponentially larger than the compact input, and Erol, Nau, and Subrahmanian (1995) establish EXPSPACE-completeness for this setting. EXPSPACE here is the succinct-input analogue of PSPACE-complete ground STRIPS; it does not require functions or quantifiers. I checked other technical characterizations (MDP definitions, admissible heuristics, A*/GBFS/Weighted A*, LAO* and LRTDP as analytic algorithms, UCT as generative, landmarks/mutexes/sketches, GP termination undecidability) against standard planning references and found no comparable red flag. The paper also includes appropriate caveats, such as the proper-policy footnote and pointers to full treatments.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper is a brief, intentionally nonexhaustive primer and survey of AI planning aimed at readers from RL and adjacent communities. It introduces a hierarchy of MDP access levels, presents classical planning as a structured, first-order MDP representation with closed-world semantics, sketches probabilistic, nondeterministic, temporal, numeric, and multi-agent extensions, reviews structure-exploiting solver techniques (heuristics, heuristic search, decomposition, symmetries), and surveys AP subfields where learning is used to acquire or exploit structure. It concludes with pointers to benchmarks, software, and textbooks. The central framing is that AP's distinctive contribution is a compact symbolic model that enables efficient solving and generalization.","tokens_in":21655,"tokens_out":10629,"duration_ms":94758,"significance":"As a survey, the paper's value is organizational and pedagogical rather than new technical results. The level-of-access taxonomy and the Generalisation-in-Planning formulation are useful lenses for cross-community communication, and the paper is generous and accurate in its pointers to the literature. I checked the potentially contentious complexity statement in §3.2: for the lifted STRIPS formalism defined in §3.1, where action-schema arity is unbounded, EXPSPACE-completeness is the standard result from Erol, Nau, and Subrahmanian (1995); the concern that this should be PSPACE-completeness applies to ground propositional STRIPS or to bounded-arity schemata, not to the formalism as written. The remaining technical characterizations I sampled (MDP definitions, admissible heuristics, A*/GBFS/Weighted A*, LAO*/LRTDP/UCT, landmarks/mutexes/sketches, generalized-planning terminology) are consistent with standard references.","major_comments":[],"minor_comments":[{"comment":"The sentence 'can be grounded from task objects to induce a high-order polynomial number of actions and transitions' is imprecise when the arity of action schemata is part of the input: for unbounded arity, the number of ground actions is exponential in the input size, not merely polynomial. Please rephrase so that this statement is consistent with the EXPSPACE-completeness claim in §3.2.","section":"§3.1"},{"comment":"The EXPSPACE-completeness statement is correct for the lifted STRIPS representation defined in §3.1 with unbounded predicate/action arity. For the benefit of readers who know the PSPACE-completeness of ground propositional STRIPS, the paper should add a one-sentence clarification that bounded-arity schemata yield the polynomial-size ground case, which is PSPACE-complete, whereas the compact lifted representation is what gives EXPSPACE-completeness.","section":"§3.2"},{"comment":"The sentence 'relative simple representations for generalised plans and are equivalent to counter-based models of computing, and thus equivalent to Turing equivalent' is ungrammatical. It should read, for example, 'relatively simple representations for generalised plans are equivalent to counter-based models of computing, and are thus Turing equivalent.'","section":"§4.3"},{"comment":"In the second bullet of the Introduction, 'On top of using learning to make planning feasible the discovery of structured models' is missing a connecting phrase; it should be something like 'On top of using learning to make the discovery of structured models feasible, we can also learn to make planning fast.'","section":"§1"},{"comment":"The package name 'Scickit-Decide' should be 'Scikit-Decide'.","section":"§3.5"},{"comment":"Figure 1 is not referenced in the text, and the caption as rendered ('train = test train size = test size train size ⊂ test size ...') is not self-explanatory. Please add a pointer to the figure in Section 4 and provide a readable caption that explains the nesting of generalization setups.","section":"Figure 1"},{"comment":"The description of GBFS and Weighted A* is ambiguous: the phrase 'where g(n)=0 and f(n)=g(n)+w·h(s), respectively' should be split into two explicit definitions, e.g., GBFS uses f(n)=h(s) (with g(n)=0) and Weighted A* uses f(n)=g(n)+w·h(s).","section":"§3.4"},{"comment":"The phrase 'UCT ... are anytime optimal algorithms' is imprecise: UCT is an anytime algorithm whose value estimates converge to optimal values in the limit, but it does not provide an optimality guarantee at every stopping time. Please reword.","section":"§3.4"},{"comment":"The phrase 'distribution models, also known as model-based RL' is loose; Sutton and Barto's dichotomy is between distribution models and sample models, and the term 'model-based RL' in the modern literature includes learned models and broader settings. Consider a more careful phrasing.","section":"§2"}],"recommendation":"minor_revision","confidential_remarks":"No concerns about scope fit or integrity. The reader's EXPSPACE worry does not land, so the main task for the authors is a careful proofreading pass and a small set of clarifying sentences. I would be happy to see the revised version without another full external review."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a genuinely useful primer, not a research contribution. It does one new thing—organizing the planning-RL continuum into five MDP access levels and framing “generalisation in planning” as a common setup—and both frames are clear enough to be adopted. The survey content is accurate, and the heavy lifting is in the selection and structure rather than in new theorems.\n\nThe strongest section is probably Sec. 3, where the formal development from predicates to action schemata to heuristic search is standard but cleanly explained, and the analogies to RL (attention, HRL, dense rewards) are apt. The MDP access hierarchy (Sec. 2) is a nice pedagogical device, though it is a re-labeling of familiar categories rather than a sharp taxonomy—“structured” does a lot of work, and the analytic/structured line is representational only. The generalisation-in-planning setup (Sec. 4) usefully unifies GP, L4P, and LPM, and the paper is honest about the field’s limitations, including the undecidability of generalized plan termination.\n\nOn the one point I checked hard: the EXPSPACE-completeness claim in Sec. 3.2 is correct for the lifted STRIPS formalism actually defined in Sec. 3.1. The reader’s worry about minimal STRIPS being PSPACE-complete conflates the grounded propositional problem with the compact lifted one. The paper says “represented in this way”—with predicates, objects, and schemata—and Erol, Nau, and Subrahmanian (1995) is the right citation. So that flag can be taken down.\n\nMinor soft spots: the survey is non-exhaustive by design (a “preliminary report”), and some choices will look arbitrary to specialists—for instance, the learning-for-planning coverage is weighted toward the authors’ own threads, though the citations check out. A few sections, like knowledge incorporation, are more list-like than the rest. These are revision-level issues, not fundamental ones.\n\nBottom line: it is a solid, careful survey that will be a useful entry point for RL researchers and for grad students. The organizing frames are worth adopting, and the paper is accurate at the level of detail it promises. It deserves a serious referee, and I’d send it out rather than desk-reject.","headline":"A useful, accurate planning-RL primer whose new organizing frames (MDP access levels, generalisation in planning) are worth adopting; the one flagged technical issue is not actually an error.","tokens_in":22187,"tokens_out":2923,"would_cite":false,"duration_ms":26664,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"AI planning's transferable core is the structured symbolic model, and this survey shows how such models enable efficient solving, learning, and generalisation to unseen problems.","keywords":["AI planning","structured representations","Markov decision processes","heuristic search","generalised planning","action model learning","domain-independent planning","generalisation"],"falsifier":"A decisive check would be a controlled benchmark on a domain family with unbounded object counts: train a structure-agnostic learner on small instances, test on much larger instances, and compare against the same learner given the symbolic action schemata; if the structure-agnostic version matches the structured version on long-horizon sparse-reward tasks, the paper's central claim that structure is what enables efficient generalisation is contradicted.","tokens_in":21256,"feed_emoji":"🧩","tokens_out":15256,"duration_ms":141482,"temperature":0.7,"pith_summary":"The paper's central message is that AI planning's distinctive and transferable contribution is the structured, symbolic model: a decision problem is described with predicates, objects, and action schemata rather than as an opaque simulator. It argues that this compact representation is what makes long-horizon, sparse-reward problems tractable, and it surveys the heuristic search, decomposition, and learning methods that exploit it. The authors aim this primer at researchers in reinforcement learning, foundation models, and operations research who know the decision-making problem but not planning's toolbox. If the framing is accepted, planning becomes a source of representations and algorithms that complement learning-based AI rather than a separate, isolated subfield.","feed_headline":"Structured models, not black-box learning, drive AI planning","feed_subtitle":"A survey argues compact symbolic world models are what make long-horizon tasks solvable and generalisable","key_machinery":"The load-bearing object is the structured MDP in the STRIPS/PDDL style: predicates and objects generate propositions; a state is any set of propositions under the closed-world assumption; goals are propositional formulas; and transitions come from action schemata with preconditions, add lists, and delete lists. This single representation carries the whole survey's argument, because each major technique is presented as a way of exploiting the compactness and logical form of that representation, and each learning subfield is presented as a way of acquiring or using it.","core_discovery":"The paper's central claim, stated on its own terms, is that AI planning's core insight is that structure in world models is a resource for decision-making. It formalises a planning task as a factored MDP whose states are sets of ground propositions under the closed-world assumption, whose goals are compact logical formulas, and whose transitions are induced by grounded action schemata with preconditions, add effects, and delete effects. From this representation the paper derives the field's main assets: attention-like relevance, declarative automation, compact encoding of combinatorially large state spaces, domain-independent heuristic search, and problem decomposition through landmarks, mutexes, factoring, and symmetries. It then presents the learning-oriented subfields—learning planning models, learning for planning, and generalised planning—as different ways to acquire, exploit, or upgrade structure, culminating in the claim that structured representations enable generalisation to unseen tasks with arbitrary numbers of objects.","pith_inferences":["A consequence the authors leave implicit is that reinforcement-learning agents should receive a symbolic domain model whenever one is available, rather than learning latent dynamics from raw pixel or state-vector observations.","The generalisation-in-planning setup gives a concrete evaluation protocol for testing whether large language models can plan: prompt on small instances and test on instances with more objects, comparing against a classical planner's guarantees.","One testable extension is to treat learned heuristic functions as ranking functions rather than cost estimators in more settings, since the survey notes that this framing often matches how search actually uses them.","A practical recipe suggested by the survey is to use classical planners to generate dense reward functions or training labels, then train fast learned policies; this pipeline could be tested across domains with unbounded object counts."],"forward_implications":["Planning's structured representations let an agent upgrade its access to a problem from raw interaction to a compact model, making long-horizon sparse-reward tasks solvable without hand-writing a solver.","Domain-independent heuristic search, width-based methods, and decomposition techniques transfer across domains expressed in a planning language, rather than being re-learned from scratch.","The same structure supports automatic generation of reward functions and training labels, so learning methods need not rely on hand-designed rewards.","Generalised plans and sketches can encode solutions for entire domains with arbitrarily many objects, offering explainable and verifiable alternatives to black-box policies.","Because the underlying ideas extend to probabilistic, temporal, numeric, hybrid, and multi-agent settings, the survey's structure-centred view covers decision-making well beyond the classical STRIPS block world."],"supporting_citations":[{"why":"introduces the STRIPS action-schema formalism that grounds the paper's structured representation of states and transitions.","marker":"(Fikes and Nilsson 1971)"},{"why":"introduces PDDL, the standardised planning language the survey credits with making domain-independent planners possible.","marker":"(McDermott et al. 1998)"},{"why":"supplies the textbook view of planning as heuristic search over structured models, which organises the survey's algorithm section.","marker":"(Geffner and Bonet 2013)"},{"why":"defines the RL/MDP baseline the paper uses to frame planning's different level of access to structure.","marker":"(Sutton and Barto 1998)"},{"why":"supplies the EXPSPACE-completeness result the paper uses to illustrate the compactness of the planning representation.","marker":"(Erol, Nau, and Subrahmanian 1995)"},{"why":"introduces the FF planner and delete-relaxation heuristic, the survey's leading example of deriving heuristics from structure.","marker":"(Hoffmann and Nebel 2001)"},{"why":"provides the abstraction and critical-path view of admissible heuristics used in the cost-optimal planning discussion.","marker":"(Helmert and Domshlak 2009)"},{"why":"introduces width-based search and novelty heuristics, which the paper presents as direct exploitation of the structured representation.","marker":"(Lipovetzky and Geffner 2012)"},{"why":"establishes counter-based generalised plans and termination analysis, a backbone of the generalised-planning section.","marker":"(Srivastava, Immerman, and Zilberstein 2011)"},{"why":"introduces sketches and subgoal structure, the paper's example of generalised plans that solve domains in polynomial time.","marker":"(Bonet and Geffner 2021)"}],"fun_headline_variants":["AI planning's edge: explicit world structure, not learning","Structure is the key to AI planning's power","Planning's power: structure, not black-box learning","AI planning relies on structured world models"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The survey's structure-centred case rests on the accuracy of its account of prior planning work; if a technical characterisation such as the claimed EXPSPACE-completeness of the minimal formalism is wrong, the survey's reliability as a reference is undermined.","fun_headline_variants_meta":{"raw":{"variants":["AI planning's edge: explicit world structure, not learning","Structure is the key to AI planning's power","Planning's power: structure, not black-box learning","AI planning relies on structured world models"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000543,"raw_usage":{"total_tokens":2564,"prompt_tokens":870,"completion_tokens":1694,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":486,"completion_tokens_details":{"reasoning_tokens":1634}},"tokens_in":486,"tokens_out":1694,"duration_ms":11799,"temperature":1.0,"reasoning_tokens":1634,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T20:36:47.122954+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A decisive check would be a controlled benchmark on a domain family with unbounded object counts: train a structure-agnostic learner on small instances, test on much larger instances, and compare against the same learner given the symbolic action schemata; if the structure-agnostic version matches the structured version on long-horizon sparse-reward tasks, the paper's central claim that structure is what enables efficient generalisation is contradicted.","supporting_citations":[],"review_version":1}