Complete and Optimal Robust Planning Against Nature

Abstract

Planning and acting in environments in which "nature" can modify the environment by exogenous events presents a challenge for intelligent agents that have to make sure their plans can still be executed. In principle, events of nature might disrupt the agent's plan, or worse, cause damage to the agent. In this paper, we build upon a recent concept of robust plans that are guaranteed to be successfully executed even if nature acts adversarially. The advantages of robust plans involve better understandability and not needing to sense the state of the environment during plan execution. We address the gap in prior work by presenting two methods for generating robust plans that are complete and guarantee optimality if an admissible heuristic is used with the A* algorithm. The methods are evaluated on five domains.