Abstract We propose a hierarchical graph for learning physics and a novel way to handle obstacles. The finest level of the graph consist of the particles itself. Coarser levels consist of the cells of sparse grids with successively doubling cell sizes covering the volume occupied by the particles. The hierarchical structure allows for the information to propagate at great distance in a single message passing iteration. The novel obstacle handling allows the simulation to be obstacle aware without the need for ghost particles. We train the network to predict effective acceleration produced by multiple sub‐steps of 3D multi‐material material point method (MPM) simulation consisting of water, sand and snow with complex obstacles. Our network produces lower error, trains up to 7.0X faster and inferences up to 11.3X faster than [SGGP*20]. It is also, on average, about 3.7X faster compared to Taichi Elements simulation running on the same hardware in our tests.

Abstract The shape matching method is a popular approach to simulate deformable objects in interactive applications due to its stability and simplicity. An important feature is that there is no need for a mesh since the method works on arbitrary local groups within a set of particles. A major drawback of shape matching is the fact that it is geometrically motivated and not derived from physical principles which makes calibration difficult. The fact that the method does not conserve volume can yield visual artifacts, e.g. when a tire is compressed but does not bulge. In this paper we present a new meshless simulation method that is related to shape matching but derived from continuous constitutive models. Volume conservation and stiffness can be specified with physical parameters. Further, if the elements of a tetrahedral mesh are used as groups, our method perfectly reproduces FEM based simulations.

Abstract We introduce a triangle mesh based convolutional neural network. The proposed network structure can be used for problems where input and/or output are defined on a manifold triangle mesh with or without boundary. We demonstrate its applications in cloth upsampling, adding back details to Principal Component Analysis (PCA) compressed cloth, regressing clothing deformation from character poses, and regressing hand skin deformation from bones' joint angles. The data used for training in this work are generated from high resolution extended position based dynamics (XPBD) physics simulations with small time steps and high iteration counts and from an offline FEM simulator, but it can come from other sources. The inference time of our prototype implementation, depending on the mesh resolution and the network size, can provide between 4 to 134 times faster than a GPU based simulator. The inference also only needs to be done for meshes currently visible by the camera.

Abstract The “procedural” approach to animating ocean waves is the dominant algorithm for animating larger bodies of water in interactive applications as well as in off‐line productions — it provides high visual quality with a low computational demand. In this paper, we widen the applicability of procedural water wave animation with an extension that guarantees the satisfaction of boundary conditions imposed by terrain while still approximating physical wave behavior. In combination with a particle system that models wave breaking, foam, and spray, this allows us to naturally model waves interacting with beaches and rocks. Our system is able to animate waves at large scales at interactive frame rates on a commodity PC.

Abstract We examine the relationship between primal, or force‐based, and dual, or constraint‐based formulations of dynamics. Variational frameworks such as Projective Dynamics have proved popular for deformable simulation, however they have not been adopted for contact‐rich scenarios such as rigid body simulation. We propose a new preconditioned frictional contact solver that is compatible with existing primal optimization methods, and competitive with complementarity‐based approaches. Our relaxed primal model generates improved contact force distributions when compared to dual methods, and has the advantage of being differentiable, making it well‐suited for trajectory optimization. We derive both primal and dual methods from a common variational point of view, and present a comprehensive numerical analysis of both methods with respect to conditioning. We demonstrate our method on scenarios including rigid body contact, deformable simulation, and robotic manipulation.

Abstract We present a rigid body simulation method that can resolve small temporal and spatial details by using a quasi explicit integration scheme that is unconditionally stable. Traditional rigid body simulators linearize constraints because they operate on the velocity level or solve the equations of motion implicitly thereby freezing the constraint directions for multiple iterations. Our method always works with the most recent constraint directions. This allows us to trace high speed motion of objects colliding against curved geometry, to reduce the number of constraints, to increase the robustness of the simulation, and to simplify the formulation of the solver. In this paper we provide all the details to implement a fully fledged rigid body solver that handles contacts, a variety of joint types and the interaction with soft objects.

Abstract We present a system for creating a hair model that matches a user's hairstyle from images. The model consists of guide hair strands and can be used in a real‐time hair simulator. Our goal differs from most previous works that aim to create realistic high‐resolution hair for off‐line applications or create a mesh of the exterior of the hair volume for image manipulation. Our primary aim is for a user to be able to put his/her hairstyle into game or other real‐time applications. By taking photos in eight views of the user's head using a smartphone camera and segmenting the images with some easy‐to‐use tools, the player will obtain his/her own hair model in NVIDIA's HairWorks, which is a hair simulator used in many games. We show a number of results demonstrating the capabilities of our system in this paper.

