Planning with Learned Object Importance in Large Problem Instances using Graph Neural Networks

• Real-world planning may require tracking hundreds or thousands of objects even though only a small, goal-dependent subset matters.For example, a robot's relevant objects differ between boiling potatoes and cleaning a sink.Source: §1 · p. 1
• Popular heuristic search planners scale poorly with many objects because they ground actions over the objects during preprocessing.Lifted planners avoid explicit grounding but struggle during search.Source: §1 · p. 1
• Finding a small sufficient object set before planning is nontrivial and highly problem-dependent.A state-of-the-art lifted planner failed to solve any test problem in the experiments within the timeout.Source: §1 · p. 1
• A graph neural network learns to predict sufficient object subsets from discrete and continuous object and relation properties.The approach learns lifted models that are agnostic to object identity and count.Source: §1 · p. 1
• At test time, the network predicts objects, removes facts involving excluded objects, and calls an off-the-shelf planner on the reduced problem.An incremental loop considers more objects until a solution is found.Source: §1 · p. 2
• Object importance prediction treats the planner and transition model as black boxes and adds negligible inference time.Its runtime does not depend on the number of ground actions when the number of objects is constant.Source: §1 · p. 2
• A greedy approximate procedure automatically generates object-relevance labels using only the relatively small training problems.This avoids assuming that relevance labels are provided.Source: §1 · p. 2
• PLOI is much more efficient than several baselines across classical, probabilistic, and robotic task and motion planning with hundreds or thousands of test objects.The baselines include policy learning and partial action grounding.Source: §1 · p. 2

Planning with Many Objects

• PLOI can be viewed as learned abstraction selection, alongside lifted planning and other approaches that simplify planning problems.Lifted planners avoid grounding actions over all objects, while abstractions simplify the problem.Source: Planning with Many Objects · p. 2

Relational Representations for Learning to Plan

• Graph neural networks support relational learning and natively handle continuous object-level and relational properties.The paper uses this flexibility in experiments in a simulated robotic environment.Source: Relational Representations for… · p. 2

Generalized Planning

• PLOI is a generalized-planning approach, and incremental search and heuristic learning are described as complementary methods.Generalized policy learning uses a different execution mode and is included as a baseline.Source: Generalized Planning · p. 2
• Partial action grounding predicts which ground actions are useful, whereas PLOI predicts which objects are sufficient for a planning problem.The paper evaluates two action-grounding variants as baselines, including the authors' implementation.Source: Generalized Planning · p. 2

• A planning problem is a tuple of properties, object-parameterized actions, a transition model, objects, an initial state, and a goal.The transition model maps a state, ground action, and next state to a probability.Source: §3 · p. 2
• The method targets problems with extraneous objects that can be ignored to make planning easier.It is biased toward this subclass and offers no benefit when planning is easier or only feasible with all objects.Source: §3 · p. 2
• PLOI scores each object from the initial state and goal, selects objects above a threshold, and calls the planner on the reduced problem.The threshold changes over an incremental loop, which validates the plan against the original problem and considers more objects if needed.Source: §3 · p. 3
• PLOI plans only when its selected object set changes and assigns a score of 1 to objects named in the goal.These optimizations limit planner calls to at most the number of objects.Source: §3 · p. 3
• The black-box planner returns a plan for deterministic transitions or a policy for stochastic transitions.A plan reaches a goal from the initial state; a policy does so within a time horizon with probability above a threshold.Source: §3 · p. 3
• The objective is to maximize test problems solved within a time budget by learning on training problems to speed planning on larger test problems.Training and test problems share properties, actions, and the transition model, but may differ in objects, initial states, and goals.Source: §3 · p. 3

4 Planning with Object Importance

