CoChat
Sign Up
PreprintCited by 21AI-based Problem Solving and PlanningRobot Manipulation and LearningRobotic Path Planning Algorithms

The DOI matches its DataCite record; 1 of the 1 references it cites were found in a registry or an index.

TASKOGRAPHY: Evaluating robot task planning over large 3D scene graphs

Open access
Agia, Christopher, Jatavallabhula, Krishna Murthy, Khodeir, Mohamed, Miksik, Ondrej, Vineet, Vibhav, Mukadam, Mustafa, Paull, Liam, Shkurti, Florian·2022·arXiv
DOI 10.48550/arxiv.2207.05006arXiv 2207.05006
Open this paper in CoChat — free accountOpen PDF

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 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.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2207.05006

Cites

1 of 1 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Scene-graph style hierarchical graphs have been shown to be effective for planning problems.

    “Scene-graph style hierarchical graphs have been shown to be effective for planning problems Gu et al. (2024); Agia et al. (2022); Rana et al. (2023).”

    From PARTNR: A Benchmark for Planning and Reasoning in Embodied Multi-agent Tasks (2024) · cites this paper as Agia et al. (2022)

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Flagged first, then by citations

Research works printed but not linked: 73

  1. B. Kuipers. The spatial semantic hierarchy. Artificial intelligence, 119(1-2):191-233, 2000.
  2. E. Remolina and B. Kuipers. Towards a general theory of topological maps. Artificial Intelli- gence, 152(1):47-104, 2004.
  3. C. Galindo, A. Saffiotti, S. Coradeschi, P. Buschka, J.-A. Fernandez-Madrigal, and J. González. Multi-hierarchical semantic maps for mobile robotics. In 2005 IEEE/RSJ international con- ference on intelligent robots and systems, pages 2278-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-502, 2008.
  5. 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. · arXiv
  6. 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 Pattern Recognition (CVPR), 2019.
  7. U.-H. Kim, J.-M. 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.
  8. Z. Ravichandran, L. Peng, N. Hughes, J. D. Griffith, and L. Carlone. Hierarchical represen- tations and explicit memory: Learning effective navigation policies on 3d scene graphs using graph neural networks. arXiv preprint arXiv:2108.01176, 2021. · arXiv
  9. A. Kurenkov, R. Martín-Martín, 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.
  10. R. Talak, S. Hu, L. Peng, and L. Carlone. Neural trees for learning on graphs. arXiv preprint arXiv:2105.07264, 2021. · arXiv
  11. 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.
  12. H. Kautz and B. Selman. Pushing the envelope: Planning, propositional logic, and stochastic search. In Proceedings of the National Conference on Artificial Intelligence, pages 1194-1201. Citeseer, 1996.
  13. H. Kautz and B. Selman. Unifying sat-based and graph-based planning. In IJCAI, volume 99, pages 318-325, 1999.
  14. 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.
  15. C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. 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 AI in games, 4(1):1-43, 2012.
  16. B. Bonet and H. Geffner. Planning as heuristic search: New results. In European Conference on Planning, pages 360-372. Springer, 1999.
  17. H. Kaindl. Tree searching algorithms. Computers, Chess, and Cognition, pages 133-158, 1990.
  18. B. Bonet and H. Geffner. Planning as heuristic search. Artificial Intelligence, 129(1-2):5-33, 2001.
  19. J. Hoffmann and B. Nebel. The ff planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research, 14:253-302, 2001.
  20. M. Helmert. The fast downward planning system. Journal of Artificial Intelligence Research, 26:191-246, 2006.
  21. M. Katz. Cerberus: Red-black heuristic for planning tasks with conditional effects meets novelty heuristic and enchanced mutex detection. IPC-9 planner abstracts, pages 47-51, 2018.
  22. D. Gnad, A. Shleyfman, and J. Hoffmann. Decstar-star-topology decoupled search at its best. IPC-9 planner abstracts, pages 42-46, 2018.
  23. D. Long and M. Fox. The 3rd international planning competition: Results and analysis. Journal of Artificial Intelligence Research, 20:1-59, 2003.
  24. 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.
  25. 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 arXiv:2007.13202, 2020. · arXiv
  26. C. Galindo, J.-A. Fernandez-Madrigal, and J. Gonzalez. Improving efficiency in mobile robot task planning through world abstraction. IEEE Transactions on Robotics (T-RO), 20(4):677- 690, 2004.
  27. 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.
  28. C. Galindo, J.-A. Fernández-Madrigal, J. González, and A. Saffiotti. Robot task planning using semantic maps. Robotics and Autonomous Systems, 56(11):955-966, 2008. ISSN 0921-8890. doi:https://doi.org/10.1016/j.robot.2008.08.007. · DOI
  29. L. P. Kaelbling and T. Lozano-Pérez. Integrated task and motion planning in belief space. The International Journal of Robotics Research, 32(9-10):1194-1227, 2013.
  30. B. Kim, Z. Wang, L. P. Kaelbling, and T. Lozano-Pérez. Learning to guide task and motion planning using score-space representation. The International Journal of Robotics Research, 38 (7):793-812, 2019.
  31. C. R. Garrett, R. Chitnis, R. Holladay, B. Kim, T. Silver, L. P. Kaelbling, and T. Lozano-Pérez. Integrated task and motion planning. Annual review of control, robotics, and autonomous systems, 4:265-293, 2021.
  32. L. P. Kaelbling and T. Lozano-Pérez. Hierarchical planning in the now. In Workshops at the Twenty-Fourth AAAI Conference on Artificial Intelligence, 2010.
  33. S. Stock, M. Mansouri, F. Pecora, and J. Hertzberg. Online task merging with a hierarchical hybrid task planner for mobile service robots. In 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 6459-6464. IEEE, 2015.
  34. 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-2471, 2012.
  35. G. Konidaris, S. Kuindersma, R. Grupen, and A. Barto. Robot learning from demonstration by constructing skill trees. The International Journal of Robotics Research, 31(3):360-375, 2012.
  36. 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.
  37. O. Rivlin, T. Hazan, and E. Karpas. Generalized planning with deep reinforcement learning. arXiv preprint arXiv:2005.02305, 2020. · arXiv
  38. R. Karia and S. Srivastava. Learning generalized relational heuristic networks for model- agnostic planning. arXiv preprint arXiv:2007.06702, 2020. · arXiv
  39. D. Gnad, A. Torralba, M. Domínguez, C. Areces, and F. Bustos. Learning how to ground a plan-partial grounding in classical planning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 7602-7609, 2019.
  40. 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.
  41. J. Andreas, D. Klein, and S. Levine. Modular multitask reinforcement learning with policy sketches. In International Conference on Machine Learning, pages 166-175. PMLR, 2017.
  42. M. Denil, S. G. Colmenarejo, S. Cabi, D. Saxton, and N. de Freitas. Programmable agents. arXiv preprint arXiv:1706.06383, 2017. · arXiv
  43. S.-H. Sun, T.-L. Wu, and J. J. Lim. Program guided agent. In International Conference on Learning Representations, 2019.
  44. Y. Yang, J. P. Inala, O. Bastani, Y. Pu, A. Solar-Lezama, and M. Rinard. Program synthesis guided reinforcement learning. arXiv preprint arXiv:2102.11137, 2021. · arXiv
  45. D. Xu, R. Martín-Martín, D.-A. Huang, Y. Zhu, S. Savarese, and L. Fei-Fei. Regression plan- ning networks. arXiv preprint arXiv:1909.13072, 2019. · arXiv
  46. A. Guez, T. Weber, I. Antonoglou, K. Simonyan, O. Vinyals, D. Wierstra, R. Munos, and D. Silver. Learning to search with mctsnets. In International Conference on Machine Learning, pages 1822-1831. PMLR, 2018.
  47. P. Karkus, D. Hsu, and W. S. Lee. Qmdp-net: Deep learning for planning under partial observ- ability. arXiv preprint arXiv:1703.06692, 2017. · arXiv
  48. P. Karkus, D. Hsu, and W. S. Lee. Integrating algorithmic planning and deep learning for partially observable navigation. arXiv preprint arXiv:1807.06696, 2018. · arXiv
  49. A. Guez, M. Mirza, K. Gregor, R. Kabra, S. Racanière, T. Weber, D. Raposo, A. Santoro, L. Orseau, T. Eccles, et al. An investigation of model-free planning. In International Confer- ence on Machine Learning, pages 2464-2473. PMLR, 2019.
  50. D.-A. 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-8574, 2019.
  51. D. Xu, S. Nair, Y. Zhu, J. Gao, A. Garg, L. Fei-Fei, and S. Savarese. Neural task programming: Learning to generalize across hierarchical tasks. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 3795-3802. IEEE, 2018.
  52. Y. Shen, J. Chen, P.-S. Huang, Y. Guo, and J. Gao. M-walk: Learning to walk over graphs using monte carlo tree search. arXiv preprint arXiv:1802.04394, 2018. · arXiv
  53. D. Fišer. Lifted fact-alternating mutex groups and pruned grounding of classical planning problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 9835-9842, 2020.
  54. 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.
  55. N. Kumar, M. Fishman, N. Danas, M. L. Littman, S. Tellex, and G. Konidaris. Task scoping: Building goal-specific abstractions for planning in complex domains. CoRR, abs/2010.08869, 2020. URL https://arxiv.org/abs/2010.08869. · arXiv
  56. P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzalez, V. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01261, 2018. · arXiv
  57. 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-2697. PMLR, 2018.
  58. T. Kipf, E. van der Pol, and M. Welling. Contrastive learning of structured world models. arXiv preprint arXiv:1911.12247, 2019. · arXiv
  59. F. Locatello, D. Weissenborn, 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. · arXiv
  60. 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. · arXiv
  61. 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.
  62. 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 on Computer Vision and Pattern Recognition, pages 8494-8502, 2018.
  63. M. Savva, A. Kadian, O. Maksymets, Y. Zhao, E. Wijmans, B. Jain, J. Straub, J. Liu, V. Koltun, J. Malik, et al. Habitat: A platform for embodied ai research. In Proceedings of Computer Vision and Pattern Recognition (CVPR), 2019.
  64. L. Weihs, M. Deitke, A. Kembhavi, and R. Mottaghi. Visual room rearrangement. arXiv preprint arXiv:2103.16544, 2021. · arXiv
  65. 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 task-and-motion planning benchmark for physically realistic embodied ai. arXiv preprint arXiv:2103.14025, 2021. · arXiv
  66. B. Shen, F. Xia, C. Li, R. Martín-Martín, L. Fan, G. Wang, S. Buch, C. D'Arpino, S. Sri- vastava, L. P. Tchapmi, et al. igibson, a simulation environment for interactive tasks in large realisticscenes. IEEE International Conference on Robotics and Automation (ICRA), 2020.
  67. Y.-q. Jiang, S.-q. Zhang, P. Khandelwal, and P. Stone. Task planning in robotics: an empirical comparison of pddl-and asp-based systems. Frontiers of Information Technology & Electronic Engineering, 20(3):363-373, 2019.
  68. M. Shridhar, X. Yuan, M.-A. Côté, Y. Bisk, A. Trischler, and M. Hausknecht. Alfworld: Align- ing text and embodied environments for interactive learning. arXiv preprint arXiv:2010.03768, 2020. · arXiv
  69. C. Gan, J. Schwartz, S. Alter, M. Schrimpf, J. Traer, J. De Freitas, J. Kubilius, A. Bhandwal- dar, N. Haber, M. Sano, et al. Threedworld: A platform for interactive multi-modal physical simulation. arXiv preprint arXiv:2007.04954, 2020. · arXiv
  70. F. Xia, A. R. Zamir, Z. He, A. Sax, J. Malik, and S. Savarese. Gibson env: Real-world per- ception for embodied agents. In Proceedings of Computer Vision and Pattern Recognition (CVPR), 2018.
  71. N. Lipovetzky and H. Geffner. Best-first width search: Exploration and exploitation in classical planning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
  72. D. Batra, A. X. Chang, S. Chernova, A. J. Davison, J. Deng, V. Koltun, S. Levine, J. Malik, I. Mordatch, R. Mottaghi, et al. Rearrangement: A challenge for embodied ai. arXiv preprint arXiv:2011.01975, 2020. · arXiv
  73. T. Silver and R. Chitnis. Pddlgym: Gym environments from pddl problems. arXiv preprint arXiv:2002.06432, 2020. · arXiv

