Interactive character system   

This application is a continuation of U.S. application Ser. No. 11/959,692, filed on Dec. 19, 2007, which is a divisional of U.S. application Ser. No. 10/415,851, filed on Nov. 14, 2003, which is a National Stage of International Application No. PCT/US01/50915, filed on Oct. 29, 2001, which claims the benefit of U.S. Provisional Application No. 60/245,823, filed on Nov. 3, 2000, and claims the benefit of U.S. Provisional Application No. 60/246,034, filed on Nov. 3, 2000, and claims the benefit of U.S. Provisional Application No. 60/246,054, filed on Nov. 3, 2000. The contents of each of the aforementioned applications are incorporated herein by reference.

Interactive media systems, such as Internet web pages, interactive television, and the like, have become important modes of providing entertainment and information to consumers. It is therefore desirable to be able to present advertising and other types of messages through these media that present in an interactive and apparently seamless fashion. It is also desirable to be able to present synthetic interactive characters to users of these systems that appear to have a broad range of emotional states, and to be able to use such characters to present advertising and other types of information to a user.

Previous approaches to this have been poor in a number of ways.

Static and animated banner advertising does not deliver compelling interactive characters. This is one of the reasons why banner ads typically cannot give the customer an emotional pull.

Interstitial ads (a pop-up window with movie-like ad content) can deliver an emotional pull in the same way as a television ad, but the user is not interacting with the characters.

Prior art includes interactive games for the purpose of advertising that do not include interactive characters. An example of this is the games on www.candystand.com. Such systems typically contain background art or functional elements that are based on the product or other branded marks. However, they do not allow the consumer to interact with interactive characters, instead interacting with the mechanism of the game. For example, the consumer might play a simulated game of miniature golf on a course that has company logos on it.

Prior art includes interactive games or activities for the purpose of advertising that do use characters. An example of this is the Coca Cola Bears advertisement from togglethis.com. However, these characters have limited interactivity, and the characters are not products brought to life.

Web browsers enable a user to download content from a network and display it on a display system. Oftentimes, it is useful to download program code to execute on the user\'s display system. Prior art display systems include web browsers that allow users to download code for running on a virtual machine or interpreted in a controlled environment (e.g. Java code for running on a Java virtual machine), thus preventing downloaded code from gaining full access to system resources. Example browsers include Netscape Navigator and Internet Explorer.

Prior art delivery systems also allow native code, i.e., machine code (including relocatable code) for executing on a computer processor, to be launched by the user\'s web browser. These browsers currently use mechanisms such as plug-ins or Active X components to allow native code to run in the browser. However, these mechanisms require special permission to run the code to be granted prior to downloading the plug-in or component, resulting in a delay or confusing moment in the user\'s browsing experience.

In presenting interactive advertising to users, it is important that the display of such advertising occur as seamlessly, and without delay, as possible. One technique for avoided delays when a program module is downloaded to a user\'s computer is “code streaming.” “Code streaming” means downloading code in sequence, running the earlier downloaded code and linking the later code with the running code. Rudimentary support for streaming program code is provided in languages such as Java: for example, when a Java applet first instantiates a class, the code for that class can be downloaded automatically from a specified server on the Internet. However, for security reasons such Java classes are not compiled to native code, but rather to bytecode that must be verified and either interpreted or compiled after downloading. This overhead renders bytecode impractical for many applications.

SUMMARY

The invention provides an enhanced capability and techniques for presenting interactive characters to a user

In general, in one aspect, the invention features a method for controlling a synthetic character using a control system that includes displaying the character engaged in an activity, receiving a first input from a user determining whether the input is relevant to the activity, if the input is relevant to the activity, showing the character react to the input, the character being highly expressive and highly reactive.

Implementations of the invention may include one or more of the following features. The character has a specified personality. A characteristic of a user avatar is changed in response to the user input, and determining whether the input is relevant to the activity includes determining whether the change in the characteristic of the user avatar is relevant to the activity. Displaying the character includes displaying an animated character on a display screen. Displaying the character includes controlling a robotic embodiment of the character. Showing the character react to the input includes having the character look out of the screen or at an avatar. Showing the character react to the input includes changing the emotional expression of the character to correspond to a first emotion. Changing the emotional expression includes changing the facial expression of the character. Changing the emotional expression includes changing the tone of the character\'s voice. Changing the emotional expression of the character includes changing the speed of motion of the character. Changing the emotional expression of the character includes changing the body posture of the character. Over a period of time, after the emotional expression of the character is changed, the appearance of the character is gradually altered to diminish the expression of the emotion by the character. A second input is received from the user after receiving the first input, it is determined whether the second input is relevant to the activity, and if the input is relevant to the activity, the emotional expression of the character is changed to correspond to a combination of the first emotional expression and a second emotional expression.

In general, in another aspect the invention features a method for displaying a synthetic character that includes providing speech data, creating modified speech data by modifying at least one of the pitch or duration of at least a portion of the speech data, and generating modified speech sounds associated with the character using the modified speech data.

Implementations of the invention may include one or more of the following features. Modifying at least a portion of the speech data includes modifying the speech data with respect to at least selected portions of the frequency spectrum. Displaying the synthetic character includes displaying an animated character on a display screen. Displaying the synthetic character includes providing a robotic embodiment of the character. Creating modified speech data includes modifying at least two of the pitch, duration or volume of at least a portion of the speech data. The speech data is modified in real time. The at least a portion of the speech data includes data representing at least one complete word of speech. The at least a portion of the speech data includes data representing at least two contiguous words of speech. An input is received from a user and the display of the character is modified based on the user input. A user avatar is displayed and a characteristic of the user avatar is changed in response to the input from the user, and modifying the display of the character based on the user input includes modifying the display of the character based on the change in the characteristic of the user avatar. The characters are fully autonomous. The speech data or the modification of the speech data is selected based on the user input. Motion data describing a motion of the character is provided, the motion date is modified in real time, and the character is displayed according to the modified motion data. Modifying the motion data includes generating motion data for coordinating the display of the character with the generation of the modified speech sounds. The displaying of the character is tightly coupled with the generated speech sounds. Creating the modified speech data includes providing first sample speech data, providing second sample speech data, comparing the first sample speech data and the second sample speech data, and using the results of the comparison to create the modified speech data. A function of one or more parameters of the speech data is generated, and creating the modified speech data includes applying the function to at least a portion of the speech data. Generating the modification function includes providing a first base function of the one or more parameters, selecting, from a continuous range of values, a weighting factor, and generating the modification function using the base function and the weighting factor. Applying the modification function to at least a portion of the speech data includes providing a first base function of the one or more parameters, selecting, from a continuous range of values, a weighting factor, and using the first base function and the weighting factor to modify the speech data. The base function represents a modification of the characteristics of the speech data with respect to at least one of the characteristics in the group inflection, emphasis, emotional quality, stylistic quality, and accent, and the modification function represents a different degree of modification of the at least one characteristic than the base function. The base function represents a modification of the characteristics of the speech data with respect to at least one of the characteristics in the group inflection, emphasis, emotional quality, stylistic quality, and accent, and using the first base function and the weighting factor to modify the speech data results in a different degree of modification of the at least one characteristic than the base function. The at least one characteristic is sadness or happiness. Distortion limits for limiting the modification of the speech data are provided, modification parameters for modifying the speech data are computed, the modification parameters to the distortion limits are compared, and the modification parameters are modified if they exceed any of the distortion limits. The modified speech data is always within pre-determined distortion limits. A representation of an emotional state is associated with the character and the speech of the character is based on the emotional state representation. The character is highly expressive. The character is highly reactive. The character has a specified personality. The character is highly expressive, highly reactive and has a specified personality. The character is highly reactive and has at least one of the following group of characteristics: highly expressive, appearing to be intelligent, exhibiting common sense, exhibiting social knowledge, exhibiting knowledge of social norms, having a specified personality.

In general, in another aspect, the invention features a method for modifying speech data that includes providing first sample speech data, providing second sample speech data, comparing the first sample speech data and the second sample speech data, and using the results of the comparison to create modified speech data.

