2014-06-14

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.


Multithreading

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);
                else
                    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.

2014-03-31

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.