Explaining goal conflicts in oversubscription planning

Abstract

Many real-world planning scenarios are characterized by oversubscription problems such as logistics with limited vehicle capacity and fuel restrictions, rover mission planning with time and energy constraints, but also your weekly activity and housework plans with insufficient free time. As a result, not all goals within the given task can be satisfied. Conventional approaches assume global optimization objectives, but it is often difficult to identify such objectives, and they are frequently in conflict with one another. An iterative planning approach is more suitable, wherein users consider sample plans and refine their preferences based on these plans. In such a setting, it is crucial to provide not only the plans themselves, but also explanations elucidating the conflicts between goals, preferences and objectives. This facilitates the user's understanding and enable them to identify satisfactory trade-offs. To this end, we introduce a form of contrastive explanation. We support user questions of the form ``Why is Q not achieved by the plan?'', by providing explanations through goals A that conflict with Q, i.e. ``To satisfy Q you have to forgo A''. We develop a set of algorithms that enable this form of explanation by computing the minimal unsolvable goal subsets based on goal space search and state space search. The evaluation of these algorithms shows that the required analysis in terms of scalability is comparable to that of oversubscription planning. Additionally, we conducted a large user study with crowdworkers (N=100 in each of 3 domains) to evaluate our framework. We compared users with and without access to explanations and found that the explanations enabled users to better identify trade-offs, indicating a better understanding of the planning task. Conflicts often arise due to resource or time constraints. We address the follow-up question "Why is A in conflict with Q?" by providing explanations based on the minimum relaxations of constraints under which the conflict resolves. We investigate two approaches to computing such explanations: specialized algorithms and compilation. A basic algorithm involves simply looping over all relaxations and computing the conflicts for each relaxation separately. We improve over this with two algorithms that exploit information such as reachable goal subsets and states across relaxations. Alternatively, we explore a compilation using specialized soft goals that identify each relaxation. In order to provide valuable explanations, it is essential that explanations cover aspects of the plans in which the user is interested. However, users often find it difficult to formalize their preferences. Therefore, we explore the potential of learning preferences from example plans, focusing on a single preference at a time and requesting that the user rates examples as either good or bad. Based on prior work on learning LTLf formulas, we then extract a preference from these examples. We conduct an empirical study of this approach in a classical planning setting, using hidden target formulas to simulate user preferences.

Viele reale Planungsszenarien sind durch Überschreibungsprobleme gekennzeichnet, z. B. die Logistik mit begrenzter Fahrzeugkapazität und Treibstoffbeschränkungen, die Planung von Rover-Missionen mit Zeit- und Energiebeschränkungen, aber auch die Planung der wöchentlichen Aktivitäten und Hausarbeiten bei unzureichender Freizeit. Infolgedessen können nicht alle Ziele erfüllt werden. Herkömmliche Ansätze gehen von globalen Optimierungszielen aus, doch ist es oft schwierig, solche Ziele zu identifizieren, und sie stehen häufig in Konflikt zueinander. Besser geeignet ist ein iterativer Planungsansatz, bei dem die Benutzer Musterpläne betrachten und ihre Präferenzen auf der Grundlage dieser Pläne verfeinern. Bei einem solchen Ansatz ist es von entscheidender Bedeutung, nicht nur die Pläne selbst, sondern auch Erklärungen zu den Konflikten zwischen Zielen, Präferenzen bereitzustellen. Dies erleichtert das Verständnis des Nutzers und versetzt ihn in die Lage, zufriedenstellende Kompromisse zu finden. Zu diesem Zweck führen wir eine Form der kontrastiven Erklärung ein. Wir unterstützen Nutzerfragen der Form ``Warum wird Q nicht durch den Plan erreicht''. Wir beantworten diese in Form von Zielen A, die mit Q in Konflikt stehen, d.h.``Um Q zu erfüllen, muss man auf A verzichten''. Wir entwickeln eine Reihe von Algorithmen, die diese Form der Erklärung ermöglichen, indem sie die minimalen unlösbaren Zielteilmengenauf der Grundlage von Zielraumsuche und Zustandsraumsuche berechnen. Die Evaluierung dieser Algorithmen zeigt, dass die erforderliche Analyse in Bezug auf Skalierbarkeit sich ähnlich wie Überschreibungsprobleme verhält. Darüber hinaus führen wir eine große Crowd-Worker-Benutzerstudie durch (N=100 in jeder von 3 Domänen), in der wir unser Framework evaluieren. Im Vergleich zwischen Nutzern mit und ohne Zugang zu den Erklärungen stellen wir fest, dass die Erklärungen es den Nutzern ermöglicht, Kompromisse besser zu erkennen, was auf ein besseres Verständnis der Planungsaufgabe hindeutet. Konflikte entstehen oft aufgrund von Ressourcen- oder Zeitmangel. Wir adressieren die Folgefragen ``Warum ist A im Konflikt mit Q?'' mit Erklärungen, die auf den minimalen Relaxierung der Beschränkungen basieren, unter denen die Konflikte verschwinden. Wir untersuchen zwei Ansätze zur Berechnung solcher Erklärungen: spezialisierte Algorithmen und Kompilierung. Der Basis-Algorithmus besteht darin, über alle Relaxierungen zu iterieren und die Konflikte für jede einzeln zu berechnen. Wir verbessern diesen Ansatz mit zwei Algorithmen, die Informationen wie erreichbare Zielteilmengen und Zustände über die Relaxierungen hinweg nutzen. Alternativ dazu erforschen wir eine Kompilierung unter Verwendung spezialisierter weicher Ziele, die die Relaxierungen identifizieren. Um nützliche Erklärungen geben zu können, ist es wichtig, dass die Erklärungen die Aspekte der Pläne abdecken, an denen der Nutzer interessiert ist.Allerdings fällt es den Nutzern oft schwer, ihre Präferenzen zu formalisieren. Daher untersuchen wir das Potenzial des Lernens von Präferenzen anhand von Beispielplänen. Wir konzentrieren uns jeweils auf eine einzelne Präferenz und fordern den Nutzer auf, Beispiele entweder als gut oder schlecht zu bewerten. Basierend auf früheren Arbeiten zum Lernen von LTLf-Formeln extrahieren wir dann eine Präferenz aus diesen Beispielen. Wir führen eine empirische Studie dieses Ansatzes in einer klassischen Planungsumgebung durch, wobei wir versteckte Zielformeln verwenden, um Benutzerpräferenzen zu simulieren.