5,289 research outputs found
Pluralismus oder Assimilation? Zum Umgang mit Norm und arealer Sprachvariation in Deutschland und anderswo
No full textPluralismus oder Assimilation? : zum Umgang mit Norm und arealer Sprachvariation in Deutschland und anderswo / Péter Maitz ; Stephan Elspaß. - In: Kommunikation und Öffentlichkeit / Susanne Günthner ... (Hrsg.). - Berlin u.a. : De Gruyter, 2012. - S. 41-58. - (Reihe Germanistische Linguistik ; 296
Hierarchical planning through propositional logic : highly efficient, versatile, and flexible
No full textAI 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
Socially cooperative behavior for artificial companions for elderly and cognitively impaired people
No full textYaghoubzadeh R, Buschmeier H, Kopp S. Socially cooperative behavior for artificial companions for elderly and cognitively impaired people. In: Biundo-Stephan S, Wendemuth A, Rukzio E, eds. Proceedings of the 1st International Symposium on Companion-Technology. Ulm: Universiät Ulm; 2015: 15-19
Interpreting Observed Action (Dagstuhl Seminar 12491)
No full textThis report documents the program and the outcomes of Dagstuhl Seminar 12491 "Interpreting Observed Action". The aim of the seminar was to get a coherent picture, which transcends the borders of applications and disciplines, of existing approaches and problems in interpreting observed action in semantic terms -- primarily action by humans, but action by artificial agents may play some role, too. The seminar brought together, on the one hand, researchers from the different camps of AI, robotics, and knowledge-based systems who are working on the various aspects and purposes of interpreting observed action by humans, or occasionally, other agents; on the other hand, it added some researchers from cognitive science (psychology, neurosciences) working on human perception of behaviour and action. The main outcome of the seminar were a set of guidelines for setting up a workbench, which can be used to explore and test methods and techniques related to interpreting observed action
Rezension: Susanne Fengler/Stephan Ruß-Mohl: Der Journalist als "Homo oeconomicus"
No full textSattler S. Rezension: Susanne Fengler/Stephan Ruß-Mohl: Der Journalist als "Homo oeconomicus". Publizistik. 2005;50:269-270
Hybrid planning - from theory to practice
No full textThis 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
Hierarchical Planning : Expressivity Analysis, Solving Techniques, and Problem Compilations
No full textAutomated 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.In reference to IEEE copyrighted material which is used with permission in this thesis, the IEEE does not endorse any of Ulm University's products or services. Internal or personal use of this material is permitted. If interested in reprinting/republishing IEEE copyrighted material for advertising or promotional purposes or for creating new collective works for resale or redistribution, please go to http://www.ieee.org/publications_standards/publications/rights/rights_link.html to learn how to obtain a License from RightsLink
Exploring the hierarchy: extracting and exploiting state information of compound tasks in HTN planning
No full textAutomated Planning is a domain-independent paradigm that can be applied to solve various problems in many areas such as robotics, autonomous factories, or assistance systems by finding a sequence of actions that an agent needs to perform in order to achieve a desired goal. In planning, the application domain is typically described using states and actions. States are represented as sets of propositional state features, and actions are characterized by their respective preconditions and effects, which in turn represent state changes. Hierarchical Task Network (HTN) planning extends this basic framework by introducing compound actions (also called abstract or compound tasks), which need to be refined into less abstract and eventually primitive actions according to predefined refinement rules.
One limitation of the conventional HTN planning formalism is the lack of explicit state-change information for compound actions. These actions primarily serve as placeholders for potential sequences of primitive and compound actions, without clearly stating their implications on states. Such insights, however, can be valuable for both planning systems and domain modelers. This dissertation addresses this insufficiency by deriving state information of compound actions based on their refinements, focusing on three core contributions in total-order HTN planning:
Firstly, a theoretical foundation is provided by formally defining several types of inferred preconditions and effects for compound actions and analyzing their computational complexity. The latter revealed that while directly computing these inferences is computationally intractable, an approximation exists that can be computed in polynomial time.
Secondly, leveraging these inferred preconditions and effects, a look-ahead technique designed for search-based HTN planning systems has been developed. This novel technique can reduce the search space by identifying dead-ends and inevitable decomposition choices.
Empirical evaluations show that incorporating this approach considerably improves the performance of state-of-the-art HTN planning systems, leading to several wins at the latest International Planning Competition. Thus, it pushes the boundaries of how quickly practical problems can be solved.
Lastly, motivated by considerations for the look-ahead technique, the concept of conjunctive possible effects is introduced, which goes beyond the before-mentioned types of inferred preconditions and effects. These offer a more nuanced representation of state changes and are found to be computationally challenging even under several relaxations but fixed-parameter tractable for a fixed number of facts, making them practically useful for smaller problem instances. As a byproduct, this investigation also revealed new complexity results for the plan existence problem under precondition-relaxation
Mixed-initiative intent recognition using cloud-based cognitive services
No full textIn spoken dialogue systems, understanding the intention of a user is essential for a succesful and natural perceived human-machine interaction. Therefore, in the scope of this thesis, the creation and evaluation of a dialogue system is presented, which relies on the cloud-based Language Understanding Intelligent Service (LUIS) from Microsoft in order to recognize automatically the intention of a user from an utterance. For the evaluation of the cloud-based approach, the LUIS-based system is tested against a conservative hand-crafted grammar-based system by conducting an online study, with regard to the degree of the complexity of the user input. The main focus of the evaluation is put on system performance and user experience. For comparison of the different approaches, a mixed-initiative dialogue is designed for each system.
Fassung June 8, 201
- …
