Hierarchical goal networks (HGNs) provide a framework for goal-directed planning by decomposing high-level goals into ordered subgoals. While prior work has examined non-determinism for hierarchical planning (specifically, HTNs), scant work studies how HGNs can help in stochastic settings. We introduce a formalism for probabilistic HGN planning with action-insertion semantics, enabling probabilistic planners to incorporate domain knowledge from goal decomposition methods. We design and evaluate two UCT-based algorithms for solving probabilistic HGN planning problems: an asymptotically optimal approach and a compressed, shared-value approach that optimizes separately for each goal within the goal-subgoal hierarchy. We compare our two UCT-based HGN search algorithms experimentally on modified benchmark domains from the FOND HTN literature. Our results demonstrate that on larger problems, the compressed search converges more quickly and outperforms the asymptotically optimal search. This suggests that HGNs can be effective in probabilistic planning, and compression may yield better performance on large problems in anytime settings with stochastic action outcomes.

Landmarks—conditions that must be satisfied at some point in every solution plan—have contributed to major advancements in classical planning, but they have seldom been used in stochastic domains. We formalize probabilistic landmarks and adapt the UCT algorithm to leverage them as subgoals to decompose MDPs; core to the adaptation is balancing between greedy landmark achievement and final goal achievement. Our results in benchmark domains show that well-chosen landmarks can significantly improve the performance of UCT in online probabilistic planning, while the best balance of greedy versus long-term goal achievement is problem-dependent. The results suggest that landmarks can provide helpful guidance for anytime algorithms solving MDPs.

We consider behavior of agents in a long-term multiagent coopetitive setting in which agents vary their cooperative and competitive stances over time. Using the game ofDiplomacyas a testbed, we study how successful agents vary their coopetitive behavior, developing a new “style of play” (SoP) characterization of player behavior. We assess five novel SoP hypotheses about successful behavior. We propose two algorithms to automatically compute an agent’s SoP vector and describe the important factors in this computation. As an agent’s SoP depends on the game state and its perception of threat, we develop a novel “means, motive, and opportunity” (MMO) model of threat and show that we can predict threats effectively using this model. We provide novel insights into how agents should behave to more successfully achieve their goals in long-term coopetitive settings.