HTN planner prototype

I’ve been working on Paragon bots for some time now, and up until now, it was mostly about making it work, having bots play the game at all. Now, when the dust has settled and the bots do indeed play the game, it’s time to start thinking about bots that can use their abilities in an advanced manner, chaining their own abilities and cooperating ability triggering with their friends. This calls for some kind of planning, and I’ve wanted to implement a generic Hierarchical Task Network (HTN) planner for UE4 for a long time now. Well, here’s my use-case :D

Since I’ve never implemented an HTN before I’ve figured I can put together a quick prototype that will allow me to get this unique, intimate understanding you can only get by doing the thing yourself. This post is a kind of a record of the process.

To refresh my memory on HTNs I’ve reached for an article I remembered had a really clear explanation of the concept (namely this one).

An HTN planner implementation consists of two parts: planning domain, and the planner itself. There’s also “world state”, but I’m considering it a part of the domain since the domain used determines the validity of the world state representation.

Following the naming convention used in the article we have:

In short, an HTN Domain is build of Primitive and Compound Tasks. Compound tasks are build of Methods. Methods are build of Primitive and Compound Tasks.

The world state is a simple “facts” lookup with additional info on how to modify and check the stored facts:

As mentioned, the second part of and HTN planner implementation is the actual planner itself.

Up until now, I’ve listed only the properties of the declared classes. With this we can (almost) build a planning domain. I’ve just taken advantage of python syntactic sugar to make planning domain look nicer once defined:

With these we can build a test domain:

Of course, this wouldn’t compile. There’s a bunch of functions used here I haven’t defined (or even declared!) yet. This is partly how I work. I lay out the high-to-mid level code, and then just fill in the blanks. Let’s fill in the blanks now. First the part I always, always, always build along with any system I implement, and so should you, the debugging/validation code:

And last but not least (by far) the code that does the actual work. Here comes the functional part of the classes declared above:

The code doesn’t require much explanation, provided you’ve read the article mentioned earlier. There’s not much I can add other than the actual implementation (which I do).

The whole code in proper order can be found on the github. And we can test it like so:

which generates the following output:

Of course, this is the most basic implementation of an HTN planner and it doesn’t handle the more exotic cases. But it’s enough for me to start a proper C++ implementation in UE4 sources.

2 thoughts on “HTN planner prototype”

  1. Just tweeted you, but I know most people don’t use twitter often. I’m having problems finding any docs on HTN Planner, assuming it’s only c++ ATM? Where can I begin?

    And cool prototype,I’m going to fire this up later this week and see what fun I can have.

    1. I tend to have my twitter tab opened at all times, but I might not be looking at it all that often :D

      I’ve replied on twitter as well, but for the record: there’s not docs yet because this code is so fresh and pretty much basic. The only uses are in HTNTest.cpp which hosts unit tests for the UE4 HTN planner implementation.

Leave a Reply

Your email address will not be published. Required fields are marked *