Building Exospecies AI: HTN Implementation Overview
The abstract HTN algorithm can be implemented in a bunch of different ways. We need a way to:
- 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
None of these seems like much of a challenge. They could be easily implemented in any language I can think of. So, why do academic researchers mostly end up implementing them in LISP or Prolog and taking a “logic programming” approach to their implementation? Nothing I could find in the literature or online described why this was the case. Some theories:
- Easier to prove things like completeness, decidability, complexity?
- Makes comparing planning approaches easier because this is the way other planners in the literature are built?
- Just the default thing AI researchers implement with?
- Some benefit to the “logic programming” approach that was not immediately obvious?
That final reason led me down the rabbit hole. Logic programming was always something I had meant to investigate and maybe this was a perfect use for it. I decided to make my prototype implementation using this approach and see if there was any benefit.
HTN Prolog-Based Architecture
I’m going to jump way ahead here and outline the finished product and then we’ll come back and go through each piece in turn to understand them and see how they are built.
The AI engine has a bunch of general purpose code that I will be open sourcing eventually to save others the trouble of having to figure it out. It has nothing to do with Exospecies, and for that matter nothing to do with Game AI, it can be used for lots of different applications. It is worth noting that it is all written in C++ so it can be more easily ported to different platforms. While it might sound like a lot of complicated stuff, it turns out the entire engine is not really that much code (1500 lines of C++ for the parser/compiler and 4800 for everything else, excluding blank lines and comments). A huge goal was to keep it simple, debuggable, understandable.
The HTN Planner engine does the work that was described in my previous blog entry about Heirarchical Task Networks. It creates a plan given a set of Methods, Operators and Facts. It also allows for “Axioms”, which are simply rules that are used like subroutines when writing HTNs (see next paragraph). This engine was modelled very closely on the work done by the [SHOP planner team] (http://www.cs.umd.edu/projects/shop/description.html), and is basically a SHOP planner.
The Prolog Resolver is a simple implementation of the Prolog language that is used for Method resolution, storing facts and for creating Axioms. Axioms are just Prolog rules that allow you to break out commonly used predicates so they can be reused. In HTN-land they are called “Axioms” since HTNs don’t have to be written in Prolog. There are open source Prolog engines out there that I could have used, but they are large code bases and implement all kinds of details required by the full Prolog language. I wanted something that was small, easy to understand, debug and customize. It doesn’t implement all of Prolog (a notable exclusion is functionality for lists), but it has everything I’ve needed for the Exospecies AI and is easy to extend. I found The Art of Prolog to be invaluable when implementing this. This writeup on Unification from the University of Iowa was also key. There is tons of information on the Internet about Prolog, the language, etc. including online Prolog compilers like SWISH that were a huge help.
The Prolog Rule Store is a pretty simple name/value pair store that stores Prolog rules and allows for making changes to them while tracking the differences to keep memory usage down. Because the HTN algorithm (and Prolog) backtracks when it fails, there can be a ton of copies of the Rule Store around with small changes.
The HTN Domain Store really is just a very simple name/value pair store, and it is just there for completeness. It is a tiny amount of code.
Finally, while it is possible to build Prolog and HTN objects like Rules, Methods, etc using code, it is much easier to write them in text, so I needed a parser/compiler that converts text into objects in the stores. I have a simple, template-based parsing engine that I’ve used for this (and lots of other Exospecies parsing tasks)
HTN Exospecies Specific Code
To actually use the engine for any purpose, you’ve got to do a few things:
- Write the Methods, Operators and Axioms that you’re going to use for whatever problem you’re trying to solve (e.g. the Exospecies AI)
- Transform the current state of your problem space (e.g. a current Exospecies game) in a form the engine understands
- Run the Planner
- Transform the output of the Planner into modifications to your problem space
All of this code forms the actual Exospecies AI:
Breaking It Down
The next many blog entries will walk through how these different pieces work and interrelate and how they are implemented. I’ll be sharing the code for the engine when I get a chance to clean it up.