The following article is an extended abstract submitted as part of AAAI’s New Faculty Highlights Program. Read the full-length article at this link: https://onlinelibrary.wiley.com/doi/10.1002/aaai.12073

Hierarchical Planning and Reasoning about Partially Ordered Plans – From Theory to Practice

 

Pascal Bercher
The Australian National University
College for Engineering and Computer Science
School of Computing

 

Abstract

This is an invited paper and part of the New Faculty Highlights Invited Speaker Program of AAAI’21. It surveys some of my work done until today in hierarchical task network (HTN) planning as well as partial order causal link (POCL) planning. Lines or research outlined include complexity investigations, heuristic search, as well as practical application for planning-based assistants.

 

Introduction

AI planning is a general problem solving technique that aims at finding a plan – a sequence of actions that transforms an initial state into a desired state of a system using a pre-defined set of actions that describe state transitions via their preconditions and effects. The research out-lined focuses on hierarchical task network (HTN) planning (Bercher, Alford, and Hӧller 2019), a hierarchical approach to planning, as well as on partial order causal link (POCL) planning (Bercher 2021), a plan-based search approach.

 

POCL Planning

POCL planning is a planning approach in the space or partially ordered plans – an example is depicted in Fig. 1. In this example we see the problem’s initial state to be empty, the goal description to be g = {P, Q, R} (both represented as additional actions), and four actions as well as four causal links protecting some preconditions. The plan is not yet a solution because there’s still an action with a precondition not yet protected by a causal link. Adding the missing link requires further reasoning as further issues might arise. Assume a link is added from w1 to the goal protecting P . Then s2 raises a so-called causal threat as its delete effect ¬P violates that link – so an ordering constraint needs to be inserted moving s2 before w1 (so far this is not present, s2 could also be executed after w1).

For such POCL plans we studied the computational complexity of checking whether a single given action can be removed from a POCL solution plan so that it can be turned into a solution again by only inserting additional causal links and ordering constraints (Olz and Bercher 2019). In subsequent work we studied the complexity of optimizing a plan regarding its makespan (the execution time when exploiting parallelism) by removing and changing ordering constraints (Bercher and Olz 2020). Most problems are NP-complete, though some can be solved in polynomial time. We also studied the computational complexity of the plan existence problem, i.e., checking whether a solution can be obtained from a current POCL plan. When ignoring delete effects or causal links to a certain extent most cases are shown to be NP-complete (Bercher et al. 2013; Bercher 2021).

 

HTN Planning

HTN planning is a hierarchical approach to planning. Here, the domain model does not just contain actions describing state transitions (in HTN planning referred to as primitive tasks), but also compound tasks and their refinements. Com- pound tasks are abstractions of various primitive or further compound tasks, and their refinements are given in terms of decomposition methods, which are pre-defined mappings from compound tasks to partially ordered plans. Instead of planning for a state-based goal, we now aim at finding a primitive and executable refinement of one or more initially given compound tasks. For this form of planning, we developed a new problem formalization (Geier and Bercher 2011), which due to its simplicity was thereafter established as another standard (Bercher, Alford, and Hӧller  2019).

We formally introduced the concept of task insertion (Geier and Bercher 2011) to HTN planning, called TIHTN planning, where we are not just allowed to replace a compound task by one of its refinement plans, but instead we may add actions arbitrarily to plans. We showed that in contrast to HTN planning, this makes TIHTN planning decidable (Geier and Bercher 2011) – because when task insertion is allowed recursive task decomposition can be prevented. We analyzed the plan existence problem for both HTN planning (Alford, Bercher, and Aha 2015a) as well as TIHTN planning (Alford, Bercher, and Aha 2015b) for several special cases (like total vs. partial order or acyclicity in task decomposition). These complexities could also be shown for hybrid planning, a variant of HTN planning fused with POCL planning, where certain criteria are posed upon the compound tasks’ refinement plans in the model (Bercher et al. 2016).

We also investigated the computational complexity of making changes to the domain model or a given plan (Lin and Bercher 2021; Barták et al. 2021) to turn a given non-solution plan into a solution. One of the motivations behind these investigations is being able to provide explanations on why a non-solution plan does not solve the given problem.

Motivated by the development of heuristics, we investigated the computational complexity of checking whether a fact or task is a landmark, i.e., whether it is contained in any solution (Hӧller and Bercher 2021). We also investigated the hardness of checking whether a fact is a necessary precondition or consequence of refining a compound task into a primitive executable refinement (Olz, Biundo, and Bercher 2021).

