Inductive functional programming systems can be characterised by two diametric approaches: Either they apply exhaustive program enumeration which uses input/output examples (IO) as test cases, or they perform an analytical, data-driven structural generalisation of the IO examples. Enumerative approaches ignore the structural information provided with the IO examples, but use type information to guide and restrict the search. They use higher-order functions which capture recursion schemes during their enumeration, but apply them randomly in a uninformed manner. Analytical approaches on the other side heavily exploit this structural information, but have ignored the benefits of a strong type system so far and use only recursion schemes either fixed and built in, or selected by an expert user. In category theory universal constructs, such as natural transformations or type morphisms, describe recursion schemes which can be defined on any inductively defined data type. They can be characterised by specific universal properties. Those type morphisms and related concepts provide a categorical approach to functional programming, which is often called categorical programming. This work shows how categorical programming can be applied to Inductive Programming and how universal constructs, such as catamorphisms, paramorphisms, and type functors, can be used as recursive program schemes for inductive functional programming. The use of program schemes for Inductive Programming is not new. The special appeal and novelty of this work is that, contrary to previous approaches, the program schemes are neither fixed, nor selected by an expert user: The applicability of those recursion schemes can be automatically detected in the given IO examples of a target function by checking the universal properties of the corresponding type morphisms. Applying this to the analytical system Igor2, both the capabilities and the expressiveness can be extended without a decrease in efficiency. An extension of the analytical functional inductive programming system Igor2 is proposed and its algorithms described. An empirical evaluation demonstrates the improvements with respect to efficiency and effectiveness that can be achieved by the use of type morphisms for Igor2 due to a reduction in search space complexity.
This thesis is concerned with the inductive synthesis of recursive declarative programs and in particular with the analytical inductive synthesis of functional programs. Program synthesis addresses the problem of (semi-)automatically generating computer programs from specifications. In inductive program synthesis, recursive programs are constructed by generalizing over incomplete specifications such as finite sets of input/output examples (I/O examples). Classical methods for induction of functional programs are analytical, that is, a recursive function definition is derived by detecting and generalizing recurrent patterns between the given I/O examples. Most recent methods, on the other side, are generate-and-test based, that is, they repeatedly generate programs independently from the provided I/O examples until a program is found that correctly computes the examples. Analytical methods are much faster than generate-and-test methods, because they do not rely on search in a program space. Therefore, however, the schemas that generatable programs conform to, must be much more restricted. This thesis at first provides a comprehensive overview of current approaches and methods to inductive program synthesis. Then we present a new algorithm to the inductive synthesis of functional programs that generalizes the analytical approach and combines it with search in a program space. Thereby, the strong restrictions of analytical methods can be resolved for the most part. At the same time, applying analytical techniques allows for pruning large parts of the problem space so that solutions can often be found faster than with generate-and-test methods. By means of several experiments with an implementation of the described algorithm, we demonstrate its capabilities.
The KI ´09 workshop on Complex Cognition was a joint venture of the Cognition group of the Special Interest Group Artificial Intelligence of the German Computer Science Society (Gesellschaft für Informatik) and the German Cognitive Science Association. Dealing with complexity has become one of the great challenges for modern information societies. To reason and decide, plan and act in complex domains is no longer limited to highly specialized professionals in restricted areas such as medical diagnosis, controlling technical processes, or serious game playing. Complexity has reached everyday life and affects people in such mundane activities as buying a train ticket, investing money, or connecting a home desktop to the internet. Research in cognitive AI can contribute to supporting people navigating through the jungle of everyday reasoning, decision making, planning and acting by providing intelligent support technology. Lessons learned from expert systems research of the nineteen-eighties show that the aim should not be to provide for fully automated systems which can solve specialized tasks autonomously but instead to develop interactive assistant systems where user and system work together by taking advantage of the respective strengths of human and machine. To accomplish a smooth collaboration between humans and intelligent systems, basic research in cognition is a necessary precondition. Insights into cognitive structures and processes underlying successful human reasoning and planning can provide suggestions for algorithm design. Even more important, insights into restrictions and typical errors and misconceptions of the cognitive systems provide information about those parts of a complex task from which the human should be relieved. For successful human-computer interaction in complex domains it has, furthermore, to be decided which information should be presented when, in what way, to the user. We strongly believe that symbolic approaches of AI and psychological research of higher cognition are at the core of success for the endeavor to create intelligent assistant system for complex domains. While insight into the neurological processes of the brain and into the realization of basic processes of perception, attention and senso-motoric coordination are important for the basic understanding of the principles of human intelligence, these processes have a much too fine granularity for the design and realization of interactive systems which must communicate with the user on knowledge level. If human system users are not to be incapacitated by a system, system decisions must be transparent for the user and the system must be able to provide explanations for the reasons of its proposals and recommendations. Therefore, even when some of the underlying algorithms are based on statistical or neuronal approaches, the top-level of such systems must be symbolical and rule-based. The papers presented at this workshop on complex cognition give an inspiring and promising overview of current work in the field which can provide first building stones for our endeavor to create knowledge level intelligent assistant systems for complex domains. The topics cover modelling basic cognitive processes, interfacing subsymbolic and symbolic representations, dealing with continuous time, Bayesian identification of problem solving strategies, linguistically inspired methods for assessing complex cognitive processes and complex domains such as recognition of sketches, predicting changes in stocks, spatial information processing, and coping with critical situations.
The Simulation of Action Strategies of Different Personalities in Perspective of the Interaction between Emotions, Motivations, and Cognition (An Experimental Study in the Field of Cognitive Psychology and Artificial Intelligence) Inaugural-Dissertation in der Fakultät Pädagogik, Philosophie und Psychologie der Otto-Friedrich-Universität Bamberg submitted by Ayman Elkady Abstract 1. Introduction: This research investigates the relationship between the theoretical basis of PSI-theory by Dietrich Dörner and the actual performance of subjects in the Island-game (a well-structured problem in an uncertain environment). The study compares the behavior of human subjects and the PSI simulation. The main results show that the PSI agent is not only able to simulate the different strategies of the experimental subjects, but also able to simulate single cases of personality. 2. Participants: A sample of 40 subjects participated in the experiment. The sample of participants was divided into two groups (group A and group B). Each group consisted of twenty participants. While "group A" played an island-game whos resources could be renewed, group B played the non-renewable resources version. 3. Materials: Island game, a computer simulation of a robot, called James, - endowed with several needs (e.g. for energy, for water), was used. The "island" contains numerous locations with different objects that can be manipulated in various ways. Manipulations of the objects can have effects on the robot (e.g. water can be drunk and the need for food is satisfied). Subjects have to control the robot and satisfy his existential needs. Moreover, they have to collect energy-rich-lumps of rock called 'Nucleotides'. 4. Experimental Design and Procedure: At the beginning of the experiment, participants were informed that they took part in a problem-solving experiment. Before beginning the first session, standard instructions for the task were given using Power Point presentation that explained the basic rules of the game and the tasks, namely, to keep the robot alive (e.g. to find enough water and food for the robot) and to collect so-called "Nucleotides". During these periods and all experimental conditions, subjects were allowed to think and speak freely. 5. Results of the experiment: The experiment show that there are no differences between the results of the participants of group A and the results of the participants of group B with respect to the eight dependent variables and the fact that the participants had played the game using different strategies. Therefore, we can assume that in this case the type of environment, whether poor or rich, does not play an important role. Most important is the way (the strategy) the available resources are managed by the actors. We have found these playing strategies: The Nucleotides-First-Strategy: Nucleotides are considered as a main motive and the existential needs of the robot are ignored. Survival-strategy: Existential needs of the robot are considered as a main motive and nucleotides are ignored. The Balance-Between-Motives-Strategy: Some participants made a balance between motives. In other words, some participants were capable of achieving both tasks (saving the robot from breakdowns and collecting nucleotides) by considering all goals of existential needs together with nucleotides. Stereotype-strategy: All goals of the different motives are included and are accompanied by a low selection threshold. 6. Simulation: We proposed that the PSI-program (and of course the theory behind the program) had motives, emotions and cognitive processes similar to those which human participants had in the experiment. Therefore, we set PSI-parameters in way that could simulate and produce the same strategies the subjects used in the experiment. The program was run with varying chance values within the specific range of all parameters. Simulation time had been varied because we discovered that the subjects had different playing-speeds. 7. Results of the simulation: The PSI model can produce the same strategies that the subjects had used during playing the Island game. There are highly significant correlations between PSI's behavioral parameters and the subjects' means for all parameter sets. Moreover, qualitative analyses of the two single cases indicated that PSI can also simulate single case strategies.