I got all wrapped up in trying to write the blog post for my survey of AI algorithms, how I classified them, etc. and even I got bored. So, I’m switching to the topic I actually wanted to write about: Hierarchical Task Networks (HTNs, sometimes called HTN Planners).
I used them in the first Exospecies AI prototype. I started there for a few reasons: It is a proven algorithm that had already been used in published games, it builds an AI that behaves like a human, and it appeared to be one of the fastest algorithms due to its hierarchical, depth-first, human-scripted approach.
Turns out there’s lots of information out there on HTNs but I couldn’t find enough to understand them to the level where I could build one from scratch. I also didn’t find any good examples of using one for strategy game AI. The next few posts will try to correct that. I may come back to writing up the survey once I get some distance from it.
What I did find was two buckets of stuff on the Internet:
The confusing part was that, if you digest the Bucket 2 stuff, HTNs seem like a relatively simple tool (along the lines of state machines) for helping you to organize a giant script that just tells the system what to do. I guess I was expecting something more magical here. So, I figured something must have gotten lost in translation from the really theoretical proofs, logic and scientific sounding stuff in the “literature”. I dug deep into that and I think I understand it now. Let me take you on the journey…
In broad strokes, an HTN solves a problem using a very human planning approach that centers on abstraction and alternatives.
Alternatives: Let’s use a travel example from the famous SHOP HTN Planner. Imagine you asked me how to get from downtown to the park. I might say, “Well, it is 2Km away but, if it is nice out, I would just walk it. However, if it is raining and you’ve got taxi fare, I’d take the taxi. Otherwise, if you have bus fare, just take a bus.” A abstract thing you accomplish like “travelling from one place to another” is known in HTNs as a “Task”. The 3 alternatives I gave for accomplishing it are known as “Methods” in HTNs. Note that each Method had a “Condition” that went with it: walk if it is nice out, take a taxi if you have the fare, etc.
Abstraction: Note that these 3 Methods are at a pretty high level of abstraction. You might further ask me how to accomplish the “TakeABus” Method. I’d say something like, “Well, wait for the #1 bus at the ‘Downtown’ bus stop, pay the driver $1, and ride it to the ‘Park’ stop.”. These three tasks are known in HTNs as “Subtasks” of the “TakeABus” Method. In HTNs, Methods do what they do by decomposing into Subtasks. Now, this is a pretty complete answer for a human but maybe not if we were talking to a robot. In that case we might need to further decompose the task of “PayTheDriver$1” into something like “Reach into your pocket, grab a $1 bill, hand to driver”. Each of those could further be decomposed until we finally have something a robot could do. The final step of an HTN, the part that actually gets done, is called an “Operator”. How detailed you need to get before you are done (and have an Operator) depends on the kind of system you are building. A big part of designing an HTN model is getting your head around what the right abstractions are.
So, HTNs have these parts:
The algorithm itself is pretty simple. You start with a Task or Goal list like
Let’s see how the above travel example would work more formally. I’ve made up a little pseudo-computer-language just to help with the example. It is described as it is used:
Note a few things about this HTN model:
Now let’s do the algorithm:
We found two
So, we found two solutions. Depending on what you are doing, you could stop with the first solution and just use it, or generate all of them and somehow evaluate which is the best:
You can see how the HTN algorithm starts with a high-level goal and breaks it down into more detailed plans until you have a set of Operators that your system can “just do”, ordered in the proper order. This all works because a human has carefully crafted the Methods and Operators to make sense for your problem. In practice, you don’t end up “thinking about the algorithm” so much. Really, you just end up thinking about the base operations your system can do and about how you’d teach someone to do the things you need done.
HTNs are a natural way to describe how to solve a planning problem where you start at a high level and refine your way down to a solution. They have some great features:
And they have some downsides:
In the future posts I’ll talk about how I actually implemented an HTN and different approaches you could take, as well as how I actually implemented the Exospecies AI as an HTN.