Implementations of the invention may have one or more of the following features The comparing step includes generating a function of one or more parameters of the speech data, and creating the modified speech data includes modifying at least a portion of the speech data based on the function. Modifying at least a portion of the speech data based on the function includes applying the function to the speech data. The first sample speech data and the second sample speech data are representations of the same utterance. Creating the modified speech data includes modifying any one of the following: pitch of the speech data or duration of the speech data. Creating the modified speech data includes modifying any two of the group pitch, duration and volume of the speech data. The first sample speech data and the second sample speech data differ in at least one of the following qualities: inflection, emphasis, emotional quality, stylistic quality, and accent. The modified speech data differs from the speech data in at least one of the following qualities: inflection, emphasis, emotional quality, stylistic quality, or accent. A second function of one or more parameters of the speech data is generated and creating the modified speech data further includes modifying the speech data based on the first function and the second function. The first function and the second function each modify at least one of the group of inflection, emphasis, emotional quality, stylistic quality, or accent of the speech data. Modifying the speech data based on the first function and the second function includes generating a third function based on the first function and the second function and applying the third function to the speech data. Generating the modification function further includes providing a second base function of the one or more parameters, selecting, from a continuous range of values, a second weighting factor, and generating the modification function using the second base function and the second weighting factor. Applying the modification function to at least a portion of the speech data includes providing a second base function of the one or more parameters, selecting, from a continuous range of values, a second weighting factor, and using the second base function and the second weighting factor to modify the speech data. The base function and the second base function each represent a modification of the characteristics of the speech data with respect to at least one of the characteristics in the group inflection, emphasis, emotional quality, stylistic quality, and accent, and the modification function represents a different degree of modification of the at least one characteristic than the base function or the second base function. The base function and the second base function each represent a modification of the characteristics of the speech data with respect to at least one of the characteristics in the group inflection, emphasis, emotional quality, stylistic quality, and accent, and using the second base function and the second weighting factor to modify the speech data results in a different degree of modification of the at least one characteristic than the second base function.

In general, in another aspect, the invention features a method of advertising a product that includes designing a fully autonomous synthetic character that represents an animated version of the product or product packaging, the product or product packaging not otherwise having the appearance of a character, displaying the synthetic character to a user, and permitting the user to interact with the character.

Implementations of the invention may include one or more of the following features. Displaying the synthetic character includes displaying an animated character on a display screen. Displaying the synthetic character includes providing a robotic embodiment of the character. The character inhabits an environment and the user interacts with the character in the environment. The character has eyes, and the eyes appear to track objects in the on-screen world or the real world. The character\'s eyes appear to track objects only at selected moments. The selected moments are determined by the fully autonomous character. Motions for the character are generated in real-time. The character is highly expressive. The character is highly reactive. The character has a specified personality. The character is highly expressive, highly reactive and has a specified personality. The character is highly reactive and has at least one of the following group of characteristics: highly expressive, appearing to be intelligent, exhibiting common sense, exhibiting social knowledge, exhibiting knowledge of social norms, having a specified personality.

In general, in another aspect, the invention features a method for loading an executable native code program into a computer system that includes loading a first portion of the program into the computer system from a non-local network, beginning execution of the first portion of the program, during execution of the first portion of the program, loading a second portion of the program into the computer system from the non-local network and linking the second portion of the program to the first portion of the program, and executing code in the second portion of the program.

Implementations of the invention may include one or more of the following features. Hyperlinked information is displayed in a display on the computer system, and the first portion of the program is loaded in response user selection of a hyperlink in the display. A component list is loaded into the computer system in response to a user input, the first portion of the program is loaded according to information in the component list, and the second portion of the program is loaded according to information in the component list. Linking the second portion of the program to the first portion of the program includes determining that the second portion of the program has been completely loaded into the computer system, and notifying the first portion of the program that the second portion has been loaded. During execution of the second portion of the program a third portion of the program is loaded into the computer system, the third portion of the program is linked to the first or second portion of the program, and code in the third portion of the program is executed. In response to a user input, content other than native code is loaded into the system and that content is displayed to the user and the first portion of the program is loaded during display of that content to the user. The program includes an interactive system for displaying an on-screen environment and, during execution of the first portion of the program, a first version of the on-screen environment is displayed and, in response to the progress of loading of the second portion of the program, the on-screen environment is modified. The on-screen environment is modified after completion of the loading of the second portion of the program. Modifying the on-screen environment includes changing the set of potential user acts in the environment. Modifying the on-screen environment includes changing the appearance of a particular location in the on-screen environment to show the additional set of potential user acts. Modifying the on-screen environment includes changing the potential behaviors of one or more characters in the environment. At least a portion of the changed potential behavior of the one or more characters is implemented by the second portion of the program. The non-local network includes a wide area network. The non-local network includes a broadcast network. The non-local network includes a wireless network. The non-local network includes a dialup network. The non-local network includes a cable TV network.

In general, in another aspect, the invention features a method for loading data into a computer system that includes starting to receive a stream of data from a network connection, during receipt of the data stream, monitoring the use of network resources by the computer system, and adjusting the rate of receipt of the data stream based on the use of network resources.

Implementations of the invention may include one or more of the following features. The network is a non-local network. Monitoring the use of network resources includes detecting a request to load additional data onto the computer system from the network. Adjusting the rate of receipt of the data stream includes temporarily suspending the receipt of the data stream while the requested additional data is loaded onto the computer system, and continuing to receive the data stream after at least a pre-defined portion of the requested additional data has been loaded onto the computer system. Adjusting the rate of receipt of the data stream includes reducing the rate of receipt of the data stream while the additional data is being loaded onto the system. Detecting a request to load additional data onto the computer system includes detecting a request to load content into a web browser. The at least a pre-defined portion of the requested additional data is displayed on the computer system to a user while the data stream continues to be received after the requested additional data has been loaded onto the computer system. The data stream includes native code for execution on the computer system. Monitoring the use of network resources by the computer system includes monitoring the throughput of a download process.

In general, in another aspect, the invention features a method for loading data onto a computer system that includes, in response to a user input, loading first content for display to the user, in response to the same user input, and after at least a predefined portion of the first content has been loaded, starting to receive a first stream of data that includes native code from a network connection, the first stream of data not being part of the first content.

Implementations of the invention may include one or more of the following features. Display of the first content provides the user with selectable options. The first content is a hyperlinked page. During display of the first content and the receipt of the first stream of data, in response to a second user input, the rate of receipt of the first stream of data is temporarily reduced, and, during the temporary reduction of the rate of receipt of the first stream of data, second content for display to the user is loaded. After loading at least a pre-defined portion of the second content, the rate of receipt of the first stream of data is increased. In response to the second user input, a second stream of data from a network connection is loaded. Temporarily reducing the rate of receipt of the first stream of data includes suspending receipt of the first stream of data.

In general, in another aspect, the invention features a method for presenting a dynamic visual model using a data processing system that includes generating in the data processing system a first representation of at least one structural element of the model, displaying the at least one structural element of the model on a display, and modifying the appearance of the displayed at least one structural element by modifying a curvature of the element over a continuous portion of the element.

Implementations of the invention may include one or more of the following features. The dynamic visual model is an animated character. The continuous portion of the element includes substantially all of the element. The modification of the appearance includes modifying the representation of the structural element in real time. The representation of the at least one structural element includes a representation of a spline curve. The representation of the at least one structural element includes or is linked to a representation of a surface defining a volume surrounding the spline curve, and displaying the at least one structural element of the model on a display includes displaying the surface on the display. Modifying the appearance of the displayed at least one structural element includes modifying the shape of the surface of the element. A representation of at least a second structural element of the model distinct from the first structural element is generated in the data processing system, and a representation of a linkage between the first structural element and the second structural element is generated. The second structural element is displayed on the display, and the appearance of the displayed second structural element is modified by modifying a curvature of the element over a continuous portion of the element. The second structural element is a rigid structural element. The representations of the at least one structural element and the second structural element include respective representations of spline curves, the representations of the at least one structural element and the second structural element are linked to a representation of a surface defining a volume surrounding the respective represented spline curves, and displaying the at least one structural element and the second structural element of the model on the display includes displaying the surface on the display. Modifying the appearance of the at least one structural element includes modifying the length of the structural element. The representation of the structural element includes a representation of a spline curve, and modifying the length of the structural element includes changing the length of the spline curve. The representation of the at least one structural element includes or is linked to a representation of a surface defining a volume, and modifying the appearance of the at least one structural element further includes modifying the representation of the surface to maintain a substantially constant defined volume when the length of the structural element is modified. A second representation of the at least one structural element of the model having a different shape from the first representation is generated and, on the display, the first representation is morphed using the second representation. A third representation of the at least one structural element of the model having a different shape from the first and second representations is generated, and both the second and third representations of the structural element are used to morph the first representation on the display. Differences between the first representation and both the second representation and the third representation are determined, and a weighted sum of the differences is used to morph the first representation. The at least one structural element has an outer surface and a central axis, and the appearance of the at least one structural element is modified by rotating portions of the outer surface of the element relative to the central axis, the degree of rotation varying at locations adjacent to different points along the axis. The central axis of the element is defined by a spline curve.

