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

Fulvio Mastrogiovanni, Antony Thomas · 2025

Read A Framework for Task and Motion Planning based on Expanding AND/OR Graphs by Fulvio Mastrogiovanni, Antony Thomas (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-00317.txt.

Introduction

Fulvio Mastrogiovanni and Antony Thomas present a task and motion planning framework for space robots in 2025 based on expanding AND/OR graphs. Space work brings high perception and motion uncertainty, strict kinematic limits, and few chances for human help. Task and motion planning joins discrete action sequencing with checks that each motion is actually feasible.

Their framework, TMP-EAOG, encodes task-level abstractions in an AND/OR graph that expands step by step as the plan runs. Motion planning checks run in the loop to test feasibility of each branch. The design gains robustness to a degree of uncertainty from that feedback. Tests show the frame adapts to distinct scenarios, from servicing to surface operations.

Catalog record

CREATORFulvio Mastrogiovanni, Antony Thomas
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-00317

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Framework for Task and Motion Planning based on Expanding AND/OR Graphs Fulvio Mastrogiovanni, Antony Thomas Abstract 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. keywords Task and Motion Planning; AND/OR Graph 1 Introduction Robot autonomy is of the utmost importance for the next generation of space missions, from satellite assembly and servicing to planetary surface exploration and in-situ resource utilisation . It is foreseen that robots will operate with minimal human oversight, often under communication delays, constrained computational resources, limited sensing and unexpected changes in the environment. Achieving mission goals will most likely demand not a single action, but the careful sequencing of multiple, interdependent operations, each to be validated for geometric feasibility and physical safety. For instance, grasping an instrument needed for a scientific experiment may require planning a collision-free trajectory in cluttered storage. If the planned trajectory were obstructed, the robot would first identify the items originating the hindrance, and if possible rearrange surrounding, movable items in order to reach the instrument. This tight coupling between symbolic decision-making and continuous geometric reasoning is why Task and Motion Planning (TMP) has received much attention in the past few years, and could be a critical capability in space robotics. TMP integrates task and motion planning in a unified framework, and has been studied extensively in manipulation kaelbling2013IJRR ; srivastava2014ICRA ; dantam2016RSS , object rearrangement krontiris2014ICHR ; krontiris2015RSS ; karami2021AIIA , navigation lo2018AAMAS ; thomas2021RAS , and mobile manipulation garrett2018IJRR ; garrett2018IJRR1 . However, we argue that applications in space robotics amplify the challenges underlying these robot tasks. TMP approaches must be robust to uncertainty, generalisable across diverse scenarios, and interpretable by human supervisors in safety-critical operations. While AND/OR graphs have been used to encode complex tasks by representing intermediate states as constraints, and (sequences of) actions as (hyper-)arcs among states, expanding AND/OR graphs allow for recursively applying the graph structure to tasks with non-deterministic (but foreseen) outcomes. In this paper, we introduce a TMP framework based on expanding AND/OR graphs, referred to as TMP-EAOG , which is designed to integrate symbolic and geometric reasoning while maintaining properties desirable for (partially) autonomous space robots, namely robustness to uncertainty, controlled autonomy, and bounded flexibility. • Robustness to uncertainty . It is expected that robots with advanced manipulation capabilities will operate in conditions characterised by limited sensing and unpredictable changes in the environment. These could require a robot to modify a course of action by selecting an alternative action sequence in the AND/OR graph, or to iteratively expand the graph to execute sequences of (previously unplanned) actions after having incorporated new information in the graph structure. This makes TMP-EAOG resilient to incomplete or changing world models. • Controlled autonomy . In space operations, fully autonomous decision-making is rarely acceptable without human oversight. AND/OR graphs encode a task, that is, a whole decision process, into a legible and explainable structure. TMP-EAOG enables mission planners to validate or constrain task branches, ensuring compliance with safety-critical rules and mission protocols. This balance between autonomy and human validation is key when communication delays make full teleoperation infeasible but accountability remains paramount. • Bounded flexibility . Flexibility is essential for autonomy, but in space it must be carefully bounded to prevent unsafe or overly resource-intensive behaviours. TMP-EAOG constrains flexibility to a well-defined set of allowed action sequences, which can be switched at run-time based on the reaching of previously defined mission states. In any case, action sequences are within mission-approved task abstractions, as encoded in the AND/OR graph. This ensures a certain degree of adaptability without compromising predictability or safety. We evaluate TMP-EAOG across two domains, inspired by widely recognised benchmarks in the TMP community lagriffoul2018RAL . We consider the operations of a mobile manipulator, to be thought of as a proxy to space robots with advanced manipulation capabilities, and we focus on the action level of TMP-EAOG . In BENCHMARK_1 , inspired by the famous Towers of Hanoi domain, the robot must sequence dexterous manipulation actions under dynamic reachability constraints. This mirrors situations where a robot must handle tools or components around obstacles fixed to a lander deck, therefore requiring dynamic reordering of actions as reachability changes. In BENCHMARK_2 , which we refer to as the Habitat , the robot must interleave symbolic state changes with geometric actions. This benchmark reflects complex mixed-mode operations aboard a planetary habitat, where symbolic-level activities such as, for example, switching equipment to a “ready” state, or preparing consumables for a scientific experiment in the lab, must be combined with object manipulations. Beyond their academic value, we believe that these two benchmarks could serve as proxies for space mission tasks, highlighting the capabilities enabled by frameworks like TMP-EAOG in addressing real-world challenges. The paper is organised as follows. Section 2 introduces relevant related work on Task and Motion Planning. Section 3 describes useful concepts related to AND/OR graphs as a way to encode TMP tasks. The overall behaviour of TMP-EAOG is introduced in Section 4 . Section 5 describes results in the two benchmarks. Conclusions follow. 2 Related Work In the recent past, different TMP approaches have been developed for various, non space robotics related, application scenarios. The aSyMov planner described in cambon2009IJRR is shown to perform mobile manipulation tasks using a Forklift and Boxes problem, where the forklifts move the boxes to specific locations. The classic Towers of Hanoi problem is also accomplished, which involves object rearrangement and manipulation. In the work of Dornhege et al. dornhege2009SSRR ; dornhege2009ICAPS , mobile manipulation is the main focus with experiments involving rearrangement of different blocks. A TMP approach that incorporates estimation and perception uncertainties is developed in kaelbling2013IJRR . The work therein focuses on a mobile manipulator performing household tasks. Manipulation in clutter or rearrangement planning is the focus of the works in srivastava2014ICRA . The planner in lagriffoul2014IJRR is shown to successfully execute different instances of pick and place , filling a glass , and stacking cups . Maximizing

Read the complete text