Integrating planning and learning: the PRODIGY architecture

A Survey of Planning and Learning in Games

In general, games pose interesting and complex problems for the implementation of intelligent agents and are a popular domain in the study of artificial intelligence. In fact, games have been at the center of some of the most well-known achievements in artificial intelligence. From classical board games such as chess, checkers, backgammon and Go, to video games such as Dota 2 and StarCraft II, artificial intelligence research has devised computer programs that can play at the level of a human master and even at a human world champion level. Planning and learning, two well-known and successful paradigms of artificial intelligence, have greatly contributed to these achievements. Although representing distinct approaches, planning and learning try to solve similar problems and share some similarities. They can even complement each other. This has led to research on methodologies to combine the strengths of both approaches to derive better solutions. This paper presents a survey of the multiple methodologies that have been proposed to integrate planning and learning in the context of games. In order to provide a richer contextualization, the paper also presents learning and planning techniques commonly used in games, both in terms of their theoretical foundations and applications.

A review of generalized planning

Generalized planningstudies the representation, computation and evaluation of solutions that are valid for multiple planning instances. These are topics studied since the early days of AI. However, in recent years, we are experiencing the appearance of novel formalisms to compactly represent generalized planning tasks, the solutions to these tasks (calledgeneralized plans) and efficient algorithms to compute generalized plans. The paper reviews recent advances in generalized planning and relates them to existing planning formalisms, such asplanning with domain control knowledgeand approaches forplanning under uncertainty, that also aim at generality.

Representation and Computation in Cognitive Models

One of the central issues in cognitive science is the nature of human representations. We argue that symbolic representations are essential for capturing human cognitive capabilities. We start by examining some common misconceptions found in discussions of representations and models. Next we examine evidence that symbolic representations are essential for capturing human cognitive capabilities, drawing on the analogy literature. Then we examine fundamental limitations of feature vectors and other distributed representations that, despite their recent successes on various practical problems, suggest that they are insufficient to capture many aspects of human cognition. After that, we describe the implications for cognitive architecture of our view that analogy is central, and we speculate on roles for hybrid approaches. We close with an analogy that might help bridge the gap.

Improving Automated Planning with Machine Learning

This chapter reports the last machine learning techniques for the assistance of automated planning. Recent discoveries in automated planning have opened the scope of planners, from toy problems to real-world applications, making new challenges come into focus. The planning community believes that machine learning can assist to address these new challenges. The chapter collects the last machine learning techniques for assisting automated planners classified in: techniques for the improvement of the planning search processes and techniques for the automatic definition of planning action models. For each technique, the chapter provides an in-depth analysis of their domain, advantages and disadvantages. Finally, the chapter draws the outline of the new promising avenues for research in learning for planning systems.

INCREMENTAL CASE-BASED PLAN RECOGNITION WITH LOCAL PREDICTIONS

We present a novel case-based plan recognition method that interprets observations of plan behavior using an incrementally constructed case library of past observations. The technique is novel in several ways. It combines plan recognition with case-based reasoning and leverages the strengths of both. The representation of a plan is a sequence of action-state pairs rather than only the actions. The technique compensates for the additional complexity with a unique abstraction scheme augmented by pseudo-isomorphic similarity relations to represent indices into the case base. Past cases are used to predict subsequent actions by adapting old actions and their arguments. Moreover, the technique makes predictions despite observations of unknown actions. This paper evaluates the algorithms and their implementation both analytically and empirically. The evaluation criteria include prediction accuracy at both an abstract and a concrete level and across multiple domains with and without case-adaptation. In each domain the system starts with an empty case base that grows to include thousands of past observations. Results demonstrate that this new method is accurate, robust, scalable, and general across domains.

EMBODIED CONCEPT DISCOVERY THROUGH QUALITATIVE ACTION MODELS

We present a novel approach to embodied learning of qualitative models. We introduce algorithm STRUDEL that enables an autonomous robot to discover new concepts by performing experiments in its environment. The robot collects data about its actions and its observations of the environment. From the obtained data, the robot learns qualitative descriptive models of the effects that its actions have in the environment. Models are learned using inductive logic programming. We describe two experiments with a humanoid robot Nao in which Nao learns descriptive qualitative models which contain what can be interpreted as simple definitions of the concepts of movability and stability.

Including cognitive biases and distance-based rewards in a connectionist model of complex problem solving

We present a cognitive, connectionist-based model of complex problem solving that integrates cognitive biases and distance-based and environmental rewards under a temporal-difference learning mechanism. The model is tested against experimental data obtained in a well-defined and planning-intensive problem. We show that incorporating cognitive biases (symmetry and simplicity) in a temporal-difference learning rule (SARSA) increases model adequacy-the solution space explored by biased models better fits observed human solutions. While learning from explicit rewards alone is intrinsically slow, adding distance-based rewards, a measure of closeness to goal, to the learning rule significantly accelerates learning. Finally, the model correctly predicts that explicit rewards have little impact on problem solvers' ability to discover optimal solutions.

PLTOOL: A knowledge engineering tool for planning and learning

Artificial intelligence (AI) planning solves the problem of generating a correct and efficient ordered set of instantiated activities, from a knowledge base of generic actions, which when executed will transform some initial state into some desirable end-state. There is a long tradition of work in AI for developing planners that make use of heuristics that are shown to improve their performance in many real world and artificial domains. The developers of planners have chosen between two extremes when defining those heuristics. The domain-independent planners use domain-independent heuristics, which exploit information only from the ‘syntactic’ structure of the problem space and of the search tree. Therefore, they do not need any ‘semantic’ information from a given domain in order to guide the search. From a knowledge engineering (KE) perspective, the planners that use this type of heuristics have the advantage that the users of this technology need only focus on defining the domain theory and not on defining how to make the planner efficient (how to obtain ‘good’ solutions with the minimal computational resources). However, the domain-dependent planners require users to manually represent knowledge not only about the domain theory, but also about how to make the planner efficient. This approach has the advantage of using either better domain-theory formulations or using domain knowledge for defining the heuristics, thus potentially making them more efficient. However, the efficiency of these domain-dependent planners strongly relies on the KE and planning expertise of the user. When the user is an expert on these two types of knowledge, domain-dependent planners clearly outperform domain-independent planners in terms of number of solved problems and quality of solutions. Machine-learning (ML) techniques applied to solve the planning problems have focused on providing middle-ground solutions as compared to the aforementioned two extremes. Here, the user first defines a domain theory, and then executes the ML techniques that automatically modify or generate new knowledge with respect to both the domain theory and the heuristics. In this paper, we present our work on building a tool, PLTOOL (planning and learning tool), to help users interact with a set of ML techniques and planners. The goal is to provide a KE framework for mixed-initiative generation of efficient and good planning knowledge.

Learning to solve planning problems efficiently by means of genetic programming

Declarative problem solving, such as planning, poses interesting challenges for Genetic Programming (GP). There have been recent attempts to apply GP to planning that fit two approaches: (a) using GP to search in plan space or (b) to evolve a planner. In this article, we propose to evolve only the heuristics to make a particular planner more efficient. This approach is more feasible than (b) because it does not have to build a planner from scratch but can take advantage of already existing planning systems. It is also more efficient than (a) because once the heuristics have been evolved, they can be used to solve a whole class of different planning problems in a planning domain, instead of running GP for every new planning problem. Empirical results show that our approach (EvoCK) is able to evolve heuristics in two planning domains (the blocks world and the logistics domain) that improve PRODIGY4.0 performance. Additionally, we experiment with a new genetic operator --Instance-Based Crossover--that is able to use traces of the base planner as raw genetic material to be injected into the evolving population.