Suppose a player wishes to move on a square lattice graph without diagonals. Vertices on this graph have a chance (fixed or time-dependent, e.g. cumulative density of X~Po(t) with range n to infinity) to become a "point of interest". Upon visiting such vertex, it will revert to a "normal" vertex, which can become a "point of interest" again. The player wishes to visit all "points of interest", but travelling through the least number of edges.
The Elevator Algorithm seems to solve a simplified version of this problem, where the "player" can only travel in two directions.
My guess is that, if the player starts from the center of the lattice graph, the optimal choice would be either try to walk over all the vertices exactly once for multiple rounds (Hamiltonian path maybe?) or to stand still. However, this guess only works for the fixed-chance scenario.
Thus, I wish to know how an optimal strategy would be derived, given a certain number of lattices are already "points of interests", especially when vertices convert to "points of interests" with a time-dependent chance.