Improving Performance of my Unity3D HTN-Planner (CUHP) with Multithreading

By adding some simple features, I have greatly increased the performance of my C# Hierarchical Task Network (HTN) Planner for use in Unity3D (CUHP). I previously explained how my Unity3D task planner works. To recap, it is a simple task planner written in C# for use in Unity3D, suitable for a wide range of video game genres (e.g. visual novels, adventure games, strategy games, shooter games). It can be used for NPC behavior, but also for story generation or even level generation! Feel free to experiment with it! I might also provide more (open source code) examples of the wide variety of applications of the planner in the future.

With this new blog post I show you how the performance of my planner is greatly improved by adding multithreading and functionality to cancel planning. In the previous version of my HTN-planner, the game could easily freeze up, resulting in a terrible user experience. Now with multithreading, the planner is run on a separate thread, so that the game continues to run on the main thread without freezing up. I will briefly explain multithreading in the next sextion, and follow this with some code examples. Furthermore, I provide a section about the cancel plan functionality and another section in which I explain some of my future steps.

The updated source code of my planner is available here: C# Unity3D HTN-planner (CUHP) on sourceforge.


I will not go into a lot of detail about multithreading, it is a complex subject and there are a lot of good sources available on the internet if you want to know more about it. That said, multithreading is "simply" the ability to execute a program on multiple threads. This is especially useful when a lot of calculations need to be done in a single method. With multithreading you can start the method with the heavy calculations on a new thread, while the main update method of your game continues to run on the main thread. This prevents the game from freezing up because now the update method does not need to wait until the heavy calculations are done.

Unity3D also provides thread-like behavior with coroutines. However, I choose threads over coroutines because threads are more flexible.

Multithreading is important for my Unity3D HTN-planner, because in some cases the planner takes a very long time to finish planning (up to several minutes). An example case is when there are a lot of applicable HTN-methods to the provided planning problem, but the planner is still unable to find a valid plan. Therefore, with multithreading, the planning can be run on a separate thread while the game continues to run on the main thread. This of course creates a new problem in some games, namely, if the NPC behavior is fully dependant on the plan generated by the planner. This could be solved in several ways, for example: by planning in advance, by adapting your planning algorithm (e.g. decrease number of HTN-methods), or by providing backup behavior for the NPC while it waits on the planner to finish.

Thanks to Mike Talbot of WhyDoIDoIt.com I found a simple way of using multithreading in Unity3D: Mike's "Loom" class. I have added this class to my CUHP project, renamed it to ThreadManager.cs and made a few minor changes.

I have added multithreading to the previously presented cleaning robot example. I have adapted my planner interface script (PlannerInterface.cs) such that when the user clicks the "Clean"-button on the GUI, a new thread starts in which the HTN-planner will run. The following code snippet shows the "SearchPlanAndSend"-method, in which the planner is started on a new thread. When a plan is found, it is automatically sent to the cleaning robot's task queue. I believe the code is very easy to understand. However, feel free to ask questions if anything is unclear.