In general, in another aspect, the invention features a system for controlling a synthetic character using a control system that includes means for displaying the character as a highly expressive, highly reactive, character engaged in an activity, means for receiving a first input from a user, means for determining whether the input is relevant to the activity, and means for, if the input is relevant to the activity, showing the character react to the input.

In general, in another aspect, the invention features a computer software product, embedded on a computer readable medium, for controlling a synthetic character using a control system that includes instructions for causing a computer system to display the character as a highly expressive, highly reactive, character engaged in an activity, instructions for causing the computer to receive a first input from a user, instructions for causing the computer to determine whether the input is relevant to the activity, and instructions for causing the computer to, if the input is relevant to the activity, show the character react to the input.

In general, in another aspect, the invention features a method of transmitting to a system a computer software product for controlling a synthetic character using a control system that includes transmitting to the system instructions for causing a computer system to display the character as a highly expressive, highly reactive, character engaged in an activity, transmitting to the system instructions for causing the computer to receive a first input from a user, transmitting to the system instructions for causing the computer to determine whether the input is relevant to the activity, and transmitting to the system instructions for causing the computer to, if the input is relevant to the activity, show the character react to the input.

In general, in another aspect, the invention features a system for displaying a synthetic character that includes means for providing speech data, means for creating modified speech data by modifying at least one of the pitch or duration of at least a portion of the speech data, and means for generating modified speech sounds associated with the character using the modified speech data.

In general, in another aspect, the invention features a computer software product, embedded on a computer readable medium, for displaying a synthetic character that includes instructions for causing a computer to provide speech data, instructions for causing a computer to create modified speech data by modifying at least one of the pitch or duration of at least a portion of the speech data, and instructions for causing a computer to generate modified speech sounds associated with the character using the modified speech data.

In general, in another aspect, the invention features a method of transmitting to a system a computer software product for displaying a synthetic character that includes transmitting to the system instructions for causing a computer to provide speech data, transmitting to the system instructions for causing a computer to create modified speech data by modifying at least one of the pitch or duration of at least a portion of the speech data, and transmitting to the system instructions for causing a computer to generate modified speech sounds associated with the character using the modified speech data.

In general, in another aspect, the invention features a system for modifying speech data that includes means for providing first sample speech data, means for providing second sample speech data, means for comparing the first sample speech data and the second sample speech data, and means for using the results of the comparison to create modified speech data.

In general, in another aspect, the invention features a computer program product, embedded on a computer readable medium, for modifying speech data that includes instructions for causing a computer to provide first sample speech data, instructions for causing a computer to provide second sample speech data, instructions for causing a computer to compare the first sample speech data and the second sample speech data, and instructions for causing a computer to use the results of the comparison to create modified speech data.

In general, in another aspect, the invention features a method for transmitting to a system a computer program product, embedded on a computer readable medium, for modifying speech data that includes transmitting to the system instructions for causing a computer to provide first sample speech data, transmitting to the system instructions for causing a computer to provide second sample speech data, transmitting to the system instructions for causing a computer to compare the first sample speech data and the second sample speech data, and transmitting to the system instructions for causing a computer to use the results of the comparison to create modified speech data.

In general, in another aspect, the invention features a system for advertising a product that includes means for enabling a user to design a fully autonomous synthetic character that represents an animated version of the product or product packaging, the product or product packaging not otherwise having the appearance of a character, means for displaying the synthetic character to a user, and means for permitting the user to interact with the character.

In general, in another aspect, the invention features a computer program product, embedded on a computer readable medium, for advertising a product that includes instructions for causing a computer to enable a user to design a fully autonomous synthetic character that represents an animated version of the product or product packaging, the product or product packaging not otherwise having the appearance of a character, instructions for causing a computer to display the synthetic character to a user, and instructions for causing a computer to permit the user to interact with the character.

In general, in another aspect, the invention features a method for transmitting to a system a computer program product for advertising a product that includes transmitting to the system instructions for causing a computer to enable a user to design a fully autonomous synthetic character that represents an animated version of the product or product packaging, the product or product packaging not otherwise having the appearance of a character, transmitting to the system instructions for causing a computer to display the synthetic character to a user, and transmitting to the system instructions for causing a computer to permit the user to interact with the character.

In general, in another aspect, the invention features a system for loading an executable native code program into a computer system that includes means for loading a first portion of the program into the computer system from a non-local network, means for beginning execution of the first portion of the program, means for, during execution of the first portion of the program, loading a second portion of the program into the computer system from the non-local network and linking the second portion of the program to the first portion of the program, and means for executing code in the second portion of the program.

In general, in another aspect, the invention features a computer program product, embedded on a computer readable medium, for loading an executable native code program into a computer system that includes instructions for causing a computer to load a first portion of the program into the computer system from a non-local network, instructions for causing a computer to begin execution of the first portion of the program, instructions for causing a computer to, during execution of the first portion of the program, load a second portion of the program into the computer system from the non-local network and link the second portion of the program to the first portion of the program, and instructions for causing a computer to execute code in the second portion of the program.

In general, in another aspect, the invention features a method for transmitting to a system a computer program product, for loading an executable native code program into a computer system that includes transmitting to the system instructions for causing a computer to load a first portion of the program into the computer system from a non-local network, transmitting to the system instructions for causing a computer to begin execution of the first portion of the program, transmitting to the system instructions for causing a computer to, during execution of the first portion of the program, load a second portion of the program into the computer system from the non-local network and link the second portion of the program to the first portion of the program, and transmitting to the system instructions for causing a computer to execute code in the second portion of the program.

In general, in another aspect, the invention features a system for loading data into a computer system that includes means for starting to receive a stream of data from a network connection, means for, during receipt of the data stream, monitoring the use of network resources by the computer system, and means for adjusting the rate of receipt of the data stream based on the use of network resources.

In general, in another aspect, the invention features a computer program product, embedded on a computer readable medium, for loading data into a computer system that includes instructions for causing a computer to start to receive a stream of data from a network connection, instructions for causing a computer to, during receipt of the data stream, monitor the use of network resources by the computer system, and instructions for causing a computer to adjust the rate of receipt of the data stream based on the use of network resources.

In general, in another aspect, the invention features a method for transmitting to a system a computer program product for loading data into a computer system that includes transmitting to the system instructions for causing a computer to start to receive a stream of data from a network connection, transmitting to the system instructions for causing a computer to, during receipt of the data stream, monitor the use of network resources by the computer system, and transmitting to the system instructions for causing a computer to adjust the rate of receipt of the data stream based on the use of network resources.

In general, in another aspect, the invention features a system for loading data onto a computer system that includes means for, in response to a user input, loading first content for display to the user, means for, in response to the same user input, and after at least a predefined portion of the first content has been loaded, starting to receive a first stream of data that includes native code from a network connection, the first stream of data not being part of the first content.

In general, in another aspect, the invention features a computer program product, embedded on a computer readable medium, for loading data onto a computer system that includes instructions for causing a computer to, in response to a user input, load first content for display to the user, instructions for causing a computer to, in response to the same user input, and after at least a predefined portion of the first content has been loaded, start to receive a first stream of data that includes native code from a network connection, the first stream of data not being part of the first content.

In general, in another aspect, the invention features a method for transmitting to a system a computer program product for loading data onto a computer system that includes transmitting to the system instructions for causing a computer to, in response to a user input, load first content for display to the user, transmitting to the system instructions for causing a computer to, in response to the same user input, and after at least a predefined portion of the first content has been loaded, start to receive a first stream of data that includes native code from a network connection, the first stream of data not being part of the first content.