• In the example, {B, D} fails because it omits obstructing A, whereas {A, B, D} is sufficient; irrelevant C receives score 0.03.With γ = 0.95, the example uses incremental planning to reach the larger set.Source: Figure 2 · p. 3
• PLOI reduces the problem to a predicted object subset, validates the resulting plan in the original problem, and incrementally expands the subset until a solution is found.The reduction removes initial-state and goal properties for excluded objects; a sufficient set yields a valid solution to the original problem.Source: §4 · p. 3

Scoring Object Importance Individually

• Individual object scores define candidate sets by threshold, and lowering the threshold geometrically provides recourse while guaranteeing completeness with a complete planner.The score is interpreted as the probability that an object belongs in a small sufficient set.Source: Scoring Object Importance Individually · p. 4
• Individual scoring cannot distinguish required copies of otherwise identical objects, so some sufficient subsets are unrepresentable.For example, it assigns the same score to all copies when a task requires a particular number of them.Source: Scoring Object Importance Individually · p. 4

Training with Supervised Learning

• Training labels are generated by greedily removing objects from the full set whenever the reduced set remains sufficient, then labeling retained objects positive and removed objects negative.The procedure uses repeated planning checks on smaller, easier training problems and may miss a smaller sufficient set.Source: Training with Supervised Learning · p. 4
• The objectwise loss uses weighted binary cross-entropy, with weight 10 increasing the penalty for false negatives to address class imbalance.The loss decomposes over objects to support data-efficient learning.Source: Training with Supervised Learning · p. 4

5 Object Importance Scorers as GNNs

• GNNs provide a relational model suited to generalizing from few training objects to many test objects without overfitting to object identity or count.They also accommodate continuous properties; other lifted, relational, efficiently learnable models that handle continuous properties are possible.Source: §5 · p. 5
• Each object becomes a node, unary properties become node features, binary properties become edge features, and each output node feature is its importance score.The output graph retains the input topology, while its node features encode object scores.Source: §5 · p. 5
• Goal features encode property presence and assignment; STRIPS-like domains can sparsify edges and remove a redundant dimension when goals lack negation.Unary properties add two node-feature dimensions, while binary properties add four edge-feature dimensions for the two object orderings.Source: §5 · p. 5
• The trained GNN predicts all object scores in one inference pass using K = 3 message-passing iterations, taking a few milliseconds in the reported experiments.Messages pass between edges and nodes through networks whose weights are shared across nodes and edges.Source: §5 · p. 5

Experimental Setup

• Baselines include pure planning, random object scoring, relational neighbors, reactive policies, and ILP or GNN action grounding; a state-of-the-art lifted planner solved no test problems.GNN baselines were supervised-trained on plans from an optimal planner for small training problems.Source: Experimental Setup · pp. 5–6
• The illustrations encode unary initial-state and goal properties as graph nodes and binary properties as edges, then show geometry-sensitive PyBullet scores and threshold-based scene reduction.The GNN runs three message-passing iterations before assigning an importance score to each object.Source: Figure 3 · p. 6, Figure 4 · p. 7

Results and Discussion

• Across domains, PLOI is consistently best and usually at least two standard deviations better; in Gripper it is two orders faster than pure planning, while in Hanoi it is comparable.The Hanoi result holds when all objects are necessary.Source: Table 1 · p. 6, Results and Discussion · p. 7

Experimental Setup

• Evaluation covers nine domains, training on 40 instances and testing on 10 larger ones, including test problems with up to 3,200 objects.The domains comprise six classical, two probabilistic, and one simulated robotic task and motion planning domain.Source: Experimental Setup · p. 6

Results and Discussion

• PLOI outperforms action-grounding baselines with less inference overhead, scoring objects rather than the much larger set of possible ground actions.Unlike those baselines, PLOI treats PLAN as a black box.Source: Results and Discussion · p. 7
• Neighbors struggle when an important object lacks a relation to another important object, while reactive policies are slow and have higher failure rates than planning baselines.The policy computes valid actions and runs inference at every timestep; PLOI infers only at the first timestep.Source: Results and Discussion · p. 7
• PLOI beats random object scoring in every domain except Hanoi, finding sufficient object sets in fewer than five iterations and often one.Figure 5 excludes Miconic and PyBullet because random scoring never succeeded there.Source: Figure 5 · p. 7, Results and Discussion · p. 7
• In continuous PyBullet task and motion planning, PLOI improves on an off-the-shelf system by predicting over discrete objects rather than continuous ground actions.Action-grounding methods cannot be applied because the domain has infinitely many ground actions.Source: Results and Discussion · p. 7

