Which Actions Are Always Necessary in Fully-Observable Non-Deterministic Planning?

Résumé

Explaining the sequential action choices of an autonomous agent is essential for understanding the agent and learning from the agent. Given a goal-reaching action sequence in a non-deterministic environment, one important aspect of explaining action choices is deciding if the action choice is always necessary for the action sequence, or if it may be omitted under certain circumstances. Most works in explainable planning (XAIP) have been focused on explanation of action choices in deterministic environments as assumed by classical planning, and one widely used notion is causal link. In this work, we will apply the notion of causal link to justifying actions choices of a trace in fully-observable non-determinisitic (FOND) settings. We will also introduce a new notion -- the always-necessary actions of a trace -- and propose an approach that derives the always-necessary actions of a trace from the causal link justifications of action choices.