Graph Neural Network Based Action Ranking for Planning

Regarding the beam search, am I correct in understanding that this is only used during test time, not for training the GNN?

[A]: Yes, beam search is only used during testing

L45: typo, "explicitly"

[A]: We will update it.

Figure 1: I think it would be much clearer to say "State and Goal" rather than just "State" for the left-most figure. The caption does not describe what the "G" prefix means.

[A]: Thank you for pointing it out. We will update the figure to say both “State and Goal”

How many training problem instances were used? Sorry if I missed it.

[A]: The number of problem instances is approximately 200 for all domains. The total number of datapoints for training are mentioned in Table 3 of Appendix A.1. (The number of datapoints are different even with the same number of problem instances because each problem instance generates a plan which could be of different lengths. Each action in this plan becomes a datapoint for our learning system).

L124: Have you tried ablating the global features to verify the claim that they are "essential in passing information at each round from nodes that are far apart"?

[A]: Yes, we have done the ablation on global features. The results are provided in Table 4, under GABAR-G (Appendix A.2 contains the analysis).

Can you explain GABAR-RANK more? You say in L286 that "Our ablation GABAR-RANK, which replaces action ranking with value function learning while keeping our graph structure intact" -- but how can the graph structure stay intact if GABAR's network outputs actions while GABAR-RANK's network outputs values (which are floats)?

