DHTN (Dynamic Hierarchical Task Network) is a reactive and dynamic robot task planner. As its name suggests, it is based on HTN. DHTN’s idea is to build and execute the plan step by step to take into account the last changes of the environment. It features context awareness and on-the-fly adaptation.
The source code is based on ROS. Contact me for further information.
Hierarchical Task Networks are a planning approach based on decomposing task into subtasks. In brief, HTN takes as input as set of expendable tasks (called compound task) and replace them by a set of subtask realizing it (called method). HTN does so until only ready to run task (called primitive task) are remaining. In the end, HTN returns a sequence of primitive tasks i.e. the task plan.
DHTN aims to provide dynamism and context awareness. Based on HTN formalism, it relies on a novel algorithm that build and execute a plan at the same times by postponing the task decomposition as late as possible: a task is decomposed only when it need to be executed.
DHTN algorithm not only deals with the plan generation, but also with the plan execution. While executing its plan, a robot may encounters obstacles and difficulties: everything won’t go as planned. To handle the execution and adapt the plan, DHTN features status. Indeed, DHTN elements (task, method, etc…) carries status data. This information allows to know how the overall plan is going. Statuses indicates, for an element, if it is ready to be executed, if it is being executed or if it was executed. Since multiples failures are possible (for instance, a task may fail because there are no possible decomposition or because the physical execution failed), multiples errors status are included, giving some semantic to the failure: the robot know why it fails, which is very convenient to adapt in consequence !
DHTN is planner designed for robot in everyday life environment with a human and smart devices presence, in other words, in a highly dynamic environment ! Context awareness is key features for planning in such context. To take the context into account porperly, DHTN has milestones. Milestones are precise moment where the context is analysed by querying the available sensors. There are two types of milestones: Status observation milestone and world observation milestone. The first one defines moments where statuses are updated by checking the availability of actuators. A status observation milestone precedes each task execution. On the other hand, the second aims to perceive the robot’s surrounding to make the proper choices (i.e. decomposition). This last milestones is defined as a precedence of a method selection: the world is analyzed each time a decomposition is needed.
Here is the DHTN recursive algorithm:
- Nathan Ramoly, Béatrice Finance, Amel Bouzeghoub, “Context-aware Planning by Refinement for Personal Robots in Smart Homes”, International Symposium of Robotics, 2016