@PhdThesis{Schattenberg09PhDThesis,
  author   = {Bernd Schattenberg},
  title    = {Hybrid Planning \& Scheduling},
  school   = {Ulm University, Germany},
  year     = {2009},
  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/>

  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/>

  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/>

  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/>

  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/>

  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.},
 doi = {10.18725/OPARU-1045},
 url_Dissertation = {https://oparu.uni-ulm.de/xmlui/bitstream/handle/123456789/1072/vts_6895_9580.pdf},
 url_Dissertation-abstract = {https://link.springer.com/article/10.1007/s13218-015-0390-z}
}

{"_id":"pw59hqPKMxwxjNi9x","bibbaseid":"schattenberg-hybridplanningscheduling-2009","authorIDs":[],"author_short":["Schattenberg, B."],"bibdata":{"bibtype":"phdthesis","type":"phdthesis","author":[{"firstnames":["Bernd"],"propositions":[],"lastnames":["Schattenberg"],"suffixes":[]}],"title":"Hybrid Planning & Scheduling","school":"Ulm University, Germany","year":"2009","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/> 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/> 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/> 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/> 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/> 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.","doi":"10.18725/OPARU-1045","url_dissertation":"https://oparu.uni-ulm.de/xmlui/bitstream/handle/123456789/1072/vts_6895_9580.pdf","url_dissertation-abstract":"https://link.springer.com/article/10.1007/s13218-015-0390-z","bibtex":"@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","author_short":["Schattenberg, B."],"key":"Schattenberg09PhDThesis","id":"Schattenberg09PhDThesis","bibbaseid":"schattenberg-hybridplanningscheduling-2009","role":"author","urls":{" dissertation":"https://oparu.uni-ulm.de/xmlui/bitstream/handle/123456789/1072/vts_6895_9580.pdf"," dissertation-abstract":"https://link.springer.com/article/10.1007/s13218-015-0390-z"},"metadata":{"authorlinks":{}}},"bibtype":"phdthesis","biburl":"hierarchical-task.net/bibtex/theses-in-hierarchical-planning.bib","creationDate":"2020-04-25T03:46:49.069Z","downloads":1,"keywords":[],"search_terms":["hybrid","planning","scheduling","schattenberg"],"title":"Hybrid Planning & Scheduling","year":2009,"dataSources":["YjidmhgCHYRtoZTo6","vY5emPje84NjvCwk9"]}