[A]: The graph network outputs a global vector (in figure 1, after the GNN processing, you can see gL -> that is the output of the graph network. This gL is used by a GRU decoder to rank actions. But, in the case of GABAR-RANK, we simply use an MLP on top of this gL to output a single real number, which is the value of a given state. During training, this output is compared to a real value function and we used MSE loss to train the GNN to output good values.

LLM baseline discussion:

[A]: We can compare our work to their work to some extent. In this LLM approach [1], they solve 2 of the same domains as we do -> Miconic and “gripper”. Their best results from the paper for these domains are as follows : For the “Gripper” domain, they solve problems upto size of 80 objects and have a best success rate of 90% . In our work, we solve problems upto size 100 and have a success rate of 100%. In the “Miconic” domain, they solve problems of size 11-150 but have a best success rate of 1% when random itself has a success rate of 13%. In our work, we solve “Miconic” problems of up to a size of 100 but have a 100% success rate. (All their results reported are from table 1 in [1]).

While LLMs show promise for planning tasks, these results demonstrate that our method provides the reliability and consistency required for generalized planning problems. The stark performance differences, particularly in Miconic where LLMs perform worse than random, highlight the current limitations of LLM-based approaches for structured planning problems.

We are also currently trying to get an LLM baseline running but it might not be ready in time before the end of the rebuttal period. We can definitely add it in the final version of the paper.

Loss function. It is said that GABAR computes scores for all actions. Are these scores 0 for all actions except the correct one? Why one action is randomly selected in the case where multiple are optimal?

[A]: Yes, during training, scores are 0 for all actions except the correct one. In the case when multiple actions are optimal, the action considered optimal is one that was output by a planner- as we use an optimal planner to generate training data on small problems - whatever the planner has output as the action to take at that current state is the one considered as the correct one.( Since the training data consists of only a single optimal plan for each problem as the set of all optimal plans is very time consuming to compute, we only have one correct action)

Limited Novelty

Our main contribution is the action centric graph structure and the conditional decoder architecture. Our ablation studies show these 2 components play a big part in learning a good action ranking function.

Can you confirm that all of the baselines were trained, validated, and tested on the same problem instances?

[A]: Yes, all the baselines were trained and tested on the same problem instances.

Can you also confirm whether the “avoid repeated states” trick was used by the baselines as well?

[A]: Yes, all baselines and ablations also avoid repeated states.

Can you report wall-clock timing results?

[A]: Here are the wall clock timing results for all baselines and our method - Wall Clock Time (WC) (in seconds). It is the average time taken per solved problem for a given domain.

While GABAR may show higher WC (therefore worse) values in some cases, this must be interpreted alongside its significantly higher coverage rates which outperforms all competing approaches. The apparent timing advantage of other methods stems from solving fewer problems overall. These methods solve easier instances within each difficulty category, creating a selection bias where their WC metrics are computed only over successfully solved problems that tend to be less challenging. This is particularly evident in Hard instances, where competing methods achieve very low coverage (GPL: 0-21%, ASNets: 21-92%, GRAPL: 0-78%) while GABAR maintains 71-100% coverage. The favorable WC values for baselines reflect computation over a smaller, easier subset of problems, making direct comparisons misleading. Each difficulty tier contains problems of varying complexity, and methods with lower coverage systematically avoid more challenging instances that GABAR successfully solves. Compared to FD-Lama-first, GABAR shows superiority in Hard instances with lower WC (39.8 vs 53.9). Even in Easy and Medium instances, GABAR achieves competitive WC performance.

Thank you for the feedback. We were able to run 2 of the latest models - OpenAI O3 model and Gemini-2.5-pro (both released in 2025) on our problems.

We used the prompt generation and processing pipeline from the following paper: “A Systematic Evaluation of the Planning and Scheduling Abilities of the Reasoning Model o1” [1]

This paper, despite its title suggesting a focus on the o1 model, actually evaluates and compares the capabilities of multiple large language models within a comprehensive planning framework. We adopted the One-Shot prompting technique described in their methodology to create prompts for our planning problems, which we then used to query both OpenAI O3 and Gemini-2.5 Pro models. We extracted the generated plans from their responses and validated them against our problem constraints. The results of this evaluation are presented below:

Results show that GABAR maintains strong performance advantages over both language models, with the gap becoming more pronounced at higher difficulty levels. For easy tasks, Gemini2.5-Pro achieves 47.8% coverage compared to OpenAI-O3's 35.3%, while GABAR reaches 95.5%. Both language models show reasonable performance quality when they succeed, with OpenAI-O3 at 0.85 and Gemini2.5-Pro at 0.80, though still below GABAR's 1.05.

The performance disparity increases substantially for medium-difficulty tasks. Gemini2.5-Pro maintains 19.8% coverage while OpenAI-O3 drops to 12.3%, compared to GABAR's 92.4%. The quality gap also widens, with both language models falling to 0.68-0.77 while GABAR maintains 1.00. This suggests that as planning complexity increases, the language models begin to struggle with both finding solutions and generating high-quality plans.

For hard tasks, both language models demonstrate severe limitations, with OpenAI-O3 managing only 0.5% coverage and Gemini2.5-Pro achieving 3.0%. Notably, while OpenAI-O3 solves problems in only a single domain at the hard level (Blocks domain only), Gemini2.5-Pro succeeds in two domains (Blocks and Miconic). However, their quality scores on these isolated successes remain substantially lower, with OpenAI-O3 at 0.61 and Gemini2.5-Pro at 0.66, compared to GABAR's consistent 1.00 across all domains.

Please let us know if any other results would be useful.

[1]Valmeekam, Karthik, et al. "A systematic evaluation of the planning and scheduling abilities of the reasoning model o1." Transactions on Machine Learning Research (2025).

How do you think this work will perform compared to using large language models to learn the generalized policies?

[A]: We can compare our work to their work (Generalized planning in pddl domains with pretrained large language models) [1] to some extent.. In this work, they solve 2 of the same domains as we do -> Miconic and grippers. The best results for their LLM approach for these domains are as follows : For the “Gripper” domain, they solve problems upto size of 80 objects and have a best success rate of 90% . In our work, we solve problems upto size 100 and have a success rate of 100%. In the “Miconic” domain, they solve problems of size 11-150 but have a best success rate of 1% when random itself has a success rate of 13%. In our work, we solve “Miconic” problems of up to a size of 100 but have a 100% success rate. (All their results reported are from table 1 in [1]).

While LLMs show promise for planning tasks, these results demonstrate that our method provides the reliability and consistency required for generalized planning problems. The stark performance differences, particularly in Miconic where LLMs perform significantly worse than random, highlight the current limitations of LLM-based approaches for structured planning problems.

We are also currently trying to get an LLM baseline running but it might not be ready in time before the end of the rebuttal period. We can definitely add it in the final version of the paper.

In the experiments, the work achieve good results in out of distribution testing. I observe that the problem sizes are higher in medium and hard cases. However, there are other variables in the initial states and goals of the problem instances, for example, graph connectivity in the grid world domains. Was that measured in any way?

[A]: Graph size increases as we go from easy to hard problems as expected. So we measured the average degree of nodes (AD) in the graph across domains and difficulty levels. What we noticed was that AD remained very similar across all difficulty levels for all domains. What this implies is, is all domains, the number of possible actions an object can be part of similar (even though more actions are applicable since there are more objects).

Other trend we noticed was that the AD was slightly higher for harder domains and lower for easier domains:

Easy domains: spanner : 1.9, blocks : 2.4, gripper 2.65 : , miconic :2.3

harder domains: visitall : 2.93, logistics : 3.15 , grid : 2.8, rovers : 3.1

In the Coverage metric, there is a hard cutoff of 1000 steps, and the measured value is 0/1. Do you have any results on the distribution of number steps taken to find the plan?

[A]: We run our method and the baselines as policies - we input a state and get the next action to take and do not do any search - running the learning method as a policy. From our understanding, the number of steps taken to find the plan would be equal to the plan length (slightly higher when we have cycles). Please let us know if you were looking for a different metric. We do have the mean plan lengths for each baseline for all domains and difficulty levels. Here are the plan lengths (PL), lower the better.

Looking at the Plan Length (PL) results, it's important to first recognize that within each difficulty level (Easy, Medium, Hard), there exists a substantial range of problem complexity and sizes. Each dataset contains problems spanning from relatively simple instances to much more challenging ones, even within the same nominal difficulty category. This inherent variability means that methods with lower coverage are naturally biased toward solving the simpler instances within each difficulty level, which fundamentally affects plan length comparisons.

GABAR demonstrates remarkable efficiency when we properly contextualize the coverage differences. While GABAR doesn't always achieve the absolute lowest plan lengths, its performance becomes exceptional when we consider that it consistently solves significantly more problems than its competitors across this entire spectrum of problem complexity.

The apparent discrepancies in plan length can be largely explained by the coverage differences between methods. When GPL achieves a lower plan length of 27 on Spanner-Easy compared to GABAR's 31, we must note that GPL only covers 73% of the problems while GABAR covers 94%. Similarly, on Visitall-Easy, GPL achieves a plan length of 79 with only 69% coverage, while GABAR produces plans of length 103 but solves 93% of the problems. The additional problems that GABAR solves are likely the more complex instances that require longer plans, explaining the higher average plan length.

When examining cases where coverage is comparable, GABAR's plan length performance becomes more impressive. On Blocks-Medium and Hard, where GABAR maintains 100% coverage compared to ASNets' 100% and 92% respectively, GABAR actually achieves the best plan lengths of 76 and 125. This demonstrates that when solving the same problem set, GABAR often produces more efficient plans than its competitors.

The combined results further reinforce this analysis. GABAR's average plan lengths of 76, 108, and 147 represent solutions to 95.5%, 92.2%, and 89.2% of all problems respectively. In contrast, competitors with seemingly better plan lengths like GPL (69, 111, 147) are only solving 79.1%, 28.5%, and 6.5% of the problems. The dramatic drop in coverage as difficulty increases explains why competitors maintain stable plan lengths - they increasingly solve only the simplest instances while GABAR continues to tackle the complete problem set, including the most complex cases that naturally require longer plans. Also, even when the average plan length is lower, PQR is still worse because PQR is computed only for solved problems and compared to the FD-LAMA method.

[1] Generalized Planning in PDDL Domains with Pretrained Large Language Models. Silver et. al., AAAI 2024.

It is possible that there are irrelevant actions (e.g., inapplicable in current state) in the planning procedure, which can be pruned.

[A]: Our current graph representation only adds information about grounded actions that are applicable in the current state into the graph. We will mention this in the paper. Thank you for pointing it out.

The beam width k=2 looks chosen arbitrarily without any justification. Larger k might improve results but is dismissed without ablation. Sequential parameter selection (for each action) could slow planning in real-time systems.

[A]: Here are the results for different values of k (k=1,2,3). As we can see, when we use fully greedy policy (k=1), our accuracy drops, especially in harder domains and hence having a value of k>1 is important. We can also see that having k=3 does not help much in the majority of the domains and it is computationally more expensive. This is why we choose k=2.

GABAR-k=1 shows poorer performance (especially in hard - drop from 89.2 to 63.8) because it employs a greedy approach and hence cannot do cycle avoidance. GABAR-k=3 demonstrates consistent improvements over k=2, particularly evident in the combined results where it achieves the best coverage and plan quality across all difficulty levels. However, these improvements are modest - typically 1-2 percentage points for coverage and 0.01-0.02 for plan quality ratio. GABAR-k=2 represents the optimal balance point. While k=3 shows slight performance gains, the computational cost increases significantly with higher k values due to the growth time taken for beam search. The marginal improvements offered by k=3 do not justify the additional computational expense, making k=2 the practical choice for the GABAR algorithm. (It takes about 30% longer to rank actions for any given state).

GPL (2022) and ASNets (2020) are not state-of-the-art. Newer relational planners (e.g., diffusion-based/LLM-guided methods) can be considered as baselines. GRAPL (2021) is called "conceptually similar", but the proposed approach is compared to an older version.

[A]: One of the LLM based works that solves very similar problems is the paper named “ Generalized Planning in PDDL Domains with Pretrained Large Language Models”. In this work, they solve 2 of the same domains as we do -> Miconic and grippers. The best results for their LLM approach for these domains are as follows : For the “Gripper” domain, they solve problems upto size of 80 objects and have a best success rate of 90% . In our work, we solve problems upto size 100 and have a success rate of 100%. In the “Miconic” domain, they solve problems of size 11-150 but have a best success rate of 1% when random itself has a success rate of 13%. In our work, we solve “Miconic” problems of up to a size of 100 but have a 100% success rate. (All their results reported are from table 1 in [1]).

While LLMs show promise for planning tasks, these results demonstrate that our method provides the reliability and consistency required for generalized planning problems. The stark performance differences, particularly in Miconic where LLMs perform significantly worse than random, highlight the current limitations of LLM-based approaches for structured planning problems.

We are also currently trying to get an LLM baseline running but it might not be ready in time before the end of the rebuttal period. We can definitely add it in the final version of the paper.

Could you also please clarify what you mean by what you mean by " GRAPL (2021) is called "conceptually similar",the proposed approach is compared to an older version." We compare our work to "Learning generalized relational heuristic networks for model-agnostic planning (which we call GRAPL)" from their 2021 paper.

The evaluation uses suboptimal Fast Downward (FD-lama) plans as baseline. FD-lama’s satisficing nature inflates PQR (e.g., PQR=1.7 in BlocksWorld implies GABAR is worse than the baseline).

[A]: Since optimal planning is intractable, we had to rely on suboptimal planners for comparison. Higher PQR means the produced plan length was smaller (and hence, better) by a particular method - PQR =(plan length by FD-Lama/Plan length by method). Hence, higher PQR of 1.7 in blocksworld implies that GABAR is better than other methods (AsNets with 1.4, GPL with 0.33 and GRAPL with 0.28 in Blocksworld Hard) as higher PQR means the plan output by GABAR was the shorter than methods with lower PQR. A PQR greater than 1 implies GABAR’s plans were shorter than FD-LAMA plans. The same trend of GABAR being better (higher PQR) is true for all domains hard dataset, and even when ASNEts is better than GABAR in some domain’s easy dataset, it is by a very small margin (1.6 for ASNets v/s 1.5 for GABAR in blocksworld easy and 0.98 v/s 0.97 in gripper medium).

Claims of "high-quality plans" are unverified since optimal planners were excluded for runtime reasons.

[A]: While we do not have optimal plans for baselines, our claim of higher quality plans is still valid from a relative stand point. The lengths of the plans produced by our system are on average shorter than the baselines as well as the ablations. While this does not guarantee that the produced plan is optimal, it does imply that our method does indeed produce higher-quality plans compared to the baselines and ablations.

Models were trained on small, optimally solved instances. Are larger problems simply “copy” small instances? It would be more interesting if some analysis on the relationship between small and larger instances is provided.

[A]: [I] : Independent Problem Generation: All problem instances are generated using PDDL generators that employ parameterized templates with randomized elements including initial states, goal configurations, and object placements. This process ensures that each instance is structurally unique rather than a scaled version of existing problems. The generators vary key structural parameters to create distinct planning challenges at scale.

The PDDL-generators for each domain follow high level structure which is as follows: Random Initial Placement: Entities start in random valid positions to create diverse problem instances Constraint-Aware Generation: Placement respects domain rules (e.g., conflicting entities can't share locations) Non-Trivial Goal Creation: Goals are designed to require actual planning steps, not just immediate solutions Solvability Assurance: Generation logic ensures created problems have valid solutions

[ii] : Empirical Evidence of Increased Complexity: We have other forms of evidence demonstrating that larger instances represent fundamentally harder problems rather than trivial extensions:

[i] : Plan Length Analysis: The plan lengths for problems in the hard domain are consistently higher than those in the easy domain when solved by satisficing planners, indicating increased solution complexity.

[ii] : Planner Performance Differential: Optimal planners successfully solve multiple problems in the easy domain but fail to solve any problems in the hard domain within reasonable time limits. This performance gap reflects genuine computational complexity differences rather than simple scaling effects.

Scalability claims are not convincing. The evaluation is not conducted on very large graphs (>1k objects) and high-arity domains. Evaluation cherry-picks baselines and metrics.

[A] We have provided results for 2 other metrics -> Plan length (PL) as response to reviewer "CZcC" , Wall Clock Time (WC) as a response to "hZMb". For scalability, even state of the art learning methods that use search [1], do not solve problems with more than 1k objects (Table 1). Also, their systems are given 30 minutes to run since they use search whereas we use less than 2 minutes to find solutions as we do not use search. That is also why we compare to methods that do not use search.

[1] Hao, Mingyu, et al. "Guiding GBFS through learned pairwise rankings." {IJCAI-24}.