3
$\begingroup$

I'm new to pathfinding algorithms and trying to find a good or even optimal heuristic for the following problem:

Say you have a 3D square-lattice cuboid graph with randomly removed edges (with probability $p$). The cuboid has a finite cross section of $n \times m$ nodes and a potentially infinite layer length $l$. Starting on any node in the first layer the agent only has a finite lookahead of the next $w$ layers. At each step: i) you must choose the node in the next layer to move to (you can access nodes on your current layer for this), ii) the layer you were previously on is removed, iii) you view the new layer $w$ steps ahead.

The task is to find a heuristic or strategy that maximises the probability of reaching the end (or for infinite length, the number of layers down the lattice).

I have searched the literature for this sort of algorithm, but most A* based algorithms do not seem to fit the problem (please correct me if I'm wrong).

Are there any standard algorithms for this problem or some good AI protocols that would fit this problem? Even advice on going about designing my own algorithm would be greatly appreciated.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.