Towards Combining HTN Planning and Geometric Task Planning

Rachid Alami, Lavindra de Silva, Amit Kumar Pandey, Mamoun Gharbi, Rachid Alami 0001arXiv 2013 · arXiv

Introduction: Bridging the Symbolic-Geometric Gap

Robots operating in dynamic, human-centric environments face a fundamental challenge: the disconnect between high-level logical reasoning and low-level physical execution. Symbolic planning handles the abstract logic of a task—for instance, determining that to lend a book, a robot must first pick it up and then present it to a human. Conversely, geometric planning manages physical constraints, such as ensuring a reach is collision-free or that a grasp is stable.

Traditionally, these two layers are loosely coupled. A symbolic planner might generate a complex sequence of actions only for the robot to discover at the final step that a physical obstacle makes the plan impossible. This necessitates costly backtracking. This paper proposes a framework that tightly integrates Hierarchical Task Network (HTN) planning with a Geometric Task Planner (GTP), allowing the two systems to communicate and interleave backtracking during the planning phase rather than after execution failure.

Methodology: Integrated Planning Framework

The proposed system combines two distinct planning paradigms through a novel interface designed for real-time interaction.

1. HTN and GTP Integration

The high-level logic is managed by a totally-ordered HTN planner, which decomposes complex goals into primitive actions. The low-level physical reasoning is handled by the GTP. Unlike standard path planners, the GTP reasons about abstract geometric tasks like "picking," "placing," or "showing" within a 4D search space that includes agent effort levels, candidate grasps, and object placement parameters.

2. The Symbolic-Geometric Interface

To facilitate communication, the authors introduce three key mechanisms:

  • Evaluable Predicates: These are symbolic conditions (e.g., is_visible?) that trigger a call to the GTP. The symbolic planner uses these to verify if a geometric solution exists before proceeding.
  • Geometric-Symbolic (GS) Operators: These actions update the symbolic state based on geometric outcomes. For example, placing a large object might automatically "delete" the visibility of smaller items behind it in the robot's logical world model.
  • Interleaved Backtracking: This is the core of the framework's robustness. If the GTP fails to find a physical solution for a specific action, it first attempts to backtrack internally (e.g., by trying a different grasp). If local geometric options are exhausted, it signals the HTN planner to backtrack and attempt an entirely different high-level strategy.
The interleaved planning process between the HTN Planner and the Geometric Task Planner (GTP), showing projections and backtracking loops.

Experimental Evaluation: The Library Assistant Task

The framework was evaluated using a PR2 robot in a simulated and real-world "Library Assistant" scenario. The robot was tasked with managing book reservations, handling payments via a POS machine, and interacting with human members at a reception desk. This environment is particularly challenging due to the need for precise object manipulation and adherence to human-centric constraints like visibility and reachability.

Execution sequence of the library assistant task, where the robot interacts with a human and manages objects at a reception desk.

Key Results

Across 100 experimental trials, the system demonstrated high reliability in complex interactions:

  • Backtracking Efficiency: The symbolic planner required an average of only 0.86 backtracks per run. In over 90% of cases, fewer than three symbolic backtracks were needed, indicating that the GTP's internal search effectively resolved most physical constraints locally.
  • Task Performance: The GIVE task (handing an object to a human) achieved a 100% success rate with an average duration of 10 seconds. However, the PUTAWAY task proved more difficult, with a 48% success rate and a 51-second average duration, primarily due to the strict visibility constraints required for placing objects on a cluttered desk.
  • Computational Bottlenecks: While HTN planning time was negligible, the GTP was computationally intensive, particularly when calculating pixel-based visibility for human-oriented constraints.

Discussion and Future Directions

The integration of HTN and GTP allows robots to make more informed decisions. A significant insight from this work is that the geometric planner should not merely be a "checker" but a decision-maker with the leeway to choose optimal grasps or placements that satisfy long-term task goals.

Future work will focus on improving the speed of the GTP, potentially through better heuristics to prune the search space. Additionally, the authors aim to more deeply integrate navigation (NAVTO) tasks and scale the system to handle higher levels of environmental clutter with dozens of interactive objects.

Summary updated

Abstract

In this paper we present an interface between a symbolic planner and a geometric task planner, which is different to a standard trajectory planner in that the former is able to perform geometric reasoning on abstract entities---tasks. We believe that this approach facilitates a more principled interface to symbolic planning, while also leaving more room for the geometric planner to make independent decisions. We show how the two planners could be interfaced, and how their planning and backtracking could be interleaved. We also provide insights for a methodology for using the combined system, and experimental results to use as a benchmark with future extensions to both the combined system, as well as to the geometric task planner.
BibTeX
@misc{alami2013towards,
  author = {Rachid Alami and Lavindra de Silva and Amit Kumar Pandey and Mamoun Gharbi and Rachid Alami},
  title = {{Towards Combining HTN Planning and Geometric Task Planning}},
  year = {2013},
  eprint = {1307.1482},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1307.1482},
}
Figure