Taskography: Evaluating robot task planning over large 3D scene graphs
Authors: Christopher Agia
Krishna Murthy Jatavallabhula
Mohamed Khodeir
Ondrej Miksik
Vibhav Vineet
Mustafa Mukadam
Liam Paull
Florian Shkurti
Venue: CoRL2021 Poster (2021)
Keywords: Robot task planning
3D scene graphs
learning to plan
benchmarks
planning

Abstract: 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 \emph{full} graph impractical. We construct \textbf{Taskography}, the first large-scale robotic task planning benchmark over 3DSGs. While most benchmarking efforts in this area focus on \emph{vision-based planning}, we systematically study \emph{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 \emph{full} 3DSGs. Enabling real-time planning demands progress on \emph{both} (a) sparsifying 3DSGs for tractable planning and (b) designing planners that better exploit 3DSG hierarchies. Towards the former goal, we propose \textbf{Scrub}, a task-conditioned 3DSG sparsification method; enabling classical planners to match (and surpass) state-of-the-art learning-based planners. Towards the latter goal, we propose \textbf{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.

TASKOGRAPHY: Evaluating robot task planning over large 3D scene graphs
Project page: http::/haakograahhygghbbbb
Christopher Agia"!, Krishna Murthy Jatavallabhula Mohamed Khodeir', Ondrej Miksik?,
Vibhav Vineet', Mustafa Mukadam", Liam Paull?, and Florian Shkurti 1.5
University of Toronto, Montreal Robotics and Embodied AI Lab, Mila, Université de Montréal, MMicrosoft, "Facebook AI Research, VVector Institute
Abstract: 3D scene graphs (3DSGs) are an emerging description; unifying sym- bolic, topological, and metric scene representations. However, typical 3DSGs contain hundreds of objects and symbols even for small environments; render- ing 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 sasion-based plamning, we systemati- cally study symbolic planning, to decouple planning performance from visual rep- resentation learning. We observe that, among existing methods, neither classical nor learning- -aannnngg- planners 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 hier- archies. Towards the former goal, we propose SCRUB, a task-conditioned 3DSG sparsification method; enabling classical planners match and in some cases sur- pass state-of-the-at SEEK, a procedure enabling learning-baid based planners to exploit 3DSG structure, reducing the number of replanning queries required by current best approaches by 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.
barning-based planners. Towards the latter goal, we propose
Keywords: Robot task planning, 3D scene graphs, learning to plan, benchmarks
Introduction
Real-worid robotic task planning problems in large environments require reasoning over tens of thousands of object-action pairs. Faced with hong-horizon tasks and an abundance of choices, state- of-the-ard art task planners struggle with an efficiency- the goal. Hence, designing actionable scene abstractions suitable for a range of robotic tasks has drawn long-standing attention from the robotics and computer vision communities [1, 2, 3, 4, 5, 6).
trade-off in grounding actions towards
A promising approach for building symbolic abstractions from raw perception data are 3D scene graphs (3DSGs, see Fig. 1) [7, 8, 9] - hierarchical representations of a scene that capture metric, semantic, and relational information, such as affordances, properties, and relationships among scene entities. While 3DSGs have to date been applied to simpler planning problems like goal-directed navigation [6, 10], active object search [11], and node classification [12], their amenability more complex robotic task planning problems has yet to be thoroughly evaluated.
To investigate the joint application of 3DSGs and modern task planners complex robotics tasks we propose TASKOGRAPHY: the first large-scale benchmark comprising a number of challenging task planning domains designed for 3DSGs. Analyzing planning times and costs a diversity of domains in TASKOGRAPHY reveals that neither classical nor learning-basse planners are capable of real-time planning over full 3DSGs, however, that they become so only when 3DSGs sparsified.
Many rorldworld problems only require reasoning over a small subset of scene objects. E.g., the task "fetch mug from the kitchen" primarily involves reasoning about scene elements associated with mugs or kitchens, rendering a vast majority of the remaining environment contextually irrelevant. Most planners aren't 't able exploit such implicitly defined task contexts, instead spending most of their computation time reasoning about extrancous scene attributes and actions [13] (see Fig. 5).
Authors contributed equally. Order determined by academic juniority.
5th Conference on Robot Learning (CoRI. 2021), London, UK.

---

We argue that performant task planning over 3DSGs demands progress on two fronts: (a) sparsi- fying 3DSGs to make planning problems tractable, and (b) designing task planners that exploit the spatial hierarchies encapsulated in 3DSGs. To address (a), we present SCRUB-a planner-agnostic strategy guaranteed to produce minimal sufficient object set for grounded planning problems. That is, planning on this reduced subset of scene entities suffices to solve the planning problem defined over the full 3DSG. Classical planning over state spaces (3DSGs) augmented by SCRUB outper- forms state-of-the-art learning-based planners the majority of tasks our benchmark, without requiring any prior learning, establishing a strong baseline for future work in robotic task planning. To address (b), present SEEK: a procedure tailored to 3DSGs, which supplements learning- based incremental planners by imposing 3DSG structure, ensuring all objects in the sufficient set reachable from the start state. In our experiments, augmenting state-of-the-an planners with SEEK results in computational savings and an order of magnitude fewer replanning iterations.
In summary, we make the following contributions:
TASKOGRAPHY: large-scale benchmark to evaluate robotic task planning over 3DSGs, SCRUB: a planner-agnostic strategy to adapt 3DSGs for performant planning,
SEEK: a procedure that enables learning-based planners to better exploit 3DSGs
We will open-source all code and baselines in TASKOGRAPHY-AN API, enabling the construction of new task planning domains, and benchmarking the performance of newer learning-baas -bsed planners.
2
Related work
Early research in symbolic planning was centered around optimal planning [14, 15, 16, 17, 18]; planners producing solutions that preserve cost or plan length optimality. These methods are com- putationally expensive and thereby untenable to even moderately sized problems. This spurred work on satisficing planners that forgo optimal solutions for cheaper, feasible plans. Notable paradigms include regression planning [19], tree search [20], and heuristic search [21, 22, 23, 24, 25J. Whilst the many successes of heuristic planners [26. 27], computing low-cost informative heuristics is de- terred by many extraneous objects [28, 13]; an inauspicious characteristic of large 3DSGs.
Robot task planning techniques have focused on constructing more effective representations to plan upon [29, 30. 31]. There are also approaches that integrate task and motion planning [32, 33, 34]- further demonstrated in hierarchical task space [35]-but which fall outside the scope of our work. Several approaches exploit task hierarchies for robot task planning [36] and control [37, 38, 39]. Different from these, our work focuses exploiting abstractions in spatial structure encapsulated in 3DSGs, not to be conflated with hierarchical planners that exploit task structure [40].
State-of-the-art learning-based planners have demonstrated promising performance in small-to- moderate problem sizes. However, techniques such as relational policy learning [41], relational heuristic learning [42]. action grounding [43]. program guided symbolic planning [44, 45, 46, 47, 48], and regression planning networks [49] fail in large problem instances with branching factors and operators of the order considered (sce Fig. 2) in the TASKOGRAPHY benchmark. Moreover, several planners that learn to search [50, 51, 52, 53) depend on hard-to-obtain dense rewards or do not scale with domain complexity [54, 55, 56].
The simplification of planning problems via pruning strategies to enable efficient search has been explored in both propositional [57, 58, 43] and numeric [59] planning contexts. Among these, PLOI [13] is a particularly performant learning-based approach that leverages object-centric rela- tional reasoning [60, 61, 62, 63) to score and prune extruneous objects to the task. While PLOI outperforms existing classical planners on the TASKOGRAPHY benchmark, it incurs a large number of replanning steps owing to inaccurate neural network predictions; and inability to exploit 3DSG hicrarchies. Our proposed SEEK procedure decreases replanning steps by two orders of magnitude.
Planning benchmarks in the symbolic planning communities have featured a variety of tasks with time complexities ranging from polynomial (e.g.. shortest- path) to harhard problems (e.g., traveling salesman). There also exists a handful of environments [64, 65, 66, 67, 68] for benchmarking learned action policies from language directives and ego-centric visual observations, task and motion plan- ning [69], or the modelling of physical interactions 170, 71]. Another recent benchmark [72] only supports navigation and block-stacking tasks. However, there isn't I currently a large-scale bench- mark tailored to robotic task planning in 3DSGs with several hundreds of objects.

---

3 Background
Task planning. A task planning problem II is a tuple (O,P..AT,C,II,) As a running example, consider the task find an apple, slice it, and place on the counter. O is the set of all ground objects (instances) in the problem. P is set of properties, each defined over one or more objects; weight(apple) = 70 grams. Predicates are subclasses of properties in that they are boolean- -allud--valued; canPlace(apple, refrigerator) = True. AA is finite set of lifted actions operating over object tuples; slice(apple), place(apple, counter). T is transition model and denotes state transition costs. I and G are initial and goal states. A state is an assignment of values to all possible properties grounded over objects. For the running example, goal state may be specified as on(apple, counter)=True and (apple
valued;
Planning problems may be grounded-slice this apple, or lifted-slice apple.
3D scene graphs (3DSGs). 3DSG [7, 8] is hierarchical multigraph G = EV) with k E {1.... K} levels, where V E V denotes the set of vertices level k. Edges originating from a vertex U E V may only terminate in
Floor
Rooms
V U VK+1 (i.e., edges connect nodes within one level of each other). Each 3DSG in our work comprises least 5 levels with in- creasing spatial precision as we move down the hierarchy: the topmost level in the hierarchy is a root node representing a scene. This node branches out to indicate the various floors in the building, which in turn branches out to de- note various rooms in a floor, and subsequently places within room. A place is a collec- tion of objects, which may themselves contain other objects (to allow for container types such as cabinets and refrigerators)). At each level, edges indicate various types of relations among nodes (e.g., at the room level, an edge indicates the existence of traversible path between two rooms; at the object level, edges indicate multiple affordance relations). Each node also stores mantic attributes such as node type, functionality, affordances, etc., following [7].
Mhiel Mio
Objects/ Places
Figure I: state a planning problem specified over a 3DSG. Nodes are seene entities and store unary pred- icates. Edges indicate binary predicates (relations). A goal is conjunction of unary and binary literals. We only show a subset of relations for brevity. E.g., if the robot executes an action that moves to another room, the robotInRoom relation shown in this figure will be set to False for the room on the lower left.
TASKOGRAPHY
We propose TASKOGRAPHY: the first large scale benchmark to evaluate symbolic planning over 3DSGs. Currently, TASKOGRAPHY comprises 20 challenging robotic task planning domains total- ing 3734 tasks. Different from current benchmarks for embodied AI that focus primarily on ego- centric visual reasoning [65, 73, 74, 64, 71. 67]; TASKOGRAPHY is designed to evaluate symbolic reasoning over 3DSGs. To emulate the complexity of real-world task planning problems, TASKOG- RAPHY builds atop the Gibson [75] dataset comprising real-world scans of large building interiors (averaging 2-3 floors per building; 7 rooms per floor), and their corresponding 3DSGs [7].
Augmenting 3DSGs with plannable attributes. A prerequisite for planning over 3DSGs-absen in existing work [9. 7, 8j-is a database of plannable aurributes predicates, actions, and transition models. To support task planning, we augment each 3DSG in Gibson [75] (tiny and medium splits) with several layers of additional unary and binary predicates. For each 3DSG node, we obtain class labels, object dimensions and pose from [7]. We annotate object affordances by building knowledge base of lifted object-action pairs and recursively applying it to every 3DSG node, while accounting for exceptions (objects that concealed contained within others). We also detect door objects in the 3DSG and use this to add additional edges describing room connectivity. We annotate objects with all possible properties in our planning domains (e.g.. "is this object typically a receptacle?") ?"). Our rich property set (plammable altributes) is chosen to support a wide range of realistic-robotic tasks geared towards large (building-scale) 3DSGs.
'The lowest level in [8] is metric-semante mesh. However since our focus is on symbolic planning, we only require scene graph levels that contain objects.
3

---

15003
80-
40-
Libe Rannonggeea
10002
The AASKOGRAPHY benchmark comprises large-scale planning problems defined over buildings from the Gibson datasct [75]. (Left) Representative buildings from Gibson [75]. (Middle//ighh) We feature variety of problem classes ranging in scale and complexity illustrated by the domain statistics.
Figure 2:
Benchmark statistics. Each of the 20 TASKOGRAPHY domains specifies a class of planning prob- lems that resemble real-world use cases (and theoretically complex extensions) that a robot would encounter in office, house, or building scale environments. These domains range from grounded planning domains to lifted planning domains, domains with no extraneous objects to domains where most objects are extraneous, and domains for which polynomial time solutions exist to NP-hard problems. The simplest domains in the benchmark have 1000 state variables and an average branch- ing factor of 5; for hard domains, these 4000 and 60 respectively (see Fig. 2).
Our project page (https:/taskography. wit.hraapppyggbbbiooooo will host code and data used in this work. In TASKOGRAPHYY CANNGGRAPY--APPP an open-source python package, we provide access to 18 classical and learning-basee symbolic planners, templates to implement novel domains, and methods to generate problem instances of varying complexities and train/evaluate Sauring-basse" planners.
TASKOGRAPHY-AL
Planners considered. TASKOGRAPHY supports a comprchensive of planners to facilitate stan- dardized evaluation on novel domains. The following planners are available at the time of writing.
Optimal planners: Fast Downward (FD) with the opt-lmcut heuristic [23], Sat- Plan [16], Delfi [17], DecStar-optimal [25], and Monte Carlo tree search.
Satisficing planners: Fast Forward (FF), FF with axioms (FF-X) [22], Fast Downward
(FD) with the 1 ama -cut heuristic [23]. Decstar-satisficnng [25], Cerberus [24]. Best First
Width Search (BFWS) [76], and regression planning.
Learning-baat planners: Relational policy learning [41], Planning with learned object
importance (PLOI) [13] (and variants see Sec. 6).
General assumptions. To facilitate evaluation of all of these classes of planners, the first edition of benehmark only considers fully observable tasks and discrete state and action spaces. All goal states are specified as conjunctions of literals. While we make no distinction between determinis- tic or stochastic transitions, all current experiments assume closed world, i.e., all possible lifted actions and effects are known apriori.
4.1 Robot planning domains: Case studies
The full TASKOGRAPHY benchmark comprises 20 domains. We discuss the four task categories from which all domains are constructed that we believe to be interesting to a broad roboties audience. Domain 1. Rearrangement(()) Based on the recently proposed rearrangement challenge [77], this task requires a robot randomly spawned to rearrange set of i objects of interest into corre- sponding receptacles. The robot often needs to execule multiple other actions along the way, such as opening/closing doors, navigating to goals, planning the sequence of objects to visit, etc.
Domain 2. Courier (n, k): A robot that couriers objects is equipped with a knapsack of maximum payload capacity of units. The robot needs locate and courier l objects (of varying weights E {1, 2, 3) units) to k distinct delivery points. The knapsack can be used to stow and retrieve items random-acee access fashion; effectively embeddding a combinatorial optimization problem into the task. Stow and retrieve actions increase branching, necessitating far deeper searches.
We also provide lifted variants of these tasks. Here, goals are specified over desired abject-receptacle class relations (e.g.. "put cup on table") as opposed to over object instances (e.g.. "put this cup on the table"). These tasks introduce ambiguity in both the search of classical task-planners and learning-base based techniques, which must now distinguish object instances of relevant classes.

---

Table 1: TASKOGRAPHY benchmark results on select grounded and lifted Rearrangement (Rearr) and Courier (Cour) 3DSG domains. Planning times are reported seconds and not incorporate planner-specific domain translation times (factored into planning timeouts). A '-' indicates planning timeouts or failures (10 minutes for optimal planners, 30 seconds for all others). Results are aggregated over 10 random seeds. Optimal task planning is infeasible in larger problem instances for more complex domains, while most satisficing planners are unable to achieve real-time performance. PLOI [13), a recent learning-bass based planner consistently performs
the best across all domains.
Rearrtll Toyy
Rearet2) Tiny
Reurri18) Median
Court?, 18) Mediun
Lifted Rearr(5) Tiny
Lifted Court5, 5) Tiny
Plauner
Lan.
Fail
Leut
Fai
Fail
Fail
Fail
Len.
Time
FD--eg--pp--mmet
0.04
15,80
0.55
SutPlun
0.45
3.27
0.67
1,00
1
1,00
Delh DecStar-apt-lt
0.16
20.10
0.29
1
1
1,00)
1,00
1,00
1.00
1.00
1.00
1.00
MCTS
1300
1300
1.00
1.00
1,00)
1.00
FF
16.71
0.19
0,90
34,44
0.55
0,00
159.34
5,30
00.9
128.4
6.62
0..4
62.96
3.40
0.47
57.74
4.03
0.44
tatviinng
FP-X
1671
0.25
0,00
34.44
0.54
0J8
150.00
5,02
11105
12
0.72
0..4
07.88
3.48
0.59
61.14
7.50
0.73
0:33
38.47
3.25
0.18
205.28
0.49
156.34
4.92
0.20
61.13
3.34
7.30
7.05
DecStar-ag--it
0.55
2.58
0.58
211.16
7.20
132,60
0.71
58,75
4,46
HFWS
15:56
0.90
0.22
32.16
0.57
0.18
181.17
0.41
0123
152.91
1,55
(121
56.90
0.04
0.41
N7.02
2.30
0.41
Regrosion-plan
1.00
1.00
1.00
1.00
1.00
1.00
Rebational policy (41)
1,00
1.00
1.00
1.00
1.00
100
[LOI[L3]
16.45
0
0.90
37,04
0,00
0.00
213.43
0.17
0,00
161.90
0.34
0,00
78.65
0.22
0.34
71.71
0.26
0.26
Domain 3. Lifted Rearrangement (k): A lifted version of the rearrangement domain where the goals are specified at an object category level, as opposed to an instance level.
Domain 4. Lifted Courier (n, k): A lifted version of the courier domain where the goals are specified at an object category level, as opposed to an instance level.
To promote compatability with a range of planning systems [27, 78), we represent all tasks in PDDL format [79, 80]. We also include mechanisms for translating tasks into alternative problem definition languages that are essential for some of our supported planners [16].
4.2 Benchmarking classical and learned planners on TASKOGRAPHY
We present the empirical results on the TASKOGRAPHY benchmark across several classes of task- planners in Table. 1. (Please consult supplementary material for number of additional results).
Evaluation protocol. We treat the evaluation of optimal planners separately to the remaining meth- ods. Optimal planners are not intended to be fast unlike satisficing and learning- based variants. Rather, they compute a solution of minimum length (not necessarily unique) to a given problem. Op- timal planners are hence allotted 10 minutes to solve each problem, while satisficing and learning- based planners are allotted 30 seconds. For learning- random seeds for statistical significance. We report standard deviations in the supplementary mate- rial. All domains comprise 40 training problems. The domains tagged Tiny and Medium comprise 55 and 182 test problems respectively, unless otherwise specified.
methods, we evaluate results over 10
Optimal planners work only on the simplest of domains. Despite the reasonable performance of optimal planners on the Rearrangment( I) domain, they are unable to efficiently scale with increasing task complexity and fail to solve single task on the Rearrangment (k) and Courier (n, k) domains for k >>>>>>>> 2. In particular, the Rearrangemen((1) domain is a superset of the grounded hierarchical path planning (HPP) task as described by Rosinol et al. [6]. Because the HPP task does not consider state changes to the scene graph (i.e., directly equating the 3DSG to the planning graph for search), efficient shortest path planning is tractable. However, increasingly complex robot tasks requires more than the mere ability to path plan in 3DSGs.
Table 2: Interestingly, task complexity does not correlate strongly with scene complex- ity. is instead determined by the number of operators, and avg. branch factor.
Planning performance degrades with domain com- plexity, not scene complexity. We observe an increase in the number of planning failures and timeouts as sat- isficing planners are applied to larger Rearrangement(k) domains (Table 2). Interestingly, larger scenes do not ap- pear to directly correlate with task complexity, as the per- formance metrics remain largely consistent between the tiny and medium splits of the same domain (Table. 2).
Remert100
Rearri10) Modium
Planner
Len.
Time
Fuil
Len.
Time
Fail
FF
16261
7,05
0.07
159.08
5.30
0.09
FD (catishetnng
203 89
7.68
0.51
300.28
6.35
0.49
DocSlar-agg-th
193.00
6.78
0.35
211.16
7,20
0.52
BEWS
161.93
0.57
0.18
151.17
0.41
0.23
5

---

Satisficing planners fail in domains requiring long-horizon reasoning. In the Courier(n, k) do- mains, satisficing planners tend to produce shorter length solutions by leveraging the knapsack's capacity stow objects on the way to various delivery points. However, the planners often dis- play shortsighted behaviours by stowing objects early in the search, depleting knapsack slots that could potentially help further along the task. This yields dead-end configurations and excessive backtracking, and thus, an increase in timeouts is observed.
Planners that do not exploit forward heuristics fail due to large branching factors. Due to the large branching factor our domains, common strategies such as Monte-Care Carto Tree Search (MCTS) and MC Regression Planning are unable to solve any task within a reasonable time constraint. For instance, a Rearrangement (0) task has an average branching factor 6.5 for MCTS. Since reward is only obtained at the end (typical planners take 200 steps to get there), MCTS degenerates to a slow breadth-fire first search.
Learning based planners that prune the state space excel on all domains. We also evaluate two preva-
lent learning-to-plan methods based on generalized rela- tional planning [41] and planning with learned abstrac- tions [13]. While the relational policy stuggles to gen- eralize in our domains (long-horizon, sparse rewards), PLOI demonstrates an impressive ability to detect and prune contextually irrelvant parts of the 3DSGs. How- ever, it also requires a significant number of replanning steps (see figure the right) as it often retains objects within graph without ensuring that all properties and ancestors required to access the object are also preserved.
Do 11
100
150
200
250
Stepe
Learning-basse planners like PLOI outperform all other planners on the benchmark, but still incur significant over- head (number of replanning steps).
Figure 3:
Discussion. Our evaluation of existing performant planners on the TASKOGRAPHYY benchmark consistently reveals two important trends across all domains.
Pruning a 3DSG is essential for real-time performance, more so on challenging domains. While learning- based planners excel across all domains, they require large number of replanning steps.
These imply that efficient utilization of 3DSGs in real-time robotic task planning requires both adapting 3DSGs to better suit existing planners, and enabling performant (learning- -baedd planners to better exploit 3DSG hierarchies. The remainder of our work addresses these issues.
5 SCRUB: Principled sparsification of 3DSGs for efficient planning
As discussed above, learning-base based planners leverage wealth of prior knowledge acquired during a training phase to significantly prune extraneous scene graph en- tities. We argue that, if equipped with the right sparsifi- cation machinery, classical planners can compete with, or outperform learning methods. We develop SCRUB, prin- cipled 3DSG sparsification scheme that prunes 3DSG G (w.r.t planning problem II (O, P. (TC.IIG)) by removing vertices and edges extraneous to the task, resulting in a sparsified 3DSG & (and planning problem f1 = (O, C.PP..A A, C)
Algorithm SCRUB
Impot: 3DSG G. Planning problem II === (O.P. A, A,T.C.I..))
Result: Spanafied 3DSG
sufficient object set O:: /A Twllt.
./
OBIECISI litemls) (robot): /v Init. objects
goall liceral
while not empty g do
④ Ô U
x all binary gredicates relating a neuty added
object o Oo its ancestors in G Olunc1s(p))
ifll abjects visited then bresk
Definition 1. A valid 3DSG sparsification of G for planning problem IG to & (and corresponding planning problem l1g) is computable function SCRUB He such that, a plan p solves Il iff it solves flg-
und
& + G:
/- Initialize spareitied
CONNECTROOMS:
All-paais shercest
hat xf
ò Prune literals that are no longer valid in the sparsifted graphi
Remove all nodes
A satisficing plan for He may thus be obtained by simply solving the (much easier to solve) sparsified problem llg. Savings in planning time depend on the complexity of the sparsified subgraph &. SCRUB presents a simple strategy which is guaranteed to be minimal for grounded planning problems and satisficing for lifted planning problems.

---

For exposition, we consider grounded planning problems; see appendix for how SCRUB is adapted lifted planning problems or stochastic transitions. SCRUB begins with an initially empty sufficient object set Ó. Satisfying the goal minimally requires all ground objects the goal to be included in the sufficient object set Ô (else goal objects are unreachable). part of the sufficient set. Let be the set of all binary predicates which include any of these objects. And let g be the set of all objects contained in p. In general, this will be a superset of the objects started with. We iteratively repeat this process, each time adding the new objects in g to our sufficient set Ó.
addition, the robot itself must be
The process terminates either when either the set g has no new objects (indicating convergence), or until all the objects in the scene graph are visited at least once (indicating the input graph already defines minimal object set). We initialize the nodes of & with objects in Ó, and copy over all edges (u, v) G' for which both u, Ô. SCRUB terminates in time linear in the number of the predicates or nodes (whichever is larger).
Proposition 1. SCRUB is complete and results in minimal scene subgraph for all grounded plan- ning problems over the scenegraph domain. (Please refer to supp. material for proof)
Neurrangement L10)
Courter 18)
Lifted Hearrangement
Litted Conrler (5.5)
Conter
Treal
Courte
Lifie Os
Serdbaed
Plus Lonath
BFWS BFWS
FD
PLOI
SCRUB
SCRUB
FD- amo-tnnt SCRUB
PLOI+ SCRUB
Figure 5: SCRUB greatly prunes operators
Figure 4: Best performing planners with and without SCRUB.
and states of planning problems.
5.1 Impact of SCRUB on modern task planners
In this section, we investigate the effect that a 3DSG reduction scheme like SCRUB may have on the performance of modern task planners. We experiment with the four domains shown in Fig. 4 and evaluate the impact of scrub on planning performance and on domain structure.
SCRUB enables classical planners to obtain performance at least good as state-of-the- art planners. In Fig. 4, we see that SCRUB drastically reduces planning time for FF, and BFWS to few milliseconds Rearrangemen and upper-bounds times at 5 seconds on Courier(10, 10). We see this enables BFWS, FD, and FF to outperform PLOI (lower plan lengths for similar plan times). The grounded domains each have 182 test problems, and the lifted domains each have 70 test problems.
FD-1ama-fize
SCRUB greatly reduces the number of operators and states. To asses the impact of SCRUB, compute statistics (number of operators, number state variables) in Fig. 5. We see that SCRUB prunes more than two-thirds of the operators and state variables for grounded planning problems, and about a third in the case of lifted planning problems.
SCRUB enables optimal planners to run on lifted domains. Table reports results of running the satisficing and optimal variants of FD with and without SCRUB, on the Lifted Rear- rangement(5) domain. While FD (optimal) did not converge even with timeout of 24 hours, FD (optimal) scrub solved about 72% of the tasks under 30-second timeout, taking seconds per task on average.
Table Planner statistics evaluated over 70 test problems on Lifted Rear- rangement()).
Plaaner
Success
Length
Time
(satidicinn)
66.81
5.20
(satidicin))
73.09
1.61
FD (splimal)
FDD (optimall) Scrun
72.86
68.31
2.56
6 SEEK: A procedure for efficient learning-based planning
While SCRUB results in a 3DSG reduction that is guaranteed to find satisficing plan- if one exists-its conservative approach hurts performance challenging lifted planning problems as shown in Fig. 4. For such problems, beasinggbbseed graph-pruning strategies like PL,II [13] out- perform classical planners over SCRUBBED 3DSGs. However, as can be seen in Sec. 4.2, even PLOI [13] incurs a significant number of replanning iterations.
7

