Source-linked AI summary
TASKOGRAPHY: Evaluating robot task planning over large 3D scene graphs
Christopher Agia, Krishna Murthy Jatavallabhula, Mohamed Khodeir, Ondrej Miksik, Vibhav Vineet, Mustafa Mukadam, Liam Paull, Florian Shkurti
TL;DR
There is not currently a large-scale benchmark tailored to robotic task planning in 3DSGs with several hundreds of objects. The paper constructs TASKOGRAPHY for symbolic planning over 3DSGs and proposes SCRUB for task-conditioned sparsification and SEEK for hierarchy-aware learning-based planning. SCRUB lets classical planners match or surpass state-of-the-art learning-based planners on most benchmark tasks, while SEEK reduces replanning iterations by an order of magnitude.
Problem
There is not currently a large-scale benchmark tailored to robotic task planning in 3DSGs with several hundreds of objects.
Source: §2 · p. 2Method
The paper constructs TASKOGRAPHY for symbolic planning over 3DSGs and proposes SCRUB for task-conditioned sparsification and SEEK for hierarchy-aware learning-based planning.
Source: §1 · pp. 1–2Results
SCRUB lets classical planners match or surpass state-of-the-art learning-based planners on most benchmark tasks, while SEEK reduces replanning iterations by an order of magnitude.
Source: §1 · p. 2Takeaways & Limitations
The work identifies graph sparsification and planner use of 3DSG hierarchies as two fronts for making planning over 3DSGs performant.
Source: §1 · p. 2TASKOGRAPHY covers only a fraction of possible 3DSG planning problems and focuses on offline, fully observable, deterministic tasks, excluding low-level motion planning.
Source: §7 · p. 8
Abstract
from arXiv · showhide
3D scene graphs (3DSGs) are an emerging description; unifying symbolic, topological, and metric scene representations. However, typical 3DSGs contain hundreds of objects and symbols even for small environments; rendering task planning on the full graph impractical. We construct TASKOGRAPHY, the first large-scale robotic task planning benchmark over 3DSGs. While most benchmarking efforts in this area focus on vision-based planning, we systematically study symbolic planning, to decouple planning performance from visual representation learning. We observe that, among existing methods, neither classical nor learning-based planners are capable of real-time planning over full 3DSGs. Enabling real-time planning demands progress on both (a) sparsifying 3DSGs for tractable planning and (b) designing planners that better exploit 3DSG hierarchies. Towards the former goal, we propose SCRUB, a task-conditioned 3DSG sparsification method; enabling classical planners to match and in some cases surpass state-of-the-art learning-based planners. Towards the latter goal, we propose SEEK, a procedure enabling learning-based planners to exploit 3DSG structure, reducing the number of replanning queries required by current best approaches by an order of magnitude. We will open-source all code and baselines to spur further research along the intersections of robot task planning, learning and 3DSGs.
1 Introduction
The introduction frames full 3D scene graphs as a challenge for task planners and presents TASKOGRAPHY to evaluate planning over them. It proposes SCRUB and SEEK to address graph sparsification and hierarchy-aware planning.
1 Introduction
- Real-world tasks may involve tens of thousands of object-action pairs, while many tasks concern only a small subset of scene objects and leave most context irrelevant.For example, fetching a mug from a kitchen primarily involves scene elements associated with mugs or kitchens.Source: §1 · p. 1
- 3DSGs hierarchically represent metric, semantic, and relational scene information, but their suitability for complex robotic task planning has not been thoroughly evaluated.Source: §1 · p. 1
- TASKOGRAPHY evaluation finds neither classical nor learning-based planners can plan in real time over full 3DSGs, but they can when the graphs are sparsified.The benchmark covers challenging task-planning domains designed for 3DSGs.Source: §1 · p. 1
- SCRUB produces a minimal sufficient object set for grounded planning, letting classical planners match or surpass state-of-the-art learning-based planners on most benchmark tasks without prior learning.Planning on the reduced set suffices to solve the problem defined over the full 3DSG.Source: §1 · p. 2
- SEEK adds 3DSG structure to learning-based incremental planners, making all objects in the sufficient set reachable from the start state and reducing replanning iterations by an order of magnitude.Source: §1 · p. 2
- The paper identifies two needs for planning over 3DSGs: make graphs tractable through sparsification and design planners that exploit their spatial hierarchies.The authors also plan to open-source code and baselines to support new domains and benchmarking newer learning-based planners.Source: §1 · p. 2
2 Related work
Prior work addresses symbolic planning efficiency, representations, learned planning, and pruning, but lacks a large-scale benchmark for robotic task planning over 3DSGs. Existing methods also face scaling or replanning challenges in these settings.
2 Related work
- Optimal symbolic planners preserve cost or plan-length optimality but are computationally expensive, motivating satisficing planners that produce cheaper feasible plans.Heuristic planning can be hindered by extraneous objects that make informative low-cost heuristics difficult to compute.Source: §2 · p. 2
- Prior robotics work includes effective representations, task-and-motion planning, and task hierarchies, whereas this paper focuses on spatial abstractions in 3DSGs rather than task structure.Source: §2 · p. 2
- Learning-based planners perform promisingly on small-to-moderate problems, but several approaches fail on large instances with the branching factors and operators in TASKOGRAPHY.Some methods that learn to search rely on difficult-to-obtain dense rewards or do not scale with domain complexity.Source: §2 · p. 2
- PLOI scores and prunes extraneous objects but incurs many replanning steps from inaccurate predictions and does not exploit 3DSG hierarchies; SEEK is reported to reduce replanning steps by two orders of magnitude.Source: §2 · p. 2
- No existing large-scale benchmark is tailored to robotic task planning over 3DSGs containing several hundred objects.Other environments cover language-directed policies, task and motion planning, physical interactions, navigation, or block stacking.Source: §2 · p. 2
3 Background
The background defines task-planning problems through objects, properties, actions, transitions, costs, and initial and goal states. It describes 3DSGs as hierarchical multigraphs whose nodes represent increasingly precise scene entities and relations.
3 Background
- A task-planning problem comprises ground objects, properties, lifted actions, a transition model, transition costs, and initial and goal states.Problems may be grounded to a specific object or lifted to an object class.Source: §3 · p. 3
- A 3DSG is a hierarchical multigraph with at least five levels in this work, from a scene root through floors, rooms, and places to objects.Source: §3 · p. 3
- 3DSG edges encode relations among nodes, while node attributes include semantic information such as type, functionality, and affordances.Source: §3 · p. 3
4 TASKOGRAPHY
TASKOGRAPHY benchmarks symbolic planning across large 3D scene graphs, which it augments with plannable attributes and organizes into varied robotic task domains. Results show that existing planners struggle on full graphs, with performance shaped by task complexity and pruning-related trade-offs.
4 TASKOGRAPHY
- TASKOGRAPHY comprises 20 domains and 3,734 tasks built on Gibson building scans and their corresponding 3DSGs.The benchmark spans tasks from rearrangement to couriering, including lifted variants whose goals specify object categories rather than instances.Source: §4 · p. 3, §4.1 · pp. 4–5
- The benchmark augments Gibson 3DSGs with unary and binary predicates, affordances, object properties, and room-connectivity edges for planning.Its annotations include object class, dimensions, and pose, and account for concealed or contained objects when applying affordance knowledge.Source: §4 · p. 3
- The benchmark spans grounded and lifted domains, from polynomial-time problems to NP-hard ones, with state variables and branching factors varying by difficulty.The simplest domains have 1,000 state variables and average branching factor 5; hard domains have 4,000 and 60, respectively.Source: §4 · p. 4
4.2 Benchmarking classical and learned planners on TASKOGRAPHY
- Evaluation gives optimal planners 10 minutes per problem and other planners 30 seconds, with learning-based results averaged over 10 seeds.Domains have 40 training problems; Tiny and Medium test splits have 55 and 182 problems, respectively, unless otherwise specified.Source: §4.2 · p. 5
- Optimal planners solve only the simplest domains, while satisficing planners encounter dead ends in long-horizon Courier tasks and timeouts.Courier tasks can exhaust knapsack slots through early stowing, causing dead ends and backtracking; MCTS and Monte Carlo Regression Planning fail under large branching factors and sparse end rewards.Source: §4.2 · pp. 5–6
- Task complexity tracks operator count and average branching factor more than scene size; performance remains largely consistent between tiny and medium splits of a domain.Failures and timeouts increase in larger Rearrangement(k) tasks, but larger scenes do not directly correlate with task complexity.Source: Table 2 · p. 5, §4.2 · p. 5
- Learning-based pruning methods excel across domains, but PLOI can require many replanning steps when it retains objects without required properties or ancestors.The benchmark discussion calls for both adapting 3DSGs for existing planners and enabling planners to exploit 3DSG hierarchies.Source: §4.2 · p. 6
- Pruning is essential for real-time performance, while learning-based planners perform well across domains but require many replanning steps.Table 1 reports PLOI [13] as consistently best across select domains, while optimal planning is infeasible for larger or more complex problems and most satisficing planners miss real-time performance.Source: Table 1 · p. 5, §4.2 · p. 6
5 SCRUB: Principled sparsification of 3DSGs for efficient planning
SCRUB removes task-irrelevant parts of a 3D scene graph while preserving what grounded planning needs, then lets classical planners perform competitively. Its benefits vary by domain and planner objective.
5 SCRUB: Principled sparsification of 3DSGs for efficient planning
- SCRUB starts from goal objects and the robot, then iteratively adds objects related through binary predicates until the sufficient object set stops growing.It removes other graph nodes and invalid literals from the reduced problem.Source: §5 · pp. 6–7
- For grounded planning, SCRUB is complete and produces a minimal scene subgraph; solving the reduced problem yields a satisficing plan when one exists.The proposition states completeness and minimality; the text describes the resulting satisficing guarantee.Source: §5 · pp. 6–7
5.1 Impact of SCRUB on modern task planners
- SCRUB prunes more than two-thirds of operators and state variables in grounded problems, and about a third in lifted problems.Figure 5 reports the reduction in operators and states.Source: Figure 5 · p. 7, §5.1 · p. 7
- SCRUB reduces planning to a few milliseconds for FF, FD-lama-first, and BFWS on Rearrangement(10), and caps times at 5 seconds on Courier(10, 10), enabling BFWS, FD, and FF to beat PLOI in plan length at similar times.The comparison is shown in Figure 4.Source: Figure 4 · p. 7, §5.1 · p. 7
- On Lifted Rearrangement(5), FD (optimal) + SCRUB solved about 72% of tasks within a 30-second timeout, averaging 2 seconds per task; FD (optimal) did not converge within 24 hours.Table 3 covers 70 test problems.Source: Table 3 · p. 7, §5.1 · p. 7
6 SEEK: A procedure for efficient learning-based planning
SEEK uses 3DSG hierarchy to retain connected subsets of objects selected by a learned scorer. It reduces replanning steps, while SCRUB’s conservative approach can lag on challenging lifted problems.
6 SEEK: A procedure for efficient learning-based planning
- SCRUB’s conservative reduction can hurt performance on challenging lifted problems, where PLOI can outperform it despite incurring many replanning iterations.SCRUB’s reduction is guaranteed to find a satisficing plan if one exists.Source: §6 · p. 7
- SEEK thresholds object scores, geometrically lowers the threshold between iterations, and adds each retained object’s ancestors to keep the selected graph connected.The scorer assigns each object an importance value, typically using a graph neural network.Source: §6 · p. 8
- SEEK reduces replanning steps by an order of magnitude across evaluated learning-based planner variants.The comparison includes random pruning, PLOI, and a hierarchical variant; Figure 6 presents replanning steps.Source: Figure 6 · p. 8, §6 · p. 8
- SCRUB is generally more performant on grounded domains, while SEEK is more performant on lifted domains because it opportunistically retains instances of important object categories.Figure 7 illustrates this domain distinction.Source: §6 · p. 8
7 Concluding remarks
The authors position TASKOGRAPHY, SCRUB, and SEEK as resources for planner evaluation and 3DSG design. The benchmark’s initial scope is limited to offline, fully observable, deterministic planning.
7 Concluding remarks
- Figure 7 contrasts SCRUB on grounded domains with SEEK on lifted domains.The accompanying text says SCRUB is generally more performant on grounded domains and SEEK on lifted domains.Source: Figure 7 · p. 8, §7 · p. 8
- TASKOGRAPHY currently covers only a fraction of possible 3DSG planning problems, focusing on offline tasks in fully observable, deterministic domains and excluding low-level motion planning.Real-world robots will also need to reason under partial observability, sensor noise, and resource constraints.Source: §7 · p. 8
- TASKOGRAPHY, SCRUB, and SEEK are intended to guide planner choice, benchmark upcoming learning-based planners, and inform future spatial representations for robotic task planning.The authors describe TASKOGRAPHY as a first step toward general planning capabilities for autonomous robots.Source: §7 · p. 8
A Benchmark Details
The benchmark comprises 20 robot task-planning domains over 3D scene graphs, with several ground objects alongside one agent in each problem.
A Benchmark Details
- TASKOGRAPHY has 20 domains; its detailed examples include Rearrangement, Courier, Lifted Rearrangement, and Lifted Courier tasks.Each problem has one agent and several ground objects from other categories.Source: A Benchmark Details · p. 13
A.1 TASKOGRAPHY domain construction: Parsing Gibson 3DSGs
The benchmark maps Gibson 3DSGs into symbolic planning representations, retaining spatial connectivity and adding predicates for robot and object state. TASKOGRAPHY-API then samples diverse planning problems and composes goals over scene entities.
A.1 TASKOGRAPHY domain construction: Parsing Gibson 3DSGs
- Gibson 3DSGs are parsed into objects and predicates, retaining connectivity between locations, places, and rooms while estimating room links from centroid distances.For larger scenes, rooms on different floors receive a single connection.Source: §A.1 · pp. 13–14
- Scene entities are assigned object types, and domain-specific subsets of predicates and relations encode robot state and interactable objects.The most challenging Lifted Courier(n, k) domain incorporates all structural relations.Source: Table 5 · p. 14, Table 6 · p. 14, §A.1 · p. 14
- TASKOGRAPHY-API samplers parse 3DSGs into symbolic initial states and compose goals over randomly sampled ground objects or object classes.Grounded goals use inReceptacle literals; lifted goals use classRelation literals.Source: §A.1 · p. 14
A.2 Domain specifications
The domain specifications define grounded and lifted task goals over a 3DSG spatial hierarchy. Symbolic operators move the robot through that hierarchy and support object interaction, including stowing and retrieval.
A.2 Domain specifications
- Grounded Rearrangement goals identify specific item–receptacle pairs, while Courier adds weighted items and a fixed-capacity knapsack for stowing and retrieval.Courier can enable lower-cost solutions than Rearrangement, at the expense of task complexity.Source: §A.2 · pp. 14–15
- Lifted goals specify item–receptacle classes, preventing planners from using goal ground objects as heuristic landmarks and reducing deterministic SCRUB's effectiveness.Lifted Rearrangement and Lifted Courier use identical goal specifications.Source: §A.2 · p. 15
A.3 Symbolic environment interaction
- The most complex domain has 16 operators, including hierarchical navigation, receptacle opening and closing, pickup and placement, and knapsack stowing and retrieval.Actions are valid only when their preconditions are satisfied.Source: §A.3 · p. 15
B SCRUB: Discussion and analysis
SCRUB is proven complete and minimal for grounded planning problems over the scenegraph domain. Its adaptations cover lifted and stochastic problems, though the lifted strategy may retain more objects than minimally required.
B SCRUB: Discussion and analysis
- SCRUB is designed for lifted or grounded problems and deterministic or stochastic transitions, with stochastic adaptations retaining predicates from possible transitions.For lifted problems, it includes all ground object tuples satisfying goal conditions, which may retain more objects than minimally required; SEEK can opportunistically retain important objects instead.Source: B SCRUB: Discussion and analysis · p. 15
- SCRUB is complete and produces a minimal scene subgraph for grounded planning problems over the scenegraph domain.The proof establishes minimality by showing that pruning any retained node makes the planning problem unsolvable.Source: B SCRUB: Discussion and analysis · pp. 15–16
- The minimality argument covers agent and building nodes, goal items, goal receptacles or access receptacles, and places, rooms, or floors needed for traversal.Removing any such node renders the problem unsolvable or makes a goal object unreachable.Source: B SCRUB: Discussion and analysis · p. 16
C Additional results on TASKOGRAPHY domains
The additional results section presents planner-performance tables across grounded and lifted TASKOGRAPHY domains. The supplied captions identify task coverage and state that lower values are better, but do not provide table values.
C Additional results on TASKOGRAPHY domains
- Planner performance on Rearrangement(k) is reported separately for tiny and medium tasks, with lower values indicating better performance.Source: Table 7 · p. 16, Table 8 · p. 17
- Courier(n, k) planner results cover tiny and medium tasks, and the captions identify lower values as better.Source: Table 9 · p. 17, Table 10 · p. 17
- Separate performance tables report results for Lifted Rearrangement(k) and Lifted Courier(n, k), with lower values indicating better performance.Source: Table 11 · p. 18, Table 12 · p. 18