Building Exospecies AI: Hierarchical Task Networks Overview

Next:

Previous:

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…

HTN Overview

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 Go from downtown to the park and an empty Plan list:

  1. Remove and start with the first goal in the Goal List
  2. See if there is an Operator that knows how to do it. If so, add the Operator to the end of the Plan List (since Operators can “just be done”) and continue at #1
  3. See if there are Methods that know how to do it. If so, add their Subtasks to the front of our Goal List and continue at #1 If there are multiple Methods, duplicate the current state of the world and run the algorithm with each, independently. Each that completes successfully will be a different solution
  4. Repeat until the Goal List is empty
  5. When done, what you have in the Plan List is the solution

An Example

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:

State: State can be looked up using syntax like State[ThingYouWantToLookup] and is modified using State.Add() and State.Remove()

Location: downtown. 
Weather: good.
Cash: $12.
TaxiFare: $2. 
DistanceFrom(Downtown,Park): 2Km. 
TaxiLocation(Taxi1) : TaxiBase.

Operators: Anything that has a ? in front of it is a variable that works just like you’d expect

Walk(?From, ?To) : 
   State.Remove(Location, ?From), 
   State.Add(Location, ?To)
Ride(?From, ?To) : 
   State.Remove(Location, ?From), 
   State.Add(Location, ?To)
HailTaxi(?Location) : 
   State.Remove(TaxiLocation(Taxi1), TaxiBase), 
   State.Add(TaxiLocation, ?Location)
SetCash(?Old, ?New) : 
   State.Remove(Cash, ?Old), 
   State.Add(Cash, ?New)

Methods: Conditions are just English expressions that should be self explanatory

TravelTo(?X) :  
   CONDITION: 
      State[Weather] is good and 
      DistanceFrom(State[Location], ?X) < 3
   SUBTASKS: 
      Walk(State[Location], ?X)
TravelTo(?X) :  
   CONDITION: 
      State[YourCash] >= State[TaxiFare] and 
      State[TaxiLocation(Taxi1)] = Taxi Base
   SUBTASKS:  
      HailTaxi(State[Location]), 
         Ride(State[Location], ?X), 
      PayDriver(State[TaxiFare])
PayDriver(?Amount) :    
   CONDITION: 
      if ?Amount <= State[Cash]
   SUBTASKS: 
      SetCash(State[Cash], State[Cash] - ?Amount)

Note a few things about this HTN model:

Now let’s do the algorithm:

Start with the State, Operators and Methods above, a Goal List: TravelTo(Park), and an empty Plan List

  1. Remove and Start with the first (and only) goal TravelTo(Park) in the Goal List TravelTo(Park)
  2. There are no Operators called TravelTo
  3. There are two Methods called TravelTo, thus we might have more than one solution. Let’s go through the first one first: The Condition State[Weather] is good and DistanceFrom(State[Location], ?X) < 3 is true in the current state Therefore: Add its Subtasks to the Goal List after substituting variables: Walk(downtown, park)
  4. Remove and Start with the first goal Walk(downtown, park) from the new goal list: Walk(downtown, park)
  5. There is a Walk(?From, ?To) Operator Fill in variables and add it to the Plan List, which is now: Walk(downtown, park) Allow it to modify the State in case we keep going. Changes Location: downtown to Location: park
  6. There are no more goals so the Plan is Walk(downtown, park)

We found two TravelTo methods that might be applicable above. So, we need to run the algorithm on the other option too if it is valid:

The Condition State[YourCash] >= State[TaxiFare] and State[TaxiLocation(Taxi1)] = Taxi Base is also true Therefore: Add its Subtasks to the Goal List after substituting variables: HailTaxi(downtown), Ride(downtown, park), PayDriver(2$)

  1. Remove and Start with the first goal HailTaxi(downtown) in the new Goal List HailTaxi(downtown), Ride(downtown, park), PayDriver(2$)
  2. There is a HailTaxi(?Location) Operator Fill in variables and add it to the Plan List which is now: HailTaxi(downtown) Allow it to modify the state in case we keep going: changes TaxiLocation(Taxi1) : Taxi Base. to TaxiLocation(Taxi1) : downtown
  3. Grab the next goal: Ride(downtown, park) in the Goal List Ride(downtown, park), PayDriver(2$)
  4. There is a Ride(?From, ?To) Operator Fill in variables and add it to the Plan List which is now: HailTaxi(downtown), Ride(downtown, park) Allow it to modify the state in case we keep going: changes Location: downtown to Location: park
  5. Grab the next goal: PayDriver(2$) in the Goal List PayDriver(2$)
  6. There is not an Operator for PayDriver
  7. There is a single Method for PayDriver(?Amount) The condition ?Amount <= State[Cash] is true in the current state Therefore: Add its Subtasks to the Goal List after substituting variables: SetCash(12$, 12$ - $2)
  8. Grab the next goal: SetCash(12$, 10$)
  9. There is a SetCash(?Old, ?New) Operator Fill in variables and add it to the Plan List which is now: HailTaxi(downtown), Ride(downtown, park), SetCash(12$, 10$) Allow it to modify the State in case we keep going: changes Cash: $12 to Cash: $10
  10. No more goals: We are done.

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:

  1. Walk(downtown, park)
  2. HailTaxi(downtown), Ride(downtown, park), SetCash(12$, 10$)

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.

Final Thoughts

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:

Coming Next

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.

Next:

Previous:

Leave a comment or question