Jump to content
  • Advertisement
Sign in to follow this  
SunnyDays

hierarchical task network planner using Multithreading

This topic is 683 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've been thinking on what consequences would arise on Hierarchical task network planner if it's used with Multi-threading


HTN: http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter12_Exploring_HTN_Planners_through_Example.pdf



So far my thoughts are the following


Pros:

- Planners can find the list of tasks faster using multithreading

Cons:

- When changing the world state, it needs to lock the variable so that race condition would not happen.


I've tried google around, but no luck in finding HTN planners being used in a multicore engine.
Please let me know if there's an efficient way to do this.

Share this post


Link to post
Share on other sites
Advertisement

It doesn't sound like a good candidate for multithreading to me. Tree-style problems are not great for multithreading - they start off with fewer tasks than threads, then quickly have more tasks than threads, and yet still have strong dependencies between the tasks.

 

But you don't need to lock the world state more than once as you don't need to change it - each part of the plan would need a copy of the world state because it works with hypothetical states, each based on changes caused by earlier parts of the plan.

 

If you can get a single copy of the current world state at the start of the process, then no problem - you can just work from there in an AI thread.

 

You might want to consider the possible ramifications of having a planner that returns sooner on faster PCs; does that mean the game gets a little bit harder the more powerful your machine is?

Share this post


Link to post
Share on other sites

Pros:
- Planners can find the list of tasks faster using multithreading
Cons:
- When changing the world state, it needs to lock the variable so that race condition would not happen.

Modern engines don't really do threading that way any more. You wouldn't have an "AI thread" that runs concurrently with a "game thread". Instead, you have one thread per hardware core and you break up all of your code into a directed acyclic graph of dependent tasks, which are executed across all threads automatically. There's no locking, as jobs are only scheduled to execute when their dependencies have already completed... But yes, you will compute plans faster, which is the point of using every core to execute the game code :D
Once you start writing code in this 'job DAG' style, then all of your code is magically multithreaded in the same way -- the actual problem domain (AI planning, physics, graphics, game rules) doesn't matter, it's all just jobs in a job-graph.

Share this post


Link to post
Share on other sites

That diagram is missing the arrow pointing back at the "Sensors"  as a planner working on anything complex may ask for additional data as it proceeds (or to synthesized interpreted data from a particular viewpoint).

 

Another 'higher level' function can be detecting WHEN the situation being analysed  has changed TOO MUCH  and requires abandoning investigating solutions (when they no longer are (or may not be) relevant).    

 

There  also can be persistent state of partial analysis data (preserved to save on recalculation/reculling rejected paths of solution investigation).   Usually with that there is some kind of 'generational' backtracking mechanism which periodically restarts the analysis from scratch (or by degree) to handle dynamic situations.

Share this post


Link to post
Share on other sites
Modern engines don't really do threading that way any more.

 

Oh, how I wish any of the engines I've worked with in the last 10 years were 'modern'. ;)

Edited by Kylotan

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!