2013-10-31

CUHP: Simple C# Task Planner for Unity3D


Artificial intelligence is a growing field, especially in the games industry. The need for realistic and intelligent behavior in games is increasing. In my previous post I presented a new planner written in C#, a so-called hierarchical task network (HTN) planner. I know of several (scientific) examples where HTN-planners are used in real-time strategy games (e.g. Total Annihilation, Warcraft) or first-person shooters (e.g. Killzone 2, Arma, Unreal Tournament). I now show how my planner can be used in video games, or more specifically, video games made with Unity3D.

In the next section I talk about how my HTN-planner works with Unity3D, after that I show an example, and finally, I talk about what direction I have in mind for the future of my HTN-planner.


The C# Unity3D HTN-Planner

I present you, the C# Unity3D HTN-planner (CUHP), a hierarchical task network (HTN) planner written in C# for use in Unity3D. The planner is downloadable as a Unity asset-file and as a Unity3D project. If you want to know how HTN-planners work, I would suggest you read my previous blog post first.

The HTN-planner takes as input a planning problem and a planning domain. The planning problem contains a knowledge representation of the current state of the world and one or more goal tasks. The planning domain contains HTN-operators and methods which represent actions an agent or an NPC can take in the world.

An interface with the HTN-planner is needed to use the CUHP-system in a game environment. It can be really simple, and can be part of another script if desired. The following code is an example of such a planner interface:
private HTNPlanner planner = new HTNPlanner(typeof(Domain), new Domain().GetMethodsDict(), typeof(Domain));

private List<string> GetPlan ()
{
    if (GetComponent<WorldModelManager>())
    {
        State initialState = GetComponent<WorldModelManager>().GetWorldStateCopy();
        List<List<string>> goalTasks = new List<List<string>>();
        goalTasks.Add(new List<string>(new string[1] { "SolveProblem" }));

        return planner.SolvePlanningProblem(initialState, goalTasks);
    }
    return null;
}

First a new HTN-planner is declared and the planning domain is given as parameters. Here, a method called "GetPlan" is made to provide a way to use the HTN-planner. It can be customized to fit specific needs. The method gets the initial state from another script (WorldModelManager) and creates a new goal task called "SolveProblem". Finally, it calls the "SolvePlanningProblem"-method of the HTN-planner, providing the initial world state and goal tasks as parameters, and then returns the plan found by the planner. The next section shows an example in which a plan is actually executed.


The Cleaning Robot Example

I made two simple examples in Unity3D, a swap object example and a cleaning robot example. The latter is the most interesting, it is a virtual environment consisting of several linked rooms which together form a building. A cleaning robot resides in this building and it can be commanded to clean dirty rooms. The user can simply click on a room to make it dirty (or clean), and by doing this, a planning problem is created. Then, when any number of rooms are made dirty, the planner can be started (with a button) to solve the planning problem and produce a plan for the cleaning robot to execute. When a feasible plan is found, the robot will execute it and clean all dirty rooms in the building.

The following picture shows the virtual environment of the cleaning robot example:


The world is abstract and basic because the focus is on planning. The tiles represent rooms, the sphere represents the cleaning robot. When the user clicks on the "Clean"-button, the HTN-planner seeks a plan and sends it to the robot for execution. The robot converts a plan of actions into an action queue and executes the actions one-by-one. If the robot is still busy and receives a new plan, it clears its action queue and fills it with new actions, but it always finishes its current action. This simple example can be easily extended into a more complex game situation.

As mentioned in my previous blog post, the HTN-planner is not perfect at backtracking yet. The user can create some planning problems in the cleaning robot example for which no feasible plan can be found. This should not be too hard to fix and I might do that soon.


Future Work

I have a few ideas in mind about the future of this CUHP-system:
  • HTN planning for strategy games. I want to make a more advanced game example to show the power of my HTN-planner, for example, I want to apply it to a real-time strategy game.
  • Extending the Unity3D Editor. I want to extend the Unity Editor GUI for easy integration of the planner with a game, and to provide a more efficient way of designing artificial intelligence when making a game.
  • Unity Asset Store. I am considering making the planner available in the Unity Asset Store.

I plan to work on these points in the future, and will write about it when I made progress.

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

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.

2013-10-18

Introduction to My New Blog

Hello users of the internet!

Welcome to my new blog about artificial intelligence and programming in general.
I am writing this post to introduce myself and to introduce my blog. In this post I will address four points: who I am, why I am blogging, what I will be blogging about, and how you can leave me feedback.


Who am I?

At the time of writing this post, I am a student who is trying to get a master's degree in technical artificial intelligence. I am busy with my final project and writing my thesis, but I have enough time to do some programming in my spare time. And I hope I can post a blog post at least once a month, but we will see.

My name is Pieterjan van Gastel, I am male, 23 years old, and from the Netherlands. I have a bachelor's degree in computer engineering and minored in game design. And now I am working in the robotics lab of Eindhoven University of Technology.

Activities I enjoy doing when I am not working are: programming, drawing (I also draw comics), playing electric guitar, playing video games, writing, skateboarding, and snowboarding.

I am interested in artificial intelligence, robotics, automation, game design and technology, and augmented reality. And I want to continue to specialize myself in those fields.


Why am I blogging?

I am blogging to showcase my programming work to the world, and also because I think it will be a fun and interesting experience.

I am always searching to innovate, thinking of new ways to use artificial intelligence in a practical way. Maybe some of the work I present here will be very useful to some people, especially those with an interest in artificial intelligence. There are still many possibilities and opportunities in AI, and a lot of it is still undiscovered. It makes working with AI even more exciting, don't you agree?

I will try to document my work as clearly as possible, so that people can also learn more easily from it. I think my work is more useful if I can share it with a wide audience.


What will I be blogging about?

I will blog about whatever code I am developing. I am currently working on a personal project in which I want to make an easy-to-use hierarchical task network (HTN) planner for use in video games, but it is a lot more generic than that and it can be used for just about any planning problem.

So, I will concentrate mostly on code, on programming. My current focus lies on artificial intelligence, but probably not every post will be about that, some will be about (less intelligent, or general) software development. And perhaps not every post will be about programming, I think I might also write some posts in the future that are more theoretical, but we will see.

If you want to know more about planning, I would suggest to get a copy of Automated Planning: Theory & Practice by Ghallab, Traverso and Nau. But there is also a lot of basic information on Wikipedia.


How can you leave me feedback?

Well, for starters, you can leave a comment on my post below. However, there are other ways to contact me, for example, you can also email me (look for the contact button on the right of my blog). And, you can also find me on twitter (see the links box on my blog).

I encourage comments and feedback on my blog and I will try to reply to any email as soon as possible.


I look forward to blogging about the progress on my programming projects.

- PJ