Search Unity

[RELEASED] Fluid Hierarchical Task Network planner [FREE]

Discussion in 'Assets and Asset Store' started by pal_trefall, Apr 18, 2019.

  1. pal_trefall

    pal_trefall

    Joined:
    Feb 5, 2019
    Posts:
    40


    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.
     
    Last edited: Apr 29, 2019
    eterlan, nirvanajie, TonyLi and 3 others like this.
  2. one_one

    one_one

    Joined:
    May 20, 2013
    Posts:
    493
    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 ;)
     
  3. pal_trefall

    pal_trefall

    Joined:
    Feb 5, 2019
    Posts:
    40
    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!
     
    one_one likes this.
  4. TheSniperFan

    TheSniperFan

    Joined:
    Jul 18, 2013
    Posts:
    686
    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.
     
  5. pal_trefall

    pal_trefall

    Joined:
    Feb 5, 2019
    Posts:
    40
    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:
     
    one_one likes this.
  6. Mohamed-Anis

    Mohamed-Anis

    Joined:
    Jun 14, 2013
    Posts:
    81
    one_one likes this.
  7. pal_trefall

    pal_trefall

    Joined:
    Feb 5, 2019
    Posts:
    40
    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.
     
  8. TheSniperFan

    TheSniperFan

    Joined:
    Jul 18, 2013
    Posts:
    686
    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
     
  9. Mohamed-Anis

    Mohamed-Anis

    Joined:
    Jun 14, 2013
    Posts:
    81
    @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!
     
  10. pal_trefall

    pal_trefall

    Joined:
    Feb 5, 2019
    Posts:
    40
    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.

     
    Arkade likes this.
  11. pal_trefall

    pal_trefall

    Joined:
    Feb 5, 2019
    Posts:
    40
    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.

     
    Last edited: Apr 27, 2019
    Mohamed-Anis likes this.
  12. Mohamed-Anis

    Mohamed-Anis

    Joined:
    Jun 14, 2013
    Posts:
    81
    @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 :)
     
    pal_trefall likes this.
  13. pal_trefall

    pal_trefall

    Joined:
    Feb 5, 2019
    Posts:
    40
    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.
     
    one_one likes this.
  14. TheSniperFan

    TheSniperFan

    Joined:
    Jul 18, 2013
    Posts:
    686
    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.
     
  15. pal_trefall

    pal_trefall

    Joined:
    Feb 5, 2019
    Posts:
    40
    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.
     
  16. TheSniperFan

    TheSniperFan

    Joined:
    Jul 18, 2013
    Posts:
    686
    Hmmm. What would you consider to be the biggest roadblocks that prevent it from being declared production ready?
     
  17. pal_trefall

    pal_trefall

    Joined:
    Feb 5, 2019
    Posts:
    40
    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.
     
  18. TheSniperFan

    TheSniperFan

    Joined:
    Jul 18, 2013
    Posts:
    686
    Thanks. I'll wait and have a look at your examples then.
     
    pal_trefall likes this.
  19. pal_trefall

    pal_trefall

    Joined:
    Feb 5, 2019
    Posts:
    40
  20. TheSniperFan

    TheSniperFan

    Joined:
    Jul 18, 2013
    Posts:
    686
    Just wanted to inform you that your Discord invite links are invalid.
     
  21. pal_trefall

    pal_trefall

    Joined:
    Feb 5, 2019
    Posts:
    40
  22. pal_trefall

    pal_trefall

    Joined:
    Feb 5, 2019
    Posts:
    40
    Last edited: May 4, 2019
    nirvanajie, TheSniperFan and one_one like this.
  23. hottabych

    hottabych

    Joined:
    Apr 18, 2015
    Posts:
    99
    Are you going to add a visual editor (like in Behavior Designer, NodeCanvas)?
    Because it's not handy without visual implementation at all.
     
  24. pal_trefall

    pal_trefall

    Joined:
    Feb 5, 2019
    Posts:
    40
    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.
     
    hottabych likes this.