Building Exospecies AI: Inductor HTN Overview
Let’s go back to our original set of requirements for building an HTN:
- Represent the current State of the world
- See if a Method Condition is true for the current state
- Make an independent copy of the state for changes
- Allow Operators to change state
- Find zero or more Methods for a Task (which is just name matching)
- Find at most one Operator for a Task (which is just name matching)
- Maintain Operators and Tasks in a list
In the previous blog post, I show how you can easily represent the state of the world using Prolog. In this blog post, I’ll describe how we use the Prolog engine and the HTN Planner to implement these and illustrate it using our simple Taxi example. In the next blog post, I’ll show production code from Exospecies that does it for real in my game.
The code for the Inductor HTN Engine is available on GitHub. This blog post will describe how to use it. It is modeled very closely on a classic HTN engine called SHOP, and the work the SHOP team has done was instrumental in helping me understand how the HTN algorithm works and served as a specification for much of the HTN Planner part of this engine.
HTN Refresher
You may want to refer back to the HTN Overview for a conceptual overview. Here, I’m going to assume you know how they work and just describe how the InductorHtn is used and implemented. But for a really quick summary, HTNs have these parts:
- State of the world:
You are downtown. Taxi fare is $2. Bus fare is $1. Distance from downtown to park is 2Km. - Tasks: What can be done abstractly in the world (there may be several ways to do it!):
Travel from A to B. Walk from A to B. Pay a Driver X$. Wait for bus A at stop B. - Operators: How to accomplish abstract Tasks when they can “just be done” without further explanation. They actually modify the State of the world. If you are human these might be Operators:
Pay the driver $1, Ride #1 bus to the 'Park' stop. If you are a robot, these might be:Move stepper motor forward by 100 steps, turn on spotlight - Methods: How to accomplish abstract Tasks when they involve several steps or more detailed plans. They have a Condition for when they can be used and a set of Subtasks for how to accomplish them:
METHOD: "Travel from A to B" CONDITION: the weather is bad and you have bus fare, SUBTASKS: Wait for the bus at the bus stop, pay the driver, and ride it to the stop
Let’s walk through how each is implemented in InductorHtn using the Prolog engine as a base.
A Word About Syntax
The InductorHtn engine uses the standard Prolog syntax with one exception: I found the Prolog model of assuming that anything capitalized is a variable to be hard to read and constraining. So, there is an alternative in the parsers for choosing a different option: variables start with ? and the casing doesn’t matter. I’ll be using this syntax in this blog post. You can choose to use the normal Prolog syntax in the code if you choose to, however.
State of the World
State of the world: You are downtown. Taxi fare is $2. Bus fare is $1. Distance from downtown to park is 2Km.
As described in the previous blog post, Prolog is great at describing state so InductorHtn just uses it. Here is the state of our Taxi example written for InductorHtn, note that is just pure Prolog facts:
at(downtown).
weatherIs(good).
haveCash(12).
distance(downtown, park, 2).
atTaxiStand(taxi1, taxiBase).
Note that one of our requirements is to be able to “Make an independent copy of the state for changes” so that we can backtrack and revert to a state before an operator was applied if something fails. In the InductorHtn, this is simply a feature of the Prolog Rule Store. It is designed to be copied quickly and only record diffs to the state so it uses memory efficiently and is reasonably fast.
Rules/Axioms
Since I am using Prolog as the base language, Prolog Rules can be used in addition to facts like the above. These are sometimes called “Axioms” in HTN-land. For example, this Taxi Example rule is true if the distance between two points is “in walking distance”:
walkingDistance(?From, ?To) :- weatherIs(good), distance(?From, ?To, ?Distance), =<(?Distance, 2).
Operators
Operators: How to accomplish abstract Tasks when they can “just be done” without further explanation. They actually modify the State of the world. If you are human these might be Operators: Pay the driver $1, Ride #1 bus to the 'Park' stop. If you are a robot, these might be: Move stepper motor forward by 100 steps, turn on spotlight
Operators have a name, can take arguments, and add or remove state. We can represent all of this using the Prolog rule syntax above. To represent Operators, I simply required that the tail had a specific form: two terms del(...) and add(...) that contain the facts to add or delete from the database. Here’s our ride operator from the taxi example, which changes the location of the person (the at fact) and the vehicle (the at(?vehicle, ?Location) fact) from one place to another:
ride(?vehicle, ?a, ?b) :- del(at(?a), at(?vehicle, ?a)), add(at(?b), at(?vehicle, ?b)).
Note that this is a legal Prolog rule, so we can parse it using the Prolog parser, but we interpret it as an HTN operator when we see a rule that has only add and del terms. My engine will not unify the arguments in the add and del terms, it will just fill the variables in using whatever got passed into the head.
Methods
Methods: How to accomplish abstract Tasks when they involve several steps or more detailed plans. They have a Condition for when they can be used and a set of Subtasks for how to accomplish them: METHOD: "Travel from A to B" CONDITION: the weather is bad and you have bus fare, SUBTASKS: Wait for the bus at the bus stop, pay the driver, and ride it to the stop
Methods have a name, a condition, and a set of subtasks to execute. Again we can represent all of this using the Prolog rule syntax:
travel-to(?q) :- if(at(?p), walking-distance(?p, ?q)), do(walk(?p, ?q)).
Methods are simply Prolog rules that have two terms in the tail: if and do.
To meet our requirement of “See if a Method Condition is true for the current state” we simply do a normal Prolog Resolution of everything inside of the if(). If the unification succeeds, the Condition is true, and the substitutions from the unification are used to fill in the do() clause. Just like described in the HTN Overview.
HTN Planner
Once you’ve written down a set of HTN Axioms, Methods, and Operators and Facts, the engine that executes the HTN Algorithm described in the HTN Overview is called the Planner. All of the source code for the entire engine including the planner is on GitHub. Here’s the high-level architecture for reference:
Examples of how to use the Planner directly in C++ will be in a future post. For now, we’ll be using a sample “Interactive Mode” to illustrate how to use it.
Pulling it all together
Let’s write out the full taxi example using InductorHtn to see how it all works:
/* Axioms */
have-taxi-fare(?distance) :- have-cash(?m),
>=(?m, +(1.5, ?distance)).
walking-distance(?u,?v) :- weather-is(good),
distance(?u,?v,?w), =<(?w, 3).
walking-distance(?u,?v) :- distance(?u,?v,?w), =<(?w, 0.5).
/* Methods */
pay-driver(?fare) :-
if(have-cash(?m), >=(?m, ?fare)),
do(set-cash(?m, -(?m,?fare))).
travel-to(?q) :-
if(at(?p), walking-distance(?p, ?q)),
do(walk(?p, ?q)).
/* Use first() so we only hail one taxi */
travel-to(?y) :-
if(first(at(?x), at-taxi-stand(?t, ?x),
distance(?x, ?y, ?d), have-taxi-fare(?d))),
do(hail(?t,?x), ride(?t, ?x, ?y), pay-driver(+(1.50, ?d))).
travel-to(?y) :-
if(at(?x), bus-route(?bus, ?x, ?y)),
do(wait-for(?bus, ?x), pay-driver(1.00), ride(?bus, ?x, ?y)).
/* Operators */
hail(?vehicle, ?location) :-
del(), add(at(?vehicle, ?location)).
wait-for(?bus, ?location) :-
del(), add(at(?bus, ?location)).
ride(?vehicle, ?a, ?b) :-
del(at(?a), at(?vehicle, ?a)), add(at(?b), at(?vehicle, ?b)).
set-cash(?old, ?new) :-
del(have-cash(?old)), add(have-cash(?new)).
walk(?here, ?there) :-
del(at(?here)), add(at(?there)).
/* State */
distance(downtown, park, 2).
distance(downtown, uptown, 8).
distance(downtown, suburb, 12).
at-taxi-stand(taxi1, downtown).
at-taxi-stand(taxi2, downtown).
bus-route(bus1, downtown, park).
bus-route(bus2, downtown, uptown).
bus-route(bus3, downtown, suburb).
at(downtown).
weather-is(good).
have-cash(12).
Once you build the InductorHtn engine on GitHub, you will be able to run the engine in an interactive mode and play with this sample. The engine is not really designed to work interactively, it is meant to be used in production, but this makes it easy to play around with.
Be warned that the engine is designed to “FailFast” (i.e. abort the process) when it encounters programmer errors because that makes it easier to find issues in testing, but does make the interactive mode more challenging sometimes.
Here’s an example of running the built executable and loading the Taxi example on a Mac:
$ ./indhtn ../../Examples/Taxi.htn
Succesfully compiled ../../Examples/Taxi.htn as Htn document
Type a Prolog query (preceeding variables with '?') or
process a goal using 'goal(...terms...)' or
hit q to end.
?- goals(travel-to(suburb)).
>> [ { (wait-for(bus3,downtown), set-cash(12,11.000000000), ride(bus3,downtown,suburb)) } ]
In this case, the Htn planner decided that riding the bus was the only solution since going from downtown to the suburb is too far to walk and taxis are too expensive.
If we change our goal to uptown, we can get a couple of solutions (each separate solution is surrounded by {}):
?- goals(travel-to(uptown)).
>> [
{ (hail(taxi1,downtown), ride(taxi1,downtown,uptown), set-cash(12,2.500000000)) }
{ (wait-for(bus2,downtown), set-cash(12,11.000000000), ride(bus2,downtown,uptown)) }
]
Advanced Planner Features
You can skip to the next section if you’re just trying to get the gist of the engine. These are here for those wanting to learn the details.
try()
Often my AI had places where Method Subtasks should be “best effort”. Meaning: do this if you can, but if not, don’t fail. There are default ways to accomplish this, but they get complicated. For example, if you have a Method which is always best-effort, you could just add a final alternative that always succeeds if the others fail like this:
myMethod() :- if(...), do(...).
myMethod() :- if(...something else...), do(...something else...).
myMethod() :- if(true), do().
but what if myMethod isn’t always best effort? Well, you could have a “best-effort wrapper” for it and call the right one for the behavior you want:
myMethod() :- if(...), do(...).
myMethod() :- if(...something else...), do(...something else...).
bestEffortMyMethod :- if(), do(myMethod()).
bestEffortMyMethod :- if(true), do().
However, that’s a bunch of extra goop to do something I ended up doing a lot. So instead, I just added the try() operator that can be used on a Subtask:
myMethod() :- if(...), do(...).
myMethod() :- if(...something else...), do(...something else...).
/* Using myMethod in a "best-effort" mode
someMethod() :- if(...), do( try(myMethod) ).
One simple example is the very top level Method of the AI called pickStrategy. It “tries” several different stages in priority order, but doesn’t want to fail completely just because one stage doesn’t work:
"pickStrategy(?Player) :-
if(),
do(
try(attackSupplyUnitAttackers(?Player)),
try(attackSupplyUnit(?Player)),
...
anyOf and allOf Methods
Imagine a method that attacks an enemy if one is in range like this simplified example:
attackEnemy() :- if(isInRange(?Unit)), do(attack(?Unit)).
If there are multiple units in range, the default behavior of the Planner would be to put each alternative into a different solution (refer back to the HTN Overview if you don’t remember how this works). In some cases like the Taxi example, this is what you want. In this example, it is not: I want all units attacked in a single solution.
One way to accomplish this is using Prolog Lists. You’d create a list of all the units and then process the list and attack them all. That’s a lot of goo for something that happens a lot. So, a simple alternative is to mark this Method with anyOf or allOf like this:
attackEnemy() :- anyOf, if(isInRange(?Unit)), do(attack(?Unit)).
or
attackEnemy() :- allOf, if(isInRange(?Unit)), do(attack(?Unit)).
anyOf tells the Planner to group all of the solutions found for this Method into one solution instead, and to treat it as succeed as long as at least one do() succeeds.
allOf is the same but requires that all alternatives found for the if() clause succeed in the do() clause.
else Methods
Just like Prolog, the HTN Planner will always try all alternative Methods, even if the first succeeds, and generate different solutions for all of them. So, for the example below, if both alternatives for myMethod() succeed, you are going to get two solutions back. In Prolog, you can use the cut (i.e. “!”) operator to prevent this behavior, but it wasn’t quite right for the case when you want only one of these methods to succeed:
myMethod() :- if(...), do(...).
myMethod() :- if(...something else...), do(...something else...).
Should I treat a cut in the if as meaning don’t run the other? In the do? It just didn’t seem right.
Instead, I introduced the else keyword that can be used like a standard if...then...else:
myMethod() :- if(...), do(...).
myMethod() :- else, if(...something else...), do(...something else...).
myMethod() :- else, if(...something else else...), do(...something else else...).
Only one of these methods will run. Note that they can be used like this too:
myMethod() :- if(...), do(...).
myMethod() :- else, if(...something else...), do(...something else...).
myMethod() :- if(...another...), do(...another...).
myMethod() :- else, if(...another else...), do(...another else...).
In this example, you could get two solutions: one from the first two methods and one from the second.
Using Inductor HTN In A Game
There are three steps to using this engine in a real world game:
- Convert the game state into Prolog Facts
- Write the HTN Axioms, Methods, and Operators that implement the AI and use these Facts
- Convert the output of the HTN engine into changes, moves, or whatever makes sense in the game
In the next blog post, I’ll walk through an example using a simple strategy game.