Dissertations / Theses on the topic 'Reasoning about actions and change'

The capability of changing beliefs upon new information in a rational and efficient way is crucial for an intelligent agent. Belief change therefore is one of the central research fields in Artificial Intelligence (AI) for over two decades. In the AI literature, two different kinds of belief change operations have been intensively investigated: belief update, which deal with situations where the new information describes changes of the world; and belief revision, which assumes the world is static. As another important research area in AI, reasoning about actions mainly studies the problem of representing and reasoning about effects of actions. These two research fields are closely related and apply a common underlying principle, that is, an agent should change its beliefs (knowledge) as little as possible whenever an adjustment is necessary. This lays down the possibility of reusing the ideas and results of one field in the other, and vice verse. This thesis aims to develop a general framework and devise computational models that are applicable in reasoning about actions. Firstly, I shall propose a new framework for iterated belief revision by introducing a new postulate to the existing AGM/DP postulates, which provides general criteria for the design of iterated revision operators. Secondly, based on the new framework, a concrete iterated revision operator is devised. The semantic model of the operator gives nice intuitions and helps to show its satisfiability of desirable postulates. I also show that the computational model of the operator is almost optimal in time and space-complexity. In order to deal with the belief change problem in multi-agent systems, I introduce a concept of mutual belief revision which is concerned with information exchange among agents. A concrete mutual revision operator is devised by generalizing the iterated revision operator. Likewise, a semantic model is used to show the intuition and many nice properties of the mutual revision operator, and the complexity of its computational model is formally analyzed. Finally, I present a belief update operator, which takes into account two important problems of reasoning about action, i.e., disjunctive updates and domain constraints. Again, the updated operator is presented with both a semantic model and a computational model.

The capability of changing beliefs upon new information in a rational and efficient way is crucial for an intelligent agent. Belief change therefore is one of the central research fields in Artificial Intelligence (AI) for over two decades. In the AI literature, two different kinds of belief change operations have been intensively investigated: belief update, which deal with situations where the new information describes changes of the world; and belief revision, which assumes the world is static. As another important research area in AI, reasoning about actions mainly studies the problem of representing and reasoning about effects of actions. These two research fields are closely related and apply a common underlying principle, that is, an agent should change its beliefs (knowledge) as little as possible whenever an adjustment is necessary. This lays down the possibility of reusing the ideas and results of one field in the other, and vice verse. This thesis aims to develop a general framework and devise computational models that are applicable in reasoning about actions. Firstly, I shall propose a new framework for iterated belief revision by introducing a new postulate to the existing AGM/DP postulates, which provides general criteria for the design of iterated revision operators. Secondly, based on the new framework, a concrete iterated revision operator is devised. The semantic model of the operator gives nice intuitions and helps to show its satisfiability of desirable postulates. I also show that the computational model of the operator is almost optimal in time and space-complexity. In order to deal with the belief change problem in multi-agent systems, I introduce a concept of mutual belief revision which is concerned with information exchange among agents. A concrete mutual revision operator is devised by generalizing the iterated revision operator. Likewise, a semantic model is used to show the intuition and many nice properties of the mutual revision operator, and the complexity of its computational model is formally analyzed. Finally, I present a belief update operator, which takes into account two important problems of reasoning about action, i.e., disjunctive updates and domain constraints. Again, the updated operator is presented with both a semantic model and a computational model.

Reasoning about actions and change based on common sense knowledge is one of the most important and difficult tasks in the artificial intelligence research area. A series of such tasks are identified which motivate the consideration and application of reasoning formalisms. There follows a discussion of the broad issues involved in modelling time and constructing a logical language. In general, worlds change over time. To model the dynamic world, the ability to predict what the state of the world will be after the execution of a particular sequence of actions, which take time and to explain how some given state change came about, i.e. the causality are basic requirements of any autonomous rational agent. The research work presented herein addresses some of the fundamental concepts and the relative issues in formal reasoning about actions and change. In this thesis, we employ a new time structure, which helps to deal with the so-called intermingling problem and the dividing instant problem. Also, the issue of how to treat the relationship between a time duration and its relative time entity is examined. In addition, some key terms for representing and reasoning about actions and change, such as states, situations, actions and events are formulated. Furthermore, a new formalism for reasoning about change over time is presented. It allows more flexible temporal causal relationships than do other formalisms for reasoning about causal change, such as the situation calculus and the event calculus. It includes effects that start during, immediately after, or some time after their causes, and which end before, simultaneously with, or after their causes. The presented formalism allows the expression of common-sense causal laws at high level. Also, it is shown how these laws can be used to deduce state change over time at low level. Finally, we show that the approach provided here is expressive.