---

Table 4: SEEK significantly reduces the number of replanning sleps required by slate-of-the-eee learning- learningbbased based
planners, For each planner, we report average wall time (including translation time).
Planer
Vilad
91nd
9.1ked
Eima
HRila
01
61
618
711
313
20.00
10:10
01:88
1180
1101
7.0
135
14
on
8.0 3541
077 7016
035
135
We posit that several replanning iterations may be avoided by exploiting the 3DSG hierarchy. Prun- ing strategies like PLOI first score all objects, and retain a minimal set by thresholding. A simple threshold does little ensure that all retained objects are reachable from the root of the scene graph. To alleviate this issue, we propose SEEK: procedure that ensures we obtain connected graph, with the objective of reducing the number of replanning steps needed.
SEEK requires as input the 3DSG, the planning problem II, and an object scoring mechanism fa- This scoring mechanism typically graph neural network (akin [13]) that, given the current state, scores each object with an importance value in [0, 1]. We first run the scorer and only retain objects above a threshold score We follow an identical approach PLOI [13] and at each step geometrically decay the threshold by such that at iteration i, the threshold is t, = 74,-1, with tu. [0, 1). For each retained object o, we recursively traverse up the 3DSG, adding all ancestors of o to the sufficient object set. This procedure ensures that all objects are reachable from their respective room nodes. While SEEK, unlike SCRUB, is not guaranteed to be satisficing. it results in far fewer replanning steps without affecting computation time.
SEEK reduces replanning steps by order of mag- nitude. To assess the impact of the SEEK procedure on
Lifted Courter
planning performance,
evaluate performance with re-
spect to other learning-based planners on TASKOGRAPP APILY Table As baseline, we evaluate a random prun- ing strategy that uniformly randomly retains or prunes every object. Even for this naive strategy, SEEK offers significant performance improvement. We also evaluate PL./ [13] and our adaptation dubbed hierarchical, which trains multiple graph neural networks, one for each level of the 3DSG hierarchy. For each variant, SEEK offers a consistent performance improvement by decreasing the number of replanning steps required as seen Fig. SEEK is thus conceptually simple strategy for use with learning-bas based planners.
Rearrangement
Herrrchica
0
50
100
150
PLOI
Num Replonning Steps
Figure 6: SEEK reduces replanning steps by order of magnitude.
Lifted Courier (5. 5)
FLOI
Rearrangement
PLCK BCRUB
PLCk SEEK
0
100
200
300
SCRUB on grounded domains, SEEK on lifted do- mains: general, we note that SCRUB is more perfor- mant on grounded domains (due to minimality properties) and SEEK more performant on lifted domains (where SCRUB typically retains all instances of important object categories, but SEEK is more effective due to its opportunistic retention of instances (Fig. 7)).
Num Replonning Steps
Figure SEEK on lifted domains.
SCRUB on grounded domains,
Concluding remarks
Limitations. TASKOGR APHY currently supports only fraction of the diverse types of planning problems possible on 3DSGs. Geared towards identifying the most promising avenues in learning- based plamning, the first release of this benchmark focuses exclusively on offline task planning in fully observable and deterministic domains. Furthermore, low-level motion planning is excluded from our benchmark. Robots operating in the real world will need to reason under partial observ- ability, sensor noise, and resource constraints.
Outlook. TASKOGRAPHY, in conjunction with SCRUB and SEEK aid the robot learning community by (a) providing guidelines and implementations for practitioners choosing task planner, (b) serv- ing as a benchmark for upcoming learning-basse planners, and (c) guiding the design futuristic spatial representations for robotic task planning. We believe MASKOGRAPHY is first step towards addressing several of the grand challenges along the road to developing general planning capabilities for autonomous intelligent robots.
8