In general, in another aspect, the invention features a system for presenting a dynamic visual model using a data processing system that includes means for generating in the data processing system a first representation of at least one structural element of the model, means for displaying the at least one structural element of the model on a display, means for modifying the appearance of the displayed at least one structural element by modifying a curvature of the element over a continuous portion of the element.

In general, in another aspect, the invention features a computer software product, embedded on a computer readable medium, for presenting a dynamic visual model using a data processing system that includes instructions for causing a computer to generate in the data processing system a first representation of at least one structural element of the model,

instructions for causing a computer to display the at least one structural element of the model on a display, instructions for causing a computer to modify the appearance of the displayed at least one structural element by modifying a curvature of the element over a continuous portion of the element.

In general, in another aspect, the invention features a method for transmitting to a system a computer software product for presenting a dynamic visual model using a data processing system that includes transmitting to the system instructions for causing a computer to generate in the data processing system a first representation of at least one structural element of the model, transmitting to the system instructions for causing a computer to display the at least one structural element of the model on a display, transmitting to the system instructions for causing a computer to modify the appearance of the displayed at least one structural element by modifying a curvature of the element over a continuous portion of the element.

In general, in another aspect, the invention features a method for controlling a synthetic character using a control system that includes displaying the character engaged in an activity, receiving a first input from a user, determining whether the input is relevant to the activity, if the input is relevant to the activity, and showing the character react to the input, the character being highly reactive and having at least one of the following group of characteristics: appearing to be intelligent, exhibiting common sense, exhibiting social knowledge, exhibiting knowledge of social norms, having a specified personality.

In general, in another aspect, the invention features a system for controlling a synthetic character using a control system that includes means for displaying the character engaged in an activity, means for receiving a first input from a user, means for determining whether the input is relevant to the activity, and means for, if the input is relevant to the activity, showing the character react to the input, the character being highly reactive and having at least one of the following group of characteristics: appearing to be intelligent, exhibiting common sense, exhibiting social knowledge, exhibiting knowledge of social norms, having a specified personality.

In general, in another aspect, the invention features a computer software product, embedded on a computer readable medium, for controlling a synthetic character using a control system that includes instructions for causing a computer to display the character engaged in an activity, instructions for causing a computer to receive a first input from a user, instructions for causing a computer to determine whether the input is relevant to the activity, and instructions for causing a computer to, if the input is relevant to the activity, show the character react to the input, the character being highly reactive and having at least one of the following group of characteristics: appearing to be intelligent, exhibiting common sense, exhibiting social knowledge, exhibiting knowledge of social norms, having a specified personality.

In general, in another aspect, the invention features a method for transmitting to a system a computer software product, embedded on a computer readable medium, for controlling a synthetic character using a control system that includes transmitting to the system instructions for causing a computer to display the character engaged in an activity, transmitting to the system instructions for causing a computer to receive a first input from a user, transmitting to the system instructions for causing a computer to determine whether the input is relevant to the activity, and transmitting to the system instructions for causing a computer to, if the input is relevant to the activity, show the character react to the input, the character being highly reactive and having at least one of the following group of characteristics: appearing to be intelligent, exhibiting common sense, exhibiting social knowledge, exhibiting knowledge of social norms, having a specified personality.

In general, in another aspect, the invention features a method for controlling a synthetic character using a control system that includes displaying the character engaged in an activity and receiving an input from a user.

In general, in another aspect, the invention features a system for controlling a synthetic character using a control system that includes means for displaying the character engaged in an activity and means for receiving an input from a user.

In general, in another aspect, the invention features a computer software product, embedded on a computer readable medium, for controlling a synthetic character using a control system that includes instructions for causing a computer to display the character engaged in an activity and instructions for causing a computer to receive an input from a user.

In general, in another aspect, the invention features a method of transmitting to a system a computer software product for controlling a synthetic character using a control system that includes transmitting to the system instructions for causing a computer to display the character engaged in an activity and transmitting to the system instructions for causing a computer to receive an input from a user.

In general, in another aspect, the invention features a method for displaying a character on a display that includes receiving a specification of an action to be performed by the character, and generating movement for the character appropriate for the specification.

Other advantages and features will become apparent from the following description and from the claims.

FIG. 1 shows elements of an exemplary interactive character system.

FIG. 2 shows the certain structures in an exemplary interactive character system.

FIG. 3 shows a flowchart.

FIG. 4 shows an exemplary character mind.

FIG. 5 shows an exemplary active behavior tree.

FIG. 6 shows exemplary behaviors.

FIG. 7 shows an exemplary sequential behavior.

FIGS. 8-13 are flowcharts.

FIG. 14 shows elements of an exemplary interactive character system.

FIG. 15 shows an exemplary act queue.

FIG. 16 shows an exemplary act.

FIG. 17 illustrates the operation of an exemplary act generator.

FIGS. 18-19 show exemplary blend trees.

FIGS. 20-24 are flowcharts.

FIG. 25 shows elements of an exemplary interactive character system.

FIG. 26-28 show diagrams of exemplary morphing hoses.

FIG. 29 shows a screen image of an exemplary interactive character.

FIG. 30 shows a screen image of an exemplary interactive character in a simulated world.

FIG. 31 shows diagrams of exemplary morphing hoses.

FIG. 32 shows a screen image of an exemplary interactive character in a simulated world.

FIGS. 33-37 show screen images of exemplary interactive characters.

FIG. 38 shows a screen image of an exemplary interactive character in a simulated world.

FIG. 39 shows a screen image of an exemplary interactive character.

FIG. 40 shows elements of an exemplary content delivery system.

FIGS. 41-42 are flowcharts.

FIG. 43-44 show screen images of an exemplary interactive character in a simulated world.

Referring now to FIG. 1, an exemplary interactive media system 100 includes user input 105, an output display 110, and a processing engine 115. User input 105 may be any known or yet to be developed device for receiving user inputs in an information processing system, such as a computer keyboard, a mouse, a joystick, a telephone pad, a touch screen, a remote control handset, microphone, video camera, or the like. Output display 110 may be any known or yet to be developed device for displaying audio or visual information generated by an information processing system, including a computer monitor, a television monitor, a personal digital assistant screen, a handheld interactive game screen, loudspeakers, headphones, a telephone display, and the like.

Processing engine 115 may include any known or yet to be developed information processing system, including a stand alone personal computer, a dedicated handheld game system, a network of computers, a programmable telephone, a set top box, a game console, a digital TV system, or a personal digital assistant. Processing engine 115 may be connected via a local area network or a non-local network (e.g. a proprietary wide-area network, a cable network, or the Internet) 120 to one or more servers 125. Processing engine 115 may receive data (e.g., program instruction data or graphical data) from server 125 that includes information to be presented to a user. Processing engine 115 may also include an interactive character presentation module 135, which will be described in more detail below. Alternatively, or in addition, processing engine 115 may also include a browser system 130 (e.g. Netscape Navigator or Microsoft Internet Explorer, or other extensible clients such as the proposed “Presentation Engine” and “Execution Engine” of the OpenCable platform for interactive television). Browser system 130 may permit a user to access information contained on servers 125, and to cause such information (or information generated by downloaded program data) to be displayed on output 110. For example browser system 130 may permit a user to install interactive character presentation module 135 in processing engine 115 in response to a user command.

Referring now to FIG. 2, there is shown an exemplary interactive character presentation system 200 that permits the presentation of fully autonomous interactive characters that are highly expressive, highly reactive, appear to be intelligent, appear to have common sense, appear to have social knowledge, appear to have knowledge of social norms, and have a specified personality. Presentation system 200 includes a character mind 210, a motor and speech module (MSM) 220, a selective sensing module 230 and a simulated world 240. The character mind 210 represents the mind of a particular interactive character that will be presented to the user of media system 100. Although only a single character mind is shown in this embodiment, any number of such characters may optionally be included. It includes data structures and functionality representing the behaviors, goals and acts of the character and produces outputs that determine how the character will interact with the user and with other characters in a simulated environment.

MSM 220 includes routines for generating audiovisual sequences corresponding to particular acts or series of acts generated by the character mind. In particular, the character mind provides the motor and speech module with a series of physical acts (i.e., motions or speech acts) and the motor and speech module determines sequences of particular images or sounds that must be generated to make such acts appear to the user.