Traditionally, consistency is the only criterion for the quality of a theory in logic-based approaches to reasoning about actions. This work goes beyond that and contributes to the meta-theory of actions by investigating what other properties a good domain description should satisfy. Having Propositional Dynamic Logic (PDL) as background, we state some meta-theoretical postulates
concerning this sore spot. When all postulates are satisfied, we call the action theory modular. We point out the problems that arise when the postulates about modularity are violated, and propose algorithmic checks that can help the designer of an action theory to overcome them. Besides being easier to understand and more elaboration tolerant in McCarthy's sense, modular theories
have interesting computational properties. Moreover, we also propose a framework for updating domain descriptions and show the importance modularity has in action theory change.

This master's thesis deals with a frame-based knowledge representa- tion language and system called The Knowledge Machine (KM), de- veloped by Peter Clark and Bruce Porter at the University of Texas at Austin. The purpose of the thesis is to show a number of ways of changing and extending KM to handle larger classes of reasoning tasks associated with reasoning about actions and change.

Cette thèse s’inscrit dans le cadre du projet ANR eThicAa, dont les ambitions ont été : de définir ce que sont des agents autonomes éthiques, de produire des représentations formelles des conflits éthiques et de leurs objets (au sein d’un seul agent autonome, entre un agent autonome et le système auquel il appartient, entre un agent autonome et un humain, entre plusieurs agents autonomes) et d’élaborer des algorithmes d’explication pour les utilisateurs humains. L’objet de la thèse plus particulièrement a été d’étudier la modélisation de conflits éthiques au sein d’un seul agent, ainsi que la production d’algorithmes explicatifs. Ainsi, le travail présenté ici décrit l’utilisation de langages de haut niveau dans la conception d’agents autonomes éthiques. Il propose un cadre logique nouveau et modulaire pour représenter et raisonner sur une variété de théories éthiques, sur la base d’une version modifiée du calcul des événements, implémentée en Answer Set Programming. Le processus de prise de décision éthique est conçu comme une procédure en plusieurs étapes, capturée par quatre types de modèles interdépendants qui permettent à l’agent d’évaluer son environnement, de raisonner sur sa responsabilité et de faire des choix éthiquement informés. En particulier, un modèle d’action permet à l’agent de représenter des scénarios et les changements qui s’y déroulent, un modèle causal piste les conséquences des décisions prises dans les scénarios, rendant possible un raisonnement sur la responsabilité et l’imputabilité des agents, un modèle du Bien donne une appréciation de la valeur éthique intrinsèque de finalités ou d’évènements, un modèle du Juste détermine les décisions acceptables selon des circonstances données. Le modèle causal joue ici un rôle central, car il permet d’identifier des propriétés que supposent les relations causales et qui déterminent comment et dans quelle mesure il est possible d’en inférer des attributions de responsabilité. Notre ambition est double. Tout d’abord, elle est de permettre la représentation systématique d’un nombre illimité de processus de raisonnements éthiques, à travers un cadre adaptable et extensible en vertu de sa hiérarchisation et de sa syntaxe standardisée. Deuxièmement, elle est d’éviter l’écueil de certains travaux d’éthique computationnelle qui directement intègrent l’information morale dans l’engin de raisonnement général sans l’expliciter – alimentant ainsi les agents avec des réponses atomiques qui ne représentent pas la dynamique sous-jacente. Nous visons à déplacer de manière globale le fardeau du raisonnement moral du programmeur vers le programme lui-même
This thesis is part of the ANR eThicAa project, which has aimed to define moral autonomous agents, provide a formal representation of ethical conflicts and of their objects (within one artificial moral agent, between an artificial moral agent and the rules of the system it belongs to, between an artificial moral agent and a human operator, between several artificial moral agents), and design explanation algorithms for the human user. The particular focus of the thesis pertains to exploring ethical conflicts within a single agent, as well as designing explanation algorithms. The work presented here investigates the use of high-level action languages for designing such ethically constrained autonomous agents. It proposes a novel and modular logic-based framework for representing and reasoning over a variety of ethical theories, based on a modified version of the event calculus and implemented in Answer Set Programming. The ethical decision-making process is conceived of as a multi-step procedure captured by four types of interdependent models which allow the agent to represent situations, reason over accountability and make ethically informed choices. More precisely, an action model enables the agent to appraise its environment and the changes that take place in it, a causal model tracks agent responsibility, a model of the Good makes a claim about the intrinsic value of goals or events, and a model of the Right considers what an agent should do, or is most justified in doing, given the circumstances of its actions. The causalmodel plays a central role here, because it permits identifying some properties that causal relations assume and that determine how, as well as to what extent, we may ascribe ethical responsibility on their basis. The overarching ambition of the presented research is twofold. First, to allow the systematic representation of an unbounded number of ethical reasoning processes, through a framework that is adaptable and extensible by virtue of its designed hierarchisation and standard syntax. Second, to avoid the pitfall of some works in current computational ethics that too readily embed moralinformation within computational engines, thereby feeding agents with atomic answers that fail to truly represent underlying dynamics. We aim instead to comprehensively displace the burden of moral reasoning from the programmer to the program itself

