Replanning in risk aware HTN planning

Abstract

Hierarchical Task Network (HTN) planning is a powerful paradigm for modeling complex decision-making problems through task decomposition. However, traditional HTN planning assumes deterministic task costs, limiting its applicability in real-world scenarios where execution outcomes are uncertain. Risk-aware HTN planning introduces the use of utility theory to rank plans in domains with probabilistic costs, according to an agents risk attitude. However, the utility of a plan is only evaluated during initial planning. Agents with dynamic risk attitudes lack a mechanism to reevaluate the plan during execution, if unexpected high or low costs are incurred. We address this gap, by developing an approach for replanning in risk-aware HTN planning. We introduce a framework to model risk-aware replanning problems. Additionally, we present an algorithm to solve such problems, allowing agents to modify the plan during execution to represent their change in risk-attitude. We implement this solution in Risk Aware Replanning in JSHOP2 (RARJSHOP2), an extension of the Java Simple Hierarchical Ordered Planner 2 (JSHOP2), supporting probabilistic costs and automatic replanning, based on changes in plan utility due to incurred costs. Evaluation in an electric vehicle routing domain demonstrates that our approach successfully adapts plans according to changing risk preferences, though at increased computational cost. HTN-Planning ist ein mächtiges Paradigma zur Modellierung komplexer Entscheidungsprobleme durch Task-Decomposition. Traditionelles HTN-Planning geht jedoch von deterministischen Task-Kosten aus, was ihre Anwendbarkeit in realen Szenarien mit unsicheren Ausführungsergebnissen einschränkt. Risk-aware HTN-Planning erweitert dieses Modell mit der Anwendung von Utility-Theorie, um Pläne in Domains mit probabilistischen Kosten entsprechend der Risk-Attitude eines Agenten zu bewerten. Der Utility-Wert eines Plans wird jedoch ausschließlich während der initialen Planung berechnet. Agenten mit dynamischer Risk-Attitude fehlt ein Mechanismus, um den Plan während der Ausführung neu zu bewerten, wenn unerwartet hohe oder niedrige Kosten auftreten. Wir schließen diese Lücke, indem wir einen Ansatz zur Replanung im Kontext von risk-aware HTN-Planning entwickeln. Wir stellen ein Framework vor, das risk-aware Replanning-Probleme formal modelliert. Darüber hinaus präsentieren wir einen Algorithmus zur Lösung dieser Probleme, der es Agenten ermöglicht, den Plan während der Ausführung anzupassen, um Änderungen in ihrer Risk-Attitude zu berücksichtigen. Wir implementieren unsere Lösung in RARJSHOP2, einer Erweiterung des JSHOP2-Planners, die probabilistische Kosten sowie automatisches Replanning, basierend auf Änderungen in der Plan-Utility aufgrund angefallener Kosten, unterstützt. Die Evaluation in einer Domain zur Routenplanung für Elektrofahrzeuge zeigt, dass unser Ansatz Pläne erfolgreich an veränderte Risk-Attitudes anpasst, allerdings mit erhöhtem Rechenaufwand.