---

Acknowledgements
CA and KMJ would like thank Tom Silver and Rohan Chitnis for their help various stages of this project, including early-stage feedback, code release, and for proofreading an initial version of this manuscript. KMJ acknowedges generous fellowship support from NVIDIA. LP acknowledges grants from IVDO and from the CIFAR Canada Al chairs program. FS acknowledges funding support from NSERC and the NFRF exploration program. The authors collectively acknowledge support during various initial stages of the project by Florian Golemo.
References
[1] B. Kuipers. The spatial semantic hierarchy. Artificial intelligence, (111)))1 2000.
[2] E. Remolina and B. Kuipers. Towards general theory of topological maps. Artificial Intelli- gence, 152(1))77-104, 2004.
[3] C. Galindo, Saffiotti, Coradeschi, Buschka, J.-A. Madriigl and González. Multi-hierarchical semantic maps for mobile robotics. In 2005 IEEE/RSJ international con- ference on intelligent robots and systems, pages 2288-2283. IEEE, 2005.
[4] H. Zender, O. M. Mozos, P. Jensfelt, G.-J. Kruijff, and W. Burgard. Conceptual spatial repre- sentations for indoor mobile robots. Robotics and Autonomous Systems, 56(6):493-50 2008
[5] J.-R. Ruiz-Sarmiento, C. Galindo, and J. Gonzalez-Jimenez. Building multiversal semantic maps for mobile robot operation. Knowledge-Bacd Systems, 1 19:2577222.. 2017.
[6] A. Rosinol, A. Violette, M. Abate, N. Hughes, Y. Chang, J. Shi, A. Gupta, and L. Car- lone. Kimera: from slam to spatial perception with 3d dynamic scene graphs. arXiv preprint arXiv:2101.06894 2021.
[7] I. Armeni, Z.-Y. He, J. Gwak, A. R. Zamir, M. Fischer, J. Malik, and S. Savarese. 3d scene graph: A structure for unified semantics, 3d space, and camera. In Proceedings of Computer Vision and Puttern Recognition (CVPR), 2019.
[8] A. Rosinol, A. Gupta, M. Abate. J. Shi, and L. Carlone. 3d dynamic scene graphs: Actionable spatial perception with places, objects, and humans. In Robotics Science and Systems (R-SS), 2020.
[9] U.-H. Kim, J.- Park, T.-J. Song, and J.-H. Kim. 3-d scene graph: A sparse and semantic rep- resentation of physical environments for intelligent agents. IEEE transactions on cybernetics, 50(12):4921-4933 2019.
[10] Z. Ruvichandran. L. Peng, N. Hughes, D. Griffith, and L. Carlone. Hicrarchical represen- tations and explicit memory: Learning effective navigation policies on 3d scene graphs using graph neural networks. arXiv preprint arXiv:2 108.01 /76, 2021.
[11] A. Kurenkov, R. Martin-Martin, J. Ichnowski, K. Goldberg, and S. Savarese. Semantic and ge- ometric modeling with neural message passing in 3d scene graphs for hierarchical mechanical search. In IEEE International Conference on Robotics and Automation (ICRA), 2020.
[12] R. Talak, S. Hu, L. Peng, and L. Carlone. Neural trees for learning on graphs. arXiv preprint arXiv:2105.07266 2021.
[13] T. Silver, R. Chitnis, A. Curtis, J. Tenenbaum, T. Lozano-Perez, and L. P. Kaelbling. Planning with learned object importance in large problem instances using graph neural networks. AAAI International conference on Artificial Intelligence, 2020.
[14] H. Kautz and B. Selman. Pushing the envelope: Planning, propositional logic, and stochastic search. In Proceedings the National Conference on Artificial Intelligence, pages 1 1194 1201. Citeseer, 1996.
[15] H. Kautz. and B. Selman, Unifying sat-based and graph-based planning. IJCAI, volume 99, pages 318-325, 1999.