We present a framework for the simulation of rigid and deformable bodies in the presence of contact and friction. Our method is based on a non-smooth Newton iteration that solves the underlying nonlinear complementarity problems (NCPs) directly. This approach allows us to support nonlinear dynamics models, including hyperelastic deformable bodies and articulated rigid mechanisms, coupled through a smooth isotropic friction model. The fixed-point nature of our method means it requires only the solution of a symmetric linear system as a building block. We propose a new complementarity preconditioner for NCP functions that improves convergence, and we develop an efficient GPU-based solver based on the conjugate residual (CR) method that is suitable for interactive simulations. We show how to improve robustness using a new geometric stiffness approximation and evaluate our method’s performance on a number of robotics simulation scenarios, including dexterous manipulation and training using reinforcement learning.

We introduce a deep reinforcement learning method that learns to control articulated humanoid bodies to imitate given target motions closely when simulated in a physics simulator. The target motion, which may not have been seen by the agent and can be noisy, is supplied at runtime. Our method can recover balance from moderate external disturbances and keep imitating the target motion. When subjected to large disturbances that cause the humanoid to fall down, our method can control the character to get up and recover to track the motion. Our method is trained to imitate the mocap clips from the CMU motion capture database and a number of other publicly available databases. We use a state-of-the-art deep reinforcement learning algorithm to learn to dynamically control the gain of PD controllers, whose target angles are derived from the mocap clip and to apply corrective torques with the goal of imitating the provided motion clip as closely as possible. Both the simulation and the learning algorithms are parallelized and run on the GPU. We demonstrate that the proposed method can control the character to imitate a wide variety of motions such as running, walking, dancing, jumping, kicking, punching, standing up, and so on.

Abstract Robustly and efficiently simulating cables and ropes that are part of a larger system such as cable driven machines, cable cars or tendons in a human or robot is a challenging task. To be able to adapt to the environment, cables are typically modeled as a large number of small segments that are connected via joints. The two main difficulties with this approach are to satisfy the inextensibility constraint and to handle the typically large mass ratio between the small segments and the larger objects they connect. In this paper we present a new approach which solves these problems in a simple and effective way. Our method is based on the idea to simulate the effect of the cables instead of the cables themselves. To this end we propose a new special type of distance constraint we call cable joint that changes both its attachment points and its rest length dynamically. A cable connecting a series of objects is then modeled as a sequence of cable joints which reduces the complexity of the simulation from the order of the number of segments to just the number of connected objects. This makes simulations both faster and more robust as we will demonstrate on a variety of examples.

The current state of the art in real-time two-dimensional water wave simulation requires developers to choose between efficient Fourier-based methods, which lack interactions with moving obstacles, and finite-difference or finite element methods, which handle environmental interactions but are significantly more expensive. This paper attempts to bridge this long-standing gap between complexity and performance, by proposing a new wave simulation method that can faithfully simulate wave interactions with moving obstacles in real time while simultaneously preserving minute details and accommodating very large simulation domains. Previous methods for simulating 2D water waves directly compute the change in height of the water surface, a strategy which imposes limitations based on the CFL condition (fast moving waves require small time steps) and Nyquist's limit (small wave details require closely-spaced simulation variables). This paper proposes a novel wavelet transformation that discretizes the liquid motion in terms of amplitude-like functions that vary over space, frequency, and direction , effectively generalizing Fourier-based methods to handle local interactions. Because these new variables change much more slowly over space than the original water height function, our change of variables drastically reduces the limitations of the CFL condition and Nyquist limit, allowing us to simulate highly detailed water waves at very large visual resolutions. Our discretization is amenable to fast summation and easy to parallelize. We also present basic extensions like pre-computed wave paths and two-way solid fluid coupling. Finally, we argue that our discretization provides a convenient set of variables for artistic manipulation, which we illustrate with a novel wave-painting interface.

We address the long-standing problem of iteration count and time step dependent constraint stiffness in position-based dynamics (PBD). We introduce a simple extension to PBD that allows it to accurately and efficiently simulate arbitrary elastic and dissipative energy potentials in an implicit manner. In addition, our method provides constraint force estimates, making it applicable to a wider range of applications, such those requiring haptic user-feedback. We compare our algorithm to more expensive non-linear solvers and find it produces visually similar results while maintaining the simplicity and robustness of the PBD method.

We present a novel algorithm to extract the rotational part of an arbitrary 3 X 3 matrix. This problem lies at the core of two popular simulation methods in computer graphics, the co-rotational Finite Element Method and Shape Matching techniques. In contrast to the traditional method based on polar decomposition, degenerate configurations and inversions are handled robustly and do not have to be treated in a special way. In addition, our method can be implemented with only a few lines of code without branches which makes it particularly well suited for GPU-based applications. We demonstrate the robustness, coherence and efficiency of our method by comparing it to stabilized polar decomposition in several simulation scenarios.

