Bridging the Gap between Structural and Semantic Similarity in Diverse Planning

Diverse planning is the problem of finding multiple plans for a given problem specification, which is at the core of many real-world applications.
For example, diverse planning is a critical piece for the efficiency of plan recognition systems when dealing with noisy and missing observations. Providing diverse solutions can also benefit situations where constraints are too expensive or impossible to model.
Current diverse planners operate by generating multiple plans and then applying a selection procedure to extract diverse solutions using a similarity metric.
Generally, current similarity metrics only consider the structural properties of the given plans. We argue that this approach is a limitation that sometimes prevents such metrics from capturing why two plans differ.
In this work, we propose two new domain-independent metrics which are able to capture relevant information on the difference between two given plans from a domain-dependent viewpoint. We showcase their utility in various situations where the currently used metrics fail to capture the similarity between plans, failing to capture some structural symmetries.