Goal Recognition Design (GRD) is the task of redesigning environments (either physical or virtual) to allow efficient online goal recognition. In this work we formulate the redesign problem as an optimization problem, aiming at early goal recognition. To this end, we use a measure of worst case distinctiveness (wcd), which represents the maximal number of steps an agent may take before his goal is revealed. With the objective ofminimizing wcd, we construct a search space in which each node in the space is a goal recognition model (one of which is the original model given as input) and one can move from one model to another by applying a model modification, chosen from a set of allowed modifications given as input. Our specific contribution in this work includes the specification of a class of modifications for which we can prune the search space using strong stubborn sets. Such positioning allows reducing the computational overhead of design while preserving completeness. We show that the proposed modification class generalizes previous works in goal recognition design and enriches the state-of-the-art with new modifications for which strong stubborn set pruning is safe. We support our approach by an empirical evaluation that reveals the performance gain brought by the proposed pruning strategy in different goal recognition design settings.

In the last years, pruning techniques based on partial order reduction have found increasing attention in the planning community. One recent result is that the expansion core method is a special case of the strong stubborn sets method proposed in model checking. However, it is still an open question if there exist efficiently computable strong stubborn sets with strictly higher pruning power than expansion core. In this paper, we prove that the pruning power of strong stubborn sets is strictly higher than the pruning power of expansion core even for a straight-forward instantiation of strong stubborn sets. This instantiation is as efficiently computable as expansion core. Hence, our theoretical results suggest that strong stubborn sets should be preferred to expansion core. Our empirical evaluation on all optimal benchmarks from the international planning competitions up to 2011 supports the theoretical results.