In computer graphics, simulated objects typically have two or three different representations, a visual mesh, a simulation mesh and a collection of convex shapes for collision handling. Using multiple representations requires skilled authoring and complicates object handing at run time. It can also produce visual artifacts such as a mismatch of collision behavior and visual appearance. The reason for using multiple representation has been performance restrictions in real time environments. However, for virtual worlds, we believe that the ultimate goal must be WYSIWYS -- what you see is what you simulate, what you can manipulate, what you can touch.

We present a system for creating hair model that matches a user's hairstyle. The model consists of guide hair strands and is ready to be used in a real-time hair simulator. Our goal differs from most previous work which aims to create realistic high resolution hair for off-line applications or create mesh of exterior of hair volume for image manipulation. Our primary aim is for user to be able to put his/her hairstyle into game or other real-time applications. By taking photos in 8 views of the user's head using a smart phone camera and segmenting images with some easy to use tools, the player will obtain his/her own hair model in NVIDIA's HairWorks, which is a hair simulator used in many games. We show a number of results demonstrating the capabilities of our system in this paper.

We present a novel explicit surface tracking method. Its main advantage over existing approaches is the fact that it is both completely grid-free and fast which makes it ideal for the use in large unbounded domains. A further advantage is that its running time is less sensitive to temporal variations of the input mesh than existing approaches. In terms of performance, the method provides a good trade-off point between speed and quality. The main idea behind our approach to handle topological changes is to delete all overlapping triangles and to fill or join the resulting holes in a robust and efficient way while guaranteeing that the output mesh is both manifold and without boundary. We demonstrate the flexibility, speed and quality of our method in various applications such as Eulerian and Lagrangian liquid simulations and the simulation of solids under large plastic deformations.

We propose a new method for both collision detection and collision response geared towards handling complex deformable objects in close contact. Our method does not miss collision events between time steps and solves the challenging problem of untangling automatically and robustly. It is conceptually simple and straight forward to parallelize due to the regularity of the algorithm. The main idea is to tessellate the air between objects once before the simulation and by considering one unilateral constraint per element that prevents its inversion during the simulation. If large relative rotations and translations are present in the simulation, an additional dynamic mesh optimization step is needed to prevent mesh locking. This step is fast in 2D and allows the simulation of arbitrary scenes. Because mesh optimization is expensive in 3D, however, the method is best suited for the subclass of 3D scenarios in which relative motions are limited. This subclass contains two important problems, namely the simulation of multi-layered clothing and tissue on animated characters.

We propose a new method to simulate large scale water phenomena by combining particle, 3D grid and height field methods. In contrast to most hybrid approaches that use particles to simulate foam and spray only, we also represent the bulk of water near the surface with both particles and a grid depending on the regions of interest and switch between those two representations during the course of the simulation. For the coupling we leverage the recent idea of tracking the water surface with a density field in grid based methods. Combining particles and a grid simulation then amounts to adding the density field of the particles and the one stored on the grid. For open scenes, we simulate the water outside of the 3D grid domain by solving the Shallow Water Equations on a height field. We propose new methods to couple these two domains such that waves travel naturally across the border. We demonstrate the effectiveness of our approach in various scenarios including a whale breaching simulation, all running in real-time or at interactive rates.

We present a unified dynamics framework for real-time visual effects. Using particles connected by constraints as our fundamental building block allows us to treat contact and collisions in a unified manner, and we show how this representation is flexible enough to model gases, liquids, deformable solids, rigid bodies and cloth with two-way interactions. We address some common problems with traditional particle-based methods and describe a parallel constraint solver based on position-based dynamics that is efficient enough for real-time applications.

We present a GPU friendly, Eulerian, free surface fluid simulation method that conserves mass locally and globally without the use of Lagrangian components. Local mass conservation prevents small-scale details of the free surface from disappearing, a problem that plagues many previous approaches, while global mass conservation ensures that the total volume of the liquid does not decrease over time. Our method handles moving solid boundaries as well as cells that are partially filled with solids. Due to its stability, it allows the use of large time steps that makes it suitable for both offline and real-time applications. We achieve this by using density-based surface tracking with a novel, unconditionally stable, conservative advection scheme. We also propose mass conserving methods to sharpen the interface and to reveal subgrid features of the liquid. While our approach conserves mass, volume loss is still possible but only temporarily. With constant mass, local volume loss causes a local increase of the density used for surface tracking which we detect and correct over time. We show the effectiveness of the proposed methods in several practical examples all running either at interactive rates or in real time.

We propose a new fast, robust and controllable method to simulate the dynamic destruction of large and complex objects in real time. The common method for fracture simulation in computer games is to pre-fracture models and replace objects by their pre-computed parts at run-time. This popular method is computationally cheap but has the disadvantages that the fracture pattern does not align with the impact location and that the number of hierarchical fracture levels is fixed. Our method allows dynamic fracturing of large objects into an unlimited number of pieces fast enough to be used in computer games. We represent visual meshes by volumetric approximate convex decompositions (VACD) and apply user-defined fracture patterns dependent on the impact location. The method supports partial fracturing meaning that fracture patterns can be applied locally at multiple locations of an object. We propose new methods for computing a VACD, for approximate convex hull construction and for detecting islands in the convex decomposition after partial destruction in order to determine support structures.

