  The safe operation of an autonomous system is a complex endeavor, one pivotal
element being its decision-making. Decision-making logic can formally be
analyzed using model checking or other formal verification approaches. Yet, the
non-deterministic nature of realistic environments makes these approaches
rather troublesome and often impractical. Constraint-based planning approaches
such as Tumato have been shown to be capable of generating policies for a
system to reach a stated goal and abiding safety constraints, with guarantees
of soundness and completeness by construction. However, uncertain outcomes of
actions in the environment are not explicitly modeled or accounted for,
severely limiting the expressiveness of Tumato.
  In this work, we extend Tumato with support for non-deterministic outcomes of
actions. Actions have a specific intended result yet can be modeled to have
alternative outcomes that may realistically occur. The adapted solver generates
a policy that enables reaching the goals in a safe manner, even when
alternative outcomes of actions occur. Furthermore, we introduce a purely
declarative way of defining safety in Tumato, increasing its expressiveness.
Finally, the addition of cost or duration values to actions enables the solver
to restore safety when necessary, in the most preferred way.
