# A Framework for Task and Motion Planning based on Expanding AND/OR Graphs

arXiv: https://arxiv.org/abs/2509.00317 · HTML: https://mlsanity.com/paper/2509.00317/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 24 references that are in the map.
- First posted on arXiv 30 Aug 2025.

## Builds on (most cited first, 9 of 9)

- [Online Replanning in Belief Space for Partially Observable Task and Motion Problems](https://mlsanity.com/paper/1911.04577/) (2019)
- [FFRob: Leveraging Symbolic Planning for Efficient Task and Motion Planning](https://mlsanity.com/paper/1608.01335/) (2016)
- [Towards Multi-Robot Task-Motion Planning for Navigation in Belief Space](https://mlsanity.com/paper/2010.00780/) (2020)
- [Sampling-Based Methods for Factored Task and Motion Planning](https://mlsanity.com/paper/1801.00680/) (2018)
- [MPTP: Motion-Planning-aware Task Planning for Navigation in Belief Space](https://mlsanity.com/paper/2104.04696/) (2021)
- [Task Allocation for Multi-Robot Task and Motion Planning: a case for Object Picking in Cluttered Workspaces](https://mlsanity.com/paper/2110.04089/) (2021)
- [Computational Tradeoff in Minimum Obstacle Displacement Planning for Robot Navigation](https://mlsanity.com/paper/2302.07114/) (2023)
- [Safe motion planning with environment uncertainty](https://mlsanity.com/paper/2305.06004/) (2023)
- [A Task and Motion Planning Framework Using Iteratively Deepened AND/OR Graph Networks](https://mlsanity.com/paper/2503.07700/) (2025)

## Abstract (arXiv)

Robot autonomy in space environments presents unique challenges, including high perception and motion uncertainty, strict kinematic constraints, and limited opportunities for human intervention. Therefore, Task and Motion Planning (TMP) may be critical for autonomous servicing, surface operations, or even in-orbit missions, just to name a few, as it models tasks as discrete action sequencing integrated with continuous motion feasibility assessments. In this paper, we introduce a TMP framework based on expanding AND/OR graphs, referred to as TMP-EAOG, and demonstrate its adaptability to different scenarios. TMP-EAOG encodes task-level abstractions within an AND/OR graph, which expands iteratively as the plan is executed, and performs in-the-loop motion planning assessments to ascertain their feasibility. As a consequence, TMP-EAOG is characterised by the desirable properties of (i) robustness to a certain degree of uncertainty, because AND/OR graph expansion can accommodate for unpredictable information about the robot environment, (ii) controlled autonomy, since an AND/OR graph can be validated by human experts, and (iii) bounded flexibility, in that unexpected events, including the assessment of unfeasible motions, can lead to different courses of action as alternative paths in the AND/OR graph. We evaluate TMP-EAOG on two benchmark domains. We use a simulated mobile manipulator as a proxy for space-grade autonomous robots. Our evaluation shows that TMP-EAOG can deal with a wide range of challenges in the benchmarks.