We present a multigrid method for solving the linear complementarity problem (LCP) resulting from discretizing the Poisson equation subject to separating solid boundary conditions in an Eulerian liquid simulation’s pressure projection step. The method requires only a few small changes to a multigrid solver for linear systems. Our generalized solver is fast enough to handle 3D liquid simulations with separating boundary conditions in practical domain sizes. Previous methods could only handle relatively small 2D domains in reasonable time, because they used expensive quadratic programming (QP) solvers. We demonstrate our technique in several practical scenarios, including nonaxis-aligned containers and moving solids in which the omission of separating boundary conditions results in disturbing artifacts of liquid sticking to solids. Our measurements show, that the convergence rate of our LCP solver is close to that of a standard multigrid solver.

We present a new Eulerian fluid simulation method, which allows real-time simulations of large scale three dimensional liquids. Such scenarios have hitherto been restricted to the domain of off-line computation. To reduce computation time we use a hybrid grid representation composed of regular cubic cells on top of a layer of tall cells. With this layout water above an arbitrary terrain can be represented without consuming an excessive amount of memory and compute power, while focusing effort on the area near the surface where it most matters. Additionally, we optimized the grid representation for a GPU implementation of the fluid solver. To further accelerate the simulation, we introduce a specialized multi-grid algorithm for solving the Poisson equation and propose solver modifications to keep the simulation stable for large time steps. We demonstrate the efficiency of our approach in several real-world scenarios, all running above 30 frames per second on a modern GPU. Some scenes include additional features such as two-way rigid body coupling as well as particle representations of sub-grid detail.

We propose a new fast and robust method to simulate various types of solid including rigid, plastic and soft bodies as well as one, two and three dimensional structures such as ropes, cloth and volumetric objects. The underlying idea is to use oriented particles that store rotation and spin, along with the usual linear attributes, i.e. position and velocity. This additional information adds substantially to traditional particle methods. First, particles can be represented by anisotropic shapes such as ellipsoids, which approximate surfaces more accurately than spheres. Second, shape matching becomes robust for sparse structures such as chains of particles or even single particles because the undefined degrees of freedom are captured in the rotational states of the particles. Third, the full transformation stored in the particles, including translation and rotation, can be used for robust skinning of graphical meshes and for transforming plastic deformations back into the rest state.

This paper considers robotic automation of a common surgical retraction primitive of exposing an underlying area by grasping and lifting a thin, 3D, possibly inhomogeneous layer of tissue. We present an algorithm that computes a set of stable and secure grasp-and-retract trajectories for a point-jaw gripper moving along a plane, and runs a 3D finite element (FEM) simulation to certify and assess the quality of each trajectory. To compute secure candidate grasp locations, we use a continuous spring model of thin, inhomogeneous deformable objects with linear energy potential. Experiments show that this method produces many of the same grasps as an exhaustive optimization with an FEM mesh, but is orders of magnitude cheaper: our method runs in O(v log v) time, where v is the number of veins, while the FEM computation takes O(pn3) time, where n is the number of nodes in the FEM mesh and p is the number of nodes on its perimeter. Furthermore, we present a constant tissue curvature (CTC) retraction trajectory that distributes strain uniformly around the medial axis of the tissue. 3D FEM simulations show that the CTC achieves retractions with lower tissue strain than circular and linear trajectories. Overall, our algorithm computes and certifies a high-quality retraction in about one minute on a PC.

We present algorithms for simulating and visualizing the insertion and steering of needles through deformable tissues for surgical training and planning. Needle insertion is an essential component of many clinical procedures such as biopsies, injections, neurosurgery, and brachytherapy cancer treatment. The success of these procedures depends on accurate guidance of the needle tip to a clinical target while avoiding vital tissues. Needle insertion deforms body tissues, making accurate placement difficult. Our interactive needle insertion simulator models the coupling between a steerable needle and deformable tissue. We introduce (1) a novel algorithm for local remeshing that quickly enforces the conformity of a tetrahedral mesh to a curvilinear needle path, enabling accurate computation of contact forces, (2) an efficient method for coupling a 3D finite element simulation with a 1D inextensible rod with stick-slip friction, and (3) optimizations that reduce the computation time for physically based simulations. We can realistically and interactively simulate needle insertion into a prostate mesh of 13,375 tetrahedra and 2,763 vertices at a 25 Hz frame rate on an 8-core 3.0 GHz Intel Xeon PC. The simulation models prostate brachytherapy with needles of varying stiffness, steering needles around obstacles, and supports motion planning for robotic needle insertion. We evaluate the accuracy of the simulation by comparing against real-world experiments in which flexible, steerable needles were inserted into gel tissue phantoms.

