I recently took it upon myself to implement an HTN (Hierarchical Task Network) planner in my game engine. While other AI methodologies (behavior trees, finite state machines, etc) are fairly well-documented, I didn’t find much on HTNs outside of Exploring HTN Planners through Example, so decided to write this blog post about my implementation and thoughts.
What Is An HTN?
HTNs are a combination of the tree-like structure of a behavior tree and the emergent behavior of a planning system. They require designers to provide more information about behaviors than traditional STRIPS-like planning algorithms, but they have the benefit of being easier to tweak to designer specifications.
HTNs consist of two types of tasks: primitive tasks (also referred to as operators) and compound tasks. Primitive tasks are the foundational building blocks of an HTN; they have a set of preconditions that must be met for the task to be valid, and a method of describing how the task changes the world state.
Compound tasks are formed of multiple methods, which can also contain a set of preconditions as well as an ordered list of subtasks. The planner’s goal is to decompose a root compound task into a single ordered list of primitive tasks that can then be executed. To do this, it analyzes which methods of a compound task are available based on the world state, and then explores each method.
Most HTNs use depth-first search for this decomposition, which has the advantage of being easily understood by designers. Methods ordered by priority are easy to make sense of, and easy to implement with backtracking and state rollback. However, it is entirely possible to implement an HTN that uses cost functions and heuristics to prioritize between different methods in a more emergent fashion, and that is the functionality I implemented.
An additional feature I wanted to implement was recursive tasks; that is, a method of a compound task might refer to a parent of that compound task or the compound task itself. This improves the expressiveness of the HTN, but also caused me a few problems when it came to calculating heuristics.
Task Definitions
Primitive and Compound tasks both inherit from an abstract Task class I define:
public abstract class Task<T>
where T : class, ICloneable
{
public string Name;
internal readonly List<IConditional<T>> PreConditions = new List<IConditional<T>>();
public bool IsSatisfied(T context)
{
for (int i = 0; i < PreConditions.Count; ++i)
{
if (!PreConditions[i].Update(context))
return false;
}
return true;
}
public void AddPreCondition(IConditional<T> condition)
{
PreConditions.Add(condition);
}
}A key feature of this implementation is the task name; this must be unique between tasks. A task planner is provided a list of all possible tasks, and these names are used to build a dictionary to reference these tasks. Compound task methods can thus use strings to refer to their subtasks, allowing us to implement recursive tasks without worrying about the order in which tasks are created.
Primitive tasks are, as the name suggests, fairly basic; they must provide costs and heuristics (which by default can simply use the cost of the task itself, assuming that these costs are easy to calculate). Additionally, primitive tasks should provide a method I called Execute() that can modify the world state.
Compound tasks contain a list of methods, which in turn contain a list of task names. Methods also contain preconditions, with a similar IsSatisfied() function to enable and disable different methods based on the world state.
The Task Planner
This is where the majority of the work gets done. The task planner holds a dictionary of available tasks, using the key of the task name. It also contains a string to denote the root task. When a task planner is asked to construct a plan, it first constructs a representation of the current PlannerState. This state informs the planner what the current plan looks like — what tasks are left to process, what the working world state looks like, what the plan thus far is, and what the cost so far is.
private struct PlannerState : ICloneable
{
public List<Task<T>> TasksToProcess;
public T WorkingWorldState;
public List<PrimitiveTask<T>> PartialPlan;
public int CostSoFar;
public object Clone()
{
return new PlannerState
{
TasksToProcess = new List<Task<T>>(TasksToProcess),
WorkingWorldState = (T)WorkingWorldState.Clone(),
PartialPlan = new List<PrimitiveTask<T>>(PartialPlan),
CostSoFar = CostSoFar,
};
}
}The initial PlannerState is very simple – the root task is the only entry in TasksToProcess, the WorkingWorldState is the current context, the PartialPlan is empty, and the CostSoFar is 0. This initial PlannerState is enqueued into a priority queue.
Next, we explore the plan space via an A* algorithm. While our priority queue is not empty, we dequeue the highest-priority planner state. Then, we check TasksToProcess – if it’s empty, we’ve found our optimal plan. Otherwise, we need to continue decomposing tasks.
We peel off the first task in the list and examine it. The simplest case is that it’s a primitive task; here, we can simply ensure it is satisfied. If so, we clone our current PlannerState, remove the task from TasksToProcess, add it to the PartialPlan, increase our CostSoFar by the task’s cost, and call Execute() to modify our new world state. Then we can enqueue our new PlannerState back onto the priority queue, and loop back. If the task’s preconditions are not satisfied, then our plan is invalid and we simply discard this failed PlannerState.
If our current task is a compound task, things get more difficult. First, we get a list of all the satisfied methods in the task. Then, for each method, we clone our PlannerState and modify it accordingly. We obtain a list of the selected method’s tasks, and replace the current task with that list of method tasks. We then estimate the new plan’s cost, by adding our cost so far and a heuristic — I’ll go into more detail on that later. Finally, we enqueue the new PlannerState into the queue using that estimated plan cost as the priority.
If our queue ever empties out, there was no viable plan we could construct given the tasks available.
Heuristics
My original plan for heuristics was to implement a GetHeuristic() method in both primitive and compound tasks, and use recursion to determine the total estimated cost of a sequence of tasks. A context-independent heuristic for compound tasks is rather simple: we use the method with the minimum heuristic cost, which in turn is comprised of the sum of the heuristic costs of the method’s tasks.
Essentially, since any method may be chosen, and for a proper heuristic we must always underestimate the actual cost, we use the lowest-cost method. For a method to run, all of its subtasks must be run, and thus we can simply add their costs together.
Unfortunately, this recursive solution runs into problems when tasks can refer to their own parents, leading to infinite loops and stack overflows. To prevent getting stuck in cycles, I implemented a more complex function GetHeuristic():
private int GetHeuristic(IReadOnlyList<Task<T>> tasksToProcess, T context)
{
Dictionary<string, int> heuristics = new Dictionary<string, int>();
HashSet<string> hasChecked = new HashSet<string>();
Stack<string> toCheck = new Stack<string>();
foreach (var t in tasksToProcess)
toCheck.Push(t.Name);
while (toCheck.Count > 0)
{
var t = _tasks[toCheck.Peek()];
if (heuristics.ContainsKey(t.Name))
{
toCheck.Pop();
continue;
}
if (t is PrimitiveTask<T> pt)
{
hasChecked.Add(pt.Name);
heuristics[pt.Name] = pt.GetHeuristic(context);
toCheck.Pop();
}
else if (t is CompoundTask<T> ct)
{
hasChecked.Add(ct.Name);
int minMethod = int.MaxValue;
bool shouldWait = false;
foreach (Method<T> method in ct)
{
int methodHeuristic = 0;
foreach (string taskName in method)
{
if (hasChecked.Contains(taskName))
{
if (heuristics.ContainsKey(taskName))
{
methodHeuristic += heuristics[taskName];
}
}
else
{
shouldWait = true;
toCheck.Push(taskName);
}
}
minMethod = Mathf.Min(minMethod, methodHeuristic);
}
if (shouldWait)
continue;
heuristics[ct.Name] = minMethod;
toCheck.Pop();
}
}
int result = 0;
foreach (var t in tasksToProcess)
result += heuristics[t.Name];
return result;
}In essence, this function traverses a spanning tree via depth-first search, and then returns up the tree to determine the total heuristic. To avoid infinite loops, I check if the task planner has previously encountered this task; if so, I under-estimate that the infinite loop will not trigger, and thus simply add zero to the cost. This has the downside that otherwise-empty infinite loops can cause the planner to spiral (as they are very low-cost tasks!), but so long as the designer avoids this hopefully-obvious pitfall, the heuristic works rather well.
The full source of this implementation can be found on my GitHub: https://github.com/aszecsei/Crimson/tree/master/Crimson/AI/HTN.