Planners: performance considerations

Iterative computation

Planning can be really computationally heavy and to make its use practical in video games, we certainly don’t want to take too much CPU time when computing the plan. To address this issue, our planner works in an iterative manner - this means that you can easily spread the computation over multiple frames.

Memory Pool

In the C++ version of Grail, planners utilize a preallocated memory pool for all object parameters. It significantly improves performance due to reduced memory fragmentation.

Important parameters

Max depth

You can significantly improve computational complexity of your planning problem by limiting maximum search depth or - in other words - maximum plan length. In most video games, there will be no need to consider plans longer than a few actions and setting a reasonable depth limit will cost you nothing while drastically shrinking the search space graph.

Max plan cost

Another way to limit search depth is to limit maximum total plan cost. This way you can still obtain long sequences of cheap actions while still getting some performance boost, especially in domains with large action cost disparities.

Max iteration count

Sometimes finding a plan is simply not possible and there’s no point searching the state space on and on. Grail’s planner gives you an option to limit maximum iteration count after which planning will be considered a failure.