>>11341955I think the best approach would be to use a greedy algorithm.
Since the cat has an equal chance to move up or down as well as to move left and right, evidently from a purely statistical standpoint, the cat should return and hover around where it started to move in the movement frame. When I speak about a movement frame, I am referring to a certain frame of consecutive moves. Due to the 25%-25%-25%-25% (assumed) probabilities, we can make the aforementioned claims. I know this is not going to be the case all of the time, but it is the best assumption we can make.
Thus, when implementing your greedy algorithm, always move toward where the cat currently is. This should almost always yield the best result due to the assumption that the cat should always statistically linger around where it currently is. In order to determine this, one needs to consider the case where the robot knows what the cats next move is in contrast to not knowing where the cats next move is. I think the only differentiating factor in the algorithm would be that in the former case the robot would need to use the cats next position when calculating its next movement; the latter need not use this information and should purely be based on the cats current position.
When determining where the robot should move next, as long as the movement brings the robot closer to the cat then the movement is efficient. This is an inherent property of the Pythagorean theorem which shows that when one decomposes a hypotenuse into two orthogonal components which each lie parallel to a standard coordinate systems basis vectors, if one can only move along these basis vectors, then the shortest path (number of moves) which effectively creates a radial displacement from the origin is the sum of the magnitudes of the two components.
If I were to implement it, personally I would move toward the larger of the two aforementioned components. An example to demonstrate how I would handle it:
