HATP: An HTN Planner for Robotics

Rachid Alami, Raphaël Lallement, Lavindra de Silva, Rachid Alami 0001arXiv 2014 · arXiv

This paper introduces HATP (Hierarchical Agent-based Task Planner), an extension of the Hierarchical Task Network (HTN) planning paradigm designed to meet the unique requirements of robotics and Human-Robot Interaction (HRI). By treating agents as first-class entities and interleaving symbolic planning with geometric reasoning, HATP generates synchronized, multi-stream plans that are both physically feasible and socially acceptable.

The Challenge of Robotic Planning

Traditional AI planning often fails in real-world robotics due to three primary factors:

  1. Search Space Complexity: Classical planners often struggle with the vast search spaces of real-time robotics. HTN planning mitigates this by using domain-specific hierarchies, but standard HTN implementations lack robot-specific features.
  2. Multi-Agent Coordination: Most planners generate a single sequence of actions. Robotics requires parallel execution and synchronization between multiple robots or humans.
  3. The Symbolic-Geometric Gap: Symbolic planners may suggest actions (e.g., "Pick up cup") that are kinematically impossible or blocked by obstacles. HATP addresses this by verifying physical constraints during the planning process.

Methodology: Agent-Based Representation

HATP is built upon the SHOP (Simple Hierarchical Ordered Planner) framework but introduces several critical enhancements. Central to HATP is the concept of Agent-Based Representation. The planner does not simply output a list of tasks; it produces synchronized "streams"—one for each agent involved. These streams are linked by causal dependencies, ensuring that one agent waits for another when necessary.

A multi-stream plan generated by HATP for the Dock-Worker Robots domain, showing synchronized actions across multiple agents.

To bridge the symbolic-geometric gap, HATP utilizes "evaluable predicates." During search, the symbolic planner can call an external 3D geometric planner (GTP) to verify if a proposed action is physically possible. If the geometry fails, HATP backtracks to explore alternative symbolic branches or different action instances (e.g., a different grasp).

Human-Robot Interaction and Social Rules

A key innovation of HATP is its ability to incorporate "social rules" as planning constraints. In HRI scenarios, a plan must be more than just logically sound; it must respect human comfort and efficiency. HATP allows users to define rules that penalize plans for "wasted time" (making a human wait too long) or "effort imbalance" (placing an unfair workload on the human).

An HTN task tree for a library scenario, illustrating the decomposition of high-level tasks into specific robot and human actions.

In the Library Domain, HATP models human kinematic capabilities to ensure the robot's actions are compatible with human reach and visibility. This ensures that when a robot "gives" a book to a human, it does so in a way that the human can actually receive it.

Key Results and Evaluation

The planner was evaluated using two primary domains:

  • Dock-Worker Robots (DWR): A benchmark involving robots, cranes, and containers. HATP successfully demonstrated complex multi-agent synchronization, splitting a single sequence of high-level goals into parallel execution streams for different hardware components.
  • Library Domain: A custom HRI scenario where a PR2 robot assists a customer. This demonstrated the planner's ability to integrate social constraints and kinematic modeling into the task decomposition process.

Future Directions

While HATP represents a significant step forward, several areas for future work remain. Currently, the planner assumes all agents share a perfect, global view of the world; future iterations aim to model individual, potentially conflicting agent beliefs. Additionally, the authors plan to move social rule filtering "online" to prune invalid branches earlier in the search process, further optimizing the computationally expensive interleaving of symbolic and geometric reasoning.

Summary updated

Abstract

Hierarchical Task Network (HTN) planning is a popular approach that cuts down on the classical planning search space by relying on a given hierarchical library of domain control knowledge. This provides an intuitive methodology for specifying high-level instructions on how robots and agents should perform tasks, while also giving the planner enough flexibility to choose the lower-level steps and their ordering. In this paper we present the HATP (Hierarchical Agent-based Task Planner) planning framework which extends the traditional HTN planning domain representation and semantics by making them more suitable for roboticists, and treating agents as "first class" entities in the language. The former is achieved by allowing "social rules" to be defined which specify what behaviour is acceptable/unacceptable by the agents/robots in the domain, and interleaving planning with geometric reasoning in order to validate online -with respect to a detailed geometric 3D world- the human/robot actions currently being pursued by HATP.
BibTeX
@misc{alami2014hatp,
  author = {Rachid Alami and Raphaël Lallement and Lavindra de Silva and Rachid Alami},
  title = {{HATP: An HTN Planner for Robotics}},
  year = {2014},
  eprint = {1405.5345},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1405.5345},
}
Figure