[RELEASED] Fluid Hierarchical Task Network planner [AI] [FREE]

I wrote an HTN planner in C# based around the builder pattern. Maybe someone can find it useful. I'll continue to expand on this and eventually build visual tools, but for now its code-only.

https://github.com/ptrefall/fluid-hierarchical-task-network

It's the same technique of AI used in Horizon Zero Dawn, Killzone 2/3, Transformers: Fall of Cybertron, and others. It is very expressive in terms of how you can design your decision making, you can apply future prediction and thus plan into the future, while it remains predictable in terms of which decision branches are prioritized, similar to behavior trees.

Its also very performant, supports partial planning, allowing you to pause a plan and continue where you left off after the partial plan is completed.

 

That looks pretty awesome! Thanks for making this open source.

I only had a chance to briefly skim over it, the domain builder struck my eye:

• It looks like it uses strings for references/IDs?
• It mostly looks like data and a fair bit of boilerplate. Wouldn't it be more suitable to store this in some sort of markup files or ScriptableObjects? Unless I'm getting something wrong here.

Nice to see the trunk thumper example put into practice, by the way

 

Hey Christoph, thanks for having a closer look!

Strings are only used for the ability to debug a d look up the name of a task, it's not actually used by the planner. A domain simply consist of tasks where a compound task can contain one parent and multiple subtasks, and a primitive task can contain one parent.

The builder pattern is not required to use this, the planner works directly on the domain.

Serialization would only really be necessary to support external tools. In C# one could have a tool that built dlls of domains, or store them through serialization. The last bit is not yet integrated, but I plan to add support for it in an extension library. The core library will remain independent of unity.

For now this remains a code-only library by design, but it will be relatively easy to add visual tools on top of it.

And yes, we need more Trunk Thumpers!

 

How interesting. I was thinking about writing a HTN solution not long ago (we're using GOAP for our current project). It's nice to see this, even though it still needs some work (proper documentation with proper examples, for starters).
One thing I'm wondering is whether this supports multithreading out of the box.

 

Thank you for your interest! Yes, this is a project that will evolve over time, with proper examples and improved documentation.

The hierarchical nature of HTN doesn't lend itself well to multi-threading, but it shouldn't be a problem to run each planner instance on separate threads. The planner only interact with the world state of the context you feed it each time you want to find a plan.

The Planner.cs is not designed with multi-threading in mind, so you'd want to make a version of it that would be.

That said, usually the sensory part of the AI is the most important to multi-thread, as that's where the heavy lifting usually is. With early reject opportunities and partial planning in HTN, its footprint can be very light.

I'll get around to test multi threading eventually myself, but as you pointed out, adding a simple example is more pressing at the moment.
Its WIP:

 

Heyo,

Unsure if you've seen otto (Unity's AI Planner): https://forum.unity.com/threads/ai-planner.649246/#post-4390798

 

Unity's planner is a GOAP/STRIPS planner, which starts with the goal and plans backward to the start, using typically A* to find a shortest path through a set of actions.

An HTN planner is more like a dynamic behavior tree, in that it starts at present time at the start of a predefined hierarchy of tasks and finds a valid list of actions by searching from the root of the hierarchy, in a predictable order. It still has similarities to GOAP in how it uses preconditions and effects to guide the planner into a predicted future.

HTN takes strengths from both behavior tree's careful design power and the dynamic adaptability in planners like GOAP. It also opens for more optimization opportunities than a planner that starts from the goal.

GOAP can find more paths through a problem domain, and be more emergent, but at the potential cost of design ability and performance. There is a very insightful interview with Troy Humphreys over on ai game dev, where he goes into how they transitioned from HFSM to GOAP to HTN, and their reasoning behind it.

I think they all have their own strengths and weaknesses, and it takes knowledge and research, and a good portion of personal preference when choosing which techniques work best for the different problem domains in your game.

 

Thanks for the quick response. I understand that the hierarchical nature of HTN limits its potential for multithreading, but the same is true for GOAP and the implementations I tried still use multiple threads. Now, I didn't look into how exactly they split the work, so I don't know. What I'm very much interested in is how your solution scales as more and more agents are added.
That being said, you mentioned that the sensory part of your AI usually needs the most processing time. That makes optimization relatively straightforward, even on a single thread. Here are some approaches from the top of my head:

1. Don't update your sensors each frame
2. Use scheduling to make sure you spread the sensor updates of different agents out so they don't all update together
3. Reduce the update frequency, if the agent is far away

 

@ptrefall_unity thank you for the quick response. I'm unsure why it matters that much which direction is used for search (so what if we start from goal and get to the current point?). I'll need to dig a little bit as my understanding of HTN vs GOAP is basically HTN is just a bunch of tasks grouped together into a bigger task. So you stick in the pre-condition for the first task inside the bigger task and post-condition at the end of performing the bigger task. Which to me sounds like something that could be done with GOAP. But looks like my understanding is wrong. So thanks for clarifying and also for releasing this HTN tool for free (I've purchased Behavior Designer and would have gladly purchased what you were offering at a reasonable price if Unity didn't have the GOAP sln). Will read up more on HTN vs GOAP thanks!

 

I have to recommend Troy Humphreys talk on modular sensory systems http://twvideo01.ubm-us.net/o1/vault/gdc2016/Presentations/Humphreys_Troy_Nuts_and_Bolts.pdf&ved=2ahUKEwjbiYf5sPDhAhUDdJoKHYvvB9gQFjABegQIBhAB&usg=AOvVaw37tvdKfy7qt5aXsBaufFRf

