Optimal path-planning under finite memory obstacle dynamics based on probabilistic finite state automata models

The v*-planning algorithm is generalized to handle finite memory obstacle dynamics. A sufficiently long observation sequence of obstacle dynamics is algorithmically compressed via symbolic dynamic filtering to obtain a probabilistic finite state model which is subsequently integrated with the navigation automaton to generate an overall model reflecting both navigation constraints and obstacle dynamics. A v*-based solution then yields a deterministic plan that maximizes the difference of the probabilities of reaching the goal and of hitting an obstacle. The approach is validated by simulated solution of dynamic mazes.