Robust Task Planning

My research focuses on AI planning, in particular hierarchical task network (HTN) planning. The goal in planning is to find an executable action sequence for accomplishing a certain task. Achieving a task can often be broken down in a series of subtasks, that may or may not be restricted in their order. Exactly those hierarchical constraints can be expressed in HTN planning, making it attractive in many real world applications, such as service robots, Mars rovers, or web service composition.


Robustness as a Challenge

HTN planning problems are typically solved in a fixed environment, where the state of the world is always known and only changes whenever one of the specified actions is executed. However, real-world environments are typically dynamic and not all plans are equally likely to succeed in such a setting. We would like to favor plans that are more likely to succeed when exposed to change in the environment, and call this ability the robustness of a plan. But various other definitions of robustness, as well as related concepts, exist. We are currently still working on a definition that allows for safe plan execution, while avoiding permanent overhead.

Train network with five stations and multiple routes

Consider for example the train network, depicted above. We have multiple routes from the starting station s1 to the final station s3. Choosing the fastest route via s2, however, leaves no alternative routes in case the connection from s2 to s3 is suddenly unavailable. In contrast, driving via s4, we still have two possible ways to reach the destination, which allows adjusting the route in case one of them gets blocked. We may say that this makes any path via s4 more robust. In practice, this could mean that we always take a longer path in order to gain some additional security.


Robust HTN Planning via CSPs

  • While measures of robustness have not yet been considered in HTN planning, they have been studied and applied in constraint satisfaction problems (CSPs)
  • We proposed a CSP encoding for HTN planning to exploit their robustness measures
  • Improving our current encodings and evaluating them is part of ongoing work.

Example of a Qualitative Constraint Network (QCN)





Safety Guarantees Through Action Reversibility

  • We have studied the notion of action reversibility, i.e. the possibility of completely reversing the outcome of some action with a (series of) other actions.
  • In case all actions are reversible (universal action reversibility), we can always return to our starting point, hence, removing the possibility of dead ends.
  • A plan without any dead ends can be regarded a safe plan.