---

[16] H. Kautz, B. Selman, and J. Hoffmann. Satplan: Planning as satisfiability. In 5th international planning competition, volume 20, page 156, 2006.
[17] M. Katz, S. Sohrabi, H. Samulowitz, and S. Sievers. Delfi: Online planner selection for cost- optimal planning. IPC-9 planner abstracts, pages 57-64, 2018.
[18] C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in games, 4(1):1-43, 2012.
[19] B. Bonet and H. Geffner. Planning as heuristic search: New results. In European Conference on Planning, pages 360-372. Springer, 1999.
[20] H. Kaindl. Tree searching algorithms. Computers, Chess, and Cognition, pages 133-158, 1990.
[21] B. Bonet and H. Geffner. Planning as heuristic search. Artificial Intelligence, (12) 2001.
[22] J. Hoffmann and B. Nebel. The planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research, 14:253-302, 2001.
[23] M. Helmert. The fast downward planning system. Journal of Artificial Intelligence Research, 26:191-244 2006.
[24] M. Katz. Cerberus: novelty heuristic and enchanced mutex detection. IPC-9 planner abstracts, pages 47-51, 2018.
Red-black heuristic for planning tasks with conditional effects meets
[25] D. Gnad, A. Shleyfman, and J. Hoffmann. Decstar-star-topology decoupled search its best. IPC-9 planner abstracts, pages 42-46, 2018
[26) D. Long and M. Fox. The 3rd international planning competition: Results and analysis. Journal of Artificial Intelligence Research, 20:1-59, 2003.
[27] M. Vallati, L. Chrpa, M. Grzeš, T. L. McCluskey, M. Roberts, S. Sanner, et al. The 2014 international planning competition: Progress and trends. Ai Magazine, 36(3):90-98, 2015.
(28) R. Chitnis, T. Silver, B. Kim, L. P. Kaelbling, and T. Lozano-Perez. Camps: Learning context- specific abstractions for efficient planning in factored mdps. arXiv preprint 13X1v:2007.13202, 2020.
[29] C. Galindo, J.-A. Fernandez-Wadriial. and Gonzalez. Improving efficiency in mobile robot task planning through world abstraction. IEEF Transactions on Robotics (T-RO), 20(4):677- 690, 2004.
[30] L. E. Kavraki. P. Svestka, J.-C. Latombe, and M. H. Overmars. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE transactions on Robotics and Automation, 12(4):566-580 1996.
[31] C. Galindo, J.-A. Fernández-Madriggll González, and A. Saffiotti. Robot task planning using semantic maps. Robotics and Autonomous Systems, 56(11):955-966, 2008. ISSN 0921-8890.
[32] I.. P. Kaelbling and T. Lozano-Pérez. Integrated task and motion planning in belief space. The International Journal of Robotics Research, 12) 2013.
[33] B. Kim, Z. Wang, L. P. Kaelbling, and Lozano-Pénn Pérez. Learning to guide task and motion planning using score-space representation. The International Journal of Robotics Research, 38 77:77938112, 2019.
[34] C. R. Garrett, R. Chitnis, R. Holladay, B. Kim, T. Silver, L. P. Kaelbling, and T. Lozano-Pééne Integrated task and motion planning- Annual review of control, robotics, and autonomous systems, 4:265-293, 2021.
10