Work on heuristics involves computing and exploiting landmarks (Hӧller and Bercher 2021), as well as analyzing the task hierarchy to estimate a minimal number of tasks that will be introduced into plans as consequence of refining a given compound task (Bercher et al. 2017).

 

Practical Application

We implemented two planning-based assistance systems that support their users in various tasks by presenting a detailed step-by-step instruction explaining them what to do. Both systems are highly flexible, as the plans presented are generated at runtime by incorporating the current situation.

The first system supports a human user in setting up a complex home theatre consisting of various devices, cables, and adapters (Bercher et al. 2014). The second system, a successor of the former, was created in cooperation with Robert Bosch GmbH (Bercher et al. 2021). It supports its users in the creation of do-it-yourself (DIY) projects. The example project that has been fully implemented and tested empirically is the construction of a keyrack (Behnke et al. 2020). The assistant can convey the instructions on various levels of abstraction, and communicates with the electic tools to access their current state for improved user feedback.

 

References

Alford, R.; Bercher, P.; and Aha, D. 2015a. Tight Bounds for HTN Planning. In ICAPS, 7–15. AAAI.

Alford, R.; Bercher, P.; and Aha, D. 2015b. Tight Bounds for HTN planning with Task Insertion. In IJCAI, 1502–1508. AAAI.

Barták, R.; Ondrčková, S.; Behnke, G.; and Bercher, P. 2021. Correcting Hierarchical Plans by Action Deletion. In KR. IJCAI.

Behnke, G.; Bercher, P.; Kraus, M.; Schiller, M.; Mickeleit, K.; Hӓge, T.; Dorna, M.; Dambier, M.; Minker, W.; Glimm, B.; and Biundo, S. 2020. New Developments for Robert – Assisting Novice Users Even Better in DIY Projects. In ICAPS, 343–347. AAAI.

Bercher, P. 2021. A Closer Look at Causal Links: Complexity Results for Delete-Relaxation in Partial Order Causal Link (POCL) Planning. In ICAPS, 36–45. AAAI.

Bercher, P.; Alford, R.; and Hӧller, D. 2019. A Survey on Hierarchical Planning – One Abstract Idea, Many Concrete Realizations. In IJCAI, 6267–6275. IJCAI.

Bercher, P.; Behnke, G.; Hӧller, D.; and Biundo, S. 2017. An Admissible HTN Planning Heuristic. In IJCAI, 480–488. IJCAI.

Bercher, P.; Behnke, G.; Kraus, M.; Schiller, M.; Manstetten, D.; Dambier, M.; Dorna, M.; Minker, W.; Glimm, B.; and Biundo, S. 2021. Do It Yourself, but Not Alone: Companion-Technology for Home Improvement – Bringing a Planning-Based Interactive DIY Assistant to Life. KI.

Bercher, P.; Biundo, S.; Geier, T.; Hӧrnle, T.; Nothdurft, F.; Richter, F.; and Schattenberg, B. 2014. Plan, Repair, Execute, Explain – How Planning Helps to Assemble your Home Theater. In ICAPS, 386–394. AAAI.

Bercher, P.; Geier, T.; Richter, F.; and Biundo, S. 2013. On Delete Relaxation in Partial-Order Causal-Link Planning. In ICTAI 2013, 674–681. IEEE Computer Society.

Bercher, P.; Hӧller, D.; Behnke, G.; and Biundo, S. 2016. More than a Name? On Implications of Preconditions and Effects of Compound HTN Planning Tasks. In ECAI, 225–233. IOS.

Bercher, P.; and Olz, C. 2020. POP ≡ POCL, right? Complexity Results for POCL Makespan Minimization. In AAAI, 9785–9793. AAAI.

Geier, T.; and Bercher, P. 2011. On the Decidability of HTN Planning with Task Insertion. In IJCAI, 1955–1961. AAAI.

Hӧller, D.; and Bercher, P. 2021. Landmark Generation in HTN Planning. In AAAI, 11826–11834. AAAI.

Lin, S.; and Bercher, P. 2021. Change the World – How Hard Can That Be? On the Computational Complexity of Fixing Planning Models. In IJCAI, 4152–4159. IJCAI.

Olz, C.; and Bercher, P. 2019. Eliminating Redundant Actions in Partially Ordered Plans – A Complexity Analysis. In ICAPS, 310–319. AAAI.

Olz, C.; Biundo, S.; and Bercher, P. 2021. Revealing Hidden Preconditions and Effects of Compound HTN Planning Tasks – A Complexity Analysis. In AAAI, 11903–11912. AAAI.