1,424 research outputs found
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
Continuous and Step-level Pay-off Functions in Public Good Games: A Conceptual Analysis
No full textConflicts between individuals’ and collective interests are ubiquitous in social life. Numerous experimental studies have investigated the resolution of such conflicts using public good games with either continuous or step-level payoff functions. A conceptual analysis using both classic game theory and social exchange theory shows that these two types of games are fundamentally different. A continuous function game is a social dilemma in that it contains a conflict between individual and collective interests whereas a step-level game is primarily a social coordination game. Thus, we conclude that one can not safely generalize results from step-level to continuous form games. Additionally, our analysis shows that the distinction between continuous and single-step games can be blurred by segmenting a continuous function into steps or adding steps to a single-step game. We identify characteristics of the payoff function that conceptually mark the transition from a dilemma to a coordination problem.
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
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
Letter from Susanne [Freitas] to the Okine Family, October 29, 1947
No full textThank you note from Susanne Freitas in San Juan Bautista, California, for the chrysanthemum flowers that the Okine's sent to her. She also mentions that she put the flowers on Mrs. Freitas' grave.The Okine Collection contains materials collected by Seiichi and Tomeyo Okine who were Issei flower growers in Whittier, California. It includes correspondence, photographs, financial documents, and a photo album. A large portion of the collection consists of family correspondence with Seiichi and Tomeyo Okine, including letters from their Nisei children, Masao and Makoto Okine, both soldiers overseas during World War II, to their Issei parents incarcerated in the Rohwer incarceration camp in McGehee, Arkansas. The correspondence also includes letters from their relatives and friends who are former incarcerees in the camps during the war and have “resettled” in Chicago, Illinois as well as letters from the Okines’ family members in Hiroshima, Japan during the Allied occupation of Japan. In addition, the collection includes a family photo album compiled by Dorothy Ai Aoki, a Nisei daughter to the Okines
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
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
Susanne M. Hoffmann discourse on observing the moon
No full textThe process of observing the moon becomes one of the important things to do. Especially in the process determining from the beginning of month kamariyah or often referred as rukyatul hilal. Where is a challenge for the observers to see a very thin moon, moreover with weather conditions that are not always bright? In addition, observing the moon at the time of eclipse can increase the faith in understanding the signs and power of Allah SWT. With regard to the presence of Susanne M. Hoffmann at Islamic Astronomy Master Program Walisongo State Islamic University, the author is very interested in examining her thoughts about observing the moon. Susanne M. Hoffmann is an expert astronomist in the history of science, physics, and didactics. She expressed the bad condition of the sky and the air in Semarang. In addition, Susanne M. Hoffmann also suggested repeating Al-Biruni observation.
This study aims to find out Susanne M. Hoffmann discourse related observing the moon and to know her suggestion to repeat Al-Biruni observation on measuring the distance between two cities. This research includes for qualitative research and includes the type of library research. Primary data is taken from in-depth interviews and documentation of Susanne M. Hoffmann’s writings, works, and photographs. While the secondary data obtained from the documentation of books, journals, and articles of others work related to research. Meanwhile, to study of Susanne M. Hoffmann discourse author uses descriptive analysis method.
The results show, that Susanne M. Hofmann discourse in observing the moon is divided into two lines. First, in response to the poor condition of the sky and air in Indonesia, or Semarang in particular, Susanne M. Hoffmann still recommends doing rukyatul hilal. Furthermore, rukyatul hilal is best to do with the naked eye than using a telescope or optical instrument. Second, about the lunar eclipse, in accordance with the field, she mastered the history of Science. Susanne M. Hoffmann was succeeding to repeat the Al-Biruni observation in measuring the distance of two cities by the lunar eclipse
- …