---

[35] L. P. Kaelbling and T. Lozano-Pérez. Hierarchical planning in the now. In Workshops at the Twenty-Fout Founth AAAI Conference on Artificial Intelligence, 2010.
[36] S. Stock, M. Mansouri, F. Pecora, and J. Hertzberg. Online task merging with a hierarchical hybrid task planner for mobile service robots. In 2015 TEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 6459-644 IEEE, 2015.
[37] J. C. González, J. C. Pulido, and F. Fernández. A three-layer planning architecture for the autonomous control of rehabilitation therapies based on social robots. Cognitive Systems Re- search, 43:232-249, 2017.
[38] M. Beetz, D. Jain, L. Mosenlechner, M. Tenorth, L. Kunze, N. Blodow, and D. Pangercic. Cognition-enabled autonomous robot control for the realization of home chore task intelli- gence. Proceedings of the IEEE, 100(8):2454-255
2012.
[39] G. Konidaris, S. Kuindersma, R. Grupen, and A. Barto. Robot learning from demonstration by constructing skill trees. The International Journal of Robotics Research, 3103:36,-337, 2012.
[40] P. Bercher, R. Alford, and D. Höller. A survey on hierarchical planning-one abstract idea, many concrete realizations. In IJCAI, pages 6267-6275, 2019.
[41] O. Rivlin, T. Hazan, and E. Karpas. Generalized planning with deep reinforcement learning. arXiv preprint arXiv:2005.02300 2020.
[42] R. Karia and S. Srivastava. Learning generalized relational heuristic networks for model- agnostic planning. arXiv preprint arXiv:2007.06702. 2020.
[43] D. Gnad, A. Torralba, M. Domínguez, C. Areces, and F. Bustos. Learning how to ground plan-partial grounding in classical planning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 7602-7609, 2019.
[44] J. Oh, S. Singh, H. Lee, and P. Kohli. Zero-shot task generalization with multi-task deep reinforcement learning. In International Conference on Machine Learning, pages 2661-2670. PMLR, 2017.
[45] Andreas, D. Klein, and Levine. Modular multitask reinforcement learning with policy sketches. In International Conference on Machine Learning, pages 166-175. PMLR, 2017.
[46] M. Denil, S. G. Colmenarejo, S. Cabi, D. Saxton, and N. de Freitas, Programmable agents. arXiv preprint arXiv; 1706.00066.3333 2017.
[47] S.-H. Sun, T.-L. Wu, and J. J. Lim. Program guided agent. In International Conference on Learning Representations, 2019.
[48] Y. Yang, J. P. Inala, O. Bastani, Y. Pu, A. Solar-Lezama, and M. Rinard. Program synthesis guided reinforcement learning. arXiv preprint a:Xiv:2102.11137, 2021.
[49] D. Xu, R. Martín-Martin, D.-A. Huang. Y. Zhu, S. Savarese, and L. Fei-Fei. Regression plan- ning networks. arXiv preprint arXiv: /9099 /te///99999990 /3072, 2019.
[50] A. Guez, T. Weber, I. Antonoglou, K. Simonyan, o. Vinyals, D. Wierstra, R. Munos, and D. Silver. Learning to search with metsnets. In International Conference on Machine Learning, pages 1822-1831. PMLR, 2018.
[51] P. Karkus, D. Hsu, and W. S. Lee. Qmdp-net: Deep learning for planning under partial observ- ability. arXiv preprint Xrviv: / 706.06692, 2017.
[52] P. Karkus, D. Hsu, and W. S. Lee. Integrating algorithmic planning and deep learning for partially observable navigation. arXiv preprint (00.:0800706696 2018.
[53] A. Guez, M. Mirza, K. Gregor, R. Kabra, S. Racanière, T. Weber, D. Raposo, A. Santoro, I. Orseau, T. Fecles, al. An investigation of model-free planning. International Confer- ence on Machine Learning, pages
PMLR, 2019.

---

[54] D.-. Huang. S. Nair, D. Xu, Y. Zhu, A. Garg, L. Fei-Fei, S. Savarese, and J. C. Niebles. Neural task graphs: Generalizing to unseen tasks from a single video demonstration. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8565-85777 2019.
[55] D. Xu, S. Nair, Y. Zhu, J. Gao, A. Garg, L. Fei-Fei, and S. Savarese. Neural task programming: I Learning to generalize across hierarchical tasks. 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 3795-3802. IEEE, 2018.
[56] Y. Shen, Chen, P.-.. Huang, Y. Guo, and Gao. M-walk: Learning to walk over graphs using monte carlo tree search. arXiv preprint arXiv:/802.0000 1002.04809904 2018.
[57] D. Fišer. Lifted fact-alternating mutex groups and pruned grounding of classical planning problems. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pages 9835-9842, 2020.
(58) D. Fišer, R. Horčík, and A. Komenda. Strengthening potential heuristics with mutexes and disambiguations. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 30, pages 124 133, 2020.
[59] N. Kumar, M. Fishman, N. Danas, M. L.. Littman, Tellex, and G. Konidaris. Task scoping: Building goal-specific abstractions for planning in complex domains. CoRR, abs/2010.08869, 2020. URL https: /tttpp:://arxee http///axvvvv/.////e//eeeeeeeev/ org/ aawaaaas/aaa 22010. 08869.
[60] P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanzhez-Gonzalez. V. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint
2018.
[61] T. Kipf, E. Fetaya, K.-C Wang. M. Welling, and R. Zemel. Neural relational inference for interacting systems. In International Conference on Machine Learning, pages 2688-228 2697. PMLR, 2018
[62] T. Kipf, E. van der Pol, and M. Welling. Contrastive learning of structured world models. arXiv preprint arXiv: 12247, 2019.
[63] F. Locatello, D. Weissenbom, T. Unterthiner, A. Mahendran, G. Heigold, J. Uszkoreit, A. Dosovitskiy, and T. Kipf. Object-centric learning with slot attention. arXiv preprint arXiv:2006. 15055, 2020.
[64] E. Kolve, R. Mottaghi, W. Han, E. VanderBilt, L. Weihs, A. Herrasti, D. Gordon, Y. Zhu, A. Gupta, and A. Farhadi. Ai2-thor: An interactive 3d environment for visual ai. arXiv preprint arXiv: 1712.05474 2017.
[65] M. Shridhar, J. Thomason, D. Gordon, Y. Bisk, W. Han, R. Mottaghi, L. Zettlemoyer, and D. Fox. Alfred: A benchmark for interpreting grounded instructions for everyday tasks. In Proceedings of Computer Vision and Pattern Recognition (CVPR). 2020.
[66] X. Puig. K. Ra, M. Boben, J. Li, T. Wang. S. Fidler, and A. Torralba. Virtualhome: Simulating household activities via programs. In Proceedings of the IEEE Conference Computer Vision and Puttern Recognition, pages 2494-8502, 2018
[67] M. Savva, A. Kadian, O. Maksymets, Y. Zhao, E. Wijmans, B. Jain, Straub, J. Liu, V. Koltun, Malik, et al. Habitat: platform for embodied research. Proceedings of Computer Vision and Puttern Recognition (CVPR), 2019.
[68] L. Weihs, M. Deitke, A. Kembhavi, and R. Mottaghi. Visual room rearrangement. arXiv preprint arXiv:2103. 16544, 2021.
[69] C. Gan, S. Zhou, J. Schwartz, S. Alter, A. Bhandwaldar, D. Gutfreund, D. L. Yamins, J. J. DiCarlo, J. McDermott, A. Torralba, et al. The threedworld transport challenge: A visu- ally guided mask-and-motion planning benchmark for physically realistic embodied ai. arXiv preprint arXiv: 14025, 2021.
12

---

[70] B. Shen, F. Xia, C. Li, R.
L. Fan, G. Wang, S. Buch, C. D' D'Arpino, S. Sri- vastava, L. Tchapmi. et al. igibson, simulation environment for interactive tasks in large realisticscenes. IEEE International Conference on Robotics and Automation (ICRA), 2020.
[71] F. Xiang, Y. Qin, K. Mo, Y. Xia, H. Zhu, F. Liu, M. Liu, H. Jiang, Y. Yuan, H. Wang, et al. Sapien: simulated part-based interactive environment. In Proceedings of Computer Vision and Pattern Recognition (CVPR), 2020.
[72] Y.-q- Jiang, S.-q. Zhang, P. Khandelwal, and P. Stone. Task planning in robotics: empirical comparison of pddl- and asp-based systems. Frontiers of Information Technology & Electronic Engineering, 20(3):363-375) 2019.
[73] M. Shridhar, X. Yuan, M.-A. Côté, Y. Bisk, Trischler, and M. Hausknecht. Alfworld: Align- ing text and embodied environments for interactive learning. arXiv preprint arXiv:2010.03768, 2020.
[74] C. Gan, Schwartz, Alter, M. Schrimpf, J. Traer, De Freitas, Kubilius, A. Bhandwal- dar, N. Haber, M. Sano, et al. Threedworid: A platform for interactive multi-modal physical simulation. arXiv preprint arXiv:2007.0495 2020.
[75] Xia, A. R. Zamir, Z. He, A. Sax, J. Malik, and Savarese. Gibson env: Real-world per- ception for embodied agents. In Proceedings of Computer Vision and Pattern Recognition (CVPR), 2018.
[76] N. Lipovetzky and H. Geffner. Best-first width search: Exploration and exploitation classical planning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
[77] D. Batra, A. X. Chang. S. Chernova, A. Davison, Deng, Koltun, S. Levine, J. Malik, I. Mordatch, R. Mottaghi, et al. Rearrangement: A challenge for embodied ai. arXiv preprint arXiv:201 1.01975, 2020.
[78] Planutils. https: 2021.
Accessed: June 18
[79] D. McDermott, M. Ghallab, A. Howe, C. Knoblock, A. Ram, M. Veloso, D. Weld, and D. Wilkins. Padl-the planning domain definition language. 1998.
[80] T. Silver and R. Chitnis. Pddlgym: Gym environments from pddl problems. arXiv preprint arXiv:2002.06432. 2020.
13