Cited by

Sorted by citations

Metadata

Authors
Agia, C., Jatavallabhula, K. M., Khodeir, M., Miksik, O., Vineet, V., Mukadam, M., Paull, L., & Shkurti, F.
Affiliations
  • University of Toronto (CA)
  • Microsoft (United States) (US)
  • Meta (United States) (US)
  • Mila - Quebec Artificial Intelligence Institute (CA)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2022
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2207.05006
arXiv
2207.05006
OpenAlex
W3214297339
Cited by
21
References
1
Citations by year
2026: 2 · 2025: 2 · 2024: 8 · 2023: 7 · 2022: 1
Type
posted content
Language
en
Open access
Licence
creativecommons.org/licenses/by/4.0/legalcode
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University) (cc-by)
  • Conference on Robot Learning
Funders
  • Nvidia
  • Canadian Institute for Advanced Research
  • Institut de Valorisation des Données
  • Natural Sciences and Engineering Research Council of Canada
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
  • Physical Sciences › Engineering › Control and Systems Engineering › Robot Manipulation and Learning
  • Physical Sciences › Engineering › Control and Systems Engineering › Robotic Path Planning Algorithms
Keywords
robot task planning, 3D scene graphs, symbolic planning, planning benchmarks, graph sparsification, real-time planning, scrub, SEEK

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review