7 Conclusion

• PLOI is presented as a general mechanism for planning in large instances containing many objects.The authors characterize it as simple, powerful, and general.Source: §7 · p. 7
• Across classical, probabilistic, and robotic task and motion planning, PLOI performs well empirically.Source: §7 · p. 7
• Future work includes comparing GNN scoring with statistical relational learning and applying PLOI to open domains with unknown object sets.The authors also frame PLOI as a step toward integrated neuro-symbolic AI.Source: §7 · p. 7

Planning details

• Fast Downward in LAMA-first mode is the test-time classical planner, while seq-opt-lmcut generates training data with an optimal planner.Source: A Experimental Details · p. 10
• Probabilistic planning uses single-outcome determinization and replanning, while the PyBullet TAMP experiment uses PDDLStream in focused mode.Source: A Experimental Details · p. 10

Hardware details

• Experiments ran on Ubuntu 18.04 with four Intel Xeon Gold 6248 cores and 10GB RAM per core.Source: A Experimental Details · p. 10

PLOI and GNN details

• The GNN uses K = 3 message-passing iterations and one-hidden-layer node and edge modules with dimension 16, ReLU, and layer normalization.Training uses PyTorch 1.5.0, Adam at learning rate 0.001 for 1000 epochs, and batch size 16; regularization, dropout, and hyperparameter search brought no consistent improvements.Source: A Experimental Details · p. 10

Domain coverage

• The evaluation covers nine domains: six classical, two probabilistic, and one simulated robotic task and motion planning domain.The classical and probabilistic domains are from the International Planning Competition.Source: B Domain Descriptions · p. 10

Classical domains

• Tower of Hanoi tests 10–15 disks after training on 4–9, while Blocks tests 100–150 blocks after training on 15–32.Hanoi includes all objects as necessary; Blocks goals involve 20–25 blocks and target a small subset of blocks.Source: B Domain Descriptions · p. 10
• Gripper tests 100–200 objects, and Miconic test instances exceed 2000 objects across 100 buildings.Gripper goals place 10–20 balls; Miconic goals move one passenger per building to a desired floor.Source: B Domain Descriptions · p. 10

Other domains

• Ferry and Logistics test instances contain 250–350 objects and around 50 airplanes, respectively; probabilistic tests include Exploding Blocks and Triangle Tireworld.The PyBullet robotic domain tests interaction with a particular can amid around 1000 irrelevant cans, using continuous object poses as node features.Source: B Domain Descriptions · p. 10

Effect of Message Passing Iterations (K)

• Performance on Blocks is robust for 2 ≤ K ≤ 5 but drops heavily at K = 1.The authors suggest some message propagation matters; too few iterations may limit fit, while too many may slow computation and risk overfitting.Source: Effect of Message Passing Iterations (K) · p. 10, Figure 6 · p. 11

Effect of Number of Training Problems

• Blocks performance peaks starting at 3 training problems and remains robust for > 3, while other domains may need more examples.The Blocks experiment varied the number of training problems from 2 to 40; Figure 7 reports results averaged over 10 seeds with standard deviations shaded.Source: Effect of Number of Training Problems · pp. 10–11, Figure 7 · p. 11

Training Times

• PLOI GNN training averages 3 min, versus 5 min for Policy and 500 min for GNN AG.Training-data generation takes 15 seconds per Blocks problem to 90 seconds per Tireworld problem; PLOI training speed is on par with ILP AG.Source: Training Times · p. 11, Table 2 · p. 11