Reviews:
[{"review_id": "ko0ecDc4q73", "reviewer": "Reviewer_TxRd", "summary": "\nThis paper presents a large-scale robotic planning benchmark over 3DSGs that is designed to evaluate symbolic reasoning and planning over 3D scene graphs (3DSGs). The proposed benchmark consists of 20 task planning domains, including object rearrangement and courier, totaling 3734 tasks. This work benchmarks the performance of optimal planners (e.g. Fast Downward, Satplan, Delfi, etc.), satisficing planners (e.g. Fast Forward, DecStar-satisficing, Cerberus, etc.), and learning-based planners (e.g. relational policy learning, planning with learned object importance). Given the findings of benchmarking existing planning methods, two techniques have been proposed to (1) prunes a 3DSG to produce a sparsified 3DSG to improve the efficiency of classical planners and (2) ensures the reachability of all objects to reduce the number of replanning steps for learning-based planners. The experiments show the two proposed techniques yield improve performance. I believe this work presents a promising benchmark together with two effective techniques. I am leaning toward acceptance yet still have some concerns regarding how the benchmark can scale up to handle partially observable environments with stochasticity and incorporate low-level interactions, the access to the benchmark, the evaluation of the proposed techniques, and the discussion on the related work.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n## Paper strengths and contributions\n**Motivation**\n- The motivation for modeling real-world environments as 3D scene graphs is convincing.\n- Utilizing 3D scene graphs modeling real-world environments to evaluate planning methods is intuitive and realistic.\n- To this end, constructing a large-scale planning benchmark over 3D scene graphs is promising.\n\n**Technical contributions**\nTo alleviate the issues of classical planners and learning-based planners, two techniques are proposed in this work.\n- The proposed technique SCRUB prunes a 3DSG by removing vertices and edges extraneous to the task to produce a sparsified 3DSG, greatly reducing the planning time required by classical planners (e.g.  FD and FF) and enabling optimal planners to run on lifted domains.\n- The proposed technique SEEK ensures that all objects are reachable from their respective room nodes to reduce the number of required replanning steps.\n\n**Clarity**\nThe overall writing is very clear. The presentation is well-organized.\n\n**Related work**\nThe authors did a good job explaining how this work is related to and different from other relevant prior works. \n\n**Experimental results**\n- The presentation of the experimental results is clear.\n- The findings of the experimental results are well-explained, which leads to the intuition of the two proposed techniques (i.e. SCRUB and SEEK).\n\n## Paper weaknesses and questions\n\n**Fully observable and deterministic domains**\nThe current benchmark only supports the environments that are fully observable and deterministic, which is rather unrealistic to many robotics domains that require planning. I believe it would be easy to incorporate environments with stochasticity. I would like to hear the authors' opinions on how this benchmark can scale up to deal with partially observable environments.\n\n**Low-level interactions**\nGiven that this benchmark does not support low-level interactions with environments, I would hardly call it a robotics environment. It seems to me that it is more suitable to call it a planning benchmark. At this point, I believe this paper oversells a little bit by saying this is a robotics benchmark.\n\n**SCRUB and SEEK on other planning benchmarks**\nWhile the effectiveness of SCRUB and SEEK is well-demonstrated on this benchmark, it would be even more convincing to also evaluate them on other commonly used planning benchmarks.\n\n**Related work**\nWhile the related work section sufficiently covers most relevant prior works, I believe it would make the discussion more comprehensive by including some works that construct and execute programs as symbolic plans, including\n- Modular multitask reinforcement learning with policy sketches\n- Zero-Shot Task Generalization with Multi-Task Deep Reinforcement Learning\n- Programmable agents\n- Program Guided Agent \n- Program Synthesis Guided Reinforcement Learning\n\n**Other domains**\nWhile it states that 20 domains are included in this benchmark, only 2 domains are discussed in the paper. I did not find descriptions of other domains in the Supplementary material. Am I missing anything?\n\n**The access to the API and data**\nWhile I do recognize the difficulty to \"submit\" the benchmark, I still find it difficult to evaluate how good this is without actually playing with it. It would be better if more examples such as videos are shown to demonstrates how the benchmark can be used.", "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": "\nI believe this work presents a promising benchmark together with two effective techniques. I am leaning toward acceptance yet still have some concerns regarding how the benchmark can scale up to handle partially observable environments with stochasticity and incorporate low-level interactions, the access to the benchmark, the evaluation of the proposed techniques, and the discussion on the related work.", "technical_quality": "Very Good:  Convincing.", "clarity_of_presentation": "Excellent: Enjoyable to read.", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "3: The work is incremental and unlikely to have much impact, even though it may be technically correct and well executed.", "issues": "\nDescribed in the strengths and weaknesses section.", "reviewer_expertise": "Good: General knowledge of the area"}, "extra_text": {}}, {"review_id": "d4hHe0wwebu", "reviewer": "Reviewer_aMNE", "summary": "This paper introduces a benchmark over 3D scene-graphs (3DSGs) for large-scale robotic task planning problems, along with two methods to improve existing planning and/or learning algorithms. \nThe proposed benchmark builds on top of an existing dataset (Gibson) and a corresponding 3DGS with a focus only on symbolic reasoning, discarding the motion planning and manipulation aspects.\nRunning existing algorithms on this benchmark provides insights on how they can be improved, for which two methods are proposed: sparsifying the graph by recursively pruning the original full-scale one (strategy called SCRUB), and exploiting the hierarchical graph structure to attend only on a subset of the objects present in the environment given a (importance) scoring function (strategy called SEEK).\nSCRUB is shown to improve performance of planning algorithms on grounded domains, whereas SEEK provides a better performance increase on lifted domains.   ", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- As the main strength of this work, well-structured and explained benchmarks are always appreciated as they tend to initiate faster progress in a particular domain.\n- Even though the proposed benchmark, as it's presented, would mainly be useful for the planning community, if it's indeed tightly coupled (or easy to integrate) with the original benchmark environment (gibson) that it builds on, a broader robotics community would also be able to make use of it.\n- The detailed analysis of different planning algorithms on a multitude of domains provides insights on the relative strengths and weaknesses of those methods, along with promising improvement directions.   \n\nweaknesses:\n- the paper (including the supp. mat.) does not provide sufficient information on the tasks. I know it relies on a prior dataset, but it'd help if a subset of the tasks are explained at least in the supp. mat. to make the paper more self-contained. (The website also fails to provide further info on that point)\n- Exclusion of motion and/or manipulation planning aspects diminishes relevance / usefulness of the benchmark for the robotics community. This might be alleviated if the paper explains / discusses how such low-level planning can be interfaced.\n- There, usually, is a strong dependency between the motion / manipulation plans and high-level decisions, e.g., due to the executability / feasibility of a low level plan, which in turn might require re-planning, or backtracking. Also, some sequential manipulation behaviors might inform high-level decisions about their (in)feasibility. None of those are captured by a pure high-level planning-based benchmark. So, it's not clear how this benchmark might be utilized by a broader robotics research community.", "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": "Benchmarks play an important role in research. Traditionally, robotics field did not have many such benchmarks or datasets compared to machine learning domain. Recently, there has been a trend to introduce them for the robotics research, and this paper (and thus the introduced environments/dataset) could be a good addition. However, since motion and manipulation planning aspects are excluded, it only allows testing of high-level decision planning algorithms. Decision-making is surely a critical component of robotics research, however, interaction with the environment, thus the motion and manipulation planning and execution are the distinct aspect compared to classical AI planning. I'm not totally convinced on its usefulness in that regard, as the paper lacks proper explanations and discussion on such interfaces.\nThe introduced SCRUB and SEEK algorithms provide improvements over existing methods but they are rather small extensions.", "technical_quality": "Very Good:  Convincing.", "clarity_of_presentation": "Good: Minor revision needed to improve organization or clarity.", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "2: Unsure, difficult to assess.", "reviewer_expertise": "Very good: Comprehensive knowledge of the area"}, "extra_text": {"issues": "Please also see (Strengths & Weaknesses). \n\nsmall issues:\n- line 39: '... vast majority [of] the ...'\n- line 202: standard deviations (detailed results) are not included in the supp. material as reported in the main text.\n- line 267: missing parenthesis \n- line 283: initialze\n- line 294-296: contrary to the claim here, SCRUB does not improve BFWS on Courier(10,10) task according to Fig.4 \n- line 328: 'While SEEK, unlike SCRUB[,] is not ...'"}}, {"review_id": "Ql7xvgSJJOi", "reviewer": "Reviewer_TvP2", "summary": "The work introduces a benchmark for 3d scene graphs while focusing on the complexities involved in symbolic planning. The authors further introduce two methods to alleviate common problems with planning over such 3dSGs. ", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The fact that there isn't a substantial benchmark on large scale complex scene graphs is a large supporting point for this work\n- I like the summarizing analyses; e.g. \"Interestingly, larger scenes do not appear to directly correlate with task complexity, as the performance metrics remains largely consistent between the tiny and medium splits of the same domain (Table. 2).\"", "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": "Overall I think the proposed work introduces an extremely useful benchmark for the community and competitive baseline augmentations to existing methods; i.e. the proposed algorithms simply take advantage of observations of deficiencies of existing works and these are well documented.", "technical_quality": "Very Good:  Convincing.", "clarity_of_presentation": "Very Good:  Well organized and clear.", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "4: The work contains interesting new ideas that will potentially have major impact in robotics or machine learning.", "reviewer_expertise": "Good: General knowledge of the area"}, "extra_text": {"issues": "line 99 \"lifted actions\" could the authors formally define what is a \"lifted\" action?\n\nI do not have any major issues with the paper since the problem domains not included in the benchmark are adressed in the Limitations section and these are totally reasonable."}}, {"review_id": "JqqmknawbO7", "reviewer": "Reviewer_PJVU", "summary": "3D scene graph is an unified and informative representation of the scene. Many existing works utilize 3D scene graph to solve tasks that require long horizonal planning and reasoning. While previous works directly take the complete scene graph as input, this work proposes a planner-agnostic algorithm to prunes the scene graph in linear time based on the goal of the task, and further propose a procedure for learning based planner to ensure the connectivity of the pruned subgraph.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.\tThe idea of pruning the large 3D scene graph and utilize the subgraph to solve tasks is convincing.\n2.\tThe designed pruning algorithm SCRUB which builds the subgraph iteratively is effective since it could finish in linear time.\n3.\tSuccessive experiments have been implemented to verify the effectiveness of the proposed algorithm.\nWeaknesses:\n1.\tThe proposed pruning algorithm SCRUB is lack of innovation. I think it is similar with BFS and just directly merge all nodes and edges between robot and goal objects into the subgraph. In complex scenes and tasks, the algorithm might fail to prune enough nodes and edges to improve the efficiency.\n2.\tThis workload of this paper with respect to robot learning is not sufficient.  It could introduce learning methods at the pruning algorithm or design a learning-based planner that fits the pruning algorithm.\n3.\tIn real world application, the 3D scene graph always have some incorrect nodes and edges. Since the pruning algorithm heavily depends on the accuracy of the scene graph, I wonder whether the planner could work well with the pruned graph in physical world. While this work does not verify the robustness of the algorithm on the imperfect 3D scene graph. \n", "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": "This work makes contribution to the application of 3D scene graph. Pruning 3D scene graph to improve the performance and efficiency of the planner is a novel and worthy of in-depth study direction. Meanwhile, this work provides a large scale benchmark to support further research and evaluation. The successive experiments illustrate that the pruning algorithm could work with both non-learning and learning-based planners well. However, the proposed algorithm has its limitation in terms of generalization and robustness. ", "technical_quality": "Good: Generally convincing, but some additional experiments or analyses needed.", "clarity_of_presentation": "Very Good:  Well organized and clear.", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "3: The work is incremental and unlikely to have much impact, even though it may be technically correct and well executed.", "issues": "Figure 4 in the paper is ambiguous since the ellipses of different methods are overlapped with each other, it should be re-drawn.", "reviewer_expertise": "Very good: Comprehensive knowledge of the area"}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, a large-scale robotic task planning benchmark over scene graphs is established. A task-conditioned 3DSG parsification method called SCRUB, and SEEK, a procedure enabling learning-based planners to exploit 3DSG structure is proposed. All reviewers recognized the importance of the benchmark to the community. While there are some concerns about the exclusion of low-level motions, which are also considered important in robotic planning tasks. And some more detailed introduction of other tasks is lacking. 

In the rebuttal session, the authors have responded to the reviewers' concerns and more details are provided. All reviewers recognize the value of the benchmark to the robot learning community, and have reached a consensus of accepting this paper. 

Decision: Accept (Poster)