Building Exospecies AI: Using Prolog to Manage HTN State
We are going bottom’s up on the architecture for the HTN Planner in this series of posts. The previous post described the Parser/Compiler and this post will describe the Prolog Resolver and Rule Store.
All the code to use the Inductor Prolog Engine and run the examples is available on Github.
Prolog is part of the Inductor HTN Engine because “the literature” describes HTN’s in terms of first order logic and uses rules and facts in much the same way as Prolog does. Seemed like the obvious route to take. It meets the requirements for implementing an HTN very nicely.
If you are trying to build an “AI Planner” that isn’t specific to a domain, you need a way to represent the state of the world that can cover just about anything. Turns out Prolog is perfect for this. A Prolog program is just a database of facts and logical rules about the facts. You represent your domain as a Prolog database and then ask it questions called “queries”. If you know SQL, it is conceptually very similiar to how SQL databases work: facts would be SQL tables, rules would be SQL queries.
Let’s go through a Prolog crash course and show how it can be used to meet the first requirement for building an HTN from a previous blog post:
1. 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
Requirement 1: Using Prolog to represent the State of the world
Prolog is all about representing state, this is where it excels. It is a very simple way to represent widely disparate domains because it doesn’t understand what you are modeling at all, it just deals with facts and relationships between them.
Prolog Facts
Recall the state from our Taxi example from the HTN Overview:
Location: downtown.
Weather: good.
Cash: $12.
TaxiFare: $2.
DistanceFrom(Downtown,Park): 2Km.
TaxiLocation(Taxi1) : TaxiBase.
These could be represented in Prolog like this:
at(downtown).
weatherIs(good).
haveCash(12).
distance(downtown, park, 2).
atTaxiStand(taxi1, taxiBase).
Everything in Prolog is a “Term”, and a Term is simply a name (e.g. distance) and a set of 0 or more arguments, separated by commas, surrounded by parenthesis (e.g. (downtown, park, 2)). Every fact ends with a period. Note that arguments can be terms too. The fact:
happy(weatherIs(good), haveCash(100)).
might mean “you are happy when the weather is good and you’ve got $100”. Real simple. Each term declares a fact that is true about the world you are modelling. In Prolog, you only describe things that are true in the world, you don’t have to describe all the things that are false (the list would be large).
The magic of Prolog is that it doesn’t care what the facts are - they could be made up words or random letters (they are just meaningless strings to Prolog). You choose what they are based on what is meaningful for you reading and using the program. This makes it very flexible for describing anything.
Prolog Fact Queries
Once you have declared a bunch of facts, you can ask Prolog questions about them using variables (which have capital letters) in place of arguments. For example (? marks where I am giving input to Prolog and ==> marks the Prolog responses in these examples):
at(downtown).
weatherIs(good).
haveCash(12).
distance(downtown, park, 2).
atTaxiStand(taxi1, taxiBase).
? at(Where)
==> Where = downtown
Prolog looked at all the facts I have declared and tried to match them with my query at(Where) by filling in the variable Where (which is a variable because it is capitalized). When it found a match, it returned what got shoved into Where.
If we make it a bit more interesting by adding distances to more than one place, we can run more interesting queries:
at(downtown).
weatherIs(good).
haveCash(12).
distance(downtown, park, 2).
distance(downtown, groceryStore, 1).
distance(downtown, uptown, 5).
atTaxiStand(taxi1, taxiBase).
? distance(downtown, Where, Distance)
==> Distance = 2, Where = park
==> Distance = 5, Where = uptown
In this example, we specified one argument (downtown) and used two variables (Where and Distance). This allowed Prolog to match more than one fact.
In addition to simple matching like the above examples, Prolog can do queries like:
happy(person(name(rick, borne))).
happy(person(name(jane, doe))).
happy(person(name(ricky, ricky))).)
? happy(person(name(rick, LastName)))
==> LastName = borne
==> LastName = doe
==> LastName = ricky
? happy(Person)
==> Person = person(name(rick, borne))
==> Person = person(name(jane, doe))
==> Person = person(name(ricky, ricky))
? happy(person(name(Name, Name)))
==> Name = ricky
The last one in particular is interesting because it uses the same Variable twice and thus only matches names that have the same first and last name.
To run any kind of Query, Prolog performs two steps:
- Find any facts that have the same name and number of terms as the query
- Do a process called “Unification” to match names with arguments
How Unification works is described below.
Unification
All of this is done using a concept called Unification. Unification takes two expressions and tries to find a way to assign something to their variables so that they are equal. The result is called a “Substitution” since it tells you what to substitute for what to make both sides equal.
The best write-up I’ve found on Unification are from University of Iowa, Stackoverflow and a summary from a hairy academic chapter on Unification. The gist of it is that you take two sides of an equation and try to figure out what to stick in the variables to make them equal.
So if we have the fact happy(rick). and we run the query happy(Who), it is equivalent to trying to solve the equation happy(rick) = happy(Who) for the variable Who. Setting Who = rick solves it, so that’s your answer. Obviously that’s an easy one.
The general algorithm is this:
Given two terms to unify: T1 and T2
Start with:
Stack initialized with a single entry {T1 = T2}
T1 will be called "Left" below since it is on
the left side of the "=" and T2 will be called
"Right"
Solution initialized to empty
while(Stack.size > 0)
Pop the top equation from the stack
if Left (the left side of the '=') is a variable
and it does not appear in Right: replace all
occurrances of the Left variable with Right,
in both Solution and Stack, add Left = Right to
Solution. Example: "A = 5" becomes "5 = 5" and
all the places where "A" appeared in the solution
and stack now become "5"
else if Right is a variable and it does not appear
in Left: substitute all occurrances of the
Right variable with Left, in both Solution
and Stack, add Right = Left to Solution.
Same as the previous rule, just reversed like
"5 = A"
else if Left and Right are both the same variable
continue
else if Left and Right are both the same constant
continue
else if Left and Right have the same number of
Arguments > 0, push each matching argument on
the stack one by one
else
Fail
If we didn't fail, the solution contains the
Substitution that is the solution that Unifies
the two equations
This surprisingly simple algorithm is a key part of how Prolog Queries are evaluated.
Prolog Rules
The truth is that Prolog programs are really lists of “Rules” which are just declarations of things that are true. The “Facts” we’ve been working with so far are just the simplest kind of rule that declare “X is true”. When writing Prolog code, though, this can get unweildy fast.
Think about how to model something like “Walking Distance”. We said in our Taxi example that the best route is walking “if it is nice out and the distance is <= 2km”. How would you declare a bunch of facts that handle this? You could try to list a fact with all possible distances like:
walkingDistance(weatherIs(good), .000001).
walkingDistance(weatherIs(good), .000002).
walkingDistance(weatherIs(good), .000003).
etc.
But this is obviously ridiculous. Prolog “Rules” allow us to combine Facts and Variables to easily handle cases like this. Our example would be more succinctly stated as:
walkingDistance(From, To) :- weatherIs(good), distance(From, To, Distance), =<(Distance, 2).
The part before the :- is called the “Head”, and the part after is called the “Tail”. The rule is declaring that the fact named by the Head walkingDistance(From, To) is true if everything in the Tail is true. The commas in the Tail are interpreted as And, so they must all be true.
Note that I’ve used a special Term =<in the tail. Prolog has many built-in Term names like this that do classic math so you don’t need to create them yourself. In fact, you usually couldn’t write them in any reasonable way.
If we now ask Prolog this query:
? walkingDistance(downtown, park)
==> true
Prolog tells us it is true. It works like this:
- Prolog looks through all of its rules to find the Head of a rule with the same name (
walkingDistance) and the same number of arguments as our query (2) - It Unifies our query (as we described in the above section on Unification) with that Rule Head to get a list of Variable Substitutions
- It then takes these Substitutions and fills them into each Term in the Tail
- Finally, it repeats the same process with each of these terms to see if they are true. Being “true”, just means they are a Fact in the database, i.e. A rule that has no Tail like
weather(good). - If, at the end of all substitutions, all of them are true, then our query is true. The Substitutions are returned as the answer. If any one of them is false, the query fails.
(A detailed walkthrough of this is in the next section)
Because of step 4, you can compose rules out of rules. This way of building rules and running queries is the fundamental thing that Prolog does and is a surprisingly powerful way to describe and then ask about things. It is called SLD Resolution (“linear resolution” with a “selection function” for “definite clauses”) (Kowalski and Kuehner 1971).
Note that you can also use Variables with Rules and Prolog will tell you all the answers that would have worked, which is kind of mind-blowing:
at(downtown).
weatherIs(good).
haveCash(12).
distance(downtown, park, 2).
distance(downtown, groceryStore, 1).
distance(downtown, uptown, 5).
atTaxiStand(taxi1, taxiBase).
walkingDistance(From, To) :- weatherIs(good), distance(From, To, Distance), =<(Distance, 2).
? walkingDistance(downtown, Where)
==> (Where = park)
==> (Where = groceryStore)
Evaluating a Prolog Rule
Let’s go through this step by step to really understand what is going on:
- Find the rule
walkingDistancewhich has the same name and number of arguments as our query:walkingDistance(From, To) :- weatherIs(good), distance(From, To, Distance), =<(Distance, 2). - Unify each argument of
walkingDistance(From, To)with our query argumentswalkingDistance(downtown, Where). This results in settingFrom = downtownandTo = Where. Note that the second assignment is setting a variable to another variable! This allows Prolog to keep sending the variable down the line until it gets resolved, as you’ll see. - Fill in Tail Variables with the assignments we just made. The Tail becomes
weatherIs(good), distance(downtown, Where, Distance), =<(Distance, 2) - Repeat the process with each of the Tail terms to see if they are true. Start with
distance(downtown, Where, Distance). It turns out there are three rules that have the same name and argument count:distance(downtown, park, 2). distance(downtown, groceryStore, 1). distance(downtown, uptown, 5).This means we might have 3 different things that are true! We have to explore each alternative and return only the ones that actually are true. To do this, Prolog will “break into 3 parallel universes” and run each one as an independent branch using the same algorithm. If it gets to a Rule that fails, it ignores it and tries the rest (called “Backtracking”. Let’s follow just the first branch by unifying:
distance(downtown, Where, Distance)with the first rule we found:distance(downtown, park, 2). Unification adds these new Substitutions (Where = parkandDistance = 2) to the set we are carrying along with us. The assignmentdowntown = downtowndisappears as a result of Unification (see the Unification algorithm above). So now we have:From = downtown,To = Where,Where = parkandDistance = 2. - The next Tail term is
=<(2, 2)The classic math operators like=<,>,*,+, etc are all built into Prolog and behave as you’d expect, including doing Unification. They act like magic rules where the laws of math determine if they are true or false. They are built into the system since there isn’t really a logic-based way to write this kind of rule. This rule resolves totrueand doesn’t add any new Substitutions to our set. - We were able to resolve all the terms to true, so this branch of the solution evaluates to true. Now we return the variables that were requested in the original Query from the set of assignments we calculated. This is a “Solution”. Since the only variable in the original query was
Where, that is all that is returned.? walkingDistance(downtown, Where) ==> (Where = park)
And that is the story of how this query worked. The other two answers are done the same way by continuing down the branches we didn’t explore above. Note that the branch where Where=uptown fails and doesn’t return a result since it doesn’t satisify the clause =<(Distance, 2) :
? walkingDistance(downtown, Where)
==> (Where = park)
==> (Where = groceryStore)
It is important to remember that Prolog doesn’t actually understand any of the strings like walkingDistance. It could just as easily been ooeyGooey(bloob, Franly) and work the same way to Prolog. They are just opaque symbols and you are declaring which are true, sometimes by composing them with other opaque symbols. This is what makes Prolog so powerful, you can be stating facts about anything, as long as it is true in your domain and makes sense to you.
OK, now we’re in a position to model our entire Taxi example using Prolog Facts and Rules and we’ve fullfilled our first requirement: “Requirement 1: Using Prolog to represent the State of the world”. Here is the state from the Taxi example in my HTN Overview, now written in Prolog:
Original Pseudocode:
Location: downtown.
Weather: good.
Cash: $12.
TaxiFare: $2.
DistanceFrom(Downtown,Park): 2Km.
TaxiLocation(Taxi1) : TaxiBase.
Rewritten in Prolog:
at(downtown).
weatherIs(good).
haveCash(12).
taxiFare(2).
distance(downtown, park, 2).
taxiLocation(taxi1, taxiBase).
As a richer example, here is the actual state from the current build of Exospecies. I represent the entire tile-based map simply by declaring that there is a tile at a location like tile(0,0). Nothing more is needed! Most of the rest of the facts are describing the abilities that units have, and the current position and state of the actual units in play in this game. Only the last two sections actually change on a given turn, the rest are static.
// Map Information that doesn't change per turn
tile(0,0).tile(1,0).tile(2,0).tile(3,0).tile(4,0).tile(5,0).tile(6,0).tile(7,0).
tile(0,1).tile(1,1).tile(2,1).tile(3,1).tile(4,1).tile(5,1).tile(6,1).tile(7,1).
tile(0,2).tile(1,2).tile(2,2).tile(3,2).tile(4,2).tile(5,2).tile(6,2).tile(7,2).
tile(0,3).tile(1,3).tile(2,3).tile(3,3).tile(4,3).tile(5,3).tile(6,3).tile(7,3).
tile(0,4).tile(1,4).tile(2,4).tile(3,4).tile(4,4).tile(5,4).tile(6,4).tile(7,4).
tile(0,5).tile(1,5).tile(2,5).tile(3,5).tile(4,5).tile(5,5).tile(6,5).tile(7,5).
tile(0,6).tile(1,6).tile(2,6).tile(3,6).tile(4,6).tile(5,6).tile(6,6).tile(7,6).
tile(0,7).tile(1,7).tile(2,7).tile(3,7).tile(4,7).tile(5,7).tile(6,7).tile(7,7).
startingPosition(Player1, tile(0,0)).
startingPosition(Player2, tile(7,7)).
// Information about units that doesn't change per turn
player(Player2). enemyPlayer(Player1).
action(Worker,Move,6). moveSpeed(Worker,2). action(Worker,Attack,13).
attackDistance(Worker,Attack,1,1,0). attackDamage(Worker,Attack,61).
action(Worker,Tunnel,6).
action(Warrior,Move,3). moveSpeed(Warrior,1). action(Warrior,Attack,30).
attackDistance(Warrior,Attack,2,3,0). attackDamage(Warrior,Attack,75).
supplyUnit(Queen). action(Queen,Move,3). moveSpeed(Queen,1). action(Queen,Attack,10).
attackDistance(Queen,Attack,1,1,0). attackDamage(Queen,Attack,30). action(Queen,Transport,24).
action(Drone,Fly,13). moveSpeed(Drone,4). action(Drone,Attack,14).
attackDistance(Drone,Attack,1,1,0). attackDamage(Drone,45).
supplyUnit(Dynamo). action(Dynamo,Move,3). moveSpeed(Dynamo,1).
action(Dynamo,Attack,10). attackDistance(Dynamo,1,1,0).
attackDamage(Dynamo,30). action(Dynamo,Transport,24).
action(Inducer,SlugTrail,1). action(Inducer,Move,25). moveSpeed(Inducer,5).
action(Inducer,Attack,14). attackDistance(Inducer,Attack,1,1,0).
attackDamage(Inducer,Attack,45). action(Inducer,Galvanize,28).
perTickDamage(Inducer, SlugTrail, 5).
action(Larva,Move,3). moveSpeed(Larva,1). action(Larva,Attack,10).
attackDistance(Larva,Attack,1,1,0). attackDamage(Larva,Attack,30).
action(Vamp,Move,9). moveSpeed(Vamp,2). action(Vamp,Attack,10).
attackDistance(Vamp,Attack,1,1,0). attackDamage(Vamp,Attack,30).
action(Vamp, TempTeleport, 26). tempTeleport(Vamp, 6, -1).
action(Maxwell,Move,3). moveSpeed(Maxwell,1). action(Maxwell,Artillery,42).
attackDistance(Maxwell,Artillery,1,6,1). attackOdds(Maxwell,Artillery,0.2).
attackHitDamage(Maxwell,Artillery,61).
action(Bender,Move,8). moveSpeed(Bender,2). action(Bender,Attack,10). attackDistance(Bender,Attack,1,1,0).
attackDamage(Bender,Attack,30).
initialLife(Worker, 66). initialLife(Warrior, 100). initialLife(Queen, 53).
initialLife(Drone, 53). initialLife(Larva, 33). initialLife(Maxwell, 100). initialLife(Bender, 53). initialLife(Vamp, 53).
initialLife(Inducer, 66).
// Map information that represents tiles that get added by units, can change every turn
chokeTile(tile(6,6), 1). chokeTile(tile(6,5), 1). chokeTile(tile(6,4), 1).
chokeTile(tile(6,3), 1).
filledChokeTile(tile(6,5), Player1, SlugTrail).
filledChokeTile(tile(6,4), Player1, SlugTrail).
filledChokeTile(tile(6,7), Player1, SlugTrail).
// Actual units on the map, can change every turn
unit(Inducer1, Inducer, Player1). life(Inducer1, 66).
at(Inducer1, tile(7, 4), 0). unitIdle(Inducer1).
attackUnitDamage(Inducer1, Attack, 45).
unit(Vamp1, Vamp, Player2). life(Vamp1, 53). at(Vamp1, tile(6, 5), 0).
unitIdle(Vamp1). attackUnitDamage(Vamp1, Attack, 30).
unit(Vamp2, Vamp, Player2). life(Vamp2, 53). at(Vamp2, tile(6, 4), 0).
unitIdle(Vamp2). attackUnitDamage(Vamp2, Attack, 30).
unit(Vamp3, Vamp, Player2). life(Vamp3, 53). at(Vamp3, tile(6, 7), 0).
unitIdle(Vamp3). attackUnitDamage(Vamp3, Attack, 30).
unit(Queen1, Queen, Player1). life(Queen1, 53).at(Queen1, tile(0, 0), 0).
unitIdle(Queen1). teleportUnits(Queen1, 10).
attackUnitDamage(Queen1, Attack, 30).
What Have We Learned?
The thing that was amazing about using Prolog for storing the state for the Exospecies AI was that the startup cost was incredibly low (after I wrote a Prolog compiler…). Prototypes could be written crazy quick since I could just declare things to be true and not have to write a bunch of code to store them, access properties about them, group them into collections, etc. Kind of like creating SQL Databases, I did more thinking and designing than writing, which was refreshing.
Next in the blog series, I’ll be describing how the other 6 requirements were met using the Prolog engine and how it got integrated with the Hierarchical Task Network engine.
Using the Inductor Prolog Engine
All the source for just the Inductor Prolog Engine is available on Github. It is a very lightweight Prolog compiler that can be used standalone, even if you are not building a Hierarchical Task Network. Note that it is not a standards compliant, fully featured Prolog compiler. It implements just what was needed for Exospecies, but is easy to extend. For more details, look through the readme on Github.