[This is the next post in a series on building an AI to play Exospecies. previous post]
The abstract HTN algorithm can be implemented in a bunch of different ways. We need a way to:
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:
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.
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 helper rules. 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. 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)
To actually use the engine for any purpose, you’ve got to do a few things:
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.