private void SearchPlanAndSend()
    this.doneSearching = false;
    this.searchSuccessful = false;
    if (GetComponent<WorldModelManager>())
        State initialState = GetComponent<WorldModelManager>().GetWorldStateCopy();
        if (initialState.ContainsVar("at"))
            initialState.Add("checked", initialState.GetStateOfVar("at")[0]);
        List<List<string>> goalTasks = new List<List<string>>();
        goalTasks.Add(new List<string>(new string[1] { "CleanRooms" }));

        ThreadManager.RunAsync(() =>
            List<string> plan = planner.SolvePlanningProblem(initialState, goalTasks);

            ThreadManager.QueueOnMainThread(() =>
                this.doneSearching = true;

                if (plan != null)
                    this.searchSuccessful = SendPlanToRobot(plan);
                    Debug.Log("no plan found");

The next section is about the cancel planning functionality.

Cancel Searching for Plan

The cancelling of searching for a plan (i.e. cancel planning) simply means that the planner is commanded to stop planning. I enabled this with a simple boolean "cancelSearch" in my HTN-planner code, which makes the planner stop instantly.

It is (for example) useful to cancel planning when the world state (or game state) changes so much that the plan currently being searched for will probably not be applicable to the current situation anymore. The plan will then most likely not produce the desired result anymore. Then after cancelling, you can issue the planner to find a new plan based on the new world state.

I provide no code sample of the cancel functionality because it is very straightforward. Just read through the code available on sourceforge and look for the "Cancel"-button in the "OnGUI"-method of the file RobotGUI.cs. This cancel button is a new addition to the cleaning robot example to showcase how to cancel planning.

In some cases of the cleaning robot example, the planner is unable to find a valid plan and gets stuck. I left this in for people who like a challenge. Experiment with the program to see when it gets stuck and try to improve my cleaning robot example so that the planner does not get stuck anymore. Good luck!

Future Work

I want to keep my future work section short this time with stating only the following: I plan to work next on a turn-based strategy game example in which my HTN-planner is used. And after that I want to work on a real-time strategy game example in which my HTN-planner is used. Feel free to ask questions though!

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.


A MSc Thesis Study: A Planning Module for a ROS-Based Ubiquitous Robot Control System

I have recently finished my master's degree research project, which I did at the Robotics lab of the Control Systems Technology Section, Department of Mechanical Engineering, of Eindhoven University of Technology. However, I was a master student of Technical Artificial Intelligence at Utrecht University. My thesis is titled "A Planning Module for a ROS-Based Ubiquitous Robot Control System". My project involved a combination of automated planning, the Semantic Web and robotic technologies. In this blog post, I present my thesis work in a summarized way.

The life expectancy of people is increasing, therefore more professional caregivers are required to take care of the elderly. This results in more expensive health care. A desire for assistive technologies in health care is therefore growing to provide the caregivers to work in a more efficient way. Such assistive technologies are researched and developed at the robotics lab of Eindhoven University of Technology (TU/e) in the form of service robots.

An example of such a service robot is the Autonomous Mate for IntelliGent Operations (AMIGO) robot developed at the robotics lab of the TU/e. A picture of this robot can be seen in the figure below. It is a mobile robot with two arms. It could use its arms, for example, to pick up a drink for a patient and then hand it to the patient.

Research efforts are made to combine these robots with intelligent environments. An example of this is the research project described in my thesis. The idea is to have several service robots in an environment, such as a health care institution, and to have them controlled by a central control system. Therefore, a ubiquitous robotic framework for multi-robot planning and control is proposed. This framework integrates with existing design efforts of the open-source robotics community. The main focus of my research project is on the planning module of the proposed system.

For such a multi-robot control system, a planning module is needed to provide for flexibility. The system needs to be flexible so that it can be used in various different environments and with different types of robots. This planning module handles the planning and scheduling of multiple tasks for the robots in an intelligent way. Therefore, the field of automated planning for robotic systems is analyzed first in my thesis. This is followed by a literature study on subjects ranging from automated planning, to Semantic Web and robotic technologies, such that all fields of ubiquitous robotics are covered. Based on the analysis and the literature study requirements are formed for the system. These requirements are then used to create the design of the framework. Furthermore, a prototype of the framework is implemented and experiments are performed with this prototype. The results of these experiments are evaluated. The thesis also includes a comparison between the proposed system and other similar planning systems as part of the discussion after the evaluation.

The design of the framework includes technologies such as Robot Operating System (ROS), Semantic Web Ontology languages (OWL and OWL-S), RoboEarth Cloud Engine (Rapyuta), and MIndiGolog, as they are innovative, provide genericness and integrate well with each other. MIndiGolog is a high-level agent programming language for multi-agent systems, and is based on situation calculus, a logic formalism designed for representing and reasoning about dynamic domains. MIndiGolog can reason over world states and transitions between states. In the proposed system, robots are also required to have a robot-type description available, which describes the specific robot capabilities of each connected robot, so that the planner can select the right robot for specific tasks. The planner searches for plans to accomplish user-given tasks.

The programming languages Python and Prolog are used to implement the prototype of the framework. PySWIP is used to query Prolog rules in Python. The prototype includes an executive layer, a planning layer and an ontology layer. The figure below displays these three layers. My thesis focuses on the planning layer.

Several qualitative tests and an experiment with real robots are performed with the implemented prototype. The tests are performed to validate the functionality of the planning module of the system. The experiment describes a use case in which robots need to help with a cocktail party. In this use case, the robots need to take orders from guests, bring drinks to the guests, find empty drinks, and clean up empty glasses. The performed experiment however only includes the subtask of detecting empty drinks, due to limited time and resources. The robots need to navigate to the location where they expect empty drinks to be found and then perceive the empty drink.

The picture below shows the experiment. As can be seen, two service robots stand in the middle of a room. The robots need to drive to a location where they expect empty drinks to be found and then perceive this drink. The planning module needs to select the closest robot to go to the closest drink. A video of the experiment is available online.

The results of both the tests and the experiment are successful, as the tests performed as expected and the robots navigated to the nearest location where they expect empty drinks to be found in the experiment. There were however some performance issues with the communication interface of the system, including latency and bandwidth issues. Based on the results, the proposed framework is evaluated as a feasible approach to a ubiquitous robotic system for multi-robot planning and control.


Rewriting the Univ-Operator (=..) in Prolog

While I was working on my research project, I stumbled on this three year old question on stackoverflow, and I got inspired by it to do an attempt at rewriting the univ-operator in Prolog.

I found one source claiming that the univ-operator was once written as a predicate with the name univ, but I could not find how this predicate was written. After searching around, I also could not find anyone who rewrote the univ-operator back into a Prolog predicate. So I saw this as an exercise for me, and tried to do it myself.

First, I explain what Prolog and the univ-operator are. Then I show how I implemented the univ-predicate, and finally, I show that my predicate works and discuss the matter further.

1. Preliminaries

1.1 Prolog

Prolog is a declarative programming language, and has its roots in First-Order Logic. The logic of Prolog programs is expressed in terms of relations, represented as facts and rules. A computation is initiated by running a query over these relations. The word arity is used to denote the number of arguments in a term. Also, www.learnprolognow.org/ is a good place to start if you want to learn Prolog.

1.2 The Univ-Operator

The univ-operator, written in Prolog as =.. (an equality sign followed by two dots), is an infix-operator that converts between a term and a list. The functionality of this operator is best shown with an example.

Here are some examples of using the univ-operator:

?- a =.. X.
X = [a].

?- f(x,y) =.. L.
L = [f, x, y].

?- Term =.. [f, x, y].
Term = f(x, y).

?- '=..'(f(x,y),L).
L = [f, x, y].

2. Implementation

I use SWI-Prolog for the implementation. The following code is what I came up with:

If you ever use this code, I would appreciate it if you gave me credit for it.

I will now explain the code per predicate.

2.1 univ

The univ-predicate has two arguments: a term and a list. Depending on which arguments are atomic and which are variable, the predicate shows slightly different behavior. First the number of arguments are count. Then either a new term is created with functor name/arity, where F is the name and N is arity, or the name and arity are retrieved from an already existing term. Next, either the arguments are filled into the new empty term, or the arguments are retracted from an already existing term. And finally, a cut is placed to prevent backtracking for multiple solutions. Only one solution (the first) is the right one, and any other attempt on getting more solutions will result in an infinite loop. Theoretically speaking, my countArgs-predicate can count up to infinity. This is also the predicate I am discussing next.

2.2 countArgs

This is a very simple predicate which counts the number of items in a list. If however both arguments of the countArgs-predicate are variable, then there are infinite solutions (every non-negative number can be unified with No in this case, and Args can be a list of any size). If only "Args" is variable, then a list with No unbounded arguments is created.

2.3 fillInArgs

The fillInArgs-predicate, as mentioned above, either fills a new empty term with give arguments, or retracts the arguments from an already existing term. It uses the arg-predicate to fill in or retrieve the arguments. It also counts the number of arguments, this needs to match the count done by countArgs so that all arguments are filled into the term.

3. Evaluation

The implentation works. The following example shows the functionality of my predicate is the same as the univ-operator:

?- univ(f(x,y),L).
L = [f, x, y].

?- univ(f(x,y),[f|Args]).
Args = [x, y].

?- univ(Term,[f,x,y]).
Term = f(x, y).

Now, this predicate can probably be improved in some ways. Perhaps it can be improved by combining the countArgs-predicate and the fillInArgs-predicate, but I see no need to do it for now. Maybe I will try that later, maybe I leave it as an exercise for you. Feel free to give the solution in the comments if you find one.

It could also be interesting to do a benchmark to see which is faster, my univ-predicate or the original univ-operator. It should not be too hard to do this, since Prolog has this nice built-in predicate statistics/2, but I did not want to do this right now. Maybe I will do it later.

Further more, is this predicate really useful? Why not use the operator? Well, it provides more freedom, you can learn from it, and adapt it. Maybe you only need part of univ's functionality, you can rewrite my univ-predicate to get only the part that you need. Maybe you need the univ-funtionality twice in succession, and it is better to rewrite it into a new single predicate. Maybe it does not improve that much on performance (but I have not benchmarked it (yet), so I do not know this), but I think it is a good practice to often try to find ways to improve the performance of your code, or your code in general.

Feel free to join the discussion.


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.


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.


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))

    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.


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