The nice thing about making sensory modular, is that you can tick different aspects of sensory at different frequencies, effectively letting you balance performance vs responsiveness.

My guess toward GOAP multi-threading is that they simply run an instance of the planner in a background-thread. You could do the same with the HTN planner. You feed in a context and get out a plan/queue of actions. This is easy enough to make isolated to the point it can be threadsafe.

 

When a planner is searching forward, and the search is in total order, we can record the traversal of the planner and store it. Next time the planner runs we can verify that our new plan is better than the previous traversal record, and if we come to a point in the record with a worse score than was recorded last time, we know the new plan can't possibly beat the old plan, and reject it early.

Another aspect to this is it allows us to do partial plans. That is, we can design long complex plans if need be, but we can pause the planner when it reaches a certain point, e.g. where it's at a task that moves the agent from A to B, and then we continue the plan once we get there if it's still valid.

Yet another thing is that search is quite different in HTN than in GOAP. Where you use A* pathfinding in GOAP, you simply just iterate the decomposition hierarchy in HTN, depth first, because you know that the first valid plan you find will be the best plan by design.

 

@ptrefall_unity thank you! Now I see it's pretty similar to a Behavior Tree. I can see it has some uses. Hope you'd continue working on it

 

Thank you, that is definitely my intention. I hope to be able to set aside enough spare time soon to finish a couple examples and move on to a unity integrated toolset for domain design and visual runtime debugging.

 

Do you already have something in mind for the visual debugging? If you want to go down the route of visualizing it with a graph, maybe you could make use of Unity's own GraphView API (the one they use for vfx and shader graphs).
Can you give a rough estimate as to when the examples will be done? At this point the development of our game's AI hasn't progressed far enough for us to commit to ReGoap yet. So I'd be open to switching to your solution provided it's better. And I'd like to look at some examples to find that out.

 

I'd say it's a bit early to declare this production ready. I should be able to have a few examples ready this week or next week at the latest. I'm doing this in my spare time and it's not very easy to predict how much spare time I have available.

I'm definitely planning on looking into the new UI Elements.

 

Hmmm. What would you consider to be the biggest roadblocks that prevent it from being declared production ready?

 

Just a lack of usage. Of course, usage is needed to get it to production quality. Just as long as you're aware of that I'd be happy to support you in the endeavor.

 

Thanks. I'll wait and have a look at your examples then.

 

I released a simple text adventure example of the planner. Unity examples are still work in progress and will be released soon.

 

Just wanted to inform you that your Discord invite links are invalid.

 

Ah, thank you for pointing that out. The link should not expire now. https://discord.gg/MuccnAz

 

I released an example for use of Fluid HTN with Unity.
https://github.com/ptrefall/fluid-troll-bridge/

 

Are you going to add a visual editor (like in Behavior Designer, NodeCanvas)?
Because it's not handy without visual implementation at all.

 

Hi hottabych! Thank you for checking out the library!

The core of this library will always support code-only, and never be strictly bound to a visual editor, but visualization is definitely on the todo list. The value of doing it like this, is that we get to test the planner itself early, by more people than just me, and it has uncovered things I never could have on my own.

Visualization will be added in multiple stages. First I will implement visualization of the code-built domains, and runtime debugging of plans and domain decomposition.

Visualized authoring will come after that, and feed on everything we learn from the iterative process.

 

Hello @pal_trefall, I just stumbled across Fluid HTN while researching a suitable AI design pattern for my game. You reference Humphreys a lot, and he had written an article in Game AI Pro about HTN (chapter 12). I actually read the next chapter, Hierarchical Plan-Space Planning, which is closer to what I need for my game, and was wondering what you think about adapting your HTN solution to this sort of specialized planning pattern. Thanks!

 

Hi @aer0ace, very interesting article. I have actually not read it. I will get back to you when I've had the chance to. My HTN solution is quite flexible (I treat it as simply a decomposition planner, and it already has GOAP sequence with A* and Utility select extensions, among others). It will be interesting to see whether there's something here to improve or extend Fluid HTN further, so thank you for bringing it to my attention!

 

I'm sorry to say I am simply swamped with work at the moment and have not had a chance to look at the article much at all yet @aer0ace. Fluid HTN already has A* planning support though via its GOAP extension, like I mentioned earlier, so I would be surprised if this was not feasible.

Do you have any tldr; on the article, or any points of view, on what that article solves that makes it stand out? Gut feeling says that if my GOAP extension supported branching (currently it will only pick shortest path through a flat subset of actions), that might be the solution the article is talking about, blending GOAP and HTN even more than I already have. Extracting proper decomposition scoring through such a process is a lot more complex however, but I believe it's possible.

Even though its been my intention for a good while, I've not yet made any examples on group AI with Fluid HTN, but it should be very capable. When you have full control of the order of priority through the decomposition hierarchy, its easy to control, for the individual, which selfish behavior should precede "orders" from the group AI.

 

Is this project still being built on? and would this work for a group of AI's instead of just single AI's like GOAP?

 

The project is being maintained and supported, but there is no active development right now. The core of the framework is stable, but it could do with some debug visualization to aid development/usage and more examples of use.

Fluid HTN is very flexible and should be able to extend to what you need. It can even use the GOAP technique to find the shortest path through a sub-set of actions and return a sequence that can be used in a larger plan. You can also set up slots in the decomposition hierarchy that can get branches stitched on during runtime. So Fluid HTN is very powerful and flexible.

You're welcome to join the Discord channel linked in the Readme if you have more questions, and we can talk further there.