Action Theories are versatile and well-studied knowledge representation formalisms for modelling dynamic domains. However, traditional action theories allow only the specification of definite world knowledge, that is, universal rules for which there are no exceptions. When modelling a complex domain for which no complete knowledge can be obtained, axiomatisers face an unpleasant choice: either they cautiously restrict themselves to the available definite knowledge and live with a limited usefulness of the axiomatisation, or they bravely model some general, defeasible rules as definite knowledge and risk inconsistency in the case of an exception for such a rule. This thesis presents a framework for default reasoning in action theories that overcomes these problems and offers useful default assumptions while retaining a correct treatment of default violations. The framework allows to extend action theories with defeasible statements that express how the domain usually behaves. Normality of the world is then assumed by default and can be used to conclude what holds in the domain under normal circumstances. In the case of an exception, the default assumption is retracted, whereby consistency of the domain axiomatisation is preserved.

Cet travail présente une solution au problème du décor inférenciel. Nous réalisons cela en donnant une éducation polynomiale d'un fragment du calcul des situations vers la logique épistémique dynamique (DEL). En suite, une nouvelle méthode de preuve pour DEL, dont la complexité algorithmique est inférieure à celle de la méthode de Reiter pour le calcul de situations, est proposée. Ce travail présente aussi une nouvelle logique pour raisonner sur les actions. Cette logique permet d'exprimer formellement "qu'il existe une suite d'action conduisant au but". L'idée étant que, avec la quantification sur les actions, la planification devient un problème de validité. Une axiomatisation et quelques résultats d'expressivité sont donnés, ainsi qu'une méthode de preuve basée sur les tableaux sémantiques
This work presents a solution to the inferential frame problem. We do so by providing a polynomial reduction from a fragment of situation calculus to espistemic dynamic logic (DEL). Then, a novel proof method for DEL, such that the computational complexity is much lower than that of Retier's proof method for situation caluculs, is proposed. This work also presents a new logic for reasoning about actions. This logic allows to formally express that "there exists a sequence of actions that leads to the goal". The idea is that, with quantification over actions, planning can become a validity problem. An axiomatisation and some expressivity results are provided, as well as a proof method based on sematic tableaux