MSM 220 acts by modifying constructs in the simulated world 240, which is a model of a three dimensional world including a representation of the character\'s body 250. The simulated world also includes audio queues 260, which represent sounds that emanate from characters in the simulated world, and may also include a user body 270, a character body controlled by inputs from the user.

MSM 220 is aware of the state of the simulated world, and uses that information to determine if and how the world may be changed to implement a particular act requested by the character mind. The MSM provides feedback to the character mind by informing it that an act has failed (e.g., because it was physically impossible given the state of the world), or succeeded. It also informs the character mind when the act is about to end. The interaction between the character mind and the MSM will be described in more detail below.

Selective sensing module 230 monitors the state of simulated world and provides selected information about the simulated world (referred to here as “sense data”) back to the character mind 210. The character mind determines what information about the simulated world is monitored by activating or deactivating particular sensors within the selective sensing module.

The user generally does not interact directly with the character mind, but instead acts by controlling an avatar, the user body 270, using input devices 274 (part of user input 105) connected to user interface 276. As the avatar moves through the simulated world 240, its behavior may be sensed by the character mind 210 (through selective sensing module 230), and the behavior of the character may change accordingly. For example, the character may move toward or away from the avatar, change its expression when the avatar approaches, or attempt to speak to or about the avatar. Thus, the character will appear to the user to be believably responding to the user\'s avatar in the simulated world. In an alternate robotic or virtual reality embodiment, for example, the user may be interacting more directly with the character.

In a preferred embodiment, input to the interactive character system is through a computer mouse. However it will be appreciated that features of the character system described herein may be applied to any computer system for controlling interactive characters. For example, input devices 274 could include a keyboard, sonar receiver, camera, microphone or any other device that permits a computer to receive inputs from the user.

As noted above, audio queues 260 contain sounds that emanate from the environment. They are processed into sound waveforms by audio routines 280 and output through sound devices 282 (part of output display 110).

Also provided are display routines 290. Display routines receive the state of the simulated world and generate visual images representing that state. These images are then output to display devices 292 (part of output display 110).

In a preferred embodiment, display devices 292 includes a normal computer screen and sound devices 282 includes normal loudspeakers for sound. However, in alternative embodiments, display devices 292 and sound devices 282 could include an interactive robot, a virtual reality system, or any other device that permits a user to perceive the appearance of an interactive character.

Referring now to FIG. 3, the basic operation of the presentation system 200 is described. The presentation system 200 operates in an infinite loop 300 as shown. Each pass through the infinite loop results in the generation of one animated frame for output to the user.

The first step (310) is to update a simulated time counter for the presentation system. The entails incrementing a time variable representing the passage of time in the interactive character\'s world. The system clock is used to measure the real time that has elapsed since the last time through the loop. In general, this change in time is added to the simulated time (sometimes called “simtime”) to get the new simtime for this frame. Simtime is fixed throughout the frame. In the description of the interactive character, we refer to time or simtime interchangeably. Real world time is indicated explicitly when necessary.

In certain cases, simtime is updated in other ways. For example, if the real time elapsed is exceptionally long (perhaps from an external performance problem), then the simtime can be increased by a maximum frame duration. This allows the presentation to appear interrupted. Without such a technique, the character would appear to move discontinuously. Additionally, the system can run at fixed frame rates and in slow motion playback. These modes require simtime to be padded or calculated differently.

Next, the user interface is updated (step 320). In a preferred embodiment, the user interface is a mouse, which is used to control the user\'s avatar character. During the user interface update step, any movement of the mouse or mouse click is noted, and the position of the user\'s character in the simulated world is modified accordingly.

Next, the sensors are updated (step 330). This step executes all of the sensors that are currently on, and sends appropriate information from the sensors to the character mind. It does this by looping through the list of sensor instances and executing each in turn. In an embodiment with multiple characters, sensors for all of the characters would be run at this time.

Next, the character mind is run (step 340). Again, if there are multiple character minds, each of them is run sequentially. When a character mind is run, it is allotted a specific time budget specified in real world time, and generally the mind runs until the allotted time is expired or there are no available acts or goals to execute. The operation of the character mind will be described in more detail below. During operation of the character mind, the mind may determine that certain acts should be performed by the character body, or that certain acts potentially already in progress should be aborted. These decisions are communicated to the MSM during the character mind run time.

Next, the MSM is updated (step 350). As noted above, the MSM is responsible for carrying out the acts generated by the character mind. Acts may take one or more frames to complete, and may also be associated with pending acts that must complete before they can begin executing. Thus, during the MSM update step, the MSM determines what acts received from the character mind can begin executing, and begins to execute them. In addition, for any pending acts that commenced executing in a prior frame, the MSM causes those acts to continue executing for the time period of the current time frame.

The MSM performs an act by generating a sequence of instructions over time to animate a character\'s body and generate speech for the character. Thus, for each frame during which an act is being performed, the MSM generates those changes in the character\'s appearance or speech required to perform the portion of the act being completed during that frame.

When an act is about to end, has successfully completed or has failed, this information is communicated back to the character mind by the MSM. Such communication may re-activate the character mind during the “update MSM” step and cause it to take additional actions. In particular, it may cause the character mind to tell the MSM to abort other pending acts.

Next, the character\'s body is updated (step 360). Again, to the extent there are multiple interactive characters, this step would be performed for each of them. The character body receives instructions from the MSM indicating the changes in appearance for the current frame and modifies the representation of the character in the simulated world accordingly. Finally, play audio and draw routines are called (step 370). The draw routines redraw the character\'s body according to its current representation in the simulated world. The play audio routines play any sounds generated by the MSM.

After the play and audio draw routines are completed, the loop repeats. This occurs many times a second, causing a continuous interactive experience with one or more personality-rich interactive characters.

We now describe in more detail the structure and operation of an exemplary character mind 210. However the present invention is not limited to the particular exemplary character mind described. Accordingly, other character minds may be within the scope of the invention. For example, the character mind described in A. Bryan Loyall, Believable Agents: Building Interactive Personalities, Ph.D. Thesis, Technical Report CMU-CS-97-123, School of Computer Science, Carnegie Mellon University, Pittsburgh, Pa., May 1997 may be utilized in particular embodiments of the present invention.

Referring now to FIG. 4, the character mind 400 includes three main data structures: the active behavior tree (ABT) 410, the Behavior Library 420, and the Working Memory 430.

The ABT is a tree structure that represents the “mindset” of the character at any given time. The ABT includes three types of elements: goals, acts, and behaviors. These elements are arranged in an annotated tree that represents various relationships among these elements. Over time during system execution, this structure is changed in response to changes in the state of mind of the interactive character.

