2013-10-28

CHP: My New HTN-Planner Written in C#


I was working with hierarchical task network (HTN) planners for my master's thesis, and I noticed there was no such planner (freely) available in the language of C#. After seeing the simplicity of Dana Nau's Pyhop implementation (an HTN-planner written in Python), I imagined it would not be so hard for me to make one in C#.

In this blog post, I showcase my C# HTN-planner (CHP) and explain how it works. But first, the next section is about the theory of HTN-planning. After these short preliminaries, I go a bit deeper into my CHP implementation, and finally, I end with what I have in mind for the future of CHP.


Preliminaries

This section briefly explains the theory of HTN-planning. It is for those who are not familiar with HTN-planning or those who want to refresh their memory on the subject.

The basic idea behind HTN-planning is to recursively replace non-primitive tasks with appropriate task networks, and to instantiate primitive tasks with actions until there are only actions remaining.

The objective of an HTN-planner is not a set of goal states, but rather a collection of goal tasks. Tasks can be decomposed into subtasks by using domain-specific rules, called methods. These subtasks can then be decomposed further until primitive tasks are reached. The primitive tasks are ungrounded actions which can directly be executed by the controller, and they form the solution to the planning problem. A plan is a list of primitive tasks. Non-primitive tasks need to be decomposed into primitive tasks before they can be executed.

The primary advantage of HTN planners, compared to classical planners, is their sophisticated knowledge representation and reasoning capabilities. They can represent and solve a variety of non-classical planning problems. They can also solve classical planning problems faster than classical or neoclassical planners.

The primary disadvantage of HTN planners is the need for the domain author to write both a set of planning operators and a set of HTN methods.


The C# HTN-Planner

With the C# HTN-planner (CHP), I've tried to make an HTN-Planner for C# applications. I released the project under a GPLv3 license, so that others can use it too.

Because of CHP's similarity to Pyhop, it should be just as easy to understand, and just as easy to integrate it with any application.

CHP represents states as objects with collections of variables, as opposed to other planners (such as SHOP2) in which states are collections of logical predicates. CHP differs from Pyhop, because in Pyhop you can write s.loc['v'] = 'd' to say that vehicle v is at location d in state s, whereas in CHP you write s.Add("loc", "v", "d") to say the same thing.

Just as in Pyhop, you do not need to learn a specialized planning language to write the HTN-methods and operators for the planning domains. You write them as ordinary C# methods, which are only constrained by their return value (methods return a list of new tasks, operators return a state) and parameters (the state is the first parameter, all other parameters are strings).

The actual HTN-planner is only 88 lines of code, it recursively looks if it can find a plan for a given set of goal tasks (a planning problem). First it checks if any tasks are left, it is done when no tasks are left, but needs to continue planning if any tasks remain. It then selects the next task and checks if an operator matches the task. If no operator matches the task, the planner looks at the methods. There can be multiple HTN-methods for the same task. If the planner found either an operator or method for a given task, and they did not fail (e.g. when preconditions are not met), the search method is called again for the next task (and thus it is recursive) until a full plan is either found or not. If no plan is found, a simple null reference is returned.

The most interesting part of the CHP is probably its ability to find HTN-operators of a (previously) given planning domain in a generic way by use of reflection. In the following code example, the method DeclareOperators goes through all methods in the file, and any static method which also returns a state is seen as an HTN-operator and added to a list of operators which the actual HTN-planner can use for solving problems.
/// <summary>
/// The type of the class containing the operators of the given planning domain
/// </summary>
private Type operatorsType;

/// <summary>
/// Finds all operators in the given domain and adds their names to the list "operators" for later use.
/// </summary>
/// <returns>Returns the list "operators" (for debugging purposes)</returns>
public List<string> DeclareOperators()
{
    MethodInfo[] methodInfos = operatorsType.GetMethods(BindingFlags.Public | BindingFlags.Instance | BindingFlags.Static);

    operators = new List<string>();

    foreach (MethodInfo info in methodInfos)
    {
        if (info.ReturnType.Name.Equals("State"))
        {
            string methodName = info.Name;
            if (!operators.Contains(methodName))
                operators.Add(methodName);
        }
    }

    return operators;
}

Since the current implementation of the CHP-system is very simplistic, it can be improved on several points. The next section goes over these points of improvement.

Future Work

There is plenty of room for improvement for the current simplistic implementation of the CHP-system. I am looking to improve it on the following points:

  • Backtracking. Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution. At the moment, the planner does not backtrack properly. For example, within an HTN-method the planner can choose between going left and going right, both are valid actions at that point and the planner chooses to go left. Now at a later stage this plan fails, and while going back, the previously mentioned method is not run through again and the planner does not look if going right was a better option. It only also checks for going right if the HTN-method has a seperate implementation for going right and going left (so then there are two HTN-methods for the same action).
  • Finding the cheapest plan. The planner only returns the first plan it finds. It could be improved to find the cheapest of all plans. Cheapest can be in terms of number of total actions in a plan or expected duration of the plan.

You are encouraged to use the CHP-system, and expand and improve on it, as long as you share alike under the same (or a similar) open-source license.

In my next blog post, I provide an example for using my C# HTN-planner in a video game environment.

No comments:

Post a Comment