Communicating Safety of Planned Paths via Optimally-Simple Explanations

Artificial intelligence is often used in path-planning contexts. Towards improved methods of explainable AI for planned paths, we seek optimally simple explanations to guarantee path safety for a planned route over roads. We present a two-dimensional discrete domain, analogous to a road map, which contains a set of obstacles to be avoided. Given a safe path and constraints on the obstacle locations, we propose a family of specially-defined constraint sets, named explanatory hulls, into which all obstacles may be grouped. We then show that an optimal grouping of the obstacles into such hulls will achieve the absolute minimum number of constraints necessary to guarantee no obstacle-path intersection. From an approximation of this minimal set, we generate a natural-language explanation which communicates path safety in a minimum number of explanatory statements.