This paper presents preliminary ideas of our work for auto- mated learning of Hierarchical Goal Networks in nondeter- ministic domains. We are currently implementing the ideas expressed in this paper. Many domains are amenable to hierarchical problem-solving representations whereby complex problems are represented and solved at different levels of abstraction. Examples include (1) some navigation tasks where hierarchical A* has been shown to be a natural solution solving the navigation problem over different levels of abstraction BID29 BID66 ; (2) dividing a reinforcement learning task into subtasks where policy control is learned for subproblems and combined to form a solution for the overall problem BID9 BID10 BID12 ; (3) abstraction planning, where concrete problems are transformed into abstract problem formulations, these abstract problems are solved as abstract plans, and in turn these abstract plans are refined into concrete solutions BID31 BID4 ; and (4) hierarchical task network (HTN) planning where complex tasks are recursively decomposed into simpler tasks BID8 BID68 BID15 BID43 . These paradigms have in common a divideand-conquer method to problem solving that is amenable to stratified representation of the subproblems.Among the various formalisms, HTN planning has been a recurrent research focus over the years. An HTN planner formulates a plan using actions and HTN methods. The latter describe how and when to reduce complex tasks into simpler subtasks. HTN methods are used to recursively decompose tasks until so-called primitive tasks are reached corresponding to actions that can be performed directly in the world. The HTN planners SHOP and SHOP2 have routinely demonstrated impressive gains in performance (runtime and otherwise) over standard planners. The primary reason for these performance gains is because of the capability of HTN planners to exploit domain-specific knowledge BID67 . HTNs provide a natuCopyright c 2019, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. ral knowledge-modeling representation for many domains , including military planning BID38 BID40 , strategy formulation in computer games BID23 BID22 , manufacturing processes BID47 BID61 , project planning BID62 BID63 , story-telling BID6 , web service composition , and UAV planning BID20 Despite these successes, HTN planning suffers from a representational flaw centered around the notion of task. A task is informally defined as a description of an activity to be performed (e.g., find the location of robot r15) (e.g., the task "dislodge red team from Magan hill" in some adversarial game) and syntactically represented as a logical atom (e.g., (locate r15)). (e.g., "(dislodge redteam Magan)"). Beyond this syntax, there is no explicit semantics of what tasks actually mean in HTN representations. HTN planners obviate this issue by requiring that a complete collection of tasks and methods is given, one that decomposes every complex task in every plausible situation. However, the knowledge engineering effort of creating a complete set of tasks and methods can be significant BID17 . Furthermore, researchers have pointed out that the lack of tasks' semantics make using HTNs problematic for execution monitoring problems BID13 BID14 ). Unlike goals, which are conditions that can be evaluated against the current state of the world, tasks have no explicit semantics other than decomposing them using methods.For example, suppose that a team of robots is trying to locate r15 and, using HTN planning, it generates a plan calling for the different robots to ascertain r15's location. While executing the plan generate a complex plan in a gaming task to dislodge red team from Magan hill, the HTN planner might set a complex plan to cutoff access to Magan, surround it, weaken the defenders with artillery fire and then proceed to assault it. If sometime while executing the plan, the opponent abandons the hill, the plan would continue to be executed despite the fact that the task is already achieved. This is due to the lack of task semantics, so their fulfillment cannot be checked against the current state; instead their fulfillment is only guaranteed when the execution of the generated plans is completed.Hierarchical Goal Networks (HGNs) solve these limitations by representing goals (not tasks) at all echelons of the hierarchy BID56 . Hence, goal fulfillment can be directly checked against the current state. In particular, even when a goal g is decomposed into other goals (i.e., in HGN, HGN methods decompose goals into subgoals), the question if the goal is achieved can be answered directly by checking if it is valid in the current state. So in the previous example, when the opponent abandons the hill, an agent executing the plan knows this goal has been achieved regardless of how far it got into executing the said plan.Another advantage of HGNs is that it relaxes the complete domain requirement of HTN planning BID57 ; in HTN planning a complete set of HTN methods for each task is needed to generate plans. Even if the HGN methods are incomplete, it is still possible to generate solution plans by falling back to standard planning techniques such as heuristic planning BID24 to achieve any open goals. Nevertheless, having a collection of well-crafted HGN methods can lead to significant improvement in performance over standard planning techniques BID59 .When the HGN domain is complete (i.e., there is no need to revert to standard planning techniques to solve any problem in the domain), its expressiveness is equivalent to Simple Hierarchical Ordered Planning BID59 , which is the particular variant of HTN planning used by the widely used SHOP and SHOP2 BID45 ) HTN planners. SHOP requires the user to specify a total order of the tasks; SHOP2 drops this requirement allowing partial-order between the tasks BID44 . Both have the same representation capabilities although SHOP2 is usually preferred since it doesn't force the user to provide a total order for the method's subtasks BID44 .In this work, we propose the automated learning of HGNs for ND domains extending our previous work on learning HTNs for deterministic domains BID21 . While work exists on learning goal hierarchies BID53 BID32 BID49 , these works are based on formalisms that have more limited representations than HGNs and in fact predate them.
Learning HGNs, ND domains
{"src": "scitldr-AIC_train", "paper_id": "S1GALrBWtN"}