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

These parameters are part of the Config structure (in C++) / class (in C#), in the Planner namespace. It can be provided to the planner object constructor.

Max Plan Length

You can significantly reduce the computational complexity of your planning problem by limiting the maximum search depth or - in other words - the 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 obtain long sequences of cheap actions while still getting some performance boost, especially in domains with large action cost disparities.

Iteration Limit

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.