var bibbase_data = {"data":"\"Loading..\"\n\n
\n\n \n\n \n\n \n \n\n \n\n \n \n\n \n\n \n
\n generated by\n \n \"bibbase.org\"\n\n \n
\n \n\n
\n\n \n\n\n
\n\n Excellent! Next you can\n create a new website with this list, or\n embed it in an existing web page by copying & pasting\n any of the following snippets.\n\n
\n JavaScript\n (easiest)\n
\n \n <script src=\"https://bibbase.org/show?bib=hierarchical-task.net/bibtex/theses-in-hierarchical-planning.bib&hidemenu=1&theme=default&fullnames=1&jsonp=1&jsonp=1\"></script>\n \n
\n\n PHP\n
\n \n <?php\n $contents = file_get_contents(\"https://bibbase.org/show?bib=hierarchical-task.net/bibtex/theses-in-hierarchical-planning.bib&hidemenu=1&theme=default&fullnames=1&jsonp=1\");\n print_r($contents);\n ?>\n \n
\n\n iFrame\n (not recommended)\n
\n \n <iframe src=\"https://bibbase.org/show?bib=hierarchical-task.net/bibtex/theses-in-hierarchical-planning.bib&hidemenu=1&theme=default&fullnames=1&jsonp=1\"></iframe>\n \n
\n\n

\n For more details see the documention.\n

\n
\n
\n\n
\n\n This is a preview! To use this list on your own web site\n or create a new web site from it,\n create a free account. The file will be added\n and you will be able to edit it in the File Manager.\n We will show you instructions once you've created your account.\n
\n\n
\n\n

To the site owner:

\n\n

Action required! Mendeley is changing its\n API. In order to keep using Mendeley with BibBase past April\n 14th, you need to:\n

    \n
  1. renew the authorization for BibBase on Mendeley, and
  2. \n
  3. update the BibBase URL\n in your page the same way you did when you initially set up\n this page.\n
  4. \n
\n

\n\n

\n \n \n Fix it now\n

\n
\n\n
\n\n\n
\n \n \n
\n
\n  \n 2023\n \n \n (2)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Scalable SAT Solving and its Application.\n \n \n \n \n\n\n \n Dominik Schreiber.\n\n\n \n\n\n\n Ph.D. Thesis, Karlsruher Institut für Technologie (KIT), 2023.\n \n\n\n\n
\n\n\n\n \n \n \"Scalable dissertation\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Schreiber2023Dissertation,\n  author   = {Dominik Schreiber},\n  title    = {Scalable SAT Solving and its Application},\n  school   = {Karlsruher Institut für Technologie (KIT)},\n  year     = {2023},\n  abstract = {The problem of propositional satisfiability (SAT) is to find a variable assignment for a given propositional formula such that the formula evaluates to true or, if no such assignment exists, to report that the formula is unsatisfiable. SAT solving has attracted a great deal of attention due to its theoretical significance, its generic nature, and its broad applicability to a wide range of problems. In this work, we target a number of scalability challenges in the realm of applied SAT solving, guided by three research questions: How can we efficiently exploit modern distributed computing environments for SAT solving? How can we render SAT solving systems in such environments trustworthy for critical applications? And: How can complex applications make more efficient use of SAT solvers in order to handle previously infeasible inputs? We present contributions which address these questions with the methodology of algorithm engineering, combining theoretic considerations with practical engineering.\n  <br><br>\n  First, we investigate the efficient scheduling of SAT tasks and other tasks with unknown execution time in large distributed environments. Especially in on-demand computing such as high performance computing (HPC) or cloud services, low scheduling latencies and response times are desirable as well as resource efficiency and fairness. We derive a decentralized scheduling approach which exploits malleability, i.e., the ability of a task to handle a fluctuating amount of computational resources during its execution. We derive fully scalable algorithms for our scheduling model and implement practically efficient variations of them. In experiments on up to 6144 cores, our approach results in scheduling latencies in the range of milliseconds and achieves near-optimal system utilization.\n  <br><br>\n  Secondly, we explore the efficient parallelization of SAT solving itself. In particular, we design a compact all-to-all clause sharing scheme which scales to thousands of solvers. In experiments on up to 3072 cores, our approach combined with state-of-the-art solver backends more than doubles the previously highest reported speedups in general-purpose distributed SAT solving. Our approach has dominated the cloud track (1600 hardware threads) of the renowned International SAT Competition four years in a row while also proving highly competitive on a moderately parallel scale (64 hardware threads). Within our job scheduling framework, we show that the combination of parallel job processing and malleable SAT solving can achieve appealing speedups while retaining good resource efficiency.\n  <br><br>\n  Thirdly, we address a major shortcoming of most parallel and distributed solvers, namely their inability to produce certificates of unsatisfiability which limits their trustworthiness. We propose the first feasible and scalable approach to generating proof certificates in massively parallel SAT solving. Our distributed algorithm essentially rewinds the solving procedure and tracks the origin of all relevant shared clauses. With reasonable overhead compared to our non proof producing solver, this approach is able to efficiently generate proofs holding many gigabytes of compressed information.\n  <br><br>\n  Last but not least, we conduct a major case study on applied SAT solving. Specifically, we present a SAT-based approach to Totally Ordered Hierarchical Task Network (TOHTN) planning—a popular branch of automated planning which provides a rich framework to model complex hierarchical tasks. We present the first SAT encoding of TOHTN problems which preserves a lifted, i.e., parametrized, problem description and therefore avoids the combinatorial blowup which other SAT-based approaches introduce. With an integrated approach that alternates between encoding and incremental SAT solving, our approach generates formulas which are oftentimes smaller by one to two orders of magnitude compared to prior SAT-based approaches. We also present a way to process hierarchical planning problems on parallel hardware using our job scheduling and malleable SAT solving framework. For this means, we enable our system to support incremental SAT solving, rendering it the first large-scale incremental SAT solver.\n  <br><br>\n  Put together, our work has led to substantial advances in scalable SAT solving and its efficient application. We thus push the frontier of automated reasoning problems that are feasible to solve in modern computing environments.},\n  doi      = {10.5445/IR/1000165224},\n  url_Dissertation = {https://publikationen.bibliothek.kit.edu/1000165224/151802078}\n}\n\n
\n
\n\n\n
\n The problem of propositional satisfiability (SAT) is to find a variable assignment for a given propositional formula such that the formula evaluates to true or, if no such assignment exists, to report that the formula is unsatisfiable. SAT solving has attracted a great deal of attention due to its theoretical significance, its generic nature, and its broad applicability to a wide range of problems. In this work, we target a number of scalability challenges in the realm of applied SAT solving, guided by three research questions: How can we efficiently exploit modern distributed computing environments for SAT solving? How can we render SAT solving systems in such environments trustworthy for critical applications? And: How can complex applications make more efficient use of SAT solvers in order to handle previously infeasible inputs? We present contributions which address these questions with the methodology of algorithm engineering, combining theoretic considerations with practical engineering.

First, we investigate the efficient scheduling of SAT tasks and other tasks with unknown execution time in large distributed environments. Especially in on-demand computing such as high performance computing (HPC) or cloud services, low scheduling latencies and response times are desirable as well as resource efficiency and fairness. We derive a decentralized scheduling approach which exploits malleability, i.e., the ability of a task to handle a fluctuating amount of computational resources during its execution. We derive fully scalable algorithms for our scheduling model and implement practically efficient variations of them. In experiments on up to 6144 cores, our approach results in scheduling latencies in the range of milliseconds and achieves near-optimal system utilization.

Secondly, we explore the efficient parallelization of SAT solving itself. In particular, we design a compact all-to-all clause sharing scheme which scales to thousands of solvers. In experiments on up to 3072 cores, our approach combined with state-of-the-art solver backends more than doubles the previously highest reported speedups in general-purpose distributed SAT solving. Our approach has dominated the cloud track (1600 hardware threads) of the renowned International SAT Competition four years in a row while also proving highly competitive on a moderately parallel scale (64 hardware threads). Within our job scheduling framework, we show that the combination of parallel job processing and malleable SAT solving can achieve appealing speedups while retaining good resource efficiency.

Thirdly, we address a major shortcoming of most parallel and distributed solvers, namely their inability to produce certificates of unsatisfiability which limits their trustworthiness. We propose the first feasible and scalable approach to generating proof certificates in massively parallel SAT solving. Our distributed algorithm essentially rewinds the solving procedure and tracks the origin of all relevant shared clauses. With reasonable overhead compared to our non proof producing solver, this approach is able to efficiently generate proofs holding many gigabytes of compressed information.

Last but not least, we conduct a major case study on applied SAT solving. Specifically, we present a SAT-based approach to Totally Ordered Hierarchical Task Network (TOHTN) planning—a popular branch of automated planning which provides a rich framework to model complex hierarchical tasks. We present the first SAT encoding of TOHTN problems which preserves a lifted, i.e., parametrized, problem description and therefore avoids the combinatorial blowup which other SAT-based approaches introduce. With an integrated approach that alternates between encoding and incremental SAT solving, our approach generates formulas which are oftentimes smaller by one to two orders of magnitude compared to prior SAT-based approaches. We also present a way to process hierarchical planning problems on parallel hardware using our job scheduling and malleable SAT solving framework. For this means, we enable our system to support incremental SAT solving, rendering it the first large-scale incremental SAT solver.

Put together, our work has led to substantial advances in scalable SAT solving and its efficient application. We thus push the frontier of automated reasoning problems that are feasible to solve in modern computing environments.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Hierarchical Planning: Expressivity Analysis, Solving Techniques, and Problem Compilations.\n \n \n \n \n\n\n \n Daniel Höller.\n\n\n \n\n\n\n Ph.D. Thesis, Ulm University, 2023.\n \n\n\n\n
\n\n\n\n \n \n \"Hierarchical dissertation\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 8 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Hoeller2023Dissertation,\n  author   = {Daniel H\\"oller},\n  title    = {Hierarchical Planning: Expressivity Analysis, Solving Techniques, and Problem Compilations},\n  school   = {Ulm University},\n  year     = {2023},\n  abstract = {Automated planning enables systems to act in a goal-directed way and flexibly react on their environment and other agents. This makes it a valuable technology for intelligent systems. Based on a model of the environment and a goal to reach or a task to accomplish, those systems come up with a detailed plan on how to achieve it. Two widely-used approaches to planning are classical planning and hierarchical planning. Classical planning comes with a large number of domain-independent solving techniques that enable a simple adaptation to new application domains. The motivation to use a hierarchy (which is usually defined on the things to do, the tasks) is manifold: some application domains can be modeled much more intuitive using hierarchical structures, the hierarchy can be exploited to communicate with a human user on different levels of abstraction, and it has often been used to guide the search to find solutions more quickly. Further it enables the definition of more complex behavior patterns than possible with commonly-used non-hierarchical formalisms. In both classical and hierarchical planning, there is a range of slightly different formalisms that come with different properties. This thesis advances the state of the art in hierarchical planning along three lines of research. We provide an expressivity analysis of common planning formalisms, novel solving techniques for hierarchical planning, and compilations to solve three problems related to planning. We first systematically investigate the expressivity of different classical and hierarchical planning formalisms. To this end, we compare them with formal languages and show what kind of languages can be expressed by which formalism. We show that the expressivity ranges from a subset of the regular languages for basic classical planning to a (non-context-free) subset of the context-sensitive languages for the most widely-used hierarchical formalism called Hierarchical Task Network (HTN) planning. We introduce novel solving techniques for HTN planning. We start with a new input language that became the standard for the 2020 International Planning Competition (IPC) and a grounding technique to compile the first-order model used to specify the planning domain into a propositional model as required for most planning systems. Then we show how HTN planners based on heuristic search can benefit from the sophisticated domain-independent heuristics developed for classical planning. We introduce a generic method to use them to guide the HTN search. Our system outperforms the participants of the 2020 IPC and several other systems from the literature. We further show that our techniques can also be used to find optimal plans, i.e. plans with minimal action cost. Besides plan generation, there are several related tasks to solve when applying planning in intelligent systems. For three of them, we show how they can be compiled into standard planning problems. This enables the use of standard planning systems to solve the problems instead of coming up with specialized solvers. We introduce compilations for (1) plan and goal recognition, the task of identifying the goals and plans of other agents, (2) plan repair, the task of coming up with a novel plan when the execution of an initial one failed, and (3) plan verification, the task of deciding whether a given sequence of actions is a solution for a given problem.},\n  doi      = {10.18725/OPARU-47463},\n  url_Dissertation = {https://oparu.uni-ulm.de/xmlui/bitstream/handle/123456789/47539/Thesis_Hoeller.pdf?sequence=3&isAllowed=y}\n}\n\n\n
\n
\n\n\n
\n Automated planning enables systems to act in a goal-directed way and flexibly react on their environment and other agents. This makes it a valuable technology for intelligent systems. Based on a model of the environment and a goal to reach or a task to accomplish, those systems come up with a detailed plan on how to achieve it. Two widely-used approaches to planning are classical planning and hierarchical planning. Classical planning comes with a large number of domain-independent solving techniques that enable a simple adaptation to new application domains. The motivation to use a hierarchy (which is usually defined on the things to do, the tasks) is manifold: some application domains can be modeled much more intuitive using hierarchical structures, the hierarchy can be exploited to communicate with a human user on different levels of abstraction, and it has often been used to guide the search to find solutions more quickly. Further it enables the definition of more complex behavior patterns than possible with commonly-used non-hierarchical formalisms. In both classical and hierarchical planning, there is a range of slightly different formalisms that come with different properties. This thesis advances the state of the art in hierarchical planning along three lines of research. We provide an expressivity analysis of common planning formalisms, novel solving techniques for hierarchical planning, and compilations to solve three problems related to planning. We first systematically investigate the expressivity of different classical and hierarchical planning formalisms. To this end, we compare them with formal languages and show what kind of languages can be expressed by which formalism. We show that the expressivity ranges from a subset of the regular languages for basic classical planning to a (non-context-free) subset of the context-sensitive languages for the most widely-used hierarchical formalism called Hierarchical Task Network (HTN) planning. We introduce novel solving techniques for HTN planning. We start with a new input language that became the standard for the 2020 International Planning Competition (IPC) and a grounding technique to compile the first-order model used to specify the planning domain into a propositional model as required for most planning systems. Then we show how HTN planners based on heuristic search can benefit from the sophisticated domain-independent heuristics developed for classical planning. We introduce a generic method to use them to guide the HTN search. Our system outperforms the participants of the 2020 IPC and several other systems from the literature. We further show that our techniques can also be used to find optimal plans, i.e. plans with minimal action cost. Besides plan generation, there are several related tasks to solve when applying planning in intelligent systems. For three of them, we show how they can be compiled into standard planning problems. This enables the use of standard planning systems to solve the problems instead of coming up with specialized solvers. We introduce compilations for (1) plan and goal recognition, the task of identifying the goals and plans of other agents, (2) plan repair, the task of coming up with a novel plan when the execution of an initial one failed, and (3) plan verification, the task of deciding whether a given sequence of actions is a solution for a given problem.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2021\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Learning Decomposition Models for Hierarchical Planning and Plan Recognition.\n \n \n \n \n\n\n \n Pavan Kantharaju.\n\n\n \n\n\n\n Ph.D. Thesis, Drexel University, 2021.\n \n\n\n\n
\n\n\n\n \n \n \"Learning dissertation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 9 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Kantharaju2021PhDThesis,\n  author    = {Pavan Kantharaju},\n  title     = {Learning Decomposition Models for Hierarchical Planning and Plan Recognition},\n  school    = {Drexel University},\n  year      = {2021},\n  abstract  = {Classical AI planning aims to solve the problem of searching for a sequence of steps that transitions an agent from some state of the world to some goal. Hierarchical planning is a particular case of AI planning that assumes the existence of a decomposition model that represents how to break down tasks or goals into sequences of actions. While hierarchical planning allows us to reduce the search space compared to classical planning, it has been shown that hand authoring these decomposition models require domain-expert knowledge and time, and can be error-prone for complex application domains. This is also the case for hierarchical plan recognition, which aims to solve the problem of inferring the goals and plans of agent(s) given a sequence of actions and a decomposition model. Our goal is to study learning techniques for automatically constructing decomposition models from training data for hierarchical planning and plan recognition. Specifically, we focus on learning a decomposition model represented using Combinatory Categorial Grammars (CCGs). This dissertation describes a study on supervised and unsupervised CCG learning techniques for hierarchical planning and plan recognition, a novel CCG plan recognition algorithm, a theoretical analysis of supervised CCG learning algorithms, and the application of learned CCGs for playing computer games. In this dissertation, we provide a background of relevant research to the dissertation, describe our study on CCG learning, and outline future steps.},\n  url_Dissertation = {https://www.researchgate.net/publication/350471822_Learning_Decomposition_Models_for_Hierarchical_Planning_and_Plan_Recognition}\n}\n\n\n
\n
\n\n\n
\n Classical AI planning aims to solve the problem of searching for a sequence of steps that transitions an agent from some state of the world to some goal. Hierarchical planning is a particular case of AI planning that assumes the existence of a decomposition model that represents how to break down tasks or goals into sequences of actions. While hierarchical planning allows us to reduce the search space compared to classical planning, it has been shown that hand authoring these decomposition models require domain-expert knowledge and time, and can be error-prone for complex application domains. This is also the case for hierarchical plan recognition, which aims to solve the problem of inferring the goals and plans of agent(s) given a sequence of actions and a decomposition model. Our goal is to study learning techniques for automatically constructing decomposition models from training data for hierarchical planning and plan recognition. Specifically, we focus on learning a decomposition model represented using Combinatory Categorial Grammars (CCGs). This dissertation describes a study on supervised and unsupervised CCG learning techniques for hierarchical planning and plan recognition, a novel CCG plan recognition algorithm, a theoretical analysis of supervised CCG learning algorithms, and the application of learned CCGs for playing computer games. In this dissertation, we provide a background of relevant research to the dissertation, describe our study on CCG learning, and outline future steps.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2020\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Acting, Planning, and Learning Using Hierarchical Operational Models.\n \n \n \n \n\n\n \n Sunandita Patra.\n\n\n \n\n\n\n Ph.D. Thesis, University of Maryland, 2020.\n \n\n\n\n
\n\n\n\n \n \n \"Acting, dissertation\n  \n \n \n \"Acting, uri\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 5 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Patra2020PhDThesis,\n  author    = {Sunandita Patra},\n  title     = {Acting, Planning, and Learning Using Hierarchical Operational Models},\n  school    = {University of Maryland},\n  year      = {2020},\n  abstract  = {The most common representation formalisms for planning are descriptive models that abstractly describe what the actions do and are tailored for efficiently computing the next state(s) in a state-transition system. However, real-world acting requires operational models that describe how to do things, with rich control structures for closed-loop online decision-making in a dynamic environment. Use of a different action model for planning than the one used for acting causes problems with combining acting and planning, in particular for the development and consistency verification of the different models.<br/><br/>\n\n  As an alternative, this dissertation defines and implements an integrated acting-and-planning system in which both planning and acting use the same operational models, which are written in a general-purpose hierarchical task-oriented language offering rich control structures. The acting component, called Reactive Acting Engine (RAE), is inspired by the well-known PRS system, except that instead of being purely reactive, it can get advice from a planner. The dissertation also describes three planning algorithms which plan by doing several Monte Carlo rollouts in the space of operational models. The best of these three planners, Plan-with-UPOM uses a UCT-like Monte Carlo Tree Search procedure called UPOM (UCT Procedure for Operational Models), whose rollouts are simulated executions of the actor's operational models. The dissertation also presents learning strategies for use with RAE and UPOM that acquire from online acting experiences and/or simulated planning results, a mapping from decision contexts to method instances as well as a heuristic function to guide UPOM. The experimental results show that Plan-with-UPOM and the learning strategies significantly improve the acting efficiency and robustness of RAE. It can be proved that UPOM converges asymptotically by mapping its search space to an MDP. The dissertation also describes a real-world prototype of RAE and Plan-with-UPOM to defend software-defined networks, a relatively new network management architecture, against incoming attacks.},\n  url_Dissertation = {https://drum.lib.umd.edu/bitstream/handle/1903/26448/Patra_umd_0117E_21050.pdf?sequence=2&isAllowed=y},\n  url_URI          = {http://hdl.handle.net/1903/26448}\n}\n\n\n
\n
\n\n\n
\n The most common representation formalisms for planning are descriptive models that abstractly describe what the actions do and are tailored for efficiently computing the next state(s) in a state-transition system. However, real-world acting requires operational models that describe how to do things, with rich control structures for closed-loop online decision-making in a dynamic environment. Use of a different action model for planning than the one used for acting causes problems with combining acting and planning, in particular for the development and consistency verification of the different models.

As an alternative, this dissertation defines and implements an integrated acting-and-planning system in which both planning and acting use the same operational models, which are written in a general-purpose hierarchical task-oriented language offering rich control structures. The acting component, called Reactive Acting Engine (RAE), is inspired by the well-known PRS system, except that instead of being purely reactive, it can get advice from a planner. The dissertation also describes three planning algorithms which plan by doing several Monte Carlo rollouts in the space of operational models. The best of these three planners, Plan-with-UPOM uses a UCT-like Monte Carlo Tree Search procedure called UPOM (UCT Procedure for Operational Models), whose rollouts are simulated executions of the actor's operational models. The dissertation also presents learning strategies for use with RAE and UPOM that acquire from online acting experiences and/or simulated planning results, a mapping from decision contexts to method instances as well as a heuristic function to guide UPOM. The experimental results show that Plan-with-UPOM and the learning strategies significantly improve the acting efficiency and robustness of RAE. It can be proved that UPOM converges asymptotically by mapping its search space to an MDP. The dissertation also describes a real-world prototype of RAE and Plan-with-UPOM to defend software-defined networks, a relatively new network management architecture, against incoming attacks.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2019\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Hierarchical Planning through Propositional Logic – Highly Efficient, Versatile, and Flexible.\n \n \n \n \n\n\n \n Gregor Behnke.\n\n\n \n\n\n\n Ph.D. Thesis, Ulm University, 2019.\n \n\n\n\n
\n\n\n\n \n \n \"Hierarchical dissertation\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 5 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Behnke2019PhDThesis,\n  author = {Gregor Behnke},\n  title = {Hierarchical Planning through Propositional Logic -- Highly Efficient, Versatile, and Flexible},\n  school = {Ulm University},\n  year = {2019},\n  abstract = {AI Planning is a core technology in enabling advanced assistance for human users. When faced with complex problems such as handicraft tasks for household repairs, Do-It-Yourself projects, or difficult assembly tasks, a planning-based assistance system can provide individualised and context-dependent instructions. It thus effectively supports the user in achieving his or her goals. High-quality assistance should in addition conform to the user’s current wishes and preferences to ensure maximum utility. This can be achieved by involving the user into the planning process, i.e. by making planning mixed-initiative. Hierarchical Task Network (HTN) planning is a method particularly well suited for providing user support, as it resembles the means and structures humans use for problem solving. We identified two major challenges that every mixed-initiative HTN planning system must face and show how to address them: generating plans quickly and flexibly altering them according to the user’s demands.<br/><br/>\n\n  The main focus of this thesis lies on addressing the first challenge, i.e. on developing a quickly responding and efficient HTN planner. Designing efficient HTN planners is particularly difficult. Their algorithms have to take both dimensions of the problem description – state and hierarchy -- into account and have to consider interactions between them. We use a translation into propositional logic, enabling for the first time a uniform view on the whole planning problem. First, we describe a new encoding for totally-ordered HTN planning, before extending it in two consecutive steps to capture general, partially-ordered domains. Second, we introduce Path Decomposition Trees (PDTs) and Solution Order Graphs (SOGs) which enable a compact encoding and alleviate unnecessary reasoning from a SAT solver. They also pave the way for future insights into structural properties of HTN planning problems, which allow for more efficient planning as well as for more advanced user support. Third, we show that our encodings are a significant empirical improvement over the current state of the art in HTN planning. Lastly, we present a fundamental technique for optimal HTN planning -- which is especially important in assistance scenarios – namely a method to compute succinct depth bounds for plan-length optimisation.<br/><br/>\n\n  In a mixed-initiative planning environment, users will frequently request the planner to change a currently considered plan. We start solving this second challenge by considering the most basic task involved: to verify that the changed plan is a solution to the planning problem at hand. First, we show that this task is NP-complete. Second, we develop the first plan verifier for HTN planning, which is based on a transformation into propositional logic. Third, we analyse and categorise the requests possibly made by a user and show that the objectives posed by her or him can be suitably represented as formulae in Linear Temporal Logic (LTL). Fourth, we analyse the computational complexity of changing a plan, showing that this task can be between NP-complete and undecidable. Lastly, we use our SAT-based planner to change a plan with respect to a request formulated as an LTL formula. We show that the full spectrum of LTL formulae can be supported efficiently in a propositional encoding. For that, we introduce a new theoretical foundation for reasoning about parallelism in LTL traces.<br/><br/>\n\n  The practical applicability of our techniques has been demonstrated within a joint transfer project with Robert Bosch GmbH. In it, we developed an assistance system that guides novice users through a handicraft Do-It-Yourself project. The underlying hierarchical planning model is highly complex. Currently the only planner that is able to find plans for this model within an acceptable time frame is the SAT-based HTN planner developed as part of this thesis.},\n  doi = {10.18725/OPARU-23396},\n  url_Dissertation = {https://oparu.uni-ulm.de/xmlui/bitstream/handle/123456789/23459/thesis_behnke.pdf}\n}\n\n\n
\n
\n\n\n
\n AI Planning is a core technology in enabling advanced assistance for human users. When faced with complex problems such as handicraft tasks for household repairs, Do-It-Yourself projects, or difficult assembly tasks, a planning-based assistance system can provide individualised and context-dependent instructions. It thus effectively supports the user in achieving his or her goals. High-quality assistance should in addition conform to the user’s current wishes and preferences to ensure maximum utility. This can be achieved by involving the user into the planning process, i.e. by making planning mixed-initiative. Hierarchical Task Network (HTN) planning is a method particularly well suited for providing user support, as it resembles the means and structures humans use for problem solving. We identified two major challenges that every mixed-initiative HTN planning system must face and show how to address them: generating plans quickly and flexibly altering them according to the user’s demands.

The main focus of this thesis lies on addressing the first challenge, i.e. on developing a quickly responding and efficient HTN planner. Designing efficient HTN planners is particularly difficult. Their algorithms have to take both dimensions of the problem description – state and hierarchy – into account and have to consider interactions between them. We use a translation into propositional logic, enabling for the first time a uniform view on the whole planning problem. First, we describe a new encoding for totally-ordered HTN planning, before extending it in two consecutive steps to capture general, partially-ordered domains. Second, we introduce Path Decomposition Trees (PDTs) and Solution Order Graphs (SOGs) which enable a compact encoding and alleviate unnecessary reasoning from a SAT solver. They also pave the way for future insights into structural properties of HTN planning problems, which allow for more efficient planning as well as for more advanced user support. Third, we show that our encodings are a significant empirical improvement over the current state of the art in HTN planning. Lastly, we present a fundamental technique for optimal HTN planning – which is especially important in assistance scenarios – namely a method to compute succinct depth bounds for plan-length optimisation.

In a mixed-initiative planning environment, users will frequently request the planner to change a currently considered plan. We start solving this second challenge by considering the most basic task involved: to verify that the changed plan is a solution to the planning problem at hand. First, we show that this task is NP-complete. Second, we develop the first plan verifier for HTN planning, which is based on a transformation into propositional logic. Third, we analyse and categorise the requests possibly made by a user and show that the objectives posed by her or him can be suitably represented as formulae in Linear Temporal Logic (LTL). Fourth, we analyse the computational complexity of changing a plan, showing that this task can be between NP-complete and undecidable. Lastly, we use our SAT-based planner to change a plan with respect to a request formulated as an LTL formula. We show that the full spectrum of LTL formulae can be supported efficiently in a propositional encoding. For that, we introduce a new theoretical foundation for reasoning about parallelism in LTL traces.

The practical applicability of our techniques has been demonstrated within a joint transfer project with Robert Bosch GmbH. In it, we developed an assistance system that guides novice users through a handicraft Do-It-Yourself project. The underlying hierarchical planning model is highly complex. Currently the only planner that is able to find plans for this model within an acceptable time frame is the SAT-based HTN planner developed as part of this thesis.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2018\n \n \n (3)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Hybrid Planning — From Theory to Practice.\n \n \n \n \n\n\n \n Pascal Bercher.\n\n\n \n\n\n\n Ph.D. Thesis, Ulm University, 2018.\n \n\n\n\n
\n\n\n\n \n \n \"Hybrid dissertation\n  \n \n \n \"Hybrid slides-from-icaps-award\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 11 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Bercher2017PhDThesis,\n  Title = {Hybrid Planning --- From Theory to Practice},\n  Author = {Pascal Bercher},\n  School = {Ulm University},\n  Year = {2018},\n  doi = {10.18725/OPARU-5242},\n  abstract = {This work lays fundamental groundwork for the development of so-called Companion Systems - cognitive technical systems that are capable to reason about themselves, their users and environment, and to plan a course of action to achieve their users' goals. They are intelligent devices that assist their users in operating them: instead of the user having to learn how to operate the respective system, the system is intelligent and flexible enough to provide its functionality in a truly user-friendly way. <br/><br/>\n\n  To fully meet a user's demands, Companion Systems rely on a multi-facet of capabilities that stem from different disciplines, such as Artificial Intelligence (AI) planning, knowledge representation and reasoning, dialog management, and user interaction management, to name just a few. This thesis focuses on the relevant aspects of AI planning technology that are of importance for such systems. AI planning is the central technology for many Companion Systems as it allows to compute a course of action that, if followed by its user, achieves his or her goals and therefore serves as a basis of providing advanced user assistance. This thesis is concerned with hybrid planning - a hierarchical planning formalism that is especially suited for the basis of providing assistance to human users. Based on this formalism we will investigate the full endeavor of developing Companion Systems - from theory to practice. <br/><br/>\n\n  The thesis presents a novel formalization for hierarchical planning problems, which has become a standard in the field. We present a categorization of different problem classes into which hybrid planning as well as other well-known problem classes fall. This formalization allowed to prove a series of novel complexity results that are of interest both for theoretical and practical considerations. For many of the identified classes we introduce novel heuristics that are used to speed up the solution generation process. Some of them are the very first for the respective problem class, and some are the first admissible ones, thereby allowing to find optimal solutions -- which is especially important when plans are generated for human users. We apply hybrid planning in a prototypical Companion System. It assists a user in the task of setting up a complex home entertainment system. Based on a declarative (planning) model of the available hardware and its functionality, the assistant computes a sequence of actions that the user simply needs to follow to complete the setup task. Several so-called user-centered planning capabilities are applied in this system, such as a technique for generating user-friendly linearizations of non-linear plans or the capability to answer questions about the necessity of actions - an essential property to ensure transparency of the system's behavior. In conclusion: Most modern technical devices are still lacking true intelligence - since no research such as AI planning is sufficiently applied, so there is still huge potential in making such devices really smart by implementing them as cognitive systems that effectively assist their human users. Applying the research presented in this thesis is one step towards achieving this goal.},\n url_Dissertation = {https://bercher.net/publications/2017/Bercher2017Dissertation.pdf},\n url_Slides-from-ICAPS-Award = {https://bercher.net/publications/2017/Bercher2019ICAPSDissertationTalk.pdf}\n}\n\n\n
\n
\n\n\n
\n This work lays fundamental groundwork for the development of so-called Companion Systems - cognitive technical systems that are capable to reason about themselves, their users and environment, and to plan a course of action to achieve their users' goals. They are intelligent devices that assist their users in operating them: instead of the user having to learn how to operate the respective system, the system is intelligent and flexible enough to provide its functionality in a truly user-friendly way.

To fully meet a user's demands, Companion Systems rely on a multi-facet of capabilities that stem from different disciplines, such as Artificial Intelligence (AI) planning, knowledge representation and reasoning, dialog management, and user interaction management, to name just a few. This thesis focuses on the relevant aspects of AI planning technology that are of importance for such systems. AI planning is the central technology for many Companion Systems as it allows to compute a course of action that, if followed by its user, achieves his or her goals and therefore serves as a basis of providing advanced user assistance. This thesis is concerned with hybrid planning - a hierarchical planning formalism that is especially suited for the basis of providing assistance to human users. Based on this formalism we will investigate the full endeavor of developing Companion Systems - from theory to practice.

The thesis presents a novel formalization for hierarchical planning problems, which has become a standard in the field. We present a categorization of different problem classes into which hybrid planning as well as other well-known problem classes fall. This formalization allowed to prove a series of novel complexity results that are of interest both for theoretical and practical considerations. For many of the identified classes we introduce novel heuristics that are used to speed up the solution generation process. Some of them are the very first for the respective problem class, and some are the first admissible ones, thereby allowing to find optimal solutions – which is especially important when plans are generated for human users. We apply hybrid planning in a prototypical Companion System. It assists a user in the task of setting up a complex home entertainment system. Based on a declarative (planning) model of the available hardware and its functionality, the assistant computes a sequence of actions that the user simply needs to follow to complete the setup task. Several so-called user-centered planning capabilities are applied in this system, such as a technique for generating user-friendly linearizations of non-linear plans or the capability to answer questions about the necessity of actions - an essential property to ensure transparency of the system's behavior. In conclusion: Most modern technical devices are still lacking true intelligence - since no research such as AI planning is sufficiently applied, so there is still huge potential in making such devices really smart by implementing them as cognitive systems that effectively assist their human users. Applying the research presented in this thesis is one step towards achieving this goal.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Hierarchical Planning Under Uncertainty.\n \n \n \n \n\n\n \n Felix Richter.\n\n\n \n\n\n\n Ph.D. Thesis, Ulm University, Germany, 2018.\n \n\n\n\n
\n\n\n\n \n \n \"Hierarchical dissertation\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 3 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Richter2018PhDThesis,\n  Title = {Hierarchical Planning Under Uncertainty},\n  Author = {Felix Richter},\n  School = {Ulm University, Germany},\n  Year = {2018},\n  Abstract = {The recent years have seen significant progress in the fields of computer science and the engineering sciences, leading to a plethora of systems and services aimed at simplifying the organization of everyday life. The great potential of these utilities is however hindered by their complexity as well as the complexity of their interplay. Automated assistance systems can help users overcome this challenge.<br/><br/>\n\n  At the core of these systems lies planning functionality, needed for automatically generating courses of action, or policies, that represent, e.g., step-by-step instructions. Often, planning requires accounting for uncertainty inherent in a given application domain, making the process of generating such instructions computationally difficult. Fortunately, many assistance tasks exhibit hierarchical structure that allows understanding planning tasks as a hierarchy of subtasks, each of which can be solved using a limited number of solution recipes. The Hierarchical Task Network planning approach can already exploit such structures in deterministic planning domains by representing subtasks and recipes using abstract actions and methods, respectively, and generating plans by iteratively refining an initial abstract plan.<br/><br/>\n\n  The main goal of this thesis is to create a similar planning approach suited for planning domains that exhibit uncertainty, modeled as Partially Observable Markov Decision Processes. Based on a newly introduced suitable policy representation formalism called logical finite state controllers, the concepts of abstract actions and methods are reintroduced to create the Partially Observable Hierarchical Task Network planning approach. Next, Monte-Carlo tree search in the space of partially abstract controllers is identified as a suitable means for planning. The approach is then empirically evaluated on four domains by comparing it to search in the space of histories, a state-of-the-art non-hierarchical planning approach also based on Monte-Carlo tree search. This reveals that, with comparable computational effort, the proposed approach leads to policies of superior quality, and that it scales well with problem size.<br/><br/>\n\n  Two further techniques are then proposed enhance the presented approach: one that further reduces the required controller construction effort during search by refining controllers only selectively where required, and one that combines hierarchical and non-hierarchical search in order to combine the advantages of both.},\n  Doi = {10.18725/OPARU-5243},\n  url_Dissertation = {https://oparu.uni-ulm.de/xmlui/bitstream/handle/123456789/5300/dissertation_richter.pdf}\n}\n\n\n
\n
\n\n\n
\n The recent years have seen significant progress in the fields of computer science and the engineering sciences, leading to a plethora of systems and services aimed at simplifying the organization of everyday life. The great potential of these utilities is however hindered by their complexity as well as the complexity of their interplay. Automated assistance systems can help users overcome this challenge.

At the core of these systems lies planning functionality, needed for automatically generating courses of action, or policies, that represent, e.g., step-by-step instructions. Often, planning requires accounting for uncertainty inherent in a given application domain, making the process of generating such instructions computationally difficult. Fortunately, many assistance tasks exhibit hierarchical structure that allows understanding planning tasks as a hierarchy of subtasks, each of which can be solved using a limited number of solution recipes. The Hierarchical Task Network planning approach can already exploit such structures in deterministic planning domains by representing subtasks and recipes using abstract actions and methods, respectively, and generating plans by iteratively refining an initial abstract plan.

The main goal of this thesis is to create a similar planning approach suited for planning domains that exhibit uncertainty, modeled as Partially Observable Markov Decision Processes. Based on a newly introduced suitable policy representation formalism called logical finite state controllers, the concepts of abstract actions and methods are reintroduced to create the Partially Observable Hierarchical Task Network planning approach. Next, Monte-Carlo tree search in the space of partially abstract controllers is identified as a suitable means for planning. The approach is then empirically evaluated on four domains by comparing it to search in the space of histories, a state-of-the-art non-hierarchical planning approach also based on Monte-Carlo tree search. This reveals that, with comparable computational effort, the proposed approach leads to policies of superior quality, and that it scales well with problem size.

Two further techniques are then proposed enhance the presented approach: one that further reduces the required controller construction effort during search by refining controllers only selectively where required, and one that combines hierarchical and non-hierarchical search in order to combine the advantages of both.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Refinement of Intentions.\n \n \n \n \n\n\n \n Zhanhao Xiao.\n\n\n \n\n\n\n Ph.D. Thesis, University of Tolouse & Western Sydney University, 2018.\n \n\n\n\n
\n\n\n\n \n \n \"Refinement dissertation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Xiao2018PhDThesis,\n  author   = {Zhanhao Xiao},\n  title    = {Refinement of Intentions},\n  school   = {University of Tolouse \\& Western Sydney University},\n  year     = {2018},\n  abstract = {The mental attitudes, such as belief, desire, and intention, play a central role in the design and implementation of autonomous agents. In 1987, Bratman proposed a so-called belief-desire-intention (BDI) theory which inspired a multitude of BDI logics and BDI architectures. Bratman highlighted the fundamental role of an agent’s future-directed intentions: they are high-level plans to which the agent is committed. Such high-level plans cannot be executed directly: they have to be stepwise refined into more elaborated plans. Ideally the plans at the end of the refinement process contain only basic actions which the agent can perform directly. The process of intention refinement is crucial to the BDI theory and every step of refinement establishes a means-end relation between the refined intentions and the intentions refining it. However, there are very few accounts of hierarchical intention refinement in the existing BDI logics.<br/><br/>\n\nThe concept of automated planning is central in Bratman’s theory. As a traditional research community of artificial intelligence, automated planning has attracted numerous attentions and it has already been integrated into BDI architectures. In particular, the way of generating solutions in hierarchical task network (HTN) planning is refining high-level actions step-by-step until basic actions. Thus, the idea of HTN planning should be revelent for BDI agents. However, except for the line of work of de Silva and Sardina et al., hierarchical intention refinement has been scarcely considered in the existing BDI agents.<br/><br/>\n\nThe aim of this thesis is to provide a logic-based comprehensive analysis of the hierarchical refinement process. In this thesis, intention refinement is considered from two perspectives: the entailment and the primitive. From the former, intentions are managed in a co-called belief-intention database where refinement is addressed via the logical entailment based on the action law; while from the latter, refinement is defined in an explicit and static way, just as in HTN planning.<br/><br/>\n\nFrom the entailment perspective, this thesis starts with an extension of Shoham’s database framework on beliefs and intentions by introducing the notions of high-level intentions and environmental events. In a belief-intention database, a set of intentions can refine an intention if the set is minimal and suffices to guarantee the satisfaction of the intention. This thesis also investigates the complexity of the decision problems of satisfiability, consequence, refinement, instrumentality in the proposed database framework, which are all PSPACE-complete. Furthermore, this thesis explores the relations between the database framework and two logics: propositional linear temporal logic and dynamic logic with propositional assignment. The reductions to these two logics contribute to finding a set of intentions to refine a high-level intention via invoking the automated tools for these two logics.<br/><br/>\n\nFrom the primitive perspective, this thesis provides a logical semantics for HTN planning based on propositional dynamic logic. In the dynamic framework, refinement is captured by the program inclusion operator. By equipping high-level actions with pre- and postcondition, a coherence condition for HTN domains is proposed to evaluate the correctness of the predefined refinement methods. Moreover, the postulates of soundness and completeness for high-level actions are given under the dynamic semantics. When it comes to the completeness, it is usually a big challenge to define all possible refinement methods in HTN planning. It is promising to relax some restrictions on solutions: Geier & Bercher’s HTN planning with task insertion (TIHTN) allows solutions obtained by inserting actions. To capture the pre- and postcondition of actions, this thesis further extends TIHTN by introducing state constraints and calls the extension TIHTNS planning. It has been shown that the property of acyclic decomposition still holds in TIHTNS planning and then an acyclic progression operator for finding a plan is proposed. Based on the progression operator, it is proved that the additional consideration of state constraints does not increase the complexity of the plan-existence problem, staying in 2-NEXPTIME-complete.},\n url_Dissertation = {https://researchdirect.westernsydney.edu.au/islandora/object/uws%3A47368/datastream/PDF/view}\n}\n\n\n
\n
\n\n\n
\n The mental attitudes, such as belief, desire, and intention, play a central role in the design and implementation of autonomous agents. In 1987, Bratman proposed a so-called belief-desire-intention (BDI) theory which inspired a multitude of BDI logics and BDI architectures. Bratman highlighted the fundamental role of an agent’s future-directed intentions: they are high-level plans to which the agent is committed. Such high-level plans cannot be executed directly: they have to be stepwise refined into more elaborated plans. Ideally the plans at the end of the refinement process contain only basic actions which the agent can perform directly. The process of intention refinement is crucial to the BDI theory and every step of refinement establishes a means-end relation between the refined intentions and the intentions refining it. However, there are very few accounts of hierarchical intention refinement in the existing BDI logics.

The concept of automated planning is central in Bratman’s theory. As a traditional research community of artificial intelligence, automated planning has attracted numerous attentions and it has already been integrated into BDI architectures. In particular, the way of generating solutions in hierarchical task network (HTN) planning is refining high-level actions step-by-step until basic actions. Thus, the idea of HTN planning should be revelent for BDI agents. However, except for the line of work of de Silva and Sardina et al., hierarchical intention refinement has been scarcely considered in the existing BDI agents.

The aim of this thesis is to provide a logic-based comprehensive analysis of the hierarchical refinement process. In this thesis, intention refinement is considered from two perspectives: the entailment and the primitive. From the former, intentions are managed in a co-called belief-intention database where refinement is addressed via the logical entailment based on the action law; while from the latter, refinement is defined in an explicit and static way, just as in HTN planning.

From the entailment perspective, this thesis starts with an extension of Shoham’s database framework on beliefs and intentions by introducing the notions of high-level intentions and environmental events. In a belief-intention database, a set of intentions can refine an intention if the set is minimal and suffices to guarantee the satisfaction of the intention. This thesis also investigates the complexity of the decision problems of satisfiability, consequence, refinement, instrumentality in the proposed database framework, which are all PSPACE-complete. Furthermore, this thesis explores the relations between the database framework and two logics: propositional linear temporal logic and dynamic logic with propositional assignment. The reductions to these two logics contribute to finding a set of intentions to refine a high-level intention via invoking the automated tools for these two logics.

From the primitive perspective, this thesis provides a logical semantics for HTN planning based on propositional dynamic logic. In the dynamic framework, refinement is captured by the program inclusion operator. By equipping high-level actions with pre- and postcondition, a coherence condition for HTN domains is proposed to evaluate the correctness of the predefined refinement methods. Moreover, the postulates of soundness and completeness for high-level actions are given under the dynamic semantics. When it comes to the completeness, it is usually a big challenge to define all possible refinement methods in HTN planning. It is promising to relax some restrictions on solutions: Geier & Bercher’s HTN planning with task insertion (TIHTN) allows solutions obtained by inserting actions. To capture the pre- and postcondition of actions, this thesis further extends TIHTN by introducing state constraints and calls the extension TIHTNS planning. It has been shown that the property of acyclic decomposition still holds in TIHTNS planning and then an acyclic progression operator for finding a plan is proposed. Based on the progression operator, it is proved that the additional consideration of state constraints does not increase the complexity of the plan-existence problem, staying in 2-NEXPTIME-complete.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2017\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Novel Approaches for Generalized Planning.\n \n \n \n \n\n\n \n Damir Lotinac.\n\n\n \n\n\n\n Ph.D. Thesis, Pompeu Fabra University, 2017.\n \n\n\n\n
\n\n\n\n \n \n \"Novel dissertation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 2 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Lotinac2017PhDThesis,\n  author   = {Damir Lotinac},\n  title    = {Novel Approaches for Generalized Planning},\n  school   = {Pompeu Fabra University},\n  year     = {2017},\n  abstract = {Classical planning is the problem of finding a sequence of actions, from a given initial state to some goal state. While, in generalized planning, a plan is a solution to a set of planning problems, which belong to the same class. In this thesis we explore novel ways of computing generalized plans, inductively from a set of examples, and deductively from a model of actions.First we present an extension of planning programs, as a representation of a generalized plan, which is induced from a set of examples. The extension, allows for modeling of classification tasks.This work also introduces a novel domain-independent algorithm for generating hierarchical task networks directly from the action model and one representative instance of the planning problem. We also present the optimizations used by the translation and show that the algorithm is competitive with the state-of-the-art algorithms.},\n  url_Dissertation = {https://www.tdx.cat/bitstream/handle/10803/458525/tdl.pdf}\n}\n\n\n
\n
\n\n\n
\n Classical planning is the problem of finding a sequence of actions, from a given initial state to some goal state. While, in generalized planning, a plan is a solution to a set of planning problems, which belong to the same class. In this thesis we explore novel ways of computing generalized plans, inductively from a set of examples, and deductively from a model of actions.First we present an extension of planning programs, as a representation of a generalized plan, which is induced from a set of examples. The extension, allows for modeling of classification tasks.This work also introduces a novel domain-independent algorithm for generating hierarchical task networks directly from the action model and one representative instance of the planning problem. We also present the optimizations used by the translation and show that the algorithm is competitive with the state-of-the-art algorithms.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2016\n \n \n (2)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Automated Hierarchical, Forward-Chaining Temporal Planner for Planetary Robots Exploring Unknown Environments.\n \n \n \n \n\n\n \n Juan Manuel Delfa Victoria.\n\n\n \n\n\n\n Ph.D. Thesis, Technischen Universität Darmstadt, 2016.\n \n\n\n\n
\n\n\n\n \n \n \"Automated dissertation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Victoria2016PhDThesis,\n  author   = {Juan Manuel Delfa Victoria},\n  title    = {Automated Hierarchical, Forward-Chaining Temporal Planner for Planetary Robots Exploring Unknown Environments},\n  school   = {Technischen Universität Darmstadt},\n  year     = {2016},\n  abstract = {The transition of mobile robots from a controlled environment towards the real-world represents a major leap in terms of complexity coming primarily from three different factors: partial observability, non-determinism and dynamic events. To cope with them, robots must achieve some intelligence behaviours to be cost and operationally effective.<br/><br/>\n\n  Two particularly interesting examples of highly complex robotic scenarios are Mars rover missions and the Darpa Robotic Challenge (DRC). In spite of the important differences they present in terms of constraints and requirements, they both have adopted certain level of autonomy to overcome some specific problems. For instance, Mars rovers have been endowed with multiple systems to enable autonomous payload operations and consequently increase science return. In the case of DRC, most teams have autonomous footstep planning or arm trajectory calculation.<br/><br/>\n\n  Even though some specific problems can be addressed with dedicated tools, the general problem remains unsolved: to deploy on-board a reliable reasoning system able to operate robots without human intervention even in complex environments. This is precisely the goal of an automated mission planner.<br/>\n  The scientific community has provided plenty of planners able to provide very fast solutions for classical problems, typically characterized by the lack of time and resources representation. Moreover, there are also a handful of applied planners with higher levels of expressiveness at the price of lower performance. However, a fast, expressive and robust planner has never been used in complex robotic missions. These three properties represent the main drivers for the outcomes of this thesis.<br/><br/>\n\n  To bridge the gap between classical and applied planning, a novel formalism named Hierarchical TimeLine Networks (HTLN) combining Timeline and HTN planning has been proposed.<br/>\n  HTLN has been implemented on a mission planner named QuijoteExpress, the first forward-chaining timeline planner to the best of our knowledge. The main idea is to benefit from the great performance of forward-chaining search to resolve temporal problems on the state-space. In addition, QuijoteExpress includes search enhancements such as parallel planning by division of the problem in sub-problems or advanced heuristics management. Regarding expressiveness, the planner incorporates HTN techniques that allow to define hierarchical models and solutions. Finally, plan robustness in uncertain scenarios has been addressed by means of sufficient plans that allow to leave parts of valid plans undefined.<br/>\n  To test the planner, a novel lightweight, timeline and ROS-based executive named SanchoExpress has been designed to translate the plans into actions understandable by the different robot subsystems.<br/><br/>\n\n  The entire approach has been tested in two realistic and complementary domains. A cooperative multi-rover Mars mission and an urban search and rescue mission. The results were extremely positive and opens new promising ways in the field of automated planning applied to robotics.},\n  url_Dissertation = {http://tuprints.ulb.tu-darmstadt.de/5537/1/dissertation.pdf}\n}\n\n\n
\n
\n\n\n
\n The transition of mobile robots from a controlled environment towards the real-world represents a major leap in terms of complexity coming primarily from three different factors: partial observability, non-determinism and dynamic events. To cope with them, robots must achieve some intelligence behaviours to be cost and operationally effective.

Two particularly interesting examples of highly complex robotic scenarios are Mars rover missions and the Darpa Robotic Challenge (DRC). In spite of the important differences they present in terms of constraints and requirements, they both have adopted certain level of autonomy to overcome some specific problems. For instance, Mars rovers have been endowed with multiple systems to enable autonomous payload operations and consequently increase science return. In the case of DRC, most teams have autonomous footstep planning or arm trajectory calculation.

Even though some specific problems can be addressed with dedicated tools, the general problem remains unsolved: to deploy on-board a reliable reasoning system able to operate robots without human intervention even in complex environments. This is precisely the goal of an automated mission planner.
The scientific community has provided plenty of planners able to provide very fast solutions for classical problems, typically characterized by the lack of time and resources representation. Moreover, there are also a handful of applied planners with higher levels of expressiveness at the price of lower performance. However, a fast, expressive and robust planner has never been used in complex robotic missions. These three properties represent the main drivers for the outcomes of this thesis.

To bridge the gap between classical and applied planning, a novel formalism named Hierarchical TimeLine Networks (HTLN) combining Timeline and HTN planning has been proposed.
HTLN has been implemented on a mission planner named QuijoteExpress, the first forward-chaining timeline planner to the best of our knowledge. The main idea is to benefit from the great performance of forward-chaining search to resolve temporal problems on the state-space. In addition, QuijoteExpress includes search enhancements such as parallel planning by division of the problem in sub-problems or advanced heuristics management. Regarding expressiveness, the planner incorporates HTN techniques that allow to define hierarchical models and solutions. Finally, plan robustness in uncertain scenarios has been addressed by means of sufficient plans that allow to leave parts of valid plans undefined.
To test the planner, a novel lightweight, timeline and ROS-based executive named SanchoExpress has been designed to translate the plans into actions understandable by the different robot subsystems.

The entire approach has been tested in two realistic and complementary domains. A cooperative multi-rover Mars mission and an urban search and rescue mission. The results were extremely positive and opens new promising ways in the field of automated planning applied to robotics.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Temporal and Hierarchical Models for Planning and Acting in Robotics.\n \n \n \n \n\n\n \n Arthur Bit-Monnot.\n\n\n \n\n\n\n Ph.D. Thesis, Université de Toulouse, 2016.\n \n\n\n\n
\n\n\n\n \n \n \"Temporal dissertation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{BitMonnot2016PhDThesis,\n  author = {Arthur Bit-Monnot},\n  title = {Temporal and Hierarchical Models for Planning and Acting in Robotics},\n  school = {Universit\\'{e} de Toulouse},\n  year = {2016},\n  abstract = {The field of AI planning has seen rapid progress over the last decade and planners are now able to find plans with hundreds of actions in a matter of seconds. Despite those important progresses, robotic systems still tend to have a reactive architecture with very little deliberation on the course of the plan they might follow. In this thesis, we argue that a successful integration with a robotic system requires the planner to have capacities for both temporal and hierarchical reasoning. The former is indeed a universal resource central in many robot activities while the latter is a critical component for the integration of reasoning capabilities at different abstraction levels, typically starting with a high level view of an activity that is iteratively refined down to motion primitives.<br/><br/>\n\n  As a first step to carry out this vision, we present a model for temporal planning unifying the generative and hierarchical approaches. At the center of the model are temporal action templates complemented with a specification of the initial state as well as the expected evolution of the environment over time. In addition, our model allows for the specification of hierarchical knowledge possibly with a partial coverage. Consequently, our model generalizes the existing generative and hierarchical approaches together with an explicit time representation.<br/><br/>\n\n  In the subsequent chapter, we introduce a planning procedure suitable for our planning model. In order to support hierarchical features, we extend the existing Partial-Order Causal Link approach used in many constraint-based planners, with the notions of task and decomposition. We implement it in FAPE (Flexible Acting and Planning Environment) together with automated problem analysis techniques used for search guidance. We show FAPE to have performance similar to state of the art temporal planners when used in a generative setting, and the addition of hierarchical information to lead to further performance gain.<br/><br/>\n\n  Next, we study the usual methods used to reason on temporal uncertainty while planning. We relax the usual assumption of total observability and instead provide techniques to reason on the observations needed to maintain a plan dispatchable. We show how such needed observations can be detected at planning time and incrementally dealt with by considering the appropriate sensing actions.<br/><br/>\n\n  In a final chapter, we discuss the place of the proposed planning system as a central component for the control of a robotic actor. We demonstrate how the explicit time representation facilitates plan monitoring and action dispatching when dealing with contingent events that require observation. We take advantage of the constraint-based and hierarchical representation to facilitate both plan-repair procedures as well opportunistic plan refinement at acting time.},\n  url_Dissertation = {https://hal.laas.fr/tel-01444926/document}\n}\n\n\n
\n
\n\n\n
\n The field of AI planning has seen rapid progress over the last decade and planners are now able to find plans with hundreds of actions in a matter of seconds. Despite those important progresses, robotic systems still tend to have a reactive architecture with very little deliberation on the course of the plan they might follow. In this thesis, we argue that a successful integration with a robotic system requires the planner to have capacities for both temporal and hierarchical reasoning. The former is indeed a universal resource central in many robot activities while the latter is a critical component for the integration of reasoning capabilities at different abstraction levels, typically starting with a high level view of an activity that is iteratively refined down to motion primitives.

As a first step to carry out this vision, we present a model for temporal planning unifying the generative and hierarchical approaches. At the center of the model are temporal action templates complemented with a specification of the initial state as well as the expected evolution of the environment over time. In addition, our model allows for the specification of hierarchical knowledge possibly with a partial coverage. Consequently, our model generalizes the existing generative and hierarchical approaches together with an explicit time representation.

In the subsequent chapter, we introduce a planning procedure suitable for our planning model. In order to support hierarchical features, we extend the existing Partial-Order Causal Link approach used in many constraint-based planners, with the notions of task and decomposition. We implement it in FAPE (Flexible Acting and Planning Environment) together with automated problem analysis techniques used for search guidance. We show FAPE to have performance similar to state of the art temporal planners when used in a generative setting, and the addition of hierarchical information to lead to further performance gain.

Next, we study the usual methods used to reason on temporal uncertainty while planning. We relax the usual assumption of total observability and instead provide techniques to reason on the observations needed to maintain a plan dispatchable. We show how such needed observations can be detected at planning time and incrementally dealt with by considering the appropriate sensing actions.

In a final chapter, we discuss the place of the proposed planning system as a central component for the control of a robotic actor. We demonstrate how the explicit time representation facilitates plan monitoring and action dispatching when dealing with contingent events that require observation. We take advantage of the constraint-based and hierarchical representation to facilitate both plan-repair procedures as well opportunistic plan refinement at acting time.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2015\n \n \n (2)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Coordinating Services Embedded Everywhere Via Hierarchical Planning.\n \n \n \n \n\n\n \n Ilche Georgievski.\n\n\n \n\n\n\n Ph.D. Thesis, University of Groningen, 2015.\n \n\n\n\n
\n\n\n\n \n \n \"Coordinating dissertation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Georgievski2015PhDThesis,\n  author   = {Ilche Georgievski},\n  title    = {Coordinating Services Embedded Everywhere Via Hierarchical Planning},\n  school   = {University of Groningen},\n  year     = {2015},\n  abstract = {--- This work has no abstract ---},\n  url_Dissertation = {https://www.rug.nl/research/portal/files/23863757/Complete_thesis.pdf}\n}\n\n\n
\n
\n\n\n
\n — This work has no abstract —\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Hierarchical Goal Network: Formalisms and Algorithms for Planning and Acting.\n \n \n \n \n\n\n \n Vikas Shivashankar.\n\n\n \n\n\n\n Ph.D. Thesis, University of Maryland, 2015.\n \n\n\n\n
\n\n\n\n \n \n \"Hierarchical dissertation\n  \n \n \n \"Hierarchical uri\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Shivashankar15PhDThesis,\n  Title = {Hierarchical Goal Network: Formalisms and Algorithms for Planning and Acting},\n  Author = {Vikas Shivashankar},\n  School = {University of Maryland},\n  Year = {2015},\n  Abstract = {In real-world applications of AI and automation such as in robotics, computer game playing and web-services, agents need to make decisions in unstructured environments that are open-world, dynamic and partially observable. In the AI and Robotics research communities in particular, there is much interest in equipping robots to operate with minimal human intervention in diverse scenarios such as in manufacturing plants, homes, hospitals, etc. Enabling agents to operate in these environments requires advanced planning and acting capabilities, some of which are not well supported by the current state of the art automated planning formalisms and algorithms. To address this problem, in my thesis I propose a new planning formalism that addresses some of the inadequacies in current planning frameworks, and a suite of planning and acting algorithms that operate under this planning framework.<br/><br/>\n\n  The main contributions of this thesis are:<br/>\n  • Hierarchical Goal Network (HGN) Planning Formalism. This planning formalism combines aspects (and therefore harnesses advantages) of Classical Planning and Hierarchical Task Network (HTN) Planning, two of the most prominent planning formalisms currently in use. In particular, HGN planning algorithms, while retaining the efficiency and scalability advantages of HTNs, also allows incorporation of heuristics and other reasoning techniques from Classical Planning.<br/>\n  • Planning Algorithms. Goal Decomposition Planner (GDP) and the Goal Decomposition with Landmarks (GoDeL) planner are two HGN planning algorithms that combines hierarchical decomposition with classical planning heuristics to outperform state-of-the-art HTN planners like SHOP and SHOP2.<br/>\n  • Integration with Robotics. The Combined HGN and Motion Planning (CHaMP) algorithm integrates GoDeLwith low-level motion and manipulation planning algorithms in Robotics to generate plans directly executable by robots. Given the need for autonomous agents to operate in open, dynamic and unstructured environments and the obvious need for high-level deliberation capabilities to enable intelligent behavior, the planning-and-acting systems that are developed as part of this thesis may provide unique insights into ways to realize these systems in the real world.},\n url_Dissertation = {https://drum.lib.umd.edu/bitstream/handle/1903/16698/Shivashankar_umd_0117E_16202.pdf},\n url_URI = {http://hdl.handle.net/1903/16698}\n}\n\n\n
\n
\n\n\n
\n In real-world applications of AI and automation such as in robotics, computer game playing and web-services, agents need to make decisions in unstructured environments that are open-world, dynamic and partially observable. In the AI and Robotics research communities in particular, there is much interest in equipping robots to operate with minimal human intervention in diverse scenarios such as in manufacturing plants, homes, hospitals, etc. Enabling agents to operate in these environments requires advanced planning and acting capabilities, some of which are not well supported by the current state of the art automated planning formalisms and algorithms. To address this problem, in my thesis I propose a new planning formalism that addresses some of the inadequacies in current planning frameworks, and a suite of planning and acting algorithms that operate under this planning framework.

The main contributions of this thesis are:
• Hierarchical Goal Network (HGN) Planning Formalism. This planning formalism combines aspects (and therefore harnesses advantages) of Classical Planning and Hierarchical Task Network (HTN) Planning, two of the most prominent planning formalisms currently in use. In particular, HGN planning algorithms, while retaining the efficiency and scalability advantages of HTNs, also allows incorporation of heuristics and other reasoning techniques from Classical Planning.
• Planning Algorithms. Goal Decomposition Planner (GDP) and the Goal Decomposition with Landmarks (GoDeL) planner are two HGN planning algorithms that combines hierarchical decomposition with classical planning heuristics to outperform state-of-the-art HTN planners like SHOP and SHOP2.
• Integration with Robotics. The Combined HGN and Motion Planning (CHaMP) algorithm integrates GoDeLwith low-level motion and manipulation planning algorithms in Robotics to generate plans directly executable by robots. Given the need for autonomous agents to operate in open, dynamic and unstructured environments and the obvious need for high-level deliberation capabilities to enable intelligent behavior, the planning-and-acting systems that are developed as part of this thesis may provide unique insights into ways to realize these systems in the real world.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2013\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Search Complexities for HTN Planning.\n \n \n \n \n\n\n \n Ron Alford.\n\n\n \n\n\n\n Ph.D. Thesis, University of Maryland, 2013.\n \n\n\n\n
\n\n\n\n \n \n \"Search dissertation\n  \n \n \n \"Search dissertation-abstract\n  \n \n \n \"Search uri\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Alford2013PhDThesis,\n  Title = {Search Complexities for HTN Planning},\n  Author = {Ron Alford},\n  School = {University of Maryland},\n  Year = {2013},\n  Abstract = {Hierarchical Task Network (HTN) planning is the problem of decomposing an initial task into a sequence of executable steps. Often viewed as just a way to encode human knowledge to solve classical planning problems faster, HTN planning is more expressive than classical planning, even to the point of being undecidable in the general case. However, HTN planning is not just a way to solve planning problems faster, but is itself a search problem that can benefit from its own distinct search algorithms and heuristics.<br/><br/>\n\n  The dissertation examines the complexities of various HTN planning problem classes in order to motivate the development of heuristic search algorithms for HTN planning which are guaranteed to terminate on a large class of syntactically identifiable problems, as well as domain independent heuristics for those algorithms to use. This will allow HTN planning to be used in a number of areas where problems may be unsolvable, including during the initial development of a domain and for use in policy generation in non-deterministic planning environments.<br/><br/>\n\n  In particular, this dissertation analyzes two commonly used algorithms for HTN planning and describes the subsets of HTN problems that these algorithms terminate on. This allows us to discuss the run-times of these algorithms and compare the expressivity of the classes of problems they decide. We provide two new HTN algorithms which terminate on a strictly broader and more expressive set of HTN problems.<br/><br/>\n\n  We also analyze the complexity of delete-free HTN planning, an analogue to delete-free classical planning which is the base of many classical planning heuristics. We show that delete-free HTN planning is NP-complete, putting the existence of strict-semantics delete-relaxation-based HTN heuristics out of reach for practical purposes.<br/><br/>\n\n  Finally, we provide a translation of a large subset of HTN planning to classical planning, which allows us to use a classical planner as a surrogate for a heuristic HTN planner. Our experiments show that even small amounts and incomplete amounts of HTN knowledge, when translated into PDDL using our algorithm, can greatly improve a classical planner’s performance.},\n  url_Dissertation = {https://drum.lib.umd.edu/bitstream/handle/1903/15114/Alford_umd_0117E_14875.pdf},\n  url_Dissertation-abstract = {https://link.springer.com/article/10.1007/s13218-015-0396-6},\n  url_URI = {http://hdl.handle.net/1903/15114}\n}\n\n\n
\n
\n\n\n
\n Hierarchical Task Network (HTN) planning is the problem of decomposing an initial task into a sequence of executable steps. Often viewed as just a way to encode human knowledge to solve classical planning problems faster, HTN planning is more expressive than classical planning, even to the point of being undecidable in the general case. However, HTN planning is not just a way to solve planning problems faster, but is itself a search problem that can benefit from its own distinct search algorithms and heuristics.

The dissertation examines the complexities of various HTN planning problem classes in order to motivate the development of heuristic search algorithms for HTN planning which are guaranteed to terminate on a large class of syntactically identifiable problems, as well as domain independent heuristics for those algorithms to use. This will allow HTN planning to be used in a number of areas where problems may be unsolvable, including during the initial development of a domain and for use in policy generation in non-deterministic planning environments.

In particular, this dissertation analyzes two commonly used algorithms for HTN planning and describes the subsets of HTN problems that these algorithms terminate on. This allows us to discuss the run-times of these algorithms and compare the expressivity of the classes of problems they decide. We provide two new HTN algorithms which terminate on a strictly broader and more expressive set of HTN problems.

We also analyze the complexity of delete-free HTN planning, an analogue to delete-free classical planning which is the base of many classical planning heuristics. We show that delete-free HTN planning is NP-complete, putting the existence of strict-semantics delete-relaxation-based HTN heuristics out of reach for practical purposes.

Finally, we provide a translation of a large subset of HTN planning to classical planning, which allows us to use a classical planner as a surrogate for a heuristic HTN planner. Our experiments show that even small amounts and incomplete amounts of HTN knowledge, when translated into PDDL using our algorithm, can greatly improve a classical planner’s performance.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2012\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Hierarchical Planning Knowledge for Refining Partial-Order Plans.\n \n \n \n \n\n\n \n Stephen Montgomery Lee-Urban.\n\n\n \n\n\n\n Ph.D. Thesis, Lehigh University, 2012.\n \n\n\n\n
\n\n\n\n \n \n \"Hierarchical dissertation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Lee-Urban2012PhDThesis,\n  author   = {Stephen Montgomery Lee-Urban},\n  title    = {Hierarchical Planning Knowledge for Refining Partial-Order Plans},\n  school   = {Lehigh University},\n  year     = {2012},\n  abstract = {Automated plan synthesis, or “generative planning”,is a process whereby a course of action -- a plan -- is generated to achieve some desired goals. When the planning process uses a previously formulated plan as a starting point for solving a new problem, the process is called “plan adaptation”.Over the years there has been a significant research effort on plan adaptation. Part of the reason for this continuing interest in plan adaptation is attributable to studies indicating a wide range of potential applications, which include military planning, computer gaming, narrative computing, manufacturing, route planning, and medicine. Despite this remarkable body of research, existing plan adaptation algorithms do not scale well with problem size; even on medium-size problems, the performance of plan adaptation tends to be rather poor. Furthermore, for some worst-case situations it has been proven that the computational complexity of plan adaptation can be greater than that of generative planning. Although these worst-case scenarios have been shown to be inapplicable to most existing adaptation algorithms, it is nevertheless a fact that the lack of scalability of plan adaptation techniques is a major hurdle preventing their use in real-world applications.<br/><br/>\n\n  Them main goal of this dissertation is to address the problem of how to efficiently represent and apply high-quality, hand-crafted plan refinement and plan adaptation knowledge. To accomplish this goal I studied domain-configurable plan adaptation, the results of which are presented in this dissertation. This new problem-solving paradigm uses domain-specific knowledge about plan adaptation to guide a domain-independent 2plan adaptation algorithm. This new technique is novel in that existing approaches for plan adaptation modify the input plan by either using domain-independent plan adaptation knowledge in a domain-independent adaptation algorithm or domain-specific plan adaptation knowledge in a domain-specific adaptation algorithm.By focusing on the use of hand-crafted expert partial-order planning control knowledge and its representation, one most notably eases the burden of knowledge acquisition –that is one does not need a complete knowledge base in order to create good plans. This permits the knowledge engineer to focus on encoding strategies most relevant to solving the problems, while leaving the more mundane and human-difficult chores of “plan bookkeeping” to the underlying planner.},\n  url_Dissertation = {https://preserve.lehigh.edu/cgi/viewcontent.cgi?article=2213&context=etd}\n}\n\n\n
\n
\n\n\n
\n Automated plan synthesis, or “generative planning”,is a process whereby a course of action – a plan – is generated to achieve some desired goals. When the planning process uses a previously formulated plan as a starting point for solving a new problem, the process is called “plan adaptation”.Over the years there has been a significant research effort on plan adaptation. Part of the reason for this continuing interest in plan adaptation is attributable to studies indicating a wide range of potential applications, which include military planning, computer gaming, narrative computing, manufacturing, route planning, and medicine. Despite this remarkable body of research, existing plan adaptation algorithms do not scale well with problem size; even on medium-size problems, the performance of plan adaptation tends to be rather poor. Furthermore, for some worst-case situations it has been proven that the computational complexity of plan adaptation can be greater than that of generative planning. Although these worst-case scenarios have been shown to be inapplicable to most existing adaptation algorithms, it is nevertheless a fact that the lack of scalability of plan adaptation techniques is a major hurdle preventing their use in real-world applications.

Them main goal of this dissertation is to address the problem of how to efficiently represent and apply high-quality, hand-crafted plan refinement and plan adaptation knowledge. To accomplish this goal I studied domain-configurable plan adaptation, the results of which are presented in this dissertation. This new problem-solving paradigm uses domain-specific knowledge about plan adaptation to guide a domain-independent 2plan adaptation algorithm. This new technique is novel in that existing approaches for plan adaptation modify the input plan by either using domain-independent plan adaptation knowledge in a domain-independent adaptation algorithm or domain-specific plan adaptation knowledge in a domain-specific adaptation algorithm.By focusing on the use of hand-crafted expert partial-order planning control knowledge and its representation, one most notably eases the burden of knowledge acquisition –that is one does not need a complete knowledge base in order to create good plans. This permits the knowledge engineer to focus on encoding strategies most relevant to solving the problems, while leaving the more mundane and human-difficult chores of “plan bookkeeping” to the underlying planner.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2011\n \n \n (2)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Learning Hierarchical Task Networks From Traces and Semantically Annotated Tasks.\n \n \n \n \n\n\n \n Chad Michael Hogg.\n\n\n \n\n\n\n Ph.D. Thesis, Lehigh University, 2011.\n \n\n\n\n
\n\n\n\n \n \n \"Learning dissertation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Hogg2011PhDThesis,\n  author   = {Chad Michael Hogg},\n  title    = {Learning Hierarchical Task Networks From Traces and Semantically Annotated Tasks},\n  school   = {Lehigh University},\n  year     = {2011},\n  abstract = {Hierarchical Task Network planning is a fast and highly expressive formalism for problem solving, but systems based on this formalism depend on the existence of domain-specific knowledge constructs (methods) describing how and in what circumstances complex tasks may be reduced into simpler tasks in order to solve problems. Writing and debugging a set of methods for a new domain has in the past been a difficult and error-prone manual process. This dissertation presents and evaluates a framework in which HTN methods can be automatically learned from a classical planning domain description, a set of example pairs of planning states from that domain with plans applicable in those states, and a set of annotated tasks for that domain. Annotated task are task symbols with associated preconditions and postconditions describing what it means to accomplish those tasks.<br/><br/>\n\n  The primary algorithm based on this framework is HTN-Maker, which works by searching the input plans for subplans over which an annotated task has been accomplished and using goal regression to build a recursive series of explanations of how the task was accomplished. Each of these explanations becomes a method stating that the task may be reduced into its subtasks and giving conditions under which this will be valid. These methods that have been learned can then be used by an HTN planner to solve HTN planning problems.<br/><br/>\n\n  The implementation of the HTN-Maker algorithm has a number of configurable options and design decisions relating to such questions as how subtasks should be grouped together, how constants should be generalized into variables, and whether or not effort should be expended in discovering and pruning unnecessary methods. Theoretical results show that if the system is configured properly, the methods learned by HTN-Maker will accurately model the annotated tasks from which they were learned. They also show that, from a finite number of examples, HTN-Maker is capable of learning a set of methods for a domain that can be used to solve all solvable problems in that domain that can be expressed using the provided annotated tasks. There are HTN planning problems that cannot be expressed using annotated tasks, and thus cannot be solved using methods learned by HTN-Maker, but there are also non-classical problems that can be solved using the methods learned by HTN-Maker.<br/><br/>\n\n  HTN-MakerND is an extension of HTN-Maker that learns methods that will be effective in domains in which actions do not have deterministic effects. It does so by learning methods with a carefully chosen structure that maximizes flexibility when using those methods. Q-Maker is an extension of HTN-Maker that learns both methods and estimated values of those methods intended to guide a planner toward a near-optimal plan quickly. A further algorithm, Q-Reinforce, uses reinforcement learning to refine these method values through planning experience, and Q-Shop uses the methods and values to solve planning problems, preferring to use methods with higher values when given a choice.<br/><br/>\n\n  Experimental results in several benchmark planning domains explore the consequences of several of the options and design decisions in HTN-Maker on the amount of useful knowledge it is able to extract from examples and on the speed of planning with the methods that it learns. The evaluation demonstrates that both HTN-Maker and HTN-MakerND are able to learn knowledge that generalizes well to new problems. In four of five deterministic domains and both nondeterministic domains, planning with the learned methods is much faster than non-HTN planning. Q-Shop using methods learned by Q-Maker and refined by Q-Reinforce produces plans that are of higher quality than those produced by traditional satisficing planners while still running much more quickly than an optimal planner in both domains in which it was tested.},\n url_Dissertation = {https://preserve.lehigh.edu/cgi/viewcontent.cgi?article=2235&context=etd}\n}\n\n\n
\n
\n\n\n
\n Hierarchical Task Network planning is a fast and highly expressive formalism for problem solving, but systems based on this formalism depend on the existence of domain-specific knowledge constructs (methods) describing how and in what circumstances complex tasks may be reduced into simpler tasks in order to solve problems. Writing and debugging a set of methods for a new domain has in the past been a difficult and error-prone manual process. This dissertation presents and evaluates a framework in which HTN methods can be automatically learned from a classical planning domain description, a set of example pairs of planning states from that domain with plans applicable in those states, and a set of annotated tasks for that domain. Annotated task are task symbols with associated preconditions and postconditions describing what it means to accomplish those tasks.

The primary algorithm based on this framework is HTN-Maker, which works by searching the input plans for subplans over which an annotated task has been accomplished and using goal regression to build a recursive series of explanations of how the task was accomplished. Each of these explanations becomes a method stating that the task may be reduced into its subtasks and giving conditions under which this will be valid. These methods that have been learned can then be used by an HTN planner to solve HTN planning problems.

The implementation of the HTN-Maker algorithm has a number of configurable options and design decisions relating to such questions as how subtasks should be grouped together, how constants should be generalized into variables, and whether or not effort should be expended in discovering and pruning unnecessary methods. Theoretical results show that if the system is configured properly, the methods learned by HTN-Maker will accurately model the annotated tasks from which they were learned. They also show that, from a finite number of examples, HTN-Maker is capable of learning a set of methods for a domain that can be used to solve all solvable problems in that domain that can be expressed using the provided annotated tasks. There are HTN planning problems that cannot be expressed using annotated tasks, and thus cannot be solved using methods learned by HTN-Maker, but there are also non-classical problems that can be solved using the methods learned by HTN-Maker.

HTN-MakerND is an extension of HTN-Maker that learns methods that will be effective in domains in which actions do not have deterministic effects. It does so by learning methods with a carefully chosen structure that maximizes flexibility when using those methods. Q-Maker is an extension of HTN-Maker that learns both methods and estimated values of those methods intended to guide a planner toward a near-optimal plan quickly. A further algorithm, Q-Reinforce, uses reinforcement learning to refine these method values through planning experience, and Q-Shop uses the methods and values to solve planning problems, preferring to use methods with higher values when given a choice.

Experimental results in several benchmark planning domains explore the consequences of several of the options and design decisions in HTN-Maker on the amount of useful knowledge it is able to extract from examples and on the speed of planning with the methods that it learns. The evaluation demonstrates that both HTN-Maker and HTN-MakerND are able to learn knowledge that generalizes well to new problems. In four of five deterministic domains and both nondeterministic domains, planning with the learned methods is much faster than non-HTN planning. Q-Shop using methods learned by Q-Maker and refined by Q-Reinforce produces plans that are of higher quality than those produced by traditional satisficing planners while still running much more quickly than an optimal planner in both domains in which it was tested.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Hierarchical Methods for Optimal Long-Term Planning.\n \n \n \n \n\n\n \n Jason Wolfe.\n\n\n \n\n\n\n Ph.D. Thesis, EECS Department, University of California, Berkeley, 2011.\n \n\n\n\n
\n\n\n\n \n \n \"Hierarchical dissertation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@phdthesis{Wolfe2011Dissertation,\n  Author   = {Jason Wolfe},\n  Title    = {Hierarchical Methods for Optimal Long-Term Planning},\n  School   = {EECS Department, University of California, Berkeley},\n  Year     = {2011},\n  Abstract = {This thesis addresses the problem of generating goal-directed plans involving very many elementary actions. For example, to achieve a real-world goal such as earning a Ph.D., an intelligent agent may carry out millions of actions at the level of reading a word or striking a key. Given computational constraints, it seems that such long-term planning must incorporate reasoning with high-level actions (such as delivering a conference talk or typing a paragraph of a research paper) that abstract over the precise details of their implementations, despite the fact that these details must eventually be determined for the actions to be executed. This multi-level decision-making process is the subject of hierarchical planning.<br/><br/>\n\n  To most effectively plan with high-level actions, one would like to be able to correctly identify whether a high-level plan works, without first considering its low-level implementations. The first contribution of this thesis is an "angelic" semantics for high-level actions that enables such inferences. This semantics also provides bounds on the costs of high-level plans, enabling the identification of provably high-quality (or even optimal) high-level solutions.<br/>\n\n  Effective hierarchical planning also requires algorithms to efficiently search through the space of high-level plans for high-quality solutions. We demonstrate how angelic bounds can be used to speed up search, and introduce a novel decomposed planning framework that leverages task-specific state abstraction to eliminate many redundant computations. These techniques are instantiated in the Decomposed, Angelic, State-abstracted, Hierarchical A* (DASH-A*) algorithm, which can find hierarchically optimal solutions exponentially faster than previous algorithms.},\n  url_dissertation = {https://www2.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-138.pdf}\n}\n\n\n
\n
\n\n\n
\n This thesis addresses the problem of generating goal-directed plans involving very many elementary actions. For example, to achieve a real-world goal such as earning a Ph.D., an intelligent agent may carry out millions of actions at the level of reading a word or striking a key. Given computational constraints, it seems that such long-term planning must incorporate reasoning with high-level actions (such as delivering a conference talk or typing a paragraph of a research paper) that abstract over the precise details of their implementations, despite the fact that these details must eventually be determined for the actions to be executed. This multi-level decision-making process is the subject of hierarchical planning.

To most effectively plan with high-level actions, one would like to be able to correctly identify whether a high-level plan works, without first considering its low-level implementations. The first contribution of this thesis is an \"angelic\" semantics for high-level actions that enables such inferences. This semantics also provides bounds on the costs of high-level plans, enabling the identification of provably high-quality (or even optimal) high-level solutions.
Effective hierarchical planning also requires algorithms to efficiently search through the space of high-level plans for high-quality solutions. We demonstrate how angelic bounds can be used to speed up search, and introduce a novel decomposed planning framework that leverages task-specific state abstraction to eliminate many redundant computations. These techniques are instantiated in the Decomposed, Angelic, State-abstracted, Hierarchical A* (DASH-A*) algorithm, which can find hierarchically optimal solutions exponentially faster than previous algorithms.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2010\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Fusing DL Reasoning with HTN Planning as a Deliberative Layer in Mobile Robotics.\n \n \n \n \n\n\n \n Ronny Hartanto.\n\n\n \n\n\n\n Ph.D. Thesis, University of Osnabrück, Institute of Computer Science, 2010.\n \n\n\n\n
\n\n\n\n \n \n \"Fusing dissertation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Hartanto2010PhDThesis,\n  author    = {Ronny Hartanto},\n  title     = {Fusing DL Reasoning with HTN Planning as a Deliberative Layer in Mobile Robotics},\n  school    = {University of Osnabr\\"uck, Institute of Computer Science},\n  year      = {2010},\n  abstract  = {Action planning has been used in the field of robotics for solving long-running tasks. In the robot architectures field, it is also known as the deliberative layer. However, there is still a gap between the symbolic representation on the one hand and the low-level control and sensor representation on the other. In addition, the definition of a planning problem for a complex, real-world robot is not trivial. The planning process could become intractable as its search spaces become large. As the defined planning problem determines the complexity and the computationability for solving the problem, it should contain only relevant states. In this work, a novel approach which amalgamates Description Logic (DL) reasoning with Hierarchical Task Network (HTN) planning is introduced.<br/><br/>\n\n  The planning domain description as well as fundamental HTN planning concepts are represented in DL and can therefore be subject to DL reasoning; from these representations, concise planning problems are generated for HTN planning. The method is presented through an example in the robot navigation domain. In addition, a case study of the RoboCup@Home domain is given. As proof of concept, a well-known planning problem that often serves as a benchmark, namely that of the blocks-world, is modeled and solved using this approach.<br/><br/>\n\n  An analysis of the performance of the approach has been conducted and the results show that this approach yields significantly smaller planning problem descriptions than those generated by current representations in HTN planning.},\n  url_Dissertation = {https://repositorium.ub.uni-osnabrueck.de/bitstream/urn:nbn:de:gbv:700-201003085604/1/thesis_hartanto.pdf}\n}\n\n\n
\n
\n\n\n
\n Action planning has been used in the field of robotics for solving long-running tasks. In the robot architectures field, it is also known as the deliberative layer. However, there is still a gap between the symbolic representation on the one hand and the low-level control and sensor representation on the other. In addition, the definition of a planning problem for a complex, real-world robot is not trivial. The planning process could become intractable as its search spaces become large. As the defined planning problem determines the complexity and the computationability for solving the problem, it should contain only relevant states. In this work, a novel approach which amalgamates Description Logic (DL) reasoning with Hierarchical Task Network (HTN) planning is introduced.

The planning domain description as well as fundamental HTN planning concepts are represented in DL and can therefore be subject to DL reasoning; from these representations, concise planning problems are generated for HTN planning. The method is presented through an example in the robot navigation domain. In addition, a case study of the RoboCup@Home domain is given. As proof of concept, a well-known planning problem that often serves as a benchmark, namely that of the blocks-world, is modeled and solved using this approach.

An analysis of the performance of the approach has been conducted and the results show that this approach yields significantly smaller planning problem descriptions than those generated by current representations in HTN planning.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2009\n \n \n (2)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Planning in BDI Agent Systems.\n \n \n \n \n\n\n \n Lavindra Silva.\n\n\n \n\n\n\n Ph.D. Thesis, School of Computer Science and Information Technology, RMIT University, 2009.\n \n\n\n\n
\n\n\n\n \n \n \"Planning dissertation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{deSilva2009PhDThesis,\n  author    = {Lavindra de Silva},\n  title     = {Planning in BDI Agent Systems},\n  school    = {School of Computer Science and Information Technology, RMIT University},\n  year      = {2009},\n  abstract  = {Belief-Desire-Intention (BDI) agent systems are a popular approach to developing agents for complex and dynamic environments. These agents rely on context sensitive expansion of plans, acting as they go, and consequently, they do not incorporate a generic mechanism to do any kind of “look-ahead” or offline planning. This is useful when, for instance, important resources may be consumed by executing steps that are not necessary for a goal; steps are not reversible and may lead to situations in which a goal cannot be solved; and side effects of steps are undesirable if they are not useful for a goal. In this thesis, we incorporate planning techniques into BDI systems.<br/><br/>\n\n  First, we provide a general mechanism for performing “look-ahead” planning, using Hierarchical Task Network (HTN) planning techniques, so that an agent may guide its selection of plans for the purpose of avoiding negative interactions between them. Unlike past work on adding such planning into BDI agents, which do so only at the implementation level without any precise semantics, we provide a solid theoretical basis for such planning.<br/><br/>\n\n  Second, we incorporate first principles planning into BDI systems, so that new plans may be created for achieving goals. Unlike past work, which focuses on creating low-level plans, losing much of the domain knowledge encoded in BDI agents, we introduce a novel technique where plans are created by respecting and reusing the procedural domain knowledge encoded in such agents; our abstract plans can be executed in the standard BDI engine using this knowledge. Furthermore, we recognise an intrinsic tension between striving for abstract plans and, at the same time, ensuring that unnecessary actions, unrelated to the specific goal to be achieved, are avoided. To explore this tension, we characterise the set of “ideal” abstract plans that are non-redundant while maximally abstract, and then develop a more limited but feasible account where an abstract plan is “specialised” into a plan that is non-redundant and as abstract as possible. We present theoretical properties of the planning frameworks, as well as insights into their practical utility.},\n  url_Dissertation = {https://researchrepository.rmit.edu.au/esploro/outputs/doctoral/Planning-in-BDI-agent-systems/9921861322501341?institution=61RMIT_INST}\n}\n\n\n
\n
\n\n\n
\n Belief-Desire-Intention (BDI) agent systems are a popular approach to developing agents for complex and dynamic environments. These agents rely on context sensitive expansion of plans, acting as they go, and consequently, they do not incorporate a generic mechanism to do any kind of “look-ahead” or offline planning. This is useful when, for instance, important resources may be consumed by executing steps that are not necessary for a goal; steps are not reversible and may lead to situations in which a goal cannot be solved; and side effects of steps are undesirable if they are not useful for a goal. In this thesis, we incorporate planning techniques into BDI systems.

First, we provide a general mechanism for performing “look-ahead” planning, using Hierarchical Task Network (HTN) planning techniques, so that an agent may guide its selection of plans for the purpose of avoiding negative interactions between them. Unlike past work on adding such planning into BDI agents, which do so only at the implementation level without any precise semantics, we provide a solid theoretical basis for such planning.

Second, we incorporate first principles planning into BDI systems, so that new plans may be created for achieving goals. Unlike past work, which focuses on creating low-level plans, losing much of the domain knowledge encoded in BDI agents, we introduce a novel technique where plans are created by respecting and reusing the procedural domain knowledge encoded in such agents; our abstract plans can be executed in the standard BDI engine using this knowledge. Furthermore, we recognise an intrinsic tension between striving for abstract plans and, at the same time, ensuring that unnecessary actions, unrelated to the specific goal to be achieved, are avoided. To explore this tension, we characterise the set of “ideal” abstract plans that are non-redundant while maximally abstract, and then develop a more limited but feasible account where an abstract plan is “specialised” into a plan that is non-redundant and as abstract as possible. We present theoretical properties of the planning frameworks, as well as insights into their practical utility.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Hybrid Planning & Scheduling.\n \n \n \n \n\n\n \n Bernd Schattenberg.\n\n\n \n\n\n\n Ph.D. Thesis, Ulm University, Germany, 2009.\n \n\n\n\n
\n\n\n\n \n \n \"Hybrid dissertation\n  \n \n \n \"Hybrid dissertation-abstract\n  \n \n\n \n \n doi\n  \n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Schattenberg09PhDThesis,\n  author   = {Bernd Schattenberg},\n  title    = {Hybrid Planning \\& Scheduling},\n  school   = {Ulm University, Germany},\n  year     = {2009},\n  abstract = {Planning and scheduling are well-established disciplines in the field of Artificial Intelligence. They provide flexibility, robustness, and effectiveness to complex software systems in a variety of application areas. While planning is the process of finding a course of action that achieves a goal or performs a specified task, scheduling deals with the assignment of resources and time to given activities, taking into account resource restrictions and temporal dependencies. In other words, planning focuses on reasoning about causal structures and identifying the necessary actions for achieving a specific goal; scheduling concentrates on resource consumption and production for optimizing a coherent parameter assignment of a plan. As successful these techniques clearly are, the actual demands of complex, real-world applications go far beyond the potential of these single methods, however. They require an adequate integration of these problem solving methods as well as a combination of different planning and scheduling paradigms. Particularly important are abstraction-based, hierarchical approaches because of both their expressive knowledge representation and their efficiency in finding solutions. Current state-of-the-art systems rarely address the question of method integration; isolated approaches do so only in ad hoc implementations and mostly lack a proper formal basis.<br/><br/>\n\n  This thesis presents a formal framework for plan and schedule generation based on a well-founded conceptualization of refinement planning: An abstract problem specification is transformed stepwise into a concrete, executable solution. In each refinement step, plan deficiencies identify faulty or under-developed parts of the plan, which in turn triggers the generation of transformation operators that try to resolve them. All involved entities are explicitly represented and therefore transparent to the framework. This property allows for two novel aspects of our approach: First, any planning and scheduling methodology can be functionally decomposed and mapped on the deficiency announcement and plan transformation generation principle, and second, the framework allows for an explicit declaration of planning strategies. We first investigate the flexibility of the extremely modular system design by instantiating the framework in a variety of system configurations including classical partial-order causal-link (POCL) planning, hierarchical task-network (HTN) planning, and classical scheduling.<br/><br/>\n\n  As a key feature, the presented approach provides a formally integrated treatment of action and state abstraction, thus naturally combining causality-focused reasoning with hierarchical, procedure-oriented methods. While the use of procedural knowledge allows to rely on well-known, predefined solutions to planning problems, the non-hierarchical methods provide the flexibility to come up with non-standard solutions and to complete under-specified problem instances, respectively. The resulting technique of hybrid planning is capable of constructing a plan's causal and hierarchical structure across multiple levels of abstraction by using plan development options of both the POCL and HTN paradigms. We also present an integrated planning and scheduling system that is defined in our framework. For the first time, such a system is able to combine any ensemble of planning and scheduling technologies on the operational level and to address the respective deficiencies opportunistically. The accordingly unique representation of application domains incorporates temporal phenomena and resource manipulations not only for basic actions but on the abstract action level as well. This leads to the novel technique of hierarchical scheduling, in which the concept of abstraction is extended to resource representation and reasoning, for example resource aggregation and approximation.<br/><br/>\n\n  Thanks to its well-defined functional composition, the framework yields a major improvement with respect to the capabilities of planning and scheduling strategies. The explicitly represented information about a plan's deficiencies and development prospects makes it possible to utilize a new quality of knowledge sources, including relationships between deficiencies, refinements, and components in the plan to which they refer. This leads to the novel class of flexible strategies, which decide upon problem characteristics and the current state of the plan generation process, respectively. The most prominent representatives are our HotSpot and HotZone strategies, which take into account the structural dependencies between problematic elements in the plan when deciding upon their resolution. They are independent of both the application domain and the concrete framework instance. Therefore, they can be deployed for POCL planning as well as for integrated planning and scheduling, for example, and any other combination of methods the overall framework allows for. In addition, these strategy components are not only easily exchangeable, they can also be combined into sequences of decision procedures in which succeeding components fine-tune the choices of the preceding ones. We present the declarations of a comprehensive strategy repertoire, ranging from classical strategy components that implement well-known search principles from the literature to an assortment of flexible strategies. <br/><br/>\n\n  Our formal framework is not only a method for specifying a variety of planning and scheduling functionality, it also enables the derivation of software architectures for fielding the corresponding systems. We show how the formal entities of the framework can be directly mapped onto software artefacts in a knowledgebased multiagent architecture, which optimally supports concurrency - by enabling parallel computations of plan deficiencies and refinement options - as well as the paradigm of distributed knowledge management. While the former addresses the practical issue of managing multiple computational resources the latter matches perfectly the idea of different modules representing different planning and scheduling aspects.<br/><br/>\n\n  Our implementation of the framework resulted in a complex planning environment in which any planning and scheduling system can be easily compiled from a rich collection of functional components. By systematically alternating the system configuration and its parameters, it can also be used as a testbed for the evaluation of framework components, in particular planning strategies and refinement methods. This allowed for conducting a large-scale empirical study on dozens of strategy configurations, which is the first extensive experimental effort in the domain of hybrid planning. It concludes this thesis with four important results: First, we gain insights into the performance of members of our strategy portfolio on a set of benchmark problems. We thereby learned how to graduate performance measures and how to assess such test results. Second, we became familiar with the characteristics of the examined strategies, the experiment problems, and also of the benchmark domains. Third, our findings clearly support both the necessity and feasibility of systematic experimentation in order to identify suitable strategies for a given application domain. Last, but not least, our evaluation effort proves that our environment is an effective platform for orchestrating and operating component-based planning and scheduling systems, in terms of flexibility as well as in terms of efficiency.},\n doi = {10.18725/OPARU-1045},\n url_Dissertation = {https://oparu.uni-ulm.de/xmlui/bitstream/handle/123456789/1072/vts_6895_9580.pdf},\n url_Dissertation-abstract = {https://link.springer.com/article/10.1007/s13218-015-0390-z}\n}\n\n\n
\n
\n\n\n
\n Planning and scheduling are well-established disciplines in the field of Artificial Intelligence. They provide flexibility, robustness, and effectiveness to complex software systems in a variety of application areas. While planning is the process of finding a course of action that achieves a goal or performs a specified task, scheduling deals with the assignment of resources and time to given activities, taking into account resource restrictions and temporal dependencies. In other words, planning focuses on reasoning about causal structures and identifying the necessary actions for achieving a specific goal; scheduling concentrates on resource consumption and production for optimizing a coherent parameter assignment of a plan. As successful these techniques clearly are, the actual demands of complex, real-world applications go far beyond the potential of these single methods, however. They require an adequate integration of these problem solving methods as well as a combination of different planning and scheduling paradigms. Particularly important are abstraction-based, hierarchical approaches because of both their expressive knowledge representation and their efficiency in finding solutions. Current state-of-the-art systems rarely address the question of method integration; isolated approaches do so only in ad hoc implementations and mostly lack a proper formal basis.

This thesis presents a formal framework for plan and schedule generation based on a well-founded conceptualization of refinement planning: An abstract problem specification is transformed stepwise into a concrete, executable solution. In each refinement step, plan deficiencies identify faulty or under-developed parts of the plan, which in turn triggers the generation of transformation operators that try to resolve them. All involved entities are explicitly represented and therefore transparent to the framework. This property allows for two novel aspects of our approach: First, any planning and scheduling methodology can be functionally decomposed and mapped on the deficiency announcement and plan transformation generation principle, and second, the framework allows for an explicit declaration of planning strategies. We first investigate the flexibility of the extremely modular system design by instantiating the framework in a variety of system configurations including classical partial-order causal-link (POCL) planning, hierarchical task-network (HTN) planning, and classical scheduling.

As a key feature, the presented approach provides a formally integrated treatment of action and state abstraction, thus naturally combining causality-focused reasoning with hierarchical, procedure-oriented methods. While the use of procedural knowledge allows to rely on well-known, predefined solutions to planning problems, the non-hierarchical methods provide the flexibility to come up with non-standard solutions and to complete under-specified problem instances, respectively. The resulting technique of hybrid planning is capable of constructing a plan's causal and hierarchical structure across multiple levels of abstraction by using plan development options of both the POCL and HTN paradigms. We also present an integrated planning and scheduling system that is defined in our framework. For the first time, such a system is able to combine any ensemble of planning and scheduling technologies on the operational level and to address the respective deficiencies opportunistically. The accordingly unique representation of application domains incorporates temporal phenomena and resource manipulations not only for basic actions but on the abstract action level as well. This leads to the novel technique of hierarchical scheduling, in which the concept of abstraction is extended to resource representation and reasoning, for example resource aggregation and approximation.

Thanks to its well-defined functional composition, the framework yields a major improvement with respect to the capabilities of planning and scheduling strategies. The explicitly represented information about a plan's deficiencies and development prospects makes it possible to utilize a new quality of knowledge sources, including relationships between deficiencies, refinements, and components in the plan to which they refer. This leads to the novel class of flexible strategies, which decide upon problem characteristics and the current state of the plan generation process, respectively. The most prominent representatives are our HotSpot and HotZone strategies, which take into account the structural dependencies between problematic elements in the plan when deciding upon their resolution. They are independent of both the application domain and the concrete framework instance. Therefore, they can be deployed for POCL planning as well as for integrated planning and scheduling, for example, and any other combination of methods the overall framework allows for. In addition, these strategy components are not only easily exchangeable, they can also be combined into sequences of decision procedures in which succeeding components fine-tune the choices of the preceding ones. We present the declarations of a comprehensive strategy repertoire, ranging from classical strategy components that implement well-known search principles from the literature to an assortment of flexible strategies.

Our formal framework is not only a method for specifying a variety of planning and scheduling functionality, it also enables the derivation of software architectures for fielding the corresponding systems. We show how the formal entities of the framework can be directly mapped onto software artefacts in a knowledgebased multiagent architecture, which optimally supports concurrency - by enabling parallel computations of plan deficiencies and refinement options - as well as the paradigm of distributed knowledge management. While the former addresses the practical issue of managing multiple computational resources the latter matches perfectly the idea of different modules representing different planning and scheduling aspects.

Our implementation of the framework resulted in a complex planning environment in which any planning and scheduling system can be easily compiled from a rich collection of functional components. By systematically alternating the system configuration and its parameters, it can also be used as a testbed for the evaluation of framework components, in particular planning strategies and refinement methods. This allowed for conducting a large-scale empirical study on dozens of strategy configurations, which is the first extensive experimental effort in the domain of hybrid planning. It concludes this thesis with four important results: First, we gain insights into the performance of members of our strategy portfolio on a set of benchmark problems. We thereby learned how to graduate performance measures and how to assess such test results. Second, we became familiar with the characteristics of the examined strategies, the experiment problems, and also of the benchmark domains. Third, our findings clearly support both the necessity and feasibility of systematic experimentation in order to identify suitable strategies for a given application domain. Last, but not least, our evaluation effort proves that our environment is an effective platform for orchestrating and operating component-based planning and scheduling systems, in terms of flexibility as well as in terms of efficiency.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2006\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Planning Under Uncertainty: Moving Forward.\n \n \n \n \n\n\n \n Ugur Kuter.\n\n\n \n\n\n\n Ph.D. Thesis, University of Maryland, 2006.\n \n\n\n\n
\n\n\n\n \n \n \"Planning dissertation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Kuter2006PhDThesis,\n  author    = {Ugur Kuter},\n  title     = {Planning Under Uncertainty: Moving Forward},\n  school    = {University of Maryland},\n  year      = {2006},\n  abstract  = {Reasoning about uncertainty is an essential component of many real-world planning problems, such as robotic and space applications, military operations planning, air and ground traffic control, and manufacturing systems. Planning under uncertainty focuses on how to generate plans that will be executed in environments where actions have nondeterministic effects (i.e., actions may have more than one possible outcome) and the states of the world are not always fully observable. The two predominant approaches for planning under uncertainty are based on Markov Decision Processes (MDPs) and Symbolic Model Checking. Despite the recent advances in these approaches, the problem of how to plan under uncertainty is still very hard: the planning algorithms must reason about more than one possible execution path in the world, and the sizes of the solution plans may grow exponentially. In planning environments that do not admit full observability, the complexity of planning increases by an additional exponential factor since the planner does not know the exact states of the world, and therefore, it must reason over the set of all states that it believes to be in.},\n  url_Dissertation = {https://apps.dtic.mil/sti/pdfs/ADA599960.pdf}\n}\n\n\n
\n
\n\n\n
\n Reasoning about uncertainty is an essential component of many real-world planning problems, such as robotic and space applications, military operations planning, air and ground traffic control, and manufacturing systems. Planning under uncertainty focuses on how to generate plans that will be executed in environments where actions have nondeterministic effects (i.e., actions may have more than one possible outcome) and the states of the world are not always fully observable. The two predominant approaches for planning under uncertainty are based on Markov Decision Processes (MDPs) and Symbolic Model Checking. Despite the recent advances in these approaches, the problem of how to plan under uncertainty is still very hard: the planning algorithms must reason about more than one possible execution path in the world, and the sizes of the solution plans may grow exponentially. In planning environments that do not admit full observability, the complexity of planning increases by an additional exponential factor since the planner does not know the exact states of the world, and therefore, it must reason over the set of all states that it believes to be in.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 2000\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n GraphHTN: Combining Planning Graphs and HTN.\n \n \n \n \n\n\n \n Amnon Lotem.\n\n\n \n\n\n\n Ph.D. Thesis, University of Maryland, 2000.\n \n\n\n\n
\n\n\n\n \n \n \"GraphHTN: dissertation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Lotem2000PhDThesis,\n  author    = {Amnon Lotem},\n  title     = {GraphHTN: Combining Planning Graphs and HTN},\n  school    = {University of Maryland},\n  year      = {2000},\n  abstract  = {The abstract, just as the dissertation itself, is not publicly available.},\n  url_Dissertation = {https://www.proquest.com/openview/6964c51d227011ac4434121080717327/1?pq-origsite=gscholar&cbl=18750&diss=y}\n}\n\n\n
\n
\n\n\n
\n The abstract, just as the dissertation itself, is not publicly available.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 1999\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Efficient Refinement Strategies for HTN Planning.\n \n \n \n \n\n\n \n Reiko Tsuneto.\n\n\n \n\n\n\n Ph.D. Thesis, University of Maryland, 1999.\n \n\n\n\n
\n\n\n\n \n \n \"Efficient dissertation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Tsuneto1999PhDThesis,\n  author    = {Reiko Tsuneto},\n  title     = {Efficient Refinement Strategies for HTN Planning},\n  school    = {University of Maryland},\n  year      = {1999},\n  abstract  = {See the PDF. (It does not allow for copying text.)},\n  url_Dissertation = {http://www.cs.umd.edu/~nau/others-papers/tsuneto-thesis.pdf}\n}\n\n\n
\n
\n\n\n
\n See the PDF. (It does not allow for copying text.)\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 1998\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Hierarchical control and learning for Markov decision processes.\n \n \n \n \n\n\n \n Ronald Edward Parr.\n\n\n \n\n\n\n Ph.D. Thesis, University of California, 1998.\n \n\n\n\n
\n\n\n\n \n \n \"Hierarchical dissertation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Parr1998PhDThesis,\n  author    = {Ronald Edward Parr},\n  title     = {Hierarchical control and learning for Markov decision processes},\n  school    = {University of California},\n  year      = {1998},\n  abstract  = {See the PDF. (It does not allow for copying text.)},\n  url_Dissertation = {https://users.cs.duke.edu/~parr/thesis600.ps.gz}\n}\n\n\n
\n
\n\n\n
\n See the PDF. (It does not allow for copying text.)\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 1997\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Task-Network Planning using Total-Order Forward Search, and Applications to Bridge and to Microwave-Module Manufacture.\n \n \n \n \n\n\n \n Stephen J. Smith.\n\n\n \n\n\n\n Ph.D. Thesis, University of Maryland, 1997.\n \n\n\n\n
\n\n\n\n \n \n \"Task-Network dissertation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Smith1997PhDThesis,\n  author    = {Stephen J. J. Smith},\n  title     = {Task-Network Planning using Total-Order Forward Search, and Applications to Bridge and to Microwave-Module Manufacture},\n  school    = {University of Maryland},\n  year      = {1997},\n  abstract  = {Because most real-world planning problems are difficult, AI planning researchers have needed to make simplifying assumptions in order to solve some of these problems at all. These simplifying assumptions eliminated some of the difficult features that need to be considered to solve other problems. For example, in existing AI planning algorithms, the approaches to dealing with uncertainty and numerical values are insufficient to handle many important problems.<br/><br/>\n\n  To address these limitations, I have developed a new variant of Hierarchical Task Network (HTN) planning, which I call planning using TOFS (Total-Order Forward Search). In TOFS, a planner always instantiates the operators in a plan in the order that they will be executed.<br/><br/>\n\n  I have applied TOFS successfully to two very different real-world problems. (1) The first problem was play of declarer's cards at contract bridge. My implementation of HTN planning using TOFS, called Tignum 2, does statistically significantly better than the best available computer bridge program. (2) The second problem was automated process planning for the manufacture of microwave modules. My implementation of HTN planning using TOFS, called the EDAPS Process Planner, incorporates electronic and mechanical manufacturing processes, works concurrently with an electronic CAD tool, and provides feedback about manufacturability and lead time to the designers, based on actual process plans for the manufacture of the device. In both domains, HTN planning using TOFS ran relatively quickly, and searched relatively few nodes.<br/><br/>\n\n  In this dissertation, I describe HTN planning using TOFS, its application to these two domains, and consequent observations. I detail the adaptations of HTN planning using TOFS required to apply it to bridge, and the adaptations required to apply it to microwave module manufacture. I observe that TOFS allows the preconditions of methods to be written with arbitrary computer code, and discuss the advantages and disadvantages of this technique.<br/><br/>\n\n  Because both research projects were successful, I am confident that HTN planning using TOFS is an important new AI planning methodology. To reap the benefits of HTN planning using TOFS, a classification of domains into those for which it is suitable and those for which it is unsuitable must be further developed.},\n  url_Dissertation = {https://dl.acm.org/doi/book/10.5555/269097},\n  url_Dissertation = {https://www.proquest.com/openview/ed7fc8fce72252c05822622671d9e460/1?pq-origsite=gscholar&cbl=18750&diss=y}\n}\n\n\n
\n
\n\n\n
\n Because most real-world planning problems are difficult, AI planning researchers have needed to make simplifying assumptions in order to solve some of these problems at all. These simplifying assumptions eliminated some of the difficult features that need to be considered to solve other problems. For example, in existing AI planning algorithms, the approaches to dealing with uncertainty and numerical values are insufficient to handle many important problems.

To address these limitations, I have developed a new variant of Hierarchical Task Network (HTN) planning, which I call planning using TOFS (Total-Order Forward Search). In TOFS, a planner always instantiates the operators in a plan in the order that they will be executed.

I have applied TOFS successfully to two very different real-world problems. (1) The first problem was play of declarer's cards at contract bridge. My implementation of HTN planning using TOFS, called Tignum 2, does statistically significantly better than the best available computer bridge program. (2) The second problem was automated process planning for the manufacture of microwave modules. My implementation of HTN planning using TOFS, called the EDAPS Process Planner, incorporates electronic and mechanical manufacturing processes, works concurrently with an electronic CAD tool, and provides feedback about manufacturability and lead time to the designers, based on actual process plans for the manufacture of the device. In both domains, HTN planning using TOFS ran relatively quickly, and searched relatively few nodes.

In this dissertation, I describe HTN planning using TOFS, its application to these two domains, and consequent observations. I detail the adaptations of HTN planning using TOFS required to apply it to bridge, and the adaptations required to apply it to microwave module manufacture. I observe that TOFS allows the preconditions of methods to be written with arbitrary computer code, and discuss the advantages and disadvantages of this technique.

Because both research projects were successful, I am confident that HTN planning using TOFS is an important new AI planning methodology. To reap the benefits of HTN planning using TOFS, a classification of domains into those for which it is suitable and those for which it is unsuitable must be further developed.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 1996\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Hierarchical Task Network Planning: Formalization, Analysis, and Implementation.\n \n \n \n \n\n\n \n Kutluhan Erol.\n\n\n \n\n\n\n Ph.D. Thesis, University of Maryland, 1996.\n \n\n\n\n
\n\n\n\n \n \n \"Hierarchical dissertation\n  \n \n \n \"Hierarchical uri\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Erol96PhDThesis,\n  Title    = {Hierarchical Task Network Planning: Formalization, Analysis, and Implementation},\n  Author   = {Kutluhan Erol},\n  School   = {University of Maryland},\n  Year     = {1996},\n  Abstract = {Planning is a central activity in many areas including robotics, manufacturing, space mission sequencing, and logistics. as the size and complexity of planning problems grow, there is great economic pressure to automate this process in order to reduce the cost of planning effort, and to improve the quality of produced plans.<br/><br/>\n\n  AI planning research has focused on general-purpose planning systems which can process the specifications of an application domain and generate solutions to planning problems in that domain. Unfortunately, there is a big gap between theoretical and application oriented work in AI planning. The theoretical work has been mostly based on state-based planning, which has limited practical applications. The application- oriented work has been based on hierarchical task network (HTN) planning, which lacks a theoretical foundation. As a result, in spite of many years of research, building planning applications remains a formidable task.<br/><br/>\n\n  The goal of this dissertation is to facilitate building reliable and effective planning applications. The methodology includes design of a mathematical framework for HTN planning, analysis of this framework, development of provably correct algorithms based on this analysis, and the implementation of these algorithms for further evaluation and exploration. The representation, analyses, and algorithms described in this thesis will make it easier to apply HTN planning techniques effectively and correctly to planning applications. The precise and mathematical nature of the descriptions will also help teaching about HTN planning, will clarify misconceptions in the literature, and will stimulate further research.},\n  url_Dissertation = {https://drum.lib.umd.edu/bitstream/handle/1903/5810/PhD_96-4.pdf},\n  url_URI = {http://hdl.handle.net/1903/5810}\n}\n\n\n
\n
\n\n\n
\n Planning is a central activity in many areas including robotics, manufacturing, space mission sequencing, and logistics. as the size and complexity of planning problems grow, there is great economic pressure to automate this process in order to reduce the cost of planning effort, and to improve the quality of produced plans.

AI planning research has focused on general-purpose planning systems which can process the specifications of an application domain and generate solutions to planning problems in that domain. Unfortunately, there is a big gap between theoretical and application oriented work in AI planning. The theoretical work has been mostly based on state-based planning, which has limited practical applications. The application- oriented work has been based on hierarchical task network (HTN) planning, which lacks a theoretical foundation. As a result, in spite of many years of research, building planning applications remains a formidable task.

The goal of this dissertation is to facilitate building reliable and effective planning applications. The methodology includes design of a mathematical framework for HTN planning, analysis of this framework, development of provably correct algorithms based on this analysis, and the implementation of these algorithms for further evaluation and exploration. The representation, analyses, and algorithms described in this thesis will make it easier to apply HTN planning techniques effectively and correctly to planning applications. The precise and mathematical nature of the descriptions will also help teaching about HTN planning, will clarify misconceptions in the literature, and will stimulate further research.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 1989\n \n \n (3)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n Improving the Efficiency of Planning.\n \n \n \n \n\n\n \n Qiang Yang.\n\n\n \n\n\n\n Ph.D. Thesis, University of Maryland, 1989.\n \n\n\n\n
\n\n\n\n \n \n \"Improving dissertation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Yang1989PhDThesis,\n  author    = {Qiang Yang},\n  title     = {Improving the Efficiency of Planning},\n  school    = {University of Maryland},\n  year      = {1989},\n  abstract  = {Symbolic planning involves extensive computation for detecting and handling goal interactions. Past planning systems can be classified as either domain-dependent or domain-independent, depending on how they deal with the goal interactions. Domain-dependent systems rely on heuristics that are specific to their particular application domains, and are of limited generality. Domain-independent systems make use of general planning knowledge independent of any particular domains, but have been mainly inefficient.<br/><br/>\n\n  This thesis presents two approaches to improving the efficiency and broadening the applicability of planning systems. First, a set of conditions are set up upon the representation of planning knowledge. Whenever these conditions enable one to preprocess the planning knowledge of a system before problem solving starts, and offer guidelines for the design of knowledge representation. Second, a set of restrictions are imposed on the goal interactions so that, whenever they are satisfied, efficient planning methods can be developed. The restrictions do not depend on any specific domain knowledge. Therefore the approach is more general than domain-dependent planning. In addition, they offer more knowledge about goal interactions and thus enable more efficient methods to be developed than purely domain-independent approaches.},\n  url_Dissertation = {https://cs.uwaterloo.ca/research/tr/1989/CS-89-34.pdf}\n}\n\n\n
\n
\n\n\n
\n Symbolic planning involves extensive computation for detecting and handling goal interactions. Past planning systems can be classified as either domain-dependent or domain-independent, depending on how they deal with the goal interactions. Domain-dependent systems rely on heuristics that are specific to their particular application domains, and are of limited generality. Domain-independent systems make use of general planning knowledge independent of any particular domains, but have been mainly inefficient.

This thesis presents two approaches to improving the efficiency and broadening the applicability of planning systems. First, a set of conditions are set up upon the representation of planning knowledge. Whenever these conditions enable one to preprocess the planning knowledge of a system before problem solving starts, and offer guidelines for the design of knowledge representation. Second, a set of restrictions are imposed on the goal interactions so that, whenever they are satisfied, efficient planning methods can be developed. The restrictions do not depend on any specific domain knowledge. Therefore the approach is more general than domain-dependent planning. In addition, they offer more knowledge about goal interactions and thus enable more efficient methods to be developed than purely domain-independent approaches.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n Flexible reuse and modification in hierarchical planning: a validation structure-based approach.\n \n \n \n \n\n\n \n Rao Kambhampati.\n\n\n \n\n\n\n Ph.D. Thesis, University of Maryland, 1989.\n \n\n\n\n
\n\n\n\n \n \n \"Flexible dissertation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 3 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Kambhampati1989PhDThesis,\n  author    = {Rao Kambhampati},\n  title     = {Flexible reuse and modification in hierarchical planning: a validation structure-based approach},\n  school    = {University of Maryland},\n  year      = {1989},\n  abstract  = {The abstract, just as the dissertation itself, is not publicly available.},\n  url_Dissertation = {https://dl.acm.org/doi/10.5555/916781}\n}\n\n\n
\n
\n\n\n
\n The abstract, just as the dissertation itself, is not publicly available.\n
\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n \n A constructive paradigm of hierarchical planning.\n \n \n \n \n\n\n \n Maria Fox.\n\n\n \n\n\n\n Ph.D. Thesis, University of Hertfordshire, 1989.\n \n\n\n\n
\n\n\n\n \n \n \"A dissertation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Fox1998PhDThesis,\n  author    = {Maria Fox},\n  title     = {A constructive paradigm of hierarchical planning},\n  school    = {University of Hertfordshire},\n  year      = {1989},\n  abstract  = {The abstract, just as the dissertation itself, is not publicly available.},\n  url_Dissertation = {https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.254477}\n}\n\n\n
\n
\n\n\n
\n The abstract, just as the dissertation itself, is not publicly available.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n
\n
\n  \n 1975\n \n \n (1)\n \n \n
\n
\n \n \n
\n \n\n \n \n \n \n \n \n A Structure for Plans and Behavior.\n \n \n \n \n\n\n \n Earl D. Sacerdoti.\n\n\n \n\n\n\n Ph.D. Thesis, Stanford University, 1975.\n \n\n\n\n
\n\n\n\n \n \n \"A dissertation\n  \n \n\n \n\n \n link\n  \n \n\n bibtex\n \n\n \n  \n \n abstract \n \n\n \n  \n \n 2 downloads\n \n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n
@PhdThesis{Sacerdoti1975PhDThesis,\n  author    = {Earl D. Sacerdoti},\n  title     = {A Structure for Plans and Behavior},\n  school    = {Stanford University},\n  year      = {1975},\n  abstract  = {This report describes progress to date in the ability of a computer system to understand and reason about actions. A new method of representing actions within a computers memory has been developed, and this new representation, called the procedural net, has been employed in developing new strategies for solving problems and monitoring the execution of the resulting solutions.<br/><br/>\n\n  A set of running computer programs, called the NOAH Nets Of Action Hierarchies system, embodies this representation. Its major goal is to provide a framework for storing expertise about the actions of a particular task domain, and to impart that expertise to a human in the cooperative achievement of nontrivial tasks.<br/><br/>\n\n  A problem is presented to NOAH as a statement that is to be made true by applying a sequence of actions in an initial state of the world. The actions are drawn from a set of actions previously defined to the system. NOAH first creates a one-step solution to the problem, then it progressively expands the level of detail of the solution, filling in ever more detailed actions. All the individual actions, composed into plans at differing levels of detail, are stored in the procedural net. The system avoids imposing unnecessary constraints on the order of the actions in a plan. Thus, plans are represented as partial orderings of actions, rather than as linear sequences.<br/><br/>\n\n  The same data structure is used to guide the human user through a task. Since the system has planned the task at varying levels of detail, it can issue requests for action to the user at varying levels of detail, depending on hisher competence and understanding of the higher level actions. If more detail is needed than was originally planned for, or if an unexpected event causes the plan to go awry, the system can continue to plan from any point during execution.<br/><br/>\n\n  In essence, the structure of a plan of actions is as important for problem solving and execution monitoring as the nature of the actions themselves.},\n  url_Dissertation = {https://apps.dtic.mil/sti/pdfs/ADA458657.pdf}\n}\n
\n
\n\n\n
\n This report describes progress to date in the ability of a computer system to understand and reason about actions. A new method of representing actions within a computers memory has been developed, and this new representation, called the procedural net, has been employed in developing new strategies for solving problems and monitoring the execution of the resulting solutions.

A set of running computer programs, called the NOAH Nets Of Action Hierarchies system, embodies this representation. Its major goal is to provide a framework for storing expertise about the actions of a particular task domain, and to impart that expertise to a human in the cooperative achievement of nontrivial tasks.

A problem is presented to NOAH as a statement that is to be made true by applying a sequence of actions in an initial state of the world. The actions are drawn from a set of actions previously defined to the system. NOAH first creates a one-step solution to the problem, then it progressively expands the level of detail of the solution, filling in ever more detailed actions. All the individual actions, composed into plans at differing levels of detail, are stored in the procedural net. The system avoids imposing unnecessary constraints on the order of the actions in a plan. Thus, plans are represented as partial orderings of actions, rather than as linear sequences.

The same data structure is used to guide the human user through a task. Since the system has planned the task at varying levels of detail, it can issue requests for action to the user at varying levels of detail, depending on hisher competence and understanding of the higher level actions. If more detail is needed than was originally planned for, or if an unexpected event causes the plan to go awry, the system can continue to plan from any point during execution.

In essence, the structure of a plan of actions is as important for problem solving and execution monitoring as the nature of the actions themselves.\n
\n\n\n
\n\n\n\n\n\n
\n
\n\n\n\n\n
\n\n\n \n\n \n \n \n \n\n
\n"}; document.write(bibbase_data.data);