Generally speaking, a behavior element in the ABT corresponds to an abstract description of the behavior of a character. A behavior will typically include (as child nodes in the ABT), one or more goals or acts that are appropriate for carrying out the behavior. An act represents a specific change in the state of the character, and can be a physical act (e.g., involving motion of the character\'s body or speech by the character), or it can be a mental act (which merely involves changing the state of the character mind). A goal represents a state of the world that the character seeks to have occur. A goal may have as a child node a behavior that has been selected by the character to try to achieve the goal.

Generally, the root node of the ABT is a behavior representing the overall behavior of the interactive character. A behavior consists of a set of goals that the character will attempt to achieve, and acts that the character will attempt to perform. We refer to the goals and acts of a behavior as the “behavior steps” of the behavior. Referring now to FIG. 5, an exemplary ABT 500 is shown. In ABT 500 the root node behavior 510 has four goals 520, the third of which is “amuse self”. As shown, this example ABT includes several other goals (G) 530, behaviors (B) 540, and acts (A) 550, in alternating layers of behavior steps and behaviors.

The Behavior Library 420 is a set of behaviors that may be used by the character to achieve goals.

Given a particular goal, the Behavior Library will contain zero or more behaviors that can be added to the ABT to achieve the goal. This set of behaviors is typically built by the author of the interactive character prior to its execution. The library could also be extended during execution using machine learning or other techniques known to one skilled in the art.

Referring now to FIG. 6, in a preferred embodiment, there are three types of behaviors. A behavior may be sequential 600, or it may be a non-sequential behavior 610, which may in turn be either a concurrent behavior or a collection behavior. A sequential behavior is a sequence of goals or acts (collectively ” behavior steps“) that are performed in order. A concurrent behavior is a set of behavior steps that can be performed in any order, including being interleaved or having portions performed in parallel. In general, all behavior steps of a sequential or concurrent behavior must succeed in order for the behavior to succeed. A collection behavior is like a concurrent behavior in that it consists of a set of behavior steps that can be performed in any order, including being interleaved or having portions performed in parallel. However, a collection does not require all behavior steps of the behavior to succeed.

Elements of the ABT may include annotations that modify the way in which the element is interpreted by the character mind. There are two distinct types of annotations in the ABT. The first type is an annotation that is placed on a behavior step. This is sometimes referred to as a “step annotation”. The performance of behavior steps in a behavior can be modified by “step annotations” that are included in the behaviors. The second type is an annotation that is placed on the behavior itself. It is included as a part of the behavior and applies to the behavior as a whole. This is sometimes referred to as a “behavior annotation”.

One difference between the step annotations and behavior annotations is that a particular behavior step may have different annotations depending on its context (i.e., which behavior it is a part of). For example, the same goal appearing as a behavior step in two different behaviors could have different annotations. On the other hand, a behavior annotation is present whenever that behavior is used to achieve a goal, regardless of the context.

Referring now to FIG. 7, there is shown an exemplary sequential behavior 700. Sequential behavior 700 includes behavior annotations 710. Sequential behavior 700 also includes a sequence 720 of behavior steps 730. Each behavior step instance includes step annotations 740 that are specific to that instance of the behavior step. The use of annotations in a character mind is described in more detail below.

Referring again to FIG. 4, Working Memory 430 is a repository of data that is used to store elements of the state of the character mind. It consists of a set of Working Memory Elements (WMEs), which are utilized to store certain auxiliary information about the current state of the character mind. The operation of WMEs is described in more detail below. Like the ABT, the Working Memory is a structure that changes over time in response to changes in the state of the interactive character.

The state of the character mind is changed when the character mind is “run.” When the mind is “run” the mind examines its currently pending behaviors and attempts to perform acts or achieve goals that are appropriate to the behaviors. We describe the operation of a running character mind in more detail below. The basic operation is as follows. On every execution cycle the character mind chooses a leaf node of the ABT to execute. If the leaf node is a physical act, that act is passed to the MSM. If the leaf node is a mental act, it is executed. If the leaf node is a goal, then the character mind queries the Behavior Library for a behavior that can achieve the goal, and adds that behavior to the ABT underneath the selected goal\'s node. This process adds nodes to the ABT. Nodes are removed as the goals, physical acts, mental acts, and behaviors finish processing. This is described in more detail below.

During operation of the character mind, the mind continuously chooses the interactive character\'s next act based on, among others, perception, current goals, emotional state and aspects of internal state. A goal in a character mind may be thought of as an atomic name and a set of parameters that are instantiated when the goal becomes active, for example (tease <other>). Behaviors for these goals may be either ordered or unordered collections of subgoals, physical acts (i.e., acts resulting in audio or visual output display) and mental acts (i.e., changes in the state of the character mind that do not directly result in audio or visual output display) which can be used to accomplish the invoking goal. For example, one behavior for the above tease goal is the sequence of subgoals: (goto <other>), (greet <other>), (run-from <other>).

An item that is a goal, physical act or mental act is called a behavior step. Mental acts can also be grouped together and labeled atomic which causes them to be treated as a single, uninterruptible behavior step.

Each behavior in the character mind may be one of three types: a “sequential behavior,” a “concurrent behavior,” or a “collection behavior.” A sequential behavior represents a list of behavior steps to be performed in sequence. The behavior steps in a concurrent behavior or a collection behavior are not ordered, and may be performed in any order. In a concurrent behavior, all of the behavior steps must succeed for the behavior to succeed. In a collection behavior, the behavior succeeds once all of the behavior steps have been attempted, regardless of whether any succeed. Behaviors have associated with them testable preconditions that are true when the behavior is applicable for a goal in the current state of the world. Preconditions are “behavior annotations.” Multiple behaviors can be written for a given goal, with the character mind choosing between the behaviors at execution time. If a behavior fails, the character mind will attempt any alternate behaviors for the given goal, and thus perform a kind of backtracking search in the real world.

Multiple behaviors for a goal can be partially ordered by another type of “behavior annotation” called a specificity. A specificity annotation is an expression that evaluates to a number. Behaviors with higher specificity (i.e. a larger number) are preferred over those with lower specificity. The character mind uses these to choose more specific behaviors when multiple behaviors apply.

The character mind stores all active goals and behaviors in a structure called an active behavior tree (ABT). An example ABT is shown in FIG. 5. An ABT is a tree of alternating layers of behavior steps and behaviors. The second layer of the ABT (after the single root behavior node) is the collection of top-level behavior steps for the character. Typically, all of the top-level behavior steps are goals. A goal\'s child, if it has one, is the active behavior for that goal. A behavior\'s children are its component subgoals, physical acts and mental acts. The ABT changes during execution of the character mind: expanding as behaviors with their component subgoals are chosen for goals and added to the ABT, and shrinking as goals and behaviors succeed and fail and are removed from the ABT. Physical acts succeed or fail depending on their execution in the MSM. Mental acts always succeed. Goals succeed when a behavior for the goal succeeds, and fail if all of the applicable behaviors have failed. Behaviors succeed if all of the component behavior steps succeed and fail if any of the behavior steps fail (subject to the modifications of annotations and behavior types described below).

Each behavior in the ABT may have one or more annotations that provide the character mind with a basis for prioritizing and managing multiple goals. In particular, behavior steps are annotated with “step annotations” and the behaviors themselves may have “behavior annotations.”

One type of “step annotation” is called a success test. A success test is an arbitrary testable expression over the perceived state of the world and the internal state of the character mind. Success tests can be associated with any behavior step in a behavior. When a success test that is associated with a behavior step that is currently in the ABT becomes true, its associated behavior step is deemed to have been accomplished and thus no longer needs to be pursued. For example, the first behavior step of the tease behavior described above may have a success test associated with it to determine if the character is already near <other>. If this test is true when the behavior begins this behavior step, the goal (goto <other>) would be skipped. Also, if the character is in the process of going toward <other> when some external factor, such as <other> moving toward it, causes the test to be true, the success test would enable the character to recognize that the goal has succeeded and stop pursuing it.

Two additional “step annotations” are ignore failure and optional. Behavior steps marked with ignore-failure treat failure as success thus making the attempt of the behavior step enough for success. The optional annotation causes the marked behavior step to be irrelevant in determining the success of its parent behavior. The parent behavior then succeeds when all of its other behavior steps succeed regardless of whether the marked behavior step has been attempted. Optional annotations (not the behavior steps themselves) are ignored in sequential behaviors.

Collection or concurrent behaviors can have the “behavior annotation” number-needed-for-success. Normally all of a behavior\'s behavior steps must succeed for the behavior to succeed, or some of the behavior steps can be explicitly annotated as optional by using the annotation optional. This is not always desirable. There are cases, for example, where two behavior steps should be pursued concurrently, but if either one succeeds, the behavior should succeed. The optional annotation does not capture this expression because the author doesn\'t know ahead of time which behavior step will succeed and which will become optional. To capture this case, the annotation number-needed-for-success indicates how many of the behavior steps must succeed for the behavior to be considered to have succeeded.

This annotation specifies the number of behavior steps that must succeed (or succeed or fail in the case of a collection behavior) in order for the behavior to succeed. Behavior steps that are marked optional are not included in the count, so this annotation can be meaningfully combined with optional. For example a behavior could be written with two optional goals and three other goals with a number-needed-for-success annotation with value two. The character mind would pursue all five goals concurrently, and the behavior would succeed whenever two of the three goals not marked optional succeed.

A context condition is an annotation that can be either a “step annotation” or a “behavior annotation”. Like a success test, a context condition is an arbitrary testable expression over the perceived state of the world and the internal state of the character mind. When a “behavior annotation” context condition for a behavior that is in the ABT becomes false, its associated behavior is deemed no longer applicable in the current state of the world. That behavior fails and a new behavior must be chosen to accomplish the invoking goal. When a “step annotation” context condition becomes false, the behavior step fails.

As an example of a “behavior annotation” context condition, consider a character that is involved in a cooperative game where the point of the game is to keep the ball in the air, and where the character is currently pursuing a goal to hit the ball. One behavior for this goal is to hit the ball by flicking the character\'s head from a standing position. This behavior has a “behavior annotation” context condition that becomes false if the ball goes below the height of the chest of the character. This context condition recognizes when the associated behavior is no longer appropriate because the ball is in a position in which it cannot be hit using this method. This causes the behavior to fail, and allows other behaviors for this goal to be chosen such as one to hit the ball with a lower part of the character body.

Success tests and context conditions can themselves be annotated with behaviors to execute when they fire. So, in addition to modifying the ABT, the success due to a success-test and failure due to a context condition can also result in other behaviors of any type. In particular, a success test or context condition may trigger a behavior to record information about the success or failure of the goal for emotion processing as described below.

Every behavior step can have a priority modifier expression. This is a type of “step annotation.” If present, the modifier value is added to the priority of the parent to calculate the priority of the behavior step. If the modifier is not present, the behavior step inherits the value of the parent\'s priority. A behavior step\'s priority is used by the character mind when choosing which behavior step to execute.

In addition, goals can have either or both of two importance expressions (importance-of-success, the emotional significance of a goal succeeding, and importance-of-failure, the emotional significance of a goal failing), used by the emotion system when considering the significance of the goal. Both of these expressions evaluate to an integer zero or greater, and if either of these expressions is omitted, one is automatically inserted with value zero. These are “step annotations” (assigned to instances of behavior steps rather than to behaviors), because identical behavior steps could have different priority or emotional importance depending on the context in which they arise. For example, the goal of going to an area as a subgoal to a run away goal would typically have a higher priority than the same goal in pursuit of an exploration goal.

Certain behaviors may include a special type of behavior step called pause that is never chosen by the step arbiter. Thus, when present in a sequential behavior it suspends that behavior until removed. It can be removed by an associated success test becoming true, or by success or failure of one of its ancestors in the tree. Arbitrary demons can be encoded using a pause behavior step. The structure of such a demon is a sequential behavior whose first behavior step is a pause behavior step with a success test. The success test contains the firing condition of the demon, and the second and later behavior steps of the behavior contain the body of the demon.

Any behavior step can be annotated as persistent with respect to success, failure or both. A behavior step so marked remains in the ABT upon success or failure rather than being removed, and is reset so that it is again available to be pursued. These are of course “step annotations.”

A goal in a behavior can be annotated with a “step annotation” that is not predefined, but instead specified by an arbitrary name and value. The value associated with this annotation can be modified over time. These customizable annotations can be useful, for instance, when creating emotions based on the likely success or failure of goals.

For example, a character has an important goal (“G”) that has an annotation called “CharacterThreateningThisGoal” that is initially set to the value “no character.” When the character\'s behavior computes that “G” is likely to fail because of the actions of another character (“B”), the value associated with the annotation can be set to “B”. If later another character (“C”) threatens the goal, the value can be updated. This specific information allows the character\'s emotion system to notice that “G” is threatened and to generate a fear response directed at the appropriate character.

The mind executes by first modifying the ABT based on changes in the world: behavior steps whose success tests are true and behaviors or behavior steps whose context conditions are false are removed along with any subordinate subgoals or behaviors. (One exception to this is that some subordinate acts may not be removable, e.g., because they are in the middle of executing. Processing of these non-removable acts is described later.) Next, one of the leaf behavior steps is chosen. This choice is made by a step arbiter that prefers high priority behavior steps and, among behavior steps of equal priority, prefers continuing the most recent line of expansion. If there is more than one behavior step that could be chosen using this mechanism, the step arbiter chooses randomly between them. If the chosen behavior step is a primitive mental act, its code is executed. If it is a physical act, it is sent to the motor and speech module to be executed. Note: if a physical act is currently executing, it will not be chosen for execution again. Otherwise, the behavior library is indexed and the behavior arbiter chooses one behavior for the goal from among those whose preconditions are true. The behavior arbiter will not choose behaviors which have already failed to achieve this goal instance, and prefers more specific behaviors over less specific ones using the specificity annotation. If there is more than one behavior that is valid to be chosen, the behavior arbiter chooses randomly between them. The chosen behavior and its component behavior steps are added to the ABT, and the execution loop repeats.

A collection behavior is the same as a concurrent behavior with all of its behavior steps annotated as ignore-failure. This allows a collection of behavior steps to run concurrently without their failure affecting each other.

We now describe some derived expressions that may be useful in defining behavior steps in a behavior. These derived expressions can each occur as a behavior step of a behavior with the specified derived meaning. A one-of expression allows the expression of multiple ways of attempting something inline in the body of an expression. The meaning of this expression is the same as if a new goal name is created, each clause of the one-of expression is expanded into a separate behavior for that new goal name, and the one-of expression is replaced by an invocation of the created goal name. Each clause of a one-of expression can include a precondition and/or specificity. If these are present in the clause, the meaning is the same as if the behavior created for this clause had the same precondition and/or specificity as a “behavior annotation”. Other derived constructs include inline sequencing, concurrent and collection constructs. These can each be expressed in terms as a derived construct in which a new subgoal is created with a single created behavior of the appropriate type

To respond to the challenges of a real-time, animated domain, a preferred embodiment of the character mind may have the following features: (1) parallel execution of multiple acts and goals, (2) early production of next acts to allow smooth animation, (3) automatic management of selective sensors, and (4) incremental evaluation of the continuously monitored conditions. We now describe particular exemplary embodiments of these features in more detail.

For interactive characters to appear alive, it is desirable that they be able to do more than one thing at a time. As described above, a character mind may hold multiple parallel goals (or other types of behavior steps) through the top-level parallel set of behavior steps and through parallel behaviors that arise during execution. The character mind manages these multiple behavior steps by concentrating on the most critical of them according to its arbitration mechanism, and for the most part only attends to other behavior steps after the current behavior step completes or as events trigger demons.

In addition to this, all of an interactive character\'s active behavior steps can be attended to in a character mind, potentially producing multiple acts or performing concurrent cognitive processing. One approach to managing multiple acts is a so-called “greedy” approach that entails attending to the most critical behavior steps first and mixing in others as time allows. In each decision cycle the character mind chooses the most critical of the available leaf behavior steps. This thread of behavior is attended to until it is interrupted, or it becomes suspended. For example, when a jump act in a sequential behavior is sent to the MSM to be executed, the behavior cannot continue (and therefore is suspended) until the act completes. When a thread is suspended the character mind uses the available processing time (for example, approximately 1200 milliseconds of real time in the case of a 1.2 second jump act) to attend to the other, perhaps unrelated, available behavior steps. A thread of behavior may also be suspended if its current behavior step is the special form pause or if its current behavior step is incompatible with a more critical executing thread.

This notion of incompatible behavior steps deserves further comment. Two acts are considered incompatible if they use the same character body resources. For example the jump and slide acts both use the character body translate-x, translate-y and translate-z resources to move the character body\'s location and so cannot execute simultaneously. Similarly, goals can be incompatible with other goals or with acts. These goal incompatibilities exist independently of any primitive act resource conflict. For example, while sleeping the primitive acts being executed are rather sparse and do not by themselves preclude concurrently executing other primitive acts. In most characters, however, the goal of sleeping is incompatible with acts or goals that significantly move the character body.

A character mind includes specifications of pairs of behavior steps that are incompatible. This is done using a defconflict construct, e.g. (defconflict sleep jump) where sleep is the name of a goal and jump is the name of an act. During processing, the character mind will not pursue two incompatible behavior steps at the same time. The more critical one is pursued while the other is temporarily suspended.

Coordination with the MSM

The character mind and the MSM work in concert to produce the character\'s behavior. As described above, the mind keeps track of which acts are currently executing and which acts are physically incompatible with which. This allows the mind to make sure no incompatible acts are issued. Instead, the character mind will delay executing one act until the conflicting one is done. It chooses which to issue and which to delay using the step arbiter and the update suspension step in the RunMind algorithm. In some cases this will mean that the character mind will need to abort an executing act in order to issue a more pressing act. If that act turns out to be unabortable (e.g., a jump in mid-air) then the character mind will wait to issue the more pressing act. Once an act has been aborted to allow a more pressing act to execute, it can be reissued once the conflicting act is done.

To allow the MSM to provide smooth motion, the character mind attempts to provide the next act for each thread before the current act finishes. If notified by the MSM that a particular act is about to end, the character mind assumes that the act will complete successfully. This success is propagated through the ABT in the normal way. The character mind then can use the time before the act actually completes to compute the next act along that thread. If an act is produced, it is sent to the MSM with the instruction that it be executed after the current act actually completes, and after any other executing acts that conflict with it or that are before it in a sequential behavior. All of the character mind\'s reactive mechanisms apply to these pending acts as well as to normal execution of the character mind, so in the event that the character mind chooses to abort a pending act, a message is sent to the MSM and it is removed.

Of course, if the character mind is currently attending to something more critical than this thread, it will continue to be attended to and the next act in this thread will likely not be computed.

It is desirable that sensing in a real-time, animated world must be efficient. To this end, the character mind deploys task-specific sensors which can be turned on or off as needed. Each sensor observes a low-level aspect of the simulated world and notifies the mind when that aspect\'s value changes. Typical sensors are “can I see character X jumping” and “what is the position of character X”. The aspects of the world which must be known to evaluate a character mind\'s preconditions, success tests and context conditions are noted when these conditions are written by associating a list of sensors for each condition. The character mind manages the sensors by turning them on and off when appropriate. As a leaf subgoal is chosen to be executed, sensors needed to evaluate the preconditions for that goal\'s behaviors are turned on, and then turned off again after a behavior is chosen. Likewise, when a particular goal or behavior is present in the ABT, the sensors relevant to evaluating any success tests or context conditions are turned on. When that goal or behavior is removed from the tree because of success, failure or irrelevance, the sensors are turned off. Because the same sensor may be needed for several different conditions at a time, the sensors are shared and reference counted (i.e., the number of references by a character mind to a particular sensor is counted, and the sensor is not deactivated unless the reference count reaches zero)

Typically a character mind has a number of continuously monitored conditions (context conditions and success tests) active at any given time. For efficiency, context conditions and success tests may be implemented in a character mind using the well-known RETE incremental matching technology. RETE is described, for example, in Charles L. Forgy. Rete: A fast algorithm for the many pattern/many object pattern match problem. Artificial Intelligence 19(1): 17-37. For consistency, preconditions may also be implemented as RETE match expressions in a preferred embodiment. Any information that is to be matched upon must be put into working memory elements (WMEs) of the RETE network. In the preferred embodiment, this includes information provided by sensing, as well as information provided by the reflection mechanism.

For ease of implementation in RETE, context conditions may be expressed as fail-when expressions. A fail-when expression encodes the condition under which the associated behavior should be removed rather than the conditions under which it should not be removed. I.e. for any given fail-when condition expression e, the equivalent context condition expression is (not e).

A desirable feature of a character mind is the ability to perform “reflection.” The term “reflection” refers to the ability of the character mind to reason about its own state and progress. In a character mind, reflection may be accomplished by creating WMEs for certain goals or acts. These WMEs contain information about these goals or acts, and can be matched using an RETE. Typically, they include the name and arguments of the goal, as well as goal status such as: available for execution, executing, suspended, succeeded, failed, or aborted. Thus, changes in the character mind\'s own state can satisfy conditions in much the same way that changes in the simulated world (reported to the mind by sensors) would do so.

WMEs are created automatically for every act in the ABT. However, WMEs are not created automatically for every goal in the ABT. These are created only for goals annotated with non-zero importances (importance-of-failure or importance-of-success) or annotated explicitly with the reflection annotation.

In addition to producing specific acts in a character, behaviors may also be used to represent high level sensing and emotional activity in a character mind.

As noted above, the task-specific sensors provide sensory information at a low level, including primitive act events. However, it is desirable that interactive characters be able to recognize abstract composites of this sensory information. For example, the author of a character might design the character mind to recognize that other characters (including the user avatar) are fighting, playing games or moping. Thus a character mind may have one or more behaviors that serve as high-level recognizers that recognize such high level behavior using inputs from low-level sensors in the selective sensing module. High-level recognizers are also called composite sensors. The composite sensors use parallel and sequential behaviors, combined with success tests, context conditions, mental acts, etc. to actively look for patterns in the sensor data as they are perceived. For example, a composite sensor might infer that a character is trying to annoy another because over time the first is staying very close and performing quick, jerky motions, even though the second is trying to move away.

As described below, a character\'s emotion system may also be implemented using behaviors. Emotions are thus managed by the character mind as some of the multiple threads of behavior, with the character mind attending to several of them simultaneously when the time available to think allows, or otherwise only attending to the ones most critical to this character mind.

One important aspect of the character mind that enables the creation of emotions and other high-level functions of mind is the ability of behaviors to reflect on the state and processing of the rest of the mind. This includes the ability to reason about the character\'s goals, their parameters, and their execution status (e.g., executing, succeeded, failed, etc.).

To make this approach concrete, consider a specific example sensor: one to recognize a threat from another interactive character or a character controlled by a human user. For this example, imagine a type of threat that is similar to a physical threat in the real world. The interactive character A has a notion of personal space, and invasion of that space causes uneasiness. Another character making quick movements toward A can be viewed as threatening A, especially if the movements are made within A′s personal space. In this example, imagine characters have a particular body motion that is used for threatening, called a puff. A puff is modeled after the way animals make themselves look larger to the entity they are threatening, for example, the way a cobra spreads its hood, a cat arches its back, or a human puffs out its chest. Of course, in general these social conventions are subject to each interactive character\'s interpretation, and misinterpretations do happen.

Since an interactive character may be concerned will the well being of other characters as well as itself, interactive characters may need to be able to recognize both when it or when other characters are being threatened. Although a character mind could be programmed to directly access the ABT of other interactive characters to determine when they are engaged in threatening behavior, such a technique would not work if a character controlled by the user (e.g., the user\'s avatar), is one of the characters that may engage in such behavior. Therefore, it is desirable for a character mind to be able to interpret the actual behavior of other characters to determine what is happening in the simulated world.

The following pseudo-code shows how such behaviors might be designed to recognize threatening behavior among characters in a simulated world. Four behaviors are provided. The first, recognize_threat, ultimately determines whether a threat has occurred to a particular character. It operates by first recognizing that that character\'s personal space has been invaded by another character. When this occurs, recognize_threat triggers as a subgoal the behavior verify_threaten. Verify_threaten succeeds when either the attacker puffs to the threatened character, or when three quick acts are made by the attacker in the vicinity of the victim in less than a minute. Verify_threaten uses the behaviors recognize_puff and recognize_quick_act as subgoals to make these determinations.

 (1) (sequential_behavior recognize_threaten (victim)  (2) (locals (aggressor unbound))  (3) (with (success_test someone is within $$personal_distance of $$victim and  (4) $$victim can see someone;  (5) set $$aggressor to someone)

Download full PDF for full patent description/claims.




You can also Monitor Keywords and Search for tracking patents relating to this Interactive character system patent application.

Patent Applications in related categories:

20130117131 - Method of and system for inserting/overlaying markers, data packets and objects relative to viewable content and enabling live social networking, n-dimensional virtual environments and/or other value derivable from the content - A method by which a User can associate selectable Markers, Data Packets and/or Objects with Content. The Content may generally be distributed electronically, and the Markers allow for insertion and/or overlay of Objects when the Content is selected for viewing by a Viewer. Objects and Data Packets are generally provided ...

20130117132 - System for inserting services in a software application - A system for inserting one or more services within a software application is provided. The system comprises memory circuitry configured to receive and store a software application and a service module. The software application is defined by a first set of instructions and the service module defined by a second ...

20130117133 - Systems and methods for rapid ad creation, including batch-ads, using a compatible mobile device, for an online marketplace - This invention details systems and methods for users in an online marketplace to easily enter one or more items using a smartphone or other compatible mobile device, then uploading the newly entered item(s) in a batch upload process directly onto the online marketplace. One aspect of the invention describes the ...


###


Other recent patent applications listed under the agent Fish & Richardson P.C. (bo):