The Hierarchical Task Network (or HTN) planner is an increasingly popular technique for implementing automated planning. It is a fast, expressive, easy to manage, and very powerful method of designing and managing artificial intelligence for games.
Unlike more common reactive techniques such as Behavior Trees, and more like other planners such as Goal-Oriented Action Planning (G.O.A.P.), HTN planners are capable of reasoning about the future state of the game and returning a planned sequence of actions that can be used to satisfy an end goal. Unlike G.O.A.P. and other STRIPS-style planners, which use a complex search strategy like A* or other bottom-up search technique to find an optimal solution to satisfy a goal state, HTN planners use a straightforward (and fast) top-down forward-decomposition model to derive a solution, and its hierarchical nature results in a significantly higher degree of directorial control.
Hierarchical Task Networks have been described by experts as "a great blend of planners and behavior trees, giving developers great control over their behaviors yet leveraging runtime computation to get more robust behaviors with less authoring" (reference), and the HTN Planner for Unity builds upon these strengths by providing a visual graphical designer for authoring HTN graphs in the Unity Editor.
NOTE: Some of the terminology used here may differ somewhat from more traditional Hierarchical Task Network planner terminology, differing especially from the terminology used by purely academic researchers. While we've made an attempt to adhere to the more familiar terminology whenever possible, we have chosen to use different terms in some cases where we felt those terms would be more descriptive in the context of a visual designer.
Blackboards in the HTN Planner are a collection of key/value pairs which can be thought of as the agent's representation of the current world state. You can store all sorts of things here - the agent’s own personal knowledge (like how much ammo is remaining, whether the agent can see enemies, etc), as well as information communicated from other agents (a squad commander might give this agent orders, for example, and those orders might be stored in the agent’s Blackboard) or systems (such as visual sensory systems).
Storing these values in the Blackboard allows the planner to use them for decision making, as well as predict future world state as the result of actions (the planner keeps its own internal copy of the blackboard which can be modified by tasks while generating a plan, representing changes made to the world state as actions are executed).
The example Blackboard in the image above stores several pieces of information of various types, each with a name that can be used in the planner or elsewhere to set or retrieve specific values of interest.
The Task Network Graph is where all of the decision-making logic is defined. Although not strictly required, it is often helpful to think of your graph design in terms of “goals” and “methods”. The top level compound nodes in the graph would be the “goal” nodes - each one represents a goal the agent wants to satisfy, ordered top to bottom by priority (the top goals are more important than the bottom goals). Each goal contains one or more methods that can be used to accomplish that goal. Subtasks can be arbitrarily nested to any depth, providing great flexibility in defining how a goal can be accomplished.
In the example below we have a "goal" of Kill Enemy, which describes five different ways that it might try to achieve that goal, depending on the current world state when planning occurs. Note that the Kill Enemy node has a decomposition mode of SelectOne, meaning that it will select only one of the subtasks to include in the plan.
The Task Network Planner is a MonoBehaviour which is attached to your agent object, and is responsible for taking the Task Network Graph and producing plans based on the current Blackboard state as well as executing those plans.
The Agent Script is a class that you will define that provides the actual code that will be called by the HTN Planner. The HTN Planner editor will use reflection on this class to determine which functions are available when presenting a list of tasks to choose from.
To create a new Blackboard, select the menu option at Tools > StagPoint > HTN Planner > Create Blackboard. You will be asked for a location to save the Blackboard asset.
Blackboards are stored as a separate .asset file in order to facilitate the sharing of Blackboards amongst any number of runtime agents. This asset serves as a "Blackboard Definition" which defines all of the variables that will be available at runtime, as well as the default values of those variables. This "Blackboard Definition" will then be cloned at runtime when any new Task Network Planner instance is activated.
This Blackboard can be edited directly by selecting the asset file in the project explorer, or can be edited inside of any Task Network Planner inspector when that component is selected.
Similar to Blackboards, the Task Network Graph is stored as a separate .asset file, but unlike the Blackboard asset there will only ever be one instance of the Task Network Graph in memory. This reduces memory requirements as well as load times and does not slow down instantiation of new agents.
To create a new Task Network Graph asset, select the menu option at Tools > StagPoint > HTN Planner > Create Hierarchical Task Network. You will be asked for a location to save the Task Network Graph.
Each Task Network Graph is specific to both an agent type and a Blackboard definition, so you will need to provide a reference to the agent script that will contain the functions that are to be executed by the planner, as well as a reference to the correct Blackboard asset.
Compound tasks may contain any number of compound or primitive subtasks. The planning process is recursive. Compound tasks are recursively decomposed until the planner finds a sequence for which all of the tasks are primitive. There are two ways that compound tasks can be decomposed, which is specified in the editor as the Decomposition Mode.
When decomposed, each subtask will be evaluated in turn, and only if all subtasks have their qualifying conditions met will the subtasks be added to the plan. For those who are familiar with Behavior Trees, it can be useful to think of a this mode as being conceptually similar to a Sequence node in a behavior tree.
In the following example image, you can see that the Patrol node has three subtasks: ChooseBridge, NavigateToBridge, and CheckBridge. If any of those subtasks had a condition that could not be satisfied by the planner, then the entire Patrol branch would be excluded from the plan.
This mode differs from the SelectAll mode in that rather than simply fail if one of the subtasks cannot be satisfied, it will continue to iterate through its subtasks until it finds one that can be satisfied. For those who are familiar with Behavior Trees, it can be useful to think of a this mode as being conceptually similar to a Selector node in a behavior tree.
In the example image above, the Reload or Switch Weapon node will first see if the conditions for the Reload task can be satisfied, and if so it will add that task to the plan and stop searching this branch. If there are no reload clips available, it will then see if the conditions for the Switch To Pistol task can be satisfied. If not, it will then proceed to the Switch to Melee task. If none of the subtasks have conditions that could be satisfied, then the entire branch is excluded from the plan.
Primitive tasks are used to execute functions in your agent script. To add a new Task, right click on any composite node and select the task from the list.
You will be presented with a list of all of the action functions that have been defined in your agent script. If the function requires parameters, the HTN Graph Editor will provide an area under the Function heading to enter those parameters, as in the following snapshot:
A GOTO node simply redirects the planner to any arbitrary compound node in the task network graph. This can be very useful for implementing recursion, and can retain modularity in the planning domain.
To add a new GOTO node, right-click any compound task and select GOTO from the menu:
To specify which node the GOTO should redirect the planner to go to, drag and drop that node onto the arrow that is to the right of the GOTO node, as shown below. Note that you may only drop compound nodes on this area.
The image below illustrates one way that a GOTO node might be used.
In this example, assume the following world state: $WsCanSeeEnemy = true, $WsTrunkHealth = 0
The agent can see the enemy, so the planner checks the [Do Attack] method. The [Do Attack] method fails the condition check because the agent does not have a trunk to use as a weapon, so the planner moves on to the [Bring Me A Shrubbery] method, which directs the planner to check the [Obtain Trunk] task. If [Obtain Trunk] succeeds, the planner will then revisit the [Do Attack] method, which will now succeed due to WsTrunkHealth having been set by the [Obtain Trunk] method.
To select any node in the tree, click on it with the mouse button. To select multiple nodes, you may either hold down the CONTROL key while clicking additional nodes, or click with the mouse on any blank part of the editing canvas and drag the mouse so that the resulting selection rectangle intersects with the nodes you wish to select, as in the image below:
To remove any node, you can right-click the node with the mouse and select the Delete option from the context menu. Alternatively, you can press the DELETE key to remove all selected nodes.
You can rearrange the order of the nodes in the tree by dragging a node from its current location to another location in the tree. As you drag the node over other nodes, you will be shown a blue line that indicates where the node will be located when you release the mouse button, as shown below:
You may also change the order of a node when it is selected by pressing the CTRL-UpArrow key to move the node up or the CTRL-DownArrow key to move the node down.
Each task in the tree may have any number of required conditions that indicate whether that task may be included in the plan. If the condition cannot be satisfied, the task will not be included.
HTN Planner has several ways for you to specify such conditions. To add a precondition to any node, click on the plus button in the Pre-Conditions section of the node inspector as shown below.
Probably the most common precondition involves checking the value of a given Blackboard variable. One way to do so is to select the blackboard variable from the context menu. Note that this menu will only show variables that are already defined - You must define the blackboard variable before you can use it as a condition.
Once you've selected the desired blackboard variable, you will be given choices for how to evaluate that variable. These choices change according to the datatype of the blackboard variable. For instance, a boolean variable will only present the option to check whether it is true or false:
By contrast other data types may present different options, like the float variable below:
The ability to control the priority of individual branches of the tree can be tremendously useful, and provides a convenient way to determine whether a plan generated during periodic replanning should be interrupt the currently active plan or whether the currently active plan should be continued.
HTN Planner uses the position of the nodes in the tree to define an implicit "in order priority", where tasks higher in the tree are considered to have a higher priority than ones that come later. This method provides the best simplicity and readability for the AI designer, and is easier to manage than explicit priorities that might have to be individually tweaked and can be prone to error.
What has been described so far is "business as usual" in terms of generating an initial plan, since all tasks are processed in top-to-bottom order until a valid plan can be generated.
The real power of this system comes into play during replanning, when the newly generated plan is compared to the currently-running plan. If the newly-generated plan is derived from tasks that are closer to the top of the tree than the current plan, the current plan will be aborted and the new plan will begin executing. If the new plan's tasks come from closer to the bottom than the current plan's tasks, the new plan will be discarded and the current plan will continue executing.
This can be illustrating using the following example:
For this example, let us assume that the initial world state is: $Orders = Patrol, $EnemyIsVisible = false, $AmmoCount = 16
The initial plan generation will result in Patrol [ SelectPatrolPoint(), NavigateToPoint() ], and the bot will begin patrolling. It is important to note that the NavigateToPoint() task will take some amount of time, during which the TaskNetworkPlanner component will be performing periodic replan attempts.
If an enemy becomes visible before the Patrol plan has had time to finish, we can assume that the bot's visual sensor system (or some other process) would set the $EnemyIsVisible blackboard variable to true. During the next replan attempt, the planner would generate a new plan consisting of the Fire at Enemy [ Reload(), FireWeapon(), TakeCover() ] tasks. Because the Fire at Enemy task is higher in the tree than the current Patrol task, the Patrol plan will be aborted and the Fire at Enemy plan will be executed immediately.
If, on the other hand, the planner had generated a plan whose task was lower in the tree than Patrol, it would be discarded because it was considered to be of lower priority than the current plan, and the bot would continue patrolling.
HTN Planner includes an automatic planning strategy that should be sufficient for most needs, and this functionality is enabled by default. It allows you to specify whether or not the planner will automatically replan, and if so at what interval it should do so.
If you would like the planner to periodically check to see if a better plan is available, then check the Auto Replan checkbox. Set the Auto Replan Frequency value to the number of seconds between replanning attempts.
When replanning, the Task Network Planner component will attempt to generate a new plan which has a higher priority than the current plan. As mentioned previously, HTN Planner supports specifying plan priority implicitly through the task's position in the graph. If a plan could be generated, but has a lower priority than the plan currently being executed, the plan will be discarded.
Note that if AutoReplan is turned on, the planner will also automatically replan immediately whenever the current plan has finished running.
If you would prefer to handle replanning yourself (perhaps to handle important changes in the world state, for example) then you can simply call the TaskNetworkPlanner.GeneratePlan() function directly. If a new plan can be successfully generated, this function returns a new TaskNetworkPlan instance, which can then be passed to the TaskNetworkPlanner.ExecutePlan() function.
You can easily detect changes to the agent's world state by attaching an event handler to the Blackboard.StateChanged event. This event is raised whenever any of the Blackboard's variables have changed. In the C# example below, we are only interested in whether a single variable has changed, but this example can be extrapolated to include any number of important variables:
blackboard.StateChanged += ( state, key ) =>
if( key == "IsUnderAttack" )
var plan = planner.GeneratePlan();
if( plan != null )
planner.ExecutePlan( plan );