This paper presents a method for animating fluid using unstructured tetrahedral meshes that change at each time step. We show that meshes that conform well to changing boundaries and that focus computation in the visually important parts of the domain can be generated quickly and reliably using existing techniques. We also describe a new approach to two-way coupling of fluid and rigid bodies that, while general, benefits from remeshing. Overall, the method provides a flexible environment for creating complex scenes involving fluid animation.

Psychologists call behavior intrinsically motivated when it is engaged in for its own sake rather than as a step toward solving a specific problem of clear practical value. But what we learn during intrinsically motivated behavior is essential for our development as competent autonomous en- tities able to efficiently solve a wide range of practical problems as they arise. In this paper we present initial results from a computational study of intrinsically motivated reinforcement learning aimed at allowing arti- ficial agents to construct and extend hierarchies of reusable skills that are needed for competent autonomy. 1 Introduction Psychologists distinguish between extrinsic motivation, which means being moved to do something because of some specific rewarding outcome, and intrinsic motivation, which refers to being moved to do something because it is inherently enjoyable. Intrinsic motiva- tion leads organisms to engage in exploration, play, and other behavior driven by curiosity in the absence of explicit reward. These activities favor the development of broad com- petence rather than being directed to more externally-directed goals (e.g., ref. [14]). In contrast, machine learning algorithms are typically applied to single problems and so do not cope flexibly with new problems as they arise over extended periods of time. Although the acquisition of competence may not be driven by specific problems, this com- petence is routinely enlisted to solve many different specific problems over the agent's lifetime. The skills making up general competence act as the "building blocks" out of which an agent can form solutions to new problems as they arise. Instead of facing each new challenge by trying to create a solution out of low-level primitives, it can focus on combining and adjusting its higher-level skills. In animals, this greatly increases the effi- ciency of learning to solve new problems, and our main objective is to achieve a similar efficiency in our machine learning algorithms and architectures. This paper presents an elaboration of the reinforcement learning (RL) framework [11] that encompasses the autonomous development of skill hierarchies through intrinsically mo- tivated reinforcement learning. We illustrate its ability to allow an agent to learn broad competence in a simple "playroom" environment. In a related paper [1], we provide more extensive background for this approach, whereas here the focus is more on algorithmic details. Lack of space prevents us from providing a comprehensive background to the many ideas to which our approach is connected. Many researchers have argued for this kind of devel- opmental approach in which an agent undergoes an extended developmental period dur- ing which collections of reusable skills are autonomously learned that will be useful for a wide range of later challenges (e.g., [4, 13]). The previous machine learning research most closely related is that of Schmidhuber (e.g., [8]) on confidence-based curiosity and the ideas of exploration and shaping bonuses [6, 10], although our definition of intrinsic re- ward differs from these. The most direct inspiration behind the experiment reported in this paper, comes from neuroscience. The neuromodulator dopamine has long been associated with reward learning [9]. Recent studies [2, 3] have focused on the idea that dopamine not only plays a critical role in the extrinsic motivational control of behaviors aimed at harvest- ing explicit rewards, but also in the intrinsic motivational control of behaviors associated with novelty and exploration. For instance, salient, novel sensory stimuli inspire the same sort of phasic activity of dopamine cells as unpredicted rewards. However, this activation extinguishes more or less quickly as the stimuli become familiar. This may underlie the fact that novelty itself has rewarding characteristics [7]. These connections are key components of our approach to intrinsically motivated RL. 2 Reinforcement Learning of Skills According to the "standard" view of RL (e.g., [11]) the agent-environment interaction is envisioned as the interaction between a controller (the agent) and the controlled system (the environment), with a specialized reward signal coming from a "critic" in the environment that evaluates (usually with a scalar reward value) the agent's behavior (Fig. 1A). The agent learns to improve its skill in controlling the environment in the sense of learning how to increase the total amount of reward it receives over time from the critic. External Environment Environment Actions Sensations Critic Internal Environment Critic Rewards Actions States Rewards Decisions States Agent Agent "Organism" A B Figure 1: Agent-Environment Interaction in RL. A: The usual view. B: An elaboration. Sutton and Barto [11] point out that one should not identify this RL agent with an entire animal or robot. An an animal's reward signals are determined by processes within its brain that monitor not only external state but also the animal's internal state. The critic is in an animal's head. Fig. 1B makes this more explicit by "factoring" the environment of Fig. 1A into an external environment and an internal environment, the latter of which contains the critic which determines primary reward. This scheme still includes cases in which reward is essentially an external stimulus (e.g., a pat on the head or a word of praise). These are simply stimuli transduced by the internal environment so as to generate the appropriate level of primary reward. The usual practice in applying RL algorithms is to formulate the problem one wants the agent to learn how to solve (e.g., win at backgammon) and define a reward function spe- cially tailored for this problem (e.g., reward = 1 on a win, reward = 0 on a loss). Sometimes considerable ingenuity is required to craft an appropriate reward function. The point of departure for our approach is to note that the internal environment contains, among other things, the organism's motivational system, which needs to be a sophisticated system that should not have to be redesigned for different problems. Handcrafting a different special- purpose motivational system (as in the usual RL practice) should be largely unnecessary. Skills--Autonomous mental development should result in a collection of reusable skills. But what do we mean by a skill? Our approach to skills builds on the theory of options [12]. Briefly, an option is something like a subroutine. It consists of 1) an option policy that directs the agent's behavior for a subset of the environment states, 2) an initiation set con- sisting of all the states in which the option can be initiated, and 3) a termination condition, which specifies the conditions under which the option terminates. It is important to note that an option is not a sequence of actions; it is a closed-loop control rule, meaning that it is responsive to on-going state changes. Furthermore, because options can invoke other options as actions, hierarchical skills and algorithms for learning them naturally emerge from the conception of skills as options. Theoretically, when options are added to the set of admissible agent actions, the usual Markov decision process (MDP) formulation of RL extends to semi-Markov decision processes (SMDPs), with the one-step actions now be- coming the "primitive actions." All of the theory and algorithms applicable to SMDPs can be appropriated for decision making and learning with options [12]. Two components of the the options framework are especially important for our approach: 1. Option Models: An option model is a probabilistic description of the effects of executing an option. As a function of an environment state where the option is initiated, it gives the probability with which the option will terminate at any other state, and it gives the total amount of reward expected over the option's execution. Option models can be learned from experience (usually only approximately) using standard methods. Option models allow stochastic planning methods to be extended to handle planning at higher levels of abstraction. 2. Intra-option Learning Methods: These methods allow the policies of many options to be updated simultaneously during an agent's interaction with the environment. If an option could have produced a primitive action in a given state, its policy can be updated on the basis of the observed consequences even though it was not directing the agent's behavior at the time. In most of the work with options, the set of options must be provided by the system designer. While an option's policy can be improved through learning, each option has to be prede- fined by providing its initiation set, termination condition, and the reward function that evaluates its performance. Many researchers have recognized the desirability of automati- cally creating options, and several approaches have recently been proposed (e.g., [5]). For the most part, these methods extract options from the learning system's attempts to solve a particular problem, whereas our approach creates options outside of the context of solving any particular problem. Developing Hierarchical Collections of Skills--Children accumulate skills while they engage in intrinsically motivated behavior, e.g., while at play. When they notice that some- thing they can do reliably results in an interesting consequence, they remember this in a form that will allow them to bring this consequence about if they wish to do so at a future time when they think it might contribute to a specific goal. Moreover, they improve the efficiency with which they bring about this interesting consequence with repetition, before they become bored and move on to something else. We claim that the concepts of an option and an option model are exactly appropriate to model this type of behavior. Indeed, one of our main contributions is a (preliminary) demonstration of this claim. 3 Intrinsically Motivated RL Our main departure from the usual application of RL is that our agent maintains a knowl- edge base of skills that it learns using intrinsic rewards. In most other regards, our ex- tended RL framework is based on putting together learning and planning algorithms for Loop forever Current state st, current primitive action at, current option ot, extrinsic reward ret, intrinsic reward rit Obtain next state st+1 //-- Deal with special case if next state is salient If st+1 is a salient event e If option for e, oe, does not exist in O (skill-KB) Create option oe in skill-KB; Add st to Ioe // initialize initiation set Set oe (st+1) = 1 // set termination probability //-- set intrinsic reward value ri = [1 - P oe (s t+1 t+1|st)] // is a constant multiplier else ri = 0 t+1 //-- Update all option models For each option o = oe in skill-KB (O) If st+1 Io, then add st to Io // grow initiation set If at is greedy action for o in state st //-- update option transition probability model P o(x|st) [(1 - o(st+1)P o(x|st+1) + o(st+1)st+1x] //-- update option reward model Ro(st) [re + (1 - o(s t t+1))Ro(st+1)] //-- Q-learning update of behavior action-value function QB(st, at) [re + ri + max t t aAO QB (st+1, a)] //-- SMDP-planning update of behavior action-value function For each option o in skill-KB QB(st, o) [Ro(st) + P o(x|s xS t) maxaAO QB (x, a)] //-- Update option action-value functions For each option o O such that st Io Qo(st, at) [re + (o(s t t+1) terminal value for option o) +(1 - o(st+1)) maxaAO Qo(st+1, a)] For each option o O such that st Io and o = o Qo(st, o ) Ro (st) + P o (x|s xS t)[o(x) terminal val for option o +((1 - o(x)) maxaAO Qo(x, a))] Choose at+1 using -greedy policy w.r.to QB // -- Choose next action //-- Determine next extrinsic reward Set ret+1 to the extrinsic reward for transition st, at st+1 Set st st+1; at at+1; re re ri t t+1; rit t+1 Figure 2: Learning Algorithm. Extrinsic reward is denoted re while intrinsic reward is denoted ri. Equations of the form x [y] are short for x (1-)x+[y]. The behavior action value function QB is updated using a combination of Q-learning and SMDP planning. Throughout is a discount factor and is the step-size. The option action value functions Qo are updated using intra-option Q-learning. Note that the intrinsic reward is only used in updating QB and not any of the Qo. options [12]. Behavior The agent behaves in its environment according to an -greedy policy with re- spect to an action-value function QB that is learned using a mix of Q-learning and SMDP planning as described in Fig. 2. Initially only the primitive actions are available to the agent. Over time, skills represented internally as options and their models also become available to the agent as action choices. Thus, QB maps states s and actions a (both primitive and options) to the expected long-term utility of taking that action a in state s. Salient Events In our current implementation we assume that the agent has intrinsic or hardwired notions of interesting or "salient" events in its environment. For example, in the playroom environment we present shortly, the agent finds changes in light and sound intensity to be salient. These are intended to be independent of any specific task and likely to be applicable to many environments. Reward In addition to the usual extrinsic rewards there are occasional intrinsic rewards generated by the agent's critic (see Fig. 1B). In this implementation, the agent's intrinsic reward is generated in a way suggested by the novelty response of dopamine neurons. The intrinsic reward for each salient event is proportional to the error in the prediction of the salient event according to the learned option model for that event (see Fig. 2 for detail). Skill-KB The agent maintains a knowledge base of skills that it has learned in its environ- ment. Initially this may be empty. The first time a salient event occurs, say light turned on, structures to learn an option that achieves that salient event (turn-light-on option) are created in the skill-KB. In addition, structures to learn an option model are also created. So for option o, Qo maps states s and actions a (again, both primitive and options) to the long-term utility of taking action a in state s. The option for a salient event terminates with probability one in any state that achieves that event and never terminates in any other state. The initiation set, Io, for an option o is incrementally expanded to includes states that lead to states in the current initiation set. Learning The details of the learning algorithm are presented in Fig. 2. 4 Playroom Domain: Empirical Results We implemented intrinsically motivated RL (of Fig. 2) in a simple artificial "playroom" domain shown in Fig. 3A. In the playroom are a number of objects: a light switch, a ball, a bell, two movable blocks that are also buttons for turning music on and off, as well as a toy monkey that can make sounds. The agent has an eye, a hand, and a visual marker (seen as a cross hair in the figure). The agent's sensors tell it what objects (if any) are under the eye, hand and marker. At any time step, the agent has the following actions available to it: 1) move eye to hand, 2) move eye to marker, 3) move eye one step north, south, east or west, 4) move eye to random object, 5) move hand to eye, and 6) move marker to eye. In addition, if both the eye and and hand are on some object, then natural operations suggested by the object become available, e.g., if both the hand and the eye are on the light switch, then the action of flicking the light switch becomes available, and if both the hand and eye are on the ball, then the action of kicking the ball becomes available (which when pushed, moves in a straight line to the marker). The objects in the playroom all have potentially interesting characteristics. The bell rings once and moves to a random adjacent square if the ball is kicked into it. The light switch controls the lighting in the room. The colors of any of the blocks in the room are only visible if the light is on, otherwise they appear similarly gray. The blue block if pressed turns music on, while the red block if pressed turns music off. Either block can be pushed and as a result moves to a random adjacent square. The toy monkey makes frightened sounds if simultaneously the room is dark and the music is on and the bell is rung. These objects were designed to have varying degrees of difficulty to engage. For example, to get the monkey to cry out requires the agent to do the following sequence of actions: 1) get its eye to the light switch, 2) move hand to eye, 3) push the light switch to turn the light on, 4) find the blue block with its eye, 5) move the hand to the eye, 6) press the blue block to turn music on, 7) find the light switch with its eye, 8) move hand to eye, 9) press light switch to turn light off, 10) find the bell with its eye, 11) move the marker to the eye, 12) find the ball with its eye, 13) move its hand to the ball, and 14) kick the ball to make the bell ring. Notice that if the agent has already learned how to turn the light on and off, how to turn music on, and how to make the bell ring, then those learned skills would be of obvious use in simplifying this process of engaging the toy monkey. A B C Performance of Learned Options Effect of Intrinsically Motivated Learning 10000 120 100 8000 80 Sound On Extrinsic Reward Only 6000 60 Light On Music On 4000 40 Toy Monkey On Intrinsic & Extrinsic Rewards 20 2000 0 Average # of Actions to Salient Event 0 0.5 1 1.5 2 2.5 0 Number of steps between extrinsic rewards 0 100 200 300 400 500 600 7 Number of Actions x 10 Number of extrinsic rewards Figure 3: A. Playroom domain. B. Speed of learning of various skills. C. The effect of intrinsically motivated learning when extrinsic reward is present. See text for details For this simple example, changes in light and sound intensity are considered salient by the playroom agent. Because the initial action value function, QB, is uninformative, the agent starts by exploring its environment randomly. Each first encounter with a salient event initiates the learning of an option and an option model for that salient event. For example, the first time the agent happens to turn the light on, it initiates the data structures necessary for learning and storing the light-on option. As the agent moves around the environment, all the options (initiated so far) and their models are simultaneously updated using intra-option learning. As shown in Fig. 2, the intrinsic reward is used to update QB. As a result, when the agent encounters an unpredicted salient event a few times, its updated action value function drives it to repeatedly attempt to achieve that salient event. There are two interesting side effects of this: 1) as the agent tries to repeatedly achieve the salient event, learning improves both its policy for doing so and its option-model that predicts the salient event, and 2) as its option policy and option model improve, the intrinsic reward diminishes and the agent gets "bored" with the associated salient event and moves on. Of course, the option policy and model become accurate in states the agent encounters frequently. Occasionally, the agent encounters the salient event in a state (set of sensor readings) that it has not encountered before, and it generates intrinsic reward again (it is "surprised"). A summary of results is presented in Fig. 4. Each panel of the figure is for a distinct salient event. The graph in each panel shows both the time steps at which the event occurs as well as the intrinsic reward associated by the agent to each occurrence. Each occurrence is denoted by a vertical bar whose height denotes the amount of associated intrinsic reward. Note that as one goes from top to bottom in this figure, the salient events become harder to achieve and, in fact, become more hierarchical. Indeed, the lowest one for turning on the monkey noise (Non) needs light on, music on, light off, sound on in sequence. A number of interesting results can be observed in this figure. First note that the salient events that are simpler to achieve occur earlier in time. For example, Lon (light turning on) and Loff (light turning off) are the simplest salient events, and the agent makes these happen quite early. The agent tries them a large number of times before getting bored and moving on to other salient events. The reward obtained for each of these events diminishes after repeated exposure to the event. Thus, automatically, the skill of achieving the simpler events are learned before those for the more complex events. Figure 4: Results from the playroom domain. Each panel depicts the occurrences of salient events as well as the associated intrinsic rewards. See text for details. Of course, the events keep happening despite their diminished capacity to reward because they are needed to achieve the more complex events. Consequently, the agent continues to turn the light on and off even after it has learned this skill because this is a step along the way toward turning on the music, as well as along the way toward turning on the monkey noise. Finally note that the more complex skills are learned relatively quickly once the required sub-skills are in place, as one can see by the few rewards the agent receives for them. The agent is able to bootstrap and build upon the options it has already learned for the simpler events. We confirmed the hierarchical nature of the learned options by inspecting the greedy policies for the more complex options like Non and Noff. The fact that all the options are successfully learned is also seen in Fig. 3B in which we show how long it takes to bring about the events at different points in the agent's experience (there is an upper cutoff of 120 steps). This figure also shows that the simpler skills are learned earlier than the more complex ones. An agent having a collection of skills learned through intrinsic reward can learn a wide variety of extrinsically rewarded tasks more easily than an agent lacking these skills. To illustrate, we looked at a playroom task in which extrinsic reward was available only if the agent succeeded in making the monkey cry out. This requires the 14 steps described above. This is difficult for an agent to learn if only the extrinsic reward is available, but much easier if the agent can use intrinsic reward to learn a collection of skills, some of which are relevant to the overall task. Fig. 3C compares the performance of two agents in this task. Each starts out with no knowledge of task, but one employs the intrinsic reward mechanism we have discussed above. The extrinsic reward is always available, but only when the monkey cries out. The figure, which shows the average of 100 repetitions of the experiment, clearly shows the advantage of learning with intrinsic reward. Discussion One of the key aspects of the Playroom example was that intrinsic reward was generated only by unexpected salient events. But this is only one of the simplest possibilities and has many limitations. It cannot account for what makes many forms of exploration and manipulation "interesting." In the future, we intend to implement compu- tational analogs of other forms of intrinsic motivation as suggested in the psychological, statistical, and neuroscience literatures. Despite the "toy" nature of this domain, these results are among the most sophisticated we have seen involving intrinsically motivated learning. Moreover, they were achieved quite directly by combining a collection of existing RL algorithms for learning options and option-models with a simple notion of intrinsic reward. The idea of intrinsic motivation for artificial agents is certainly not new, but we hope to have shown that the elaboration of the formal RL framework in the direction we have pursued, together with the use of recently- developed hierarchical RL algorithms, provides a fruitful basis for developing competently autonomous agents. Acknowledgement Satinder Singh and Nuttapong Chentanez were funded by NSF grant CCF 0432027 and by a grant from DARPA's IPTO program. Andrew Barto was funded by NSF grant CCF 0432143 and by a grant from DARPA's IPTO program.