Solving risk-aware HTN planning problems: algorithmic, formal, and empirical results

Abstract

Actual, realistic domains are characterised by inherent uncertainty, compelling the development of planning strategies that enable the embracing of risks, where performing actions incurs costs, such as fuel and time, that cannot be predefined as constants during planning. In such domains, an agent’s perspective of desired plans is widened to not only accept plans with an average expected cost but also plans that comply with its attitude towards risk. For instance, in autonomous vehicle navigation, unforeseen obstacles and changing traffic conditions introduce significant risks that necessitate adapting driving tasks and route choices to comply with a particular risk attitude, ranging from extreme risk aversion to extreme risk seeking. Risk-aware Hierarchical Task Network (HTN) planning, a general framework that extends classical HTN planning with capabilities for embracing risk by leveraging established concepts from decision theory, is specifically developed to address planning problems in real-world domains. Here, we develop an approach that solves a subset of planning problems defined by that general framework, thereby surpassing the expressiveness of current approaches by allowing HTN planning agents to compute plans tailored to a particular risk attitude. We empirically evaluate the approach on four risk-involving HTN planning domains, perform an ablation study isolating the individual contributions of the approach, and compare the approach against four state-of-the-art HTN planners, including cost-unaware and cost-optimal. The results demonstrate the feasibility and expressiveness of the approach, showing that it is on par with established state-of-the-art HTN planners while producing plans that are meaningfully sensitive to risk. We also discuss open issues raised by the proposed approach, including their adaptability to solve other risk-aware HTN planning problems.