With the global population growth, the food production will need to rise, potentially causing extensive environmental damage. In Brazil, the demand for farmland is the key immediate driver of land use change, which has influence in public policies. For example, the soy and beef moratorium, that aim at reducing the advance of soybean cropping and pasture areas expansion over the Amazon biome. Currently, Earth observation satellites form part of a comprehensive Earth observation system due to their higher spatial, temporal and spectral resolutions, providing continuous and consistent information about Earths surface. It is the era of big Earth observation data. It has been creating new perspectives in remote sensing data analysis that enable the development of land use and land cover maps at higher spatial resolution and with high temporal frequency. Given this scenery, this thesis introduces a spatiotemporal interval logic mechanism that can be used for reasoning about land use change dynamics, from big Earth observation data systems. The main contribution of this mechanism is to use the concept of events to reason about land use change. Building on this view this thesis extends Allens interval temporal logic to the spatial context, resulting in a formal calculus that allows users to express queries about the land use dynamics. The calculus allows scientists to manipulate large sets of land use data in a flexible way, to understand the environmental and economic effects of land use change. The formalism was applied in three cases studies to identify and quantifying land use transitions in Mato Grosso state in Brazil.
Com o crescimento da população mundial, a produção de alimentos precisará aumentar potencialmente causando grandes danos ambientais. No Brasil, a demanda por terras agrícolas é o principal condutor imediato da mudança de uso da terra, que influência políticas públicas. Por exemplo, a moratória da soja e da carne que visam reduzir o avanço da expansão de áreas de cultivo de soja e pastagem sobre o bioma Amazônia. Atualmente, satélites de observação da Terra fazem parte de um sistema abrangente de observação da Terra devido às suas maiores resoluções espaciais, temporais e espectrais, fornecendo informações contínuas e consistentes sobre a superfície terrestre. É a era dos grandes conjuntos de dados de observação da Terra. Isso tem criado novas perspectivas na análise de dados de sensoriamento remoto que permitem o desenvolvimento de mapas de uso e cobertura da terra com maior resolução espacial e com alta frequência temporal. Dado este cenário, esta tese introduz um mecanismo de lógica de intervalo espaço-temporal que pode ser usado para raciocinar sobre as dinâmicas de mudança de uso da terra, a partir de sistemas de grandes conjuntos de dados de observação da Terra. A principal contribuição deste mecanismo é usar o conceito de eventos para raciocinar sobre mudança de uso da terra. Com base nesta perspectiva, essa tese estende a lógica temporal de intervalos de Allen para o contexto espacial, resultando em um cálculo formal que permite usuários expressar consultas sobre a dinâmica de uso da terra. O cálculo permite aos cientistas manipular grandes conjuntos de dados de uso da terra de uma maneira flexível para entender os efeitos ambientais e econômicos da mudança de uso da terra. O formalismo foi aplicado em três estudos de casos para identificar e quantificar transições de uso da terra no estado de Mato Grosso, Brasil.

In this thesis, we study advanced reasoning about dynamical systems in a logical framework -- the situation calculus. In particular, we consider promoting the efficiency of reasoning about action in the situation calculus from three different aspects. First, we propose a modified situation calculus based on the two-variable predicate logic with counting quantifiers. We show that solving the projection and executability problems via regression in such language are decidable. We prove that generally these two problems are co-NExpTime-complete in the modified language. We also consider restricting the format of regressable formulas and basic action theories (BATs) further to gain better computational complexity for reasoning about action via regression. We mention possible applications to formalization of Semantic Web services. Then, we propose a hierarchical representation of actions based on the situation calculus to facilitate development, maintenance and elaboration of very large taxonomies of actions. We show that our axioms can be more succinct, while still using an extended regression operator to solve the projection problem. Moreover, such representation has significant computational advantages. For taxonomies of actions that can be represented as finitely branching trees, the regression operator can sometimes work exponentially faster with our theories than it works with the BATs current situation calculus. We also propose a general guideline on how a taxonomy of actions can be constructed from the given set of effect axioms. Finally, we extend the current situation calculus with the order-sorted logic. In the new formalism, we add sort theories to the usual initial theories to describe taxonomies of objects. We then investigate what is the well-sortness for BATs under such framework. We consider extending the current regression operator with well-sortness checking and unification techniques. With the modified regression, we gain computational efficiency by terminating the regression earlier when reasoning tasks are ill-sorted and by reducing the search spaces for well-sorted objects. We also study that the connection between the order-sorted situation calculus and the current situation calculus.

abstract: Modeling dynamic systems is an interesting problem in Knowledge Representation (KR) due to their usefulness in reasoning about real-world environments. In order to effectively do this, a number of different formalisms have been considered ranging from low-level languages, such as Answer Set Programming (ASP), to high-level action languages, such as C+ and BC. These languages show a lot of promise over many traditional approaches as they allow a developer to automate many tasks which require reasoning within dynamic environments in a succinct and elaboration tolerant manner. However, despite their strengths, they are still insufficient for modeling many systems, especially those of non-trivial scale or that require the ability to cope with exceptions which occur during execution, such as unexpected events or unintended consequences to actions which have been performed. In order to address these challenges, a theoretical framework is created which focuses on improving the feasibility of applying KR techniques to such problems. The framework is centered on the action language BC+, which integrates many of the strengths of existing KR formalisms, and provides the ability to perform efficient reasoning in an incremental fashion while handling exceptions which occur during execution. The result is a developer friendly formalism suitable for performing reasoning in an online environment. Finally, the newly enhanced Cplus2ASP 2 is introduced, which provides a number of improvements over the original version. These improvements include implementing BC+ among several additional languages, providing enhanced developer support, and exhibiting a significant performance increase over its predecessors and similar systems.
Dissertation/Thesis
M.S. Computer Science 2014

The appearance-reality distinction refers to the understanding that objects can have misleading appearances that contradict reality. Traditionally, studies investigating children's ability to make this distinction have used a verbal-based task that requires children to answer two questions regarding the appearance and reality of a target object whose appearance has been altered. In general, these studies have found that children are not successful in this task until 4–5 years of age. The purpose of the current study was to investigate three different hypotheses regarding why 3-year-olds fail the traditional verbal-based task in order to determine whether their poor performance truly represents an inability to distinguish appearance from reality. In Experiment 1, the hypothesis that 3-year-olds fail the traditional task simply because they are unfamiliar with the property-distorting devices typically used to alter the appearances of target objects, rather than an inability to distinguish appearance from reality, was examined. Experiments 1 and 2 also examined the hypothesis that 3-year-olds' failure in this task may be due to an inability to assign conflicting, dual representations to a single object. Finally, the role of the language used in making the appearance-reality distinction also was examined in both experiments. In this case, the hypothesis that 3-year-olds may be able to distinguish appearances from reality in an action-based, but not verbal-based task, was evaluated. In Experiment 1, all of this was done using a property-distorting device typically used in traditional appearance-reality studies, whereas a completely new method for altering the appearances of objects was used in Experiment 2. No supporting evidence for the familiarity or dual representation hypotheses was found in either experiment, however, children in both experiments performed better on an action-based task than on two verbal-based tasks. Children went from answering the traditional appearance-reality questions on the basis of misleading perceptual information to overriding this misleading information in an action-based task. Together, these results provide evidence that 3-year-olds have some competence in distinguishing appearances from reality that is masked by the language demands of the traditional verbal-based task.

This dissertation is about the design of a modular language for describing actions. The modular action description language, MAD, is based on the action language C+. In this new language, the possibility of "importing" a module allows us to describe actions by referring to descriptions of related actions introduced earlier, rather than by listing all effects and preconditions of every action explicitly. The use of modular action descriptions eliminates the need to reinvent theories of similar domains over and over again. Another advantage of this representation style is that it is similar to the way humans describe actions in terms of other actions. We first define the syntax of a fragment of MAD, called mini-MAD, and then extend it to the full version of MAD. The semantics of mini-MAD is defined by grounding action descriptions and translating them into C+. However, for the full version of MAD, it would be difficult to define grounding. Instead, we use a new approach to the semantics of variables in action descriptions, which is based on more complex logical machinery---first-order causal logic. Grounding is important as an implementation method, but we argue that it should be best avoided in the definition of the semantics of expressive action languages. We show that, in application to mini-MAD, the two semantics are equivalent. Furthermore, we prove that MAD action descriptions have some desirable, intuitively expected mathematical properties. We hope that MAD will make it possible to create a useful general-purpose library of standard action descriptions and will contribute in this way to solving the problem of generality in Artificial Intelligence.
text

abstract: This dissertation describes an investigation of four students' ways of thinking about functions of two variables and rate of change of those two-variable functions. Most secondary, introductory algebra, pre-calculus, and first and second semester calculus courses do not require students to think about functions of more than one variable. Yet vector calculus, calculus on manifolds, linear algebra, and differential equations all rest upon the idea of functions of two (or more) variables. This dissertation contributes to understanding productive ways of thinking that can support students in thinking about functions of two or more variables as they describe complex systems with multiple variables interacting. This dissertation focuses on modeling the way of thinking of four students who participated in a specific instructional sequence designed to explore the limits of their ways of thinking and in turn, develop a robust model that could explain, describe, and predict students' actions relative to specific tasks. The data was collected using a teaching experiment methodology, and the tasks within the teaching experiment leveraged quantitative reasoning and covariation as foundations of students developing a coherent understanding of two-variable functions and their rates of change. The findings of this study indicated that I could characterize students' ways of thinking about two-variable functions by focusing on their use of novice and/or expert shape thinking, and the students' ways of thinking about rate of change by focusing on their quantitative reasoning. The findings suggested that quantitative and covariational reasoning were foundational to a student's ability to generalize their understanding of a single-variable function to two or more variables, and their conception of rate of change to rate of change at a point in space. These results created a need to better understand how experts in the field, such as mathematicians and mathematics educators, thinking about multivariable functions and their rates of change.
Dissertation/Thesis
Ph.D. Mathematics 2012

abstract: Different logic-based knowledge representation formalisms have different limitations either with respect to expressivity or with respect to computational efficiency. First-order logic, which is the basis of Description Logics (DLs), is not suitable for defeasible reasoning due to its monotonic nature. The nonmonotonic formalisms that extend first-order logic, such as circumscription and default logic, are expressive but lack efficient implementations. The nonmonotonic formalisms that are based on the declarative logic programming approach, such as Answer Set Programming (ASP), have efficient implementations but are not expressive enough for representing and reasoning with open domains. This dissertation uses the first-order stable model semantics, which extends both first-order logic and ASP, to relate circumscription to ASP, and to integrate DLs and ASP, thereby partially overcoming the limitations of the formalisms. By exploiting the relationship between circumscription and ASP, well-known action formalisms, such as the situation calculus, the event calculus, and Temporal Action Logics, are reformulated in ASP. The advantages of these reformulations are shown with respect to the generality of the reasoning tasks that can be handled and with respect to the computational efficiency. The integration of DLs and ASP presented in this dissertation provides a framework for integrating rules and ontologies for the semantic web. This framework enables us to perform nonmonotonic reasoning with DL knowledge bases. Observing the need to integrate action theories and ontologies, the above results are used to reformulate the problem of integrating action theories and ontologies as a problem of integrating rules and ontologies, thus enabling us to use the computational tools developed in the context of the latter for the former.
Dissertation/Thesis
Ph.D. Computer Science 2012

An important component of a developing identity is an understanding of personal persistence or self-continuity—how one remains the same person throughout the various changes in their life (Chandler, Lalonde, Sokol & Hallet, 2003). Chandler et al., (2003) have suggested that individuals vary in terms of both the style (essentialist or narrativist) and the level of complexity of their reasoning regarding self-continuity. In previous research this variability has been measured using a lengthy interview process. The present study explored the feasibility of more efficiently measuring variability in selfcontinuity understanding with the creation of a new Likert scaled questionnaire. Factor analysis suggested that 20 of the newly created questionnaire items clearly displayed a 2- factor structure mirroring the “essentialist” and “narrativist” styles reported by Chandler et al. (2003). Initial evidence of convergence between the interview and questionnaire methods is also apparent in that those rated as essentialists in the interview scored higher on the first essentialist factor than narrativists and narrativists by the interview scored higher on the second narrativist factor than essentialists.