On Eventual Applicability of Plans in Dynamic Environments with Cyclic Phenomena

Planning and acting in dynamic environments deals with non-deterministic events that might change the state of the environment without consent of the agent. In the worst case, some events might cause the agent to become ``trapped'' in a dead-end state, which in practice might mean damage or destruction of the agent. Presence of non-deterministic events often considerably increases the number of alternatives that might occur in a single step and hence traditional non-deterministic planning techniques might not scale.

In this paper, we address a class of problems where non-deterministic events represent ``cyclic phenomena''. If they interfere with the agent, they might be dangerous for it (e.g. ships cruising through the area of AUV operations). We present techniques that initially analyse the problem whether it falls within this class by considering the notion of event reversibility and if so, these techniques generate a plan such that encountered unsafe states, in which the ``cyclic phenomena'' might interfere with the agent, can be eventually crossed without any risk of ``falling'' into a dead-end state. Our approach is evaluated in the AUV and Perestroika domains.