Front-end device independence for natural interaction platform

[0001] This application claims the benefit of U.S. Provisional Application No. 60/342,231, filed 20 Dec. 2001, which is incorporated herein by reference in its entirety.

[0002] Computer program listings and Table appendices comprising duplicate copies of a compact disc, named “DEJI 1008-2 CPLA,” accompany this application and are incorporated by reference. The appendices include the following files:

[0003]

CD-Agent.java.txt	14,359	created
	bytes	Jul. 15, 2002
CD-EmailIOMode.java.txt	36,701	created
	bytes	Jul. 15, 2002
CD-InteractionAgent.java.txt	10,618	created
	bytes	Jul. 15, 2002
CD-InteractionListener.java.txt	1,101	created
	bytes	Jul. 15, 2002
CD-InteractionMessage.java.txt	2,132	created
	bytes	Jul. 15, 2002
CD-InteractionResultMessage.java.txt	2,102	created
	bytes	Jul. 15, 2002
CD-IOFormat.java.txt	2,252	created
	bytes	Jul. 15, 2002
CD-IOMode.java.txt	22,021	created
	bytes	Jul. 15, 2002
CD-MessageContent.java.txt	5,384	created
	bytes	Jul. 15, 2002
CD-NaturalInteractionComponent.java.txt	3,313	created
	bytes	Jul. 15, 2002
CD-NaturalInteractionRemoteObject.java.txt	8,949	created
	bytes	Jul. 15, 2002
CD-opal.txt	286,080	created
	bytes	Jul. 15, 2002
CD-StandardAgent.java.txt	107,906	created
	bytes	Jul. 15, 2002
CD-SystemIOMode.java.txt	4,482	created
	bytes	Jul. 15, 2002
CD-TextIOFormat.java.txt	4,103	created
	bytes	Jul. 15, 2002
CD-WebIOMode.java.txt	9,048	created
	bytes	Jul. 15, 2002
CD-XmlIOFormat.java.txt	3,706	created
	bytes	Jul. 15, 2002

[0004] A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the U.S. Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.

[0005] The invention relates to natural language interpretation systems, and more particularly to techniques for supporting natural user interaction with a back-end application via different kinds of I/O modalities.

[0006] U.S. Pat. No. 6,144,989, incorporated by reference herein, describes an adaptive agent oriented software architecture (AAOSA), in which an agent network is developed for the purpose of interpreting user input as commands and inquiries for a back-end application, such as an audiovisual system or a financial reporting system. User input is provided to the natural language interpreter in a predefined format, such as a sequence of tokens, often in the form of text words and other indicators. The interpreter sometimes needs to interact with the user in order to make an accurate interpretation, and it can do so by outputting to the user an inquiry or request for clarification. In addition, the back-end application also needs to be able to provide output to the user, such as responses to the user's commands, or other output initiated by the application. AAOSA is one example of a natural language interpreter; another example is Nuance Communications' Nuance Version 8 (“Say Anything”) product, described in Nuance Communications, “Developing Flexible Say Anything Grammars, Nuance Speech University Student Guide” (2001), incorporated herein by reference.

[0007] In the past, many natural language interpretation engines were designed to communicate with the user via a specific, predefined I/O modality. For example, some systems were designed to receive user input via a computer keyboard and to output results and clarification requests via a display monitor attached to the same computer as the keyboard. Other systems were designed to receive user input via a microphone and speech recognition software, and to provide output back to the user via text-to-speech software. Still other systems were designed to communicate with a user bidirectionally via the Web. Some systems were designed to support more than one I/O modality, but even then, the communication modalities were designed into the interaction system as a single unit.

[0008] Built-in communication mechanisms was problematical because, among other things, it was often necessary to re-program parts of the natural language interface whenever it was desired to support a new or different I/O modality. In addition, as the interface was reprogrammed to support new I/O modalities, it was difficult to maintain a consistent user feel for the application. A consistent user feel for a back-end application would afford a comfort level to the user, with both the application and the natural interaction platform, thereby increasing productivity and shortening the user learning curve.

[0009] Roughly described, the invention addresses the above problems by separating a user interaction subsystem from the natural language interpretation system. A user interaction subsystem can include an interaction block that is specific to a particular I/O modality and user device, and which converts user input received from that device into a device-independent form for providing to the natural language interpretation system. The user interaction subsystem also can take results from a back-end application in a device-independent form, and clarification requests and other dialoguing from the natural language interpretation system, and convert it to the appropriate format specific to the particular I/O modality and device. In this way all of the development for generating a natural language interpretation system optimized for a particular back-end application can be re-used for different I/O modalities and devices simply by substituting in a different interaction block into the user interaction subsystem. Similarly, all of the complications of interacting with particular modalities also can be concentrated in one module that is separate from the module(s) performing the natural language interpretation tasks.

[0010] In an embodiment, an interaction block includes an VO mode object that is specific to a particular I/O modality, and an I/O formatting object that is specific to the layout requirements of a particular I/O device. In an embodiment, the user interaction subsystem simultaneously supports more than one I/O device, such as by running several simultaneous instantiations of the I/O mode class for a particular modality, each referencing its own respective I/O Formatter object.

[0011] The following description, the drawings, and the claims further set forth these and other aspects, objects, features, and advantages of the invention.

1. System Overview

[0018] FIG. 1 is a functional block diagram overview of a system 100 incorporating invention. It includes one or more natural language interpreters (NLIs) 110-1 . . . 110-m (illustratively 110) running under one or more Java virtual machines (JVM's), which can themselves be running on one or more different processors. Each natural language interpreter 110 communicates bidirectionally with a user 112 via an interaction subsystem 114. It receives commands from the user 112 via the interaction subsystem 114, and in some embodiments and in some situations, it can also generate replies back to the user 112 such as for requesting clarification or continuation of the user's input. The purpose of the natural language interpreter 110 is to attempt to discern the intent of the user 112 as evidenced by the input, and to generate actuation strings toward a back-end application subsystem 116 that describe the functionality that the user is requesting. If the back-end application subsystem 116 has a response, or if it desires to communicate with the user 112 on its own initiative, it transmits its communication back to the user 112 via the I/O subsystem 114. As used herein, user input can include input of all kinds, including commands, queries, inquiries, and so on. All of these terms are used interchangeably herein.

[0019] The interaction subsystem 114 includes one or more interaction blocks 118-1 . . . 118-n (illustratively 118). Each Interaction block 118 receives input from a user 112 via a different modality or I/O device and translates it into a device-independent form for use by the natural language interpreter 110. The interaction block 118 also receives output from the natural language interpreter 110 and/or the application subsystem 116, in a device independent form, and converts it to the appropriate form for presentation to the user 112 via the specific modality and device of the particular interaction block 118. As used herein, modalities are distinguished by the transport mechanism via which the interaction blocks communicate with the user 112. E-mail, World Wide Web, SMS, local computer console, and so on, are considered different modalities. I/O devices, the other hand, are distinguished by the layouts and amount of space available on the device for communicating with the user. PDAs, desktop computer consoles, and voice communication devices, for example, are considered different I/O devices. A single modality might be used to communicate with more than one kind of device. For example, e-mail transport might be used to communicate with desktop computer e-mail systems and also a PDA e-mail systems. The layout requirements of each of these devices might be very different even though the transport mechanism from the viewpoint of the interaction block 118 might be the same. On the other hand, multiple modalities might be used to communicate with a single kind of device. For example, the system 100 might communicate with a desktop computer device via e-mail, the Web, or via direct local computer console reading and writing. The layout requirements might be similar regardless of the transport mechanism used by the system 100 to reach the device, although the interaction block 118 must reach the device via different transport mechanisms. Typically (but not essentially) a different interaction block 118 is required for each combination of modality and I/O device. As used herein, an I/O agency is the combination of an I/O modality and an I/O device.

[0020] The system 100 runs on a Natural Interaction Platform that includes natural language interpreters 110, parts of the application subsystem 116, interaction agents 122, and interaction blocks 118, and also one or more interaction servers 120. Each instance of these components executes inside its own JVM, communicating with each other through RMI (Remote Method Invocation). Alternatively, in various installations some or all of the various components can execute together inside a single JVM.

[0021] The servers and components of the platform can be created or restarted independently with no particular sequence required. The I/O and interpretation components are launched with their RMI addresses and the RMI address of one or more interaction servers specified in the program argument list. The interaction servers 120 are launched with their RMI address and “Opal” configuration file specified in the argument list.

[0022] When an I/O or interpretation component is launched it binds itself to the RMI registry and starts a thread (PingServer) to check the state of servers 120 specified in the launch parameters. If a server 120 is available, the thread immediately registers the component with the server. If no server is available, then the thread periodically checks for an available server. When it finds one it will register the remote object component with the server. When an interaction server 120 is launched, it binds itself to the RMI registry and waits for remote components to register themselves. When a component registers, the server 120 creates a remote object property class (IOModeProperties for interaction blocks 118 and InterpretationNetworkProperties for natural language interpreters 110) that it stores to track and administer the components. This class starts a thread (PingRemoteObject) that periodically checks the existence of the remote object so that it can unregister the object from the server 120 if the object process terminates.

[0023] The remote components invoke methods in the interaction server through a NaturalInteractionServerInterface. These methods include mechanisms whereby components can register themselves with the server 120 and interaction blocks can request new interpretation sessions and register existing sessions. The interaction server 120 invokes methods in the I/O components through an IOModeInterface. The interaction server 120 and I/O components invoke methods in the interpretation components, including requests by the interaction blocks 118 for natural language interpretations, through an InterpretationNetworkInterface.

[0024] The interaction server 120 therefore manages the sessions with which an interaction block 118 works with a natural language interpreter 110. When an interaction block 118 receives input from a new user, it requests an interpretation session from the interaction server 120 with which the interaction block 118 is registered. The interaction block 118 can recognize a new user by methods that depend on the I/O modality, such as by email address for email modalities, phone number for SMS modalities, or HTTPSessionID for web modalities. The interaction server 120 accesses a user database 124 to validate the user and retrieve any required login information and session information for the back-end application subsystem 116, and then assigns a unique ID for the requested interpretation session. The interaction server 120 returns to the interaction block 118 with the interpretation session ID, the application login information and (in embodiments that support more than one natural language interpreter instantiation) an identification of an interaction agent 122 (discussed below) to which the interaction block 118 should route the user's requests. The interaction block 118 stores this information in a TimedHashtable and uses it to forward queries into the assigned natural language interpreter 110 originating from the particular user.

[0025] The system 100 is designed to recover automatically if any one of the processes fails, so long as there is at least one more instance of that process still running. If a natural language interpreter 110 fails, then any interaction block 118 that has a user assigned to that interpreter 110 will receive a remote exception when it tries to forward a user query to the interpreter 110. At this point the interaction block 118 returns to the interaction server, requests a new interpretation session, and submits the query to the new interpreter 110 assigned. If an interaction server 120 fails, pinging threads in the remote object components will detect this and try to register with another interaction server 120 or wait for a new one to be started. If an interaction block 118 fails, then it is up to the application subsystem 116 to detect this and route its output via other available I/O components.

2. Natural Language Interpreter

[0026] The natural language interpreter 110 can be any functional unit that attempts to discern from user input, the intent of the user relative to the back-end application. It receives commands from the user 112 (via the I/O subsystem 114), and outputs toward the back-end application subsystem 116 an indication of the function or functions that the NLI believes the user intends. Many NLIs operate in part by attempting to spot concepts in an incoming token sequence, typically by reference to specific keywords or classes of keywords. Some of the keywords are the concepts themselves (like “Monday” in the phrase, “I'll be there on Monday”), and some of the keywords are indicators of where the concept is likely to appear (like “on” in the same phrase). The NLI 110 can include, for example, Nuance Commumications' Nuance Version 8 (“Say Anything”) product or an AAOSA agent network from Dejima, Inc.

[0027] In an AAOSA agent network, agents contain policy conditions which either do or do not apply to the incoming text string, and if they do, they make a claim to at least a portion of the incoming text string. Such claims imply a tentative interpretation of part or all of the input string. For example, if the back-end application subsystem 116 includes an airline reservation system, then an agent network in NLI 110 might be designed to include policy conditions to look for any of the words “depart”, “departing” or “leaving”, earlier in the text string than the word “from”, which in turn is earlier in the text string than a city name.

[0028] FIG. 2 is a diagram of an example AAOSA agent network 202, used for implementing a natural language interface to a back-end application that is designed for financial reporting. In particular, the back-end application in this example is an Internet-queryable database provided by EDGAR Online, Inc. More information about the database can be found at http://www.finsight.com, visited Feb. 5, 2002, and incorporated herein by reference. This product permits a web client to retrieve desired financial information automatically using URL-based queries. The interface to this back-end application, therefore, includes the formulation of the appropriate URL for satisfying the user's inquiry.

[0029] Only a partial representation of the agent network 202 appears in FIG. 2. A more complete version of the network is described in the Opal file named CD-opal.txt in the accompanying Computer Program Listing and Table Appendices. An Opal file is an XML document which defines certain properties of each of the agents in an agent network. The agents themselves are implemented as instances of java classes and subclasses, and the Opal file specifies, for each agent and among other things, the specific class or subclasses from which the agent is to be instantiated, which other agents each particular agent listens to for each particular kind of message, as well as (for most agents) a set of one or more “interpretation policies” which implement the interpretation task for which the particular agent is responsible. The Opal file is used by an Opal converter program at system startup time to instantiate the entire agent network such as network 202. The Opal file in CD-opal.txt can be understood by a person of ordinary skill, especially with the assistance of the Dejima Policy Reference, Platform 3.0, a copy of which is attached hereto in Appendix A. In addition, it will be understood that the Opal file uses standard XML coding, in which (among other things):

[0030]

![CDATA[ . . . ]]	indicates that “ . . . ” is to be interpreted as Character
	data;
&letter;	means “<” (left angle bracket)
&gt;	means “>” (right angle bracket)
&amp;	means “&” (ampersand)
&apos;	means “'” (apostrophe)
&quot;	means “ ” (quotation mark)

[0031] As described in the Dejima policy reference, an interpretation policy contains, among other things, a policy condition and a policy action. When an agent receives a message from another agent to attempt to interpret and input string, it compares the input string to each of the agent's policy conditions in sequence. If a condition does apply to the input string, or to part of the input string, then the policy makes a “claim” on the applicable portion of the input string, and returns the claim to the agent that requested the interpretation. A claim identifies (among other things) the agent and policy which is making the claim, the portion of the input string to which the claim applies (called the claim “focus”), the priority number of the agent or policy, and also a confidence level which indicates how well the input matches the policy condition. The priority and confidence levels, and the focus, all can be used subsequently by upchain agents for comparison with other claims made by other downchain agents, so as to permit the upchain agent to select a “best” one among competing claims.

[0032] Policy conditions are written as expressions made up from operators and operands. The various operators include unary operators such as <exists>, <exact>, <substring>, <accent>, <accent-substring>, REPEAT and RECURSIVE. They also include binary operators such as OR, AND, ORDERED, ADJACENT and COMBO. The operands on which an operator can act include tokens (words, strings, numbers, symbols, delimiters), text files (which can contain their own policy conditions), databases, and claims made by other policies. If a first policy condition (the “referencing policy condition”) refers to a second policy (the “referenced policy”) previously evaluated in the same agent, then any claim made by the referenced policy can be figured into the evaluation of the referencing policy condition in the manner specified by the operators. If a policy condition refers to another agent (the “referenced agent”) downchain of the current agent (the “referring agent”), then the claim or claims returned by the referenced downchain agent are figured into the evaluation of the referencing policy condition in the manner specified by the operators. Note that a policy condition that references a downchain agent cannot be completely resolved until the input string is passed to that other agent for comparing to its own policy conditions. In one embodiment, the referencing agent passes the input string to each downchain agent only upon encountering the agent's name while evaluating a policy condition. In the present embodiment, however, the referencing agent passes the input string to all downchain agents mentioned in any policy condition in the referencing agent, before the referencing agent begins evaluating even its first policy condition.

[0033] Returning to FIG. 2, loading of the interpretation network is initiated by the interaction server 120 when it is initialized. The interaction server has the knowledge of which network (opal file) the system is using, and when this value is initialized or changed the server 120 tells all interpretation systems to load this network. The system then reads the Opal file (such as that in CD-opal.txt) and instantiates all of the agents designated therein. This includes the interaction agent 122, discussed below. Subsequently, when an input token sequence is ready, the I/O mode object 126 passes it to the interpretation network 202 by calling the Process method of an Interaction agent 122. Whenever the Interaction agent 122 receives a token string, it initiates an interpretation attempt into the agent network by communicating the input token sequence, in an object of class “InitiateInterpretationMessage”, to the Top agent of the network. In the network of FIG. 2, the Top agent is System agent 212. The Top agent contains one or more interpretation policies whose policy conditions, in a typical network, do very little aside from referencing one or more other agents deeper in the network. System agent 212, for example, contains a single interpretation policy whose policy condition does nothing more than reference the Finance agent 214. Such a policy condition applies to the input token string if and only if the Finance agent can make a claim to at least part of the input token string. When System agent 212 encounters this policy condition, therefore, it forwards the input token string to the Finance agent 214 in an object of class “IntepretItMessage”. The Finance agent 214 is thus considered to be “downchain” of the System agent 212, and the System agent 212 is considered to be “upchain” of the Finance agent 214.

[0034] When the Finance agent 214 receives the input token sequence, it first looks in its policies for policy conditions that make reference to further agents downchain of the Finance agent 214. If there are any, then the Finance agent 214 forwards the input token string to each of the further downchain agents in an “IntepretItMessage” and awaits replies. In the embodiment of FIG. 2, the Chart, Report and Companies agents 216, 218 and 220, respectively, are all referenced in the Finance Agent's policy conditions and are therefore downchain of the Finance Agent 214. Each agent downchain of the Finance agent 214 does the same upon receipt of an InterpretItMessage. When an agent has received all replies (or in certain embodiments, times out on all replies not yet received), the agent tests the input token sequence against the agent's policy conditions. The agent processes the input in order from the agent's first policy to its last policy. Each policy makes all the claims it can on the input. Subsequent policies in the agent can make reference to claims made by previously processed policies in the agent, as well as to claims made by downchain agents. After all policies have made their claims the agent uses a predetermined algorithm to select the “best” claim. If the best claim is one made from a non-grammatical condition (e.g. combo operator), then the sub-claims are also selected. The agent then returns the selected claim or claims to the agent's upchain agent in an object of class ClaimMessage. If the agent is not able to make any claims on the input, then the agent passes upchain an object of class NoClaimMessage.

[0035] Thus in the embodiment of FIG. 2, the Finance agent 214 eventually will receive any claims made by its downchain agents and will refer to such claims in the evaluation of its own policy conditions. The Finance agent 214 then will respond to the System agent 212 with either a ClaimMessage or a NoClaimMessage. If the System agent 212 receives a NoClaimMessage, then the System agent's single policy does not apply and no user-perceptible action is taken in response to the input utterance. If the System agent 212 receives a ClaimMessage, then the System agent's policy does apply.

[0036] The System agent 212 evaluates its own policy conditions in the same manner as other agents in the network, and each such policy again makes as many claims as it can on the input. But because the System agent 212 is the Top agent, it does not transmit any resulting claims (or NoClaims) to any further upchain agents. Instead, as the Top agent of a network, after selecting one or more “best” claim(s) in the manner described above, System agent 212 has the responsibility to delegate “actuation” to the agents and policies that made up the claim(s). This process, which is sometimes called “executing” the winning claim, takes place according to the “action” part of the winning policy or policies in the Top agent. The action part of a policy builds up an actuation string in a manner similar to that in which policy conditions build up the result of the condition, that is, by string operators and operands that can include words, numbers, symbols, actuation sub-strings already created by other policies within the same agent, and actuation sub-strings created by other downchain agents. Typically the downchain agents referred to in the action part of a policy are the same agents referred to in the condition part of the policy. Also typically, the actuation string built up by this process is an XML string.

[0037] In order to fill in the actuation sub-strings defined by downchain agents, the Top agent sends an object of class DelegationMessage to each downchain agent referenced in the action part of the winning policy(ies). In the embodiment of FIG. 2, the System agent 212 contains only one policy, the action part of which does nothing more than delegate to the Finance agent 214. The actuation sub-string returned by the Finance agent 214 therefore will be the actuation string output of the network. The DelegationMessage received by an agent includes a reference to the particular policy or policies of that agent which formed part of the winning claim. Upon receipt of such a message, therefore, the agent executes the action part of each of its policies that formed part of the winning claim, issuing DelegationMessages of its own to its own downchain neighbors as called for in the action part of the such policies, and building up an actuation sub-string for returning to the agent's upchain caller. Actuation sub-strings are passed to upchain agents in objects of class ActuationMessage, ultimately once again reaching the Top agent of the network (System agent 212). This agent then forwards the actuation message in the form of an XML string toward the back-end application subsystem 116 (FIG. 1).

[0038] Thus it can be seen that interpretation of the user's intent takes place in an agent network in a distributed manner. Each of the agents in agent network 202 can be thought of as having a view of its own domain of responsibility, as defined by its interpretation policies. Typically the application domain is organized by the designer into a hierarchy of semantic sub-domains, and individual agents are defined for each node in the semantic hierarchy. In the embodiment of FIG. 2, for example, the Finance agent 214 is responsible for all semantics that relate to finance (i.e., all queries in the entire application domain in this example). The Chart agent 216 is responsible for detecting and acting upon parts of user queries that have to do with financial charting, whereas Report agent 218 is responsible for detecting and acting upon parts of user queries that have to do with financial reporting. Companies agent 220 is responsible for detecting and acting upon parts of user queries that have to do with company names. The Companies agent 220 has downchain thereof a Symbol agent 222, responsible for detecting and acting upon parts of user queries that involve company names provided in the form of an trading symbol; a Name agent 224, responsible for detecting and acting upon parts of user queries that involve company names provided as a company name; an Exchange agent 226, responsible for detecting and acting upon parts of user queries that involve companies that are trading exchanges, and so on.

[0039] It can also be seen that the Top agent of a network is responsible for receiving input and initiating queries into the network, and the agents representing the functionality of the system (the agents constructing their actuation sub-strings without reference to further agents) are the lowest order nodes (leaf agents) of the network. The network operates in two main phases: the interpretation phase and the delegation phase. In the interpretation phase, an initiator agent (such as the Top agent) receives the input token sequence and, by following its policy conditions, queries its downchain agents whether the queried agent considers the input token sequence, or part of it, to be in its domain of responsibility. Each queried agent recursively determines whether it has an interpretation policy of its own that applies to the input token sequence, if necessary further querying its own further downchain agents in order to evaluate its policy conditions. The further agents eventually respond to such further queries, thereby allowing the first-queried agents to respond to the initiator agent. The recursive invocation of this procedure ultimately determines a path, or a set of paths, through the network from the initiator agent to one or more leaf agents. The path is represented by the claim(s) ultimately made by the initiator agent. After the appropriate paths through the network are determined, in the delegation phase, delegation messages are then transmitted down each determined path, in accordance with the action parts of winning policies, with each agent along the way taking any local action thereon and filling in with further action taken by the agents further down in the path. The local action involves building up segments of the actuation string, with each agent providing the word(s) or token(s) that its policies now know, by virtue of being in the delegation path, represent a proper interpretation of at least part of the user's intent. The resulting actuation string built up by the selected agents in the network are returned to the initiator agent as the output of the network. This actuation string contains the fields and field designators required to issue a command or query to the back-end application subsystem 116, to effect the intent of the user as expressed in the input token string and interpreted by the agent network.

3. Interaction Block

[0040] As mentioned, the interaction block 118 typically is specific to one I/O modality (or a group of very similar I/O modalities), and one I/O device (or a group of I/O devices that are very similar in their layout requirements). Although in one embodiment a single interaction block 118 class is usable with any back-end application, in the embodiment described herein it is specific, or somewhat specific, to a kind of application that includes back-end application subsystem 116. For example, if the back-end application is a financial reporting application, then the interaction block 118 might be generic to financial reporting applications from several suppliers. In the embodiment of FIG. 1, an interaction block 118 is further divided into two components, namely an I/O mode object 126 and an I/O formatter object 128. Specifically, interaction blocks 118-1 . . . 118-n include respective I/O mode objects 126-1 . . . 126-n (illustratively 126), and further include respective I/O formatter objects 128-1 . . . 128-n (illustratively 128). The aspects of an interaction block 118 that depend on the I/O modality are concentrated (typically exclusively) in the I/O mode object 126, and the aspects of an interaction block 118 that depend on the layout of information on the I/O device are concentrated (typically exclusively) in the I/O formatter object 128.

[0041] The I/O mode object 126 is the basic interface between a particular user interface modality (standard email, the web, SMS, a window on the user's screen, an e-mail modality that supports PGP encryption, etc.) and the NLI 110. The class defining each I/O mode object preferably is re-usable with any application and for any I/O device that supports the same transport mechanism as the I/O modality. There should be no application specific code in an I/O mode class definition. In some cases that might be unavoidable, however, so to include features specific to one kind of application, the I/O mode object 126 is instantiated from a generic base class, which is reusable for any kind of application, and a separate subclass specific to the kind of application targeted.

[0042] Each I/O mode object is responsible for:

• • [0043] Processing the user's input and building the appropriate query out of it. In an e-mail I/O mode object, for example, this might involve picking the mail off the mailbox, parsing the subject and body, and looking for the query. In a web I/O mode object, this might involve taking information from a webform.
  • [0044] Managing when the user will create a new context. A context is a conversation, including initial user interaction together with an optional set of followup interactions. Follow-up input usually involves resolution of ambiguity in previous input, narrowing down of previous input, next/previous relative to previous input, and so on. The I/O mode object does not maintain the context; it merely discerns whether or not the user intends new input to maintain context with previous interactions, and submits this intent to the NLI 110 together with the new query. In an e-mail I/O mode object, a user's intent to retain context might be discerned from the inclusion, in the subject line of the input message, of a context ID number that the system had included in the subject line of a previous outgoing message that the system had sent in response to previous user input. In a web I/O mode object, the user's intent to retain context might be discernced by looking for user selection in the webform of an explicit “retain context” check-box, for example. In some I/O mode objects, such as an SMS I/O mode object, the I/O mode object might not attempt to discern whether the user intends to retain context, but rather, it might always report to the NLI 110 that new user input is not a follow-up of previous input.
  • [0045] Rendering output to the user, whether it be a reply originating from the back-end application subsystem 116 or a clarification request or other output from the NLI 110 itself. In an e-mail I/O mode object, this might include creating a plain text response. In a web I/O mode object, this might include creating a proper html page, and so on.
  • [0046] Delivering the output to the user. In an e-mail I/O mode object, this might include composing a letter with the response as the body and forwarding it to an email program. In a web I/O mode object, this might include forwarding sending the HTML page back to the user's browser, and so on.

[0047] FIG. 3 is a class diagram of a sample I/O Mode Object class and its subclasses. As shown, an IOMode class 310 has separate subclasses for each particular modality: a WebIOMode subclass 312 for web modalities, an EmailIOMode subclass 314 for email modalities, and an SmsIOMode subclass 316 for SMS modalities. The IOMode class 310 also has a SystemIOMode subclass 318 that provides a command line interface for debugging and stand-alone applications. An example IOMode class definition is set forth in the java file named CD-IOMode.java.txt in the accompanying Computer Program Listing and Table Appendices. The IOMode class extends a NaturalInteractionComponent class whose definition is set forth in the java file named CD-NaturalInteractionComponent.java.txt in the accompanying Computer Program Listing and Table Appendices. The NaturalInteractionComponent class extends a NaturalInteractionRemoteObject class whose definition is set forth in the java file named CD-NaturalInteractionRemoteObject.java.txt in the accompanying Computer Program Listing and Table Appendices, and the NaturalInteractionRemoteObject class extends the UnicastRemoteObject class which is defined in a conventional java RMI package. An example WebIOMode class definition is set forth in the java file named CD-WebIOMode.java.txt in the accompanying Computer Program Listing and Table Appendices, and an example EmailIOMode class definition is set forth in the java file named CD-EmailIOMode.java.txt in the accompanying Computer Program Listing and Table Appendices. An example SystemIOMode class definition is set forth in the java file named CD-SystemIOMode.java.txt in the accompanying Computer Program Listing and Table Appendices.

[0048] I/O mode objects are designed to be as much as possible application independent, but the format of the output of one kind of application is most likely unique and very different than the format of the output for another kind of application. For example, the format of output from a contacts manager is very likely to be very different from that of a financial reporting application. In addition, even for a single application, the layout of output required for a computer monitor is likely to be very different than that required for a PDA. To allow the I/O mode objects to remain application and device independent, their presentation methods are encapsulated within I/O formatter objects 128. Thus an I/O mode object 126 can take an I/O formatter object AX_iof for an application of kind A and a device of kind X, and the same I/O mode class definition can be used to instantiate an I/O mode object for application of kind B and a device of kind Y merely by being assigned an I/O formatter BY_iof. The I/O mode objects would behave the same way in essence, but the output of each I/O mode object would depend on the particular I/O formatter object 128 to which it is assigned. As examples, I/O formatter objects 128 can be designed for displaying display web pages on PDA's, for displaying e-mail on desktop computer monitors, for displaying e-mail on PDA's, for displaying SMS messages on SMS devices, and for formatting voice output for voice devices. In another embodiment, all of the presentation methods could be encapsulated in subclasses of a parent I/O Mode class, rather than in a separate I/O Formatter object.

[0049] An I/O formatter object 128 is assigned to each I/O mode object 126 at initialization. System output destined for user 112 is provided to the I/O mode object 126 in a generic form, such as an XML string, and the I/O mode object 126 calls methods of the assigned I/O formatter object 128 in order to convert the string to a new format that the I/O mode object 126 then can simply transmit to the user via the particular transport mechanism that the I/O mode object 126 is designed to use.

[0050] FIG. 4 is a class diagram for an I/O formatter class 410 and its subclasses. Three of the subclasses shown in the diagram are specific to a particular kind of application (a finance application), and the fourth is not application specific. All of the subclasses are specific to a particular kind of I/O device: a Finance SMS IOFormat subclass 412 for SMS devices, a Finance RIM IOFormat subclass 414 for RIM devices, a Finance Desktop IOFormat subclass 416 for desktop computer devices, and a TextIOFormat subclass 418 for text-based devices. An example IOFormat class definition is set forth in the java file named CD-IOFormat.java.txt in the accompanying Computer Program Listing and Table Appendices, and an example TextIOFormat class definition is set forth in the java file named CD-TextIOFormat.java.txt in the accompanying Computer Program Listing and Table Appendices.

[0051] The TextIO Format class 418 also has an XML IO Format subclass 420, which provides the system designer with a standardized method for defining the formats required for various I/O devices. In particular, an object of class XmlIOFormat uses XML Stylesheet Transformations (XSLT) to define the formats. Such an object takes in an XML input originating from the NLI 110 or back-end application subsystem 116, uses an application- and I/O device-specific stylesheet 422 to transform the XML, and sends the transformed data toward the user 112. An example XmlIOFormat class definition is set forth in the java file named CD-XmlIOFormat.java.txt in the accompanying Computer Program Listing and Table Appendices. Note that for stylesheets, it may be preferable to use parameters and named-templates. For instance, the layout for an entire back-end application can be based on one generic template layout, with specific parts filled in according to the particular nodes that are in the output XML. Instead of having similar logic repeated throughout the stylesheet, the stylesheet processing can begin with the logic, use the logic to assign values to parameters, then call the named-template (representing the basic layout of the application) with the parameters (representing the values that should be used to fill in the template). This technique also allows easier re-use of the same logic across different I/O modalities, for example since e-mail and web modalities often use the same general logic.

4. Interaction Agent

[0052] In one embodiment, the NLI 110 communicates directly with an interaction block 118, and directly with the back-end application subsystem 116. In the embodiment of FIG. 1, however, the I/O mode object 126 processes information by way of method calls into the same or different java objects, whereas the interfaces to the NLI 110 are by way of messages. The embodiment of FIG. 1 therefore includes an interaction agent 122, which acts as a bridge between the messaging interface of the agent network in the NLI 110 and the method calls of the I/O mode object 126. As a bridge, it can be viewed either as part of the interpretation subsystem, or as part of the interaction subsystem 114, or both, or as a separate independent module. The main function of interaction agent 122 is to convert method calls from the I/O mode objects 126 into messages that it sends into the NLI 110, and to convert messages that it receives from either the NLI 110 or the application subsystem 116, into information returned by a method call made previously from within the I/O mode object. An example interaction agent class definition, in java, is set forth in the file CD-InteractionAgent.java.txt in the CD-ROM appendix hereto. InteractionAgent.java implements class InteractionListener, which is set forth in the file CD-InteractionListener.java.txt in the CD-ROM appendix. InteractionAgent.java also extends a StandardAgent class whose definition is set forth in the java file named CD-StandardAgent.java.txt in the accompanying Computer Program Listing and Table Appendices. The StandardAgent class extends an Agent class whose definition is set forth in the java file named CD-Agent.java.txt in the accompanying Computer Program Listing and Table Appendices.

[0053] The messages sent by the NLI 110 or the application subsystem 116 to the interaction agent 122 for forwarding toward the user 112 are objects of class InteractionMessage. A message of this class can contain any object within it, though the I/O formatter object that will process the message must know how to handle the data within the InteractionMessage. Facts (data from the system), questions (when more information is needed), and lists (when a choice must be made between several items—for ambiguities—did you mean A or B?) are all different types of data that can be contained within an InteractionMessage and formatted appropriately by the I/O formatter object. An example InteractionMessage class definition, in java, is set forth in the file CD-InteractionMessage.java.txt in the CD-ROM appendix hereto. The InteractionMessage class extends a MessageContent class whose definition is set forth in the java file named CD-MessageContent.java.txt in the accompanying Computer Program Listing and Table Appendices.

[0054] The messages sent by the interaction agent 122 into the NLI 110 are objects of class InteractionResultMessage. A message of class InteractionResultMessage generally encapsulates a user query, which is processed into a command by the agent network in the interpretation subsystem. Occasionally, a message of class InteractionResultMessage contains followup information from the user 112 and prior context. For example, when the user has answered a question, the answer to the question and the context of the question is maintained. An example InteractionResultMessage class definition, in java, is set forth in the file CD-InteractionResultMessage.java.txt in the CD-ROM appendix hereto. The InteractionResultMessage class also extends the MessageContent class mentioned above.

[0055] It can be seen that the above-described system separates the particulars of user interaction via various I/O agencies, from the natural language interpretation system and the back-end application subsystem. In this way, all of the development for generating a natural language interpretation system optimized for a particular back-end application can be re-used for different I/O agencies simply by substituting in a different I/O interaction block 118 into the user interaction subsystem. Similarly, all of the complications of interacting with particular agencies also can be concentrated in one module that is separate from the module(s) performing the natural language interpretation tasks.

[0056] As used herein, a given signal, event or value is “responsive” to a predecessor signal, event or value if the predecessor signal, event or value influenced the given signal, event or value. If there is an intervening processing element, step or time period, the given signal, event or value can still be “responsive” to the predecessor signal, event or value. If the intervening processing element or step combines more than one signal, event or value, the signal output of the processing element or step is considered “responsive” to each of the signal, event or value inputs. If the given signal, event or value is the same as the predecessor signal, event or value, this is merely a degenerate case in which the given signal, event or value is still considered to be “responsive” to the predecessor signal, event or value. “Dependency” of a given signal, event or value upon another signal, event or value is defined similarly.

[0057] As used herein, an item is “identified” if sufficient information is provided to distinguish the item from other items. For example, information identifies an item if the information can be used to access data relating to the item rather than to access data relating to other items.

[0058] The foregoing description of preferred embodiments of the present invention has been provided for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise forms disclosed. Obviously, many modifications and variations will be apparent to practitioners skilled in this art. In particular, and without limitation, any and all variations described, suggested or incorporated by reference in the Background section of this patent application are specifically incorporated by reference into the description herein of embodiments of the invention. The embodiments described herein were chosen and described in order to best explain the principles of the invention and its practical application, thereby enabling others skilled in the art to understand the invention for various embodiments and with various modifications as are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the following claims and their equivalents.

1 Introduction

[0059] Policies are written in a language called OPAL. This reference intends to describe the OPAL language. The current version of the platform can run in backward compatibility mode. In this mode some of the features described in this document would not be available. The comment “(not available in backward compatibility mode)” is written in front of each of these features. Set the system property USE_AMBIGUITY_XML to alse to run the platform in the backward compatibility mode. Example: java-DUSE_AMBIGUITY_XML=false IDE.

2 Policy

[0060] An AAOSA agent uses a set of policies to make claims on the input and to make actions based on those claims.

2.1 Overview of Claim

[0061] A claim is the part of the input that an agent policy recognizes as part of its domain. A claim may be built by putting together claims made by other policies or other agents. For example a HOME_ENTERTAINMENT policy may make claims based on claims made by a TV policy and a VCR policy. We would refer to TV and VCR claims as sub claims in the context of the HOME_ENTERTAINMENT claim.

2.2 Propagation of Claims

[0062] An AAOSA agent will use its policies to process the input when it receives an initiate interpretation, interpretation or reinterpretation message. Agents process the input in order from first policy declared in the agent to the last policy. Each policy makes all the claims it can on the input. Following policies can access these claims. After all policies have made their claims the agent selects the best claim. If the best claim is made from a non-grammatical condition (e.g. combo), then the sub-claims are also selected. The selected claims are handed up to up chain agents (i.e. using claim message).

2.3 Actuation of Claims

[0063] An Actuation is a standardized output. The actuation phase begins when the top AAOSA agent selects its best claim. The top agent will actuate the best claim using the action part of the policy that made that claim. The policy's action dictates whether the actuation of the claim should be delegated to other policies or agents. If the actuation is delegated to another agent a delegation message is sent to that agent. When an AAOSA agent receives a delegation message for actuating a claim, it will use the policy responsible for making that claim to actuate it. Each policy will either actuate the claim entirely or delegate parts of the actuation to other policies or agents responsible for making its sub claims.

2.4 Overview of Policy Components

[0064] A policy can have several components:

• • [0065] Name: Makes it possible to refer to the policy in OPAL language.
  • [0066] Title: Makes it possible to refer to the policy in the interactions and menus.
  • [0067] XML tags: Makes it possible to wrap the action in XML tags
  • [0068] Priority: Prioritizes the claim made by this policy.
  • [0069] Continuation: Sets the dependency of the claim to the claims made on previous input.
  • [0070] Condition: Makes claims by processing the input. A condition could be:
    • [0071] Terminal: Atomic operands of OPAL language.
    • [0072] References: Operands referring to claims made by other conditions.
    • [0073] Unary: A condition with only one operand.
    • [0074] Binary: A condition with two or more operand.
  • [0075] Action: Creates an action from a claim.
    3 Claim

[0076] A claim quantifies how well an input matches a policy condition. The information associated with a claim includes:

3.1 Owner

[0077] The name of the policy making the claim and the agent to which that policy belongs.

3.2 Focus

[0078] The parts of the input matched by the policy condition. Focus is represented using the character indexes of the input. (Characters in the input are indexed from 0). For example, focus [5 . . . 8] represents the word ‘book’ in the input ‘Sell book’. The characters of the input that correspond to the token separators (for example, white space) are never considered to be part of the focus. Therefore, a policy condition that matched ‘Sell’ and ‘book’ would have focus [0 . . . 3,5 . . . 8]. However, when there is no chance of confusion, for convenience this focus would be written as [0 . . . 8].

3.3 Priority

[0079] The precedence of the claim. (For details on assigning priorities to claims, see the Policy Components section.) Priorities are local to an agent. When an agent sends a claim to an up chain agent, the priority is reset to 0. The exception is priorities that are assigned for adding dialoging focus. These priorities are passed up-chain with the claim.

[0080] A vector is kept of all different priorities that were associated to sub-claims building up a claim. The focus size of the sub-claims with the same priority will be added up and would be kept in the vector.

[0081] The priority vector of claim on ‘aaa bb’ made by policy P3.

• • [0082] P1: ‘aaa’ {priority:+1}
  • [0083] P2: ‘bb’ {priority: 0}
  • [0084] P3: P1 & P2
  • [0085] User-Input: ‘aaa bb’

[0086]

	Priority	1	0
	Focus size	3	2

[0087] The priority criterion of two claims will be compared in the following manner:

• • [0088] 1. The claim with highest priority will be chosen as the better claim.
  • [0089] 2. If both claims have the same highest priority then the coverage percentage of that priority is compared. The coverage percentage is the focus size of that priority divided by the total focus size of that claim. The claim that has the higher coverage percentage will be chosen as the better claim.
  • [0090] 3. If both claims have the same coverage on their highest priority then that vector will be compared again from step 1 disregarding the highest priority.
    3.4 Ambiguity

[0091] A claim is said to be ambiguous if it contains two or more sub-claims with overlapping focuses. The ambiguity of the claim is equal to the number of ambiguous sub-claims that are found in the claim, including the claim itself.

3.5 Connection Weight

[0092] The total sum of connection weights assigned to operators making the claim. Each operator and operand has a predefined grammatical weight. The operators and operands in descending order of grammatical weight are:

[0093] 1. Combo (,) and Recursive (+). Weight=∞. (loose connection)

[0094] 2. Inexact matches. Weight=10000.

[0095] 3. And (&). Weight=100.

[0096] 4. Ordered (<). Weight=1.

[0097] 5. Adjacent (and all other operators and operands). Weight=0.

3.6 Loose Connections Count

[0098] The number of Combo (,) or Recursive (+) operators used to make a claim.

3.7 Unknown

[0099] Used to identify the number of items missing in the user input (deprecated). See Section 3-3-4 on <unknown if missing> condition.

3.8 Adjacency Score

[0100] Indicates the relative closeness of the claimed parts of the input. Adjacency score is calculated by adding up the number of tokens between claimed parts. If a claim has marked ‘Siamak’ and ‘Hodjat’ on the input “Siamak is a Hodjat”, its adjacency score is 2. A claim marking ‘Sia’ and ‘Hodjat’ on input “Siamak is a Hodjat”, will also have adjacency score of 2, because ‘Sia’ is part of the ‘Siamak’ token, but the same claim will have an adjacency threshold of 5 on the input “Siamak's family name is Hodjat” (Assuming the default USTokenizer is used). The following table shows the how adjacency score is calculated for different inputs claimed by the policy: ‘aaaaa’ & ‘bbbbb’.

[0101] Computing Adjacency Score

[0102]

	Input	Adjacency score
	aaaaa	bbbbb	0
	aaaaa	bbbbb	0
	aaaaas	bbbbb	0
	Aaaaa	cc bbbbb	1
	Aaaaa	cc dd bbbbb	2
	Aaaaa's	bbbbb	2

Note that adjacency is handled slightly differently in the case of the combo operator. See the section on the combo operator for details.
3.9 Variable

[0103] Variables mark parts of the input that is not claimed by other conditions in a policy. Variables are adjustable and the part they mark may vary as the claim is manipulated (see variable condition).

4 Claim List

[0104] All claims made by policy conditions are added to an ordered list. The default criteria used to order the claims is as follows, listed in the order in which they are considered when comparing two claims. Each criterion is checked only if none of the criteria above it would apply. If two claims are equivalent with respect to all of the criteria, the claim that was made by the policy listed later in the Agent will win.

4.1 Coverage

[0105] A claim whose focus includes another claim's focus wins. If the focuses are equivalent, neither is considered to cover the other. For example, a claim made on ‘Being John Malkovich’ with focus [0 . . . 4] [6 . . . 9] [11 . . . 19] will win over a claim with focus [6 . . . 9] [11 . . . 19]. However, if two claims both had focus [0 . . . 4], the claims would be equivalent in terms of the coverage criterion.

4.2 Priority

[0106] A claim with higher priority wins. If the priorities are the same, the claim with the higher priority score will win. (See the Policy Components section on Priority for details on how priority and priority score are assigned.)

4.3 Ambiguity

[0107] A claim with more ambiguity wins. This criterion is checked only if the current claim can be merged with the claim it's compared to. (See Claim Manipulation in Appendix 3 for further information.) If two claims have equivalent ambiguity, the ambiguity due only to the current claim is compared. If this differs, the claim with the smaller local ambiguity will win (regardless of whether the two claims can be merged).

4.4 Connection Weight

[0108] A claim made by more grammatical operators and exactly matched operands wins (that is with smaller connection weight). If the connection weights of two claims are equal then the claim with fewer loose connections wins.

4.5 Adjacent

[0109] A claim with smaller adjacency score wins.

4.6 Focus Size

[0110] A claim with a larger focus wins. For example, a claim made on ‘Sell Book and Buy Toy’ with focus [0 . . . 3] [5 . . . 8], will win over a claim with focus [9 . . . 11] [13 . . . 15]).

4.7 Match Restrictiveness

[0111] A claim using a more restrictive token matcher wins. The most restrictive token matcher is the exact token matcher, which has a restrictiveness of 100. The substring token matcher has a restrictiveness of 60.

4.8 Variable

[0112] When comparing two claims the claims with no variables is better than a claim with variables. If both claims have variables then the one with more variables but smaller ones is preferred to the one with less but wider variables (see variable condition).

4.9 Unknown (Deprecated)

[0113] A claim with unknown element(s) will win over a claim with no unknown elements. If both claims have unknown elements the one with less unknown elements wins.

4.10 Default criterion:

[0114] A claim, which its focus is closer to the beginning of the input wins.

5 Policy Components

5.1 Name

[0115] Used to refer to the policy in the OPAL language. A policy name is a series of capital letters (‘A’ to ‘Z’), digits (‘0’ to ‘9’) or under score (‘_’) that begins with a capital letter. Policies names should be unique (in the scope of the agent they are declared in).

5.2 Title

[0116] Used to refer to the policy in interactions and menus. Spaces/symbols can be used in the title and it does not need to be in capital letters. The title is a literal and is automatically enclosed in quotes.

5.3 XML Tags (Not Available in Backward Compatibility Mode)

[0117] The interpretation network will support the generation of output that contains XML tags. This section will discuss the types of tags that will be used and how they are generated. It will use the AV Network as an example. See FIG. 5.

[0118] An XML tag is made up of three components

• • [0119] 1. name: The name of the tag
  • [0120] 2. parameter: The name of a tag parameter. Each tag may have 0 or more parameters.
  • [0121] 3. value: The value of a tag parameter. Each parameter must have exactly one value.

[0122] A basic XML tag has the form:

[0123] <<name> [<parameter>=“<value>”]> </<name>>

[0124] For example, a tag having two parameters would have the form:

[0125] <name parameter1=“value1” parameter2=“value2”> </name>

[0126] The interpretation network supports two parameters, type and ID. These are discussed in more detail later. For now, just note that the general form of an XML tag generated by the network is:

[0127] <name type=“value1” ID=“value2”> </name>

[0128] The XML tags that are supported by the interpretation network can be divided into four groups (two of which consist of a single tag):

[0129] 1. The Interpretation Tag

[0130] 2. The Ambiguity Tag

[0131] 3. The Logical Tags

[0132] 4. Domain Specific Tags

[0133] The first three groups are common to all applications. The domain specific tags vary from application to application.

[0134] The tags are generated in two ways. The interpretation tag and the ambiguity tag are generated automatically by the interpretation network. The logical tags and domain specific tags are generated by setting the xml-tag and xml-type fields in the policy of a network agent.

[0135] As mentioned above, the system supports two parameters: type and ID. The type parameter is optional. For logical and domain specific tags, it can be specified by setting the xml-type field of a policy. The ID parameter is generated automatically by the system. Its value is equal to the ID of the claim that is being actuated by the policy.

[0136]

XML Tags Generated Automatically by the System
	Tag Name	Type (optional)	Data Values
	interpretation	none	none
	xor	relation	none
XML Logical Tags Common to All Applications
	Tag Name	Type (optional)	Data Values
	and	relation	none
	or	relation	none
	lessThan	relation	none
	greaterThan	relation	none
	ifThen	relation	none
AV Network Application Specific XML Tags
	Tag Name	Type (optional)	Values
	TV	function	none
	VCR	function	none
	Power	parameter	none
	Channel	parameter	none
	Volume	parameter	none
	On	attribute	none
	Off	attribute	none
	Up	attribute	none
	Down	attribute	none
	Station	attribute	PBS, CBS, NBC, etc.

[0137] Simple Command

[0138]

	Input: ‘Turn TV on’.
	XML: <interpretation>
	<TV type=“function” ID=“1_”>
	<power type=“parameter” ID=“2_”>
	<on type=“attribute” ID=“3_”>
	</on>
	</power>
	</TV>
	</interpretation>

[0139] Simple Command: Attribute with Values

[0140]

	Input: ‘Turn TV to PBS’.
	XML: <interpretation>
	<TV type=“function” ID=“1_”>
	<channel type=“parameter” ID=“2_”>
	<station type=“attribute” ID=“3_”>
	PBS
	</station>
	</channel>
	</TV>
	</interpretation>

[0141] Compound Attributes

[0142]

	Input: ‘Turn TV to PBS’
	XML: <interpretation>
	<TV type=“function” ID=“1_”>
	<and type=“relation” ID=“2_”>
	<power type=“parameter” ID=“3_”>
	<on type=“attribute” ID=“4_”>
	</on>
	</power>
	<channel type=“parameter” ID=“5_”>
	<station type=“attribute” ID=“6_”>
	PBS
	</station>
	</channel>
	</and>
	</TV>
	</interpretation>

[0143] Compound Commands

[0144]

	Input: ‘Turn VCR off and TV volume down.’
	XML: <interpretation>
	<and type=“relation” ID=“1_”>
	<VCR type=“function” ID=“2_”>
	<power type=“parameter” ID=“3_”>
	<off type=“attribute” ID=“4_”>
	</off>
	</power>
	</VCR>
	<TV type=“function” ID=“5_”>
	<volume type=“parameter” ID=“6_”>
	<down type=“attribute” ID=“7_”>
	</down>
	</volume>
	</TV>
	</and>
	</interpretation>

[0145] Ambiguity

[0146]

	Input: ‘Turn off.’
	XML: <interpretation>
	<xor type=“relation”>
	<TV type=“function” ID=“1_”>
	<power type=“parameter” ID=“2_”>
	<on type=“attribute” ID=“3_”>
	</on>
	</power>
	</TV>
	<VCR type=“function” ID=“4_”>
	<power type=“parameter” ID=“5_”>
	<on type=“attribute” ID=“6_”>
	</on>
	</power>
	</VCR>
	</xor>
	</interpretation>

5.3.1 Generating XML Tags

[0147] Syntax: {XML tag: tag-name}

[0148] XML tag goes after the policy condition.

[0149] Generating XML tags

[0150]

	Policy::
	(THEATERNAME:
	″
	‘AMC’ | ′century21
	{xml-tag: ‘theaterName’}
	{action:
	{execute:*}}
	″),
	Input: ‘amc’
	Output: <theaterName ID=“1_”> amc </theaterName>

5.3.2 Generating XML Type Tags

[0151] Syntax: {XML tag: tag-name}

[0152] XML type tag goes after the XML tag. XML type is valid only if XML tag is provided for the policy.

[0153] Generating XML Type Tags

[0154]

Policy::
(THEATERNAME:
″
‘AMC’ | ′century21
{xml-tag: ‘theaterName’}
{xml-type: ‘attrib’}
{action:
{execute:*}}
″),
Input: ‘amc’
Output: <theaterName type=“attrib” ID=“1_”> amc </theaterName>

5.3.3 Ambiguity Tags

[0155] Ambiguity tags are generated automatically.

[0156] Generating XHL Type Tags

[0157]

	Policy::
	(MOVIENAME:
	″
	‘john malkovich’
	{xml-tag: ‘movieName’}
	{xml-type: ‘attrib’}
	{action:
	{execute:*}}
	″) ,
	(MOVIESTAR:
	″
	‘being john mlkaovich’
	{xml-tag: ‘movieStar’}
	{xml-type: ‘attrib’}
	{action:
	{execute:*}}
	″),
	(MOVIE:
	″
	MOVIENAME,MOVIESTAR
	{xml-tag: ‘movie’}
	{action:
	{execute:*}}
	″) ,
	Input: ‘john malkovich’
	Output:
	<movie ID=“1_”><ambiguity>
	<movieName ID=“2_”>john malkovich</movieName>
	<movieStar ID=“3_”>john malkovich</movieStar>
	</ambiguity></movie>

5.3.4 Backward Compatibility

• • [0158] Using the backward compatibility mode will stop the automatic generation of the ambiguity XML tags and would prevent the XML tag and XML type from showing in the tree mode of policy editor.
    5.4 Priority

[0159] The priority assigned to a policy. A policy's priority is assigned to all claims made by that policy.

[0160] Of the criteria used to order the claim list, priority is the only one that can be set explicitly in the policy. Priority is the second criterion used when comparing two claims; coverage is compared first. If two claims are equal in terms of coverage, then the one with a higher priority will win. Therefore, priority provides the policy writer with a good amount of control over which policy should produce the winning claims.

[0161] The default priority is 0. Priority can explicitly be set to any integer between −1000 and +1000, inclusive. A positive integer will give the claims made by the policy higher priority; a negative integer will give them lower priority.

[0162] A list is kept of all different priorities that were associated to sub-claims building up a claim. The focus of the sub-claims with the same priority will be added up and would be kept in the list.

[0163] The Priority List of Claims

• • [0164] P1: ‘aaa’ p=1
  • [0165] P2: ‘bb’ p=2
  • [0166] P3: ‘cccc’ p=2
  • [0167] P4: (A B) & C
  • [0168] User-Input: “cccc aaa bb”.

[0169]

	Priority	2	1
	Focus size	5 . . . 7	[0 . . .3][9 . . . 12]

[0170] The priority criterion of two claims will be compared in the following manner:

• • [0171] 1. The claim with highest priority will be chosen as the better claim.
  • [0172] 2. If both claims have the same highest priority then the coverage percentage of that priority is compared. The coverage percentage is the focus size of that priority divided by the total focus size of that claim. The claim that has the higher coverage percentage will be chosen as the better claim.
  • [0173] 3. If both claims have the same coverage on their highest priority then that vector will be compared again from step 1 disregarding the highest priority.

[0174] Priority is used only for ordering the claim list of the agent containing the policy. When an agent passes a claim up chain, the priority of the claim is removed.

5.5 Continuation (Not Available in Backward Compatibility Mode)

[0175] The continuation field provides support for recognizing continuation in the interpretation network.

[0176] For example consider the following dialog:

[0177] 01 User: “Movies starring Tom Hanks”

• • [0178] System: Lists all movies starring Tom Hanks

[0179] 02 User: “And Meg Ryan”

• • [0180] System: Lists all movies starring Tom Hanks and Meg Ryan
    The interpretation network should recognize that the input 02 depends on the input 01. The “continuation field” is used to indicate if the interpretation of an input depends on the interpretation made on the previous input. The continuation field has the following syntax (which goes right after the policy condition):
    {continuation: join}

[0181] Current input is a continuation:

[0182]

	P1:
	/BOI ‘and’
	/*
	/BOI is a terminal condition that claims the beginning of the input
	*/
	{continuation: join}
	{action: {execute: ‘Recognized dependency’ }}

[0183] Whenever a policy is a join continuation then any claims made by that policy will be tagged as continued. Lets say the claim made by a policy with a {continuation: join} field would be part of the winning claim. If this is true then the input is going to be reinterpreted based on the claims made on the previous input. So in the above example the “And Meg Ryan” input will be claimed with dependency to the previous input (“Movies starring Tom Hanks”) and therefore “And Meg Ryan” will be reinterpreted again but this time the claims made on the previous input (“Movies starring Tom Hanks”) would be used.

5.6 Condition

[0184] Used to make claims from the input. Each condition will return a claim list of all claims it produces. There are four types of conditions: terminal, reference, unary and binary.

5.6.1 Terminal Condition

[0185] There are four types of terminal conditions:

[0186] Token Terminal Predefined patterns retrieved from a string, a file or a database.

[0187] Number Terminal Refers to claims made by other policies within the same agent.

[0188] Symbol Terminal Refers to claims made by other agents.

[0189] Type Terminal Refers to a part of the input not claimed.

5.6.1.1 Token

[0190] Tokens are identified based on the following parameters:

• • [0191] 1. Alphabet: Defines letters as the normal token type. Example: Characters ‘a’ to ‘z’ define the English alphabet.
  • [0192] 2. Number: Defines digits as the numeric token type.
  • [0193] 3. Symbol: Defines special characters (i.e. not alpha or number) as the token type.
  • [0194] 4. Delimiters: Defines what may separate tokens (e.g. white space, tabs, new line . . . ).
  • [0195] 5. Tokenizer class: The class used to identify tokens based on the above parameters.

[0196] The above parameters are defined in properties/ParserParameters.xml. Whatever is not included as an alphabet, numeral or symbol is considered a delimiter by the tokenizer.

[0197] Defining alphabet in ParserParameters.xml

• • [0198] <Policy:Alphabet>
  • [0199] <Policy:CharacterRange lowerLimit=“a” upperLimit=“z” />
  • [0200] <Policy:CharacterRange lowerLimit=“A” upperLimit=“Z” />
  • [0201] <Policy:CharacterRange lowerLimit=“&#x3000;” upperLimit=“&#xffee;” />
  • [0202] </Policy:Alphabet>

[0203] Defining numerals in ParserParameters.xml

• • [0204] <Policy:Numeric>
  • [0205] <Policy:CharacterRange lowerLimit=“0” upperLimit=“9” />
  • [0206] </Policy:Numeric>

[0207] Defining symbols in ParserParameters.xml

• • [0208] <Policy:Symbols>
  • [0209] <Policy:CharacterRange lowerLimit=“!” upperLimit=“/” />
  • [0210] <Policy:CharacterRange lowerLimit=“:” upperLimit=“@” />
  • [0211] <Policy:CharacterRange lowerLimit=“[” upperLimit=“{grave over ( )}” />
  • [0212] <Policy:CharacterRange lowerLimit=“{” upperLimit=“{tilde over ( )}” />
  • [0213] </Policy:Symbols>

[0214] Note that based on example 11, the symbol $ will be recognized as a symbol because it is in the range between “!” and “/”. But the symbol £ will not be recognized because it is not in any of the defined ranges. For it to be recognized as a symbol a new range would have to be added to the symbol definition (“&#x00A3;” is the Unicode for £).

[0215] Recognizing the £ Sign

• • [0216] <Policy:Symbols>
  • [0217] . . .
  • [0218] <Policy:CharacterRange lowerLimit=“&#x00A3;” upperLimit=“&#x00A3;”/>
  • [0219] </Policy:Symbols>

[0220] Other than the above-mentioned parameters, customized tokenizer classes may introduce application or language dependent types. The custom tokenizer class should replace USTextTokenizer in ParserParameters.xml.

[0221] A token is any stream of characters of the same type (e.g. alphabet, number, symbol) separated by delimiters or other tokens. Symbols are exception to this rule because symbols are broken up character by character.

[0222] Tokenizing

[0223]

	Input	Tokens
	‘John Smith’	‘john’
		‘smith’
	‘mp3’	‘mp’ (alphabet),
		‘3’ (number)
	‘we are: “world's greatest”	‘we’ (alphabet),
	company’	‘are’ (alphabet),
		‘:’ (symbol),
		‘“’ (symbol),
		‘world’ (alphabet),
		‘'’ (symbol),
		‘s’ (alphabet),
		greatest (alphabet),
		‘”’ (symbol),
		‘company’ (alphabet)

To see details on number tokens, see the section on number terminals.
5.6.1.2 Token Terminals

[0224] There are three types of token terminals:

[0225] Strings

[0226] Files (/F)

[0227] Databases (/DB)

5.6.1.2.1 Strings

[0228] The condition applies if part of the input matches the string. The string is broken into tokens. The tokens are implicitly joined using the adjacent operator. Each token is matched using the default <exact, substring> match. See Section 5.3.3 on how each token is matched using <exact> and <substring>; see Section 5.4.4 on how the ADJACENT operator works.

[0229] String Condition

• • [0230] Condition: ‘john malkovich’
  • [0231] User-Input: ‘a john malkovich movie’
  • [0232] The condition will apply and will mark ‘john malkovich’ as claimed
  • [0233] User-Input: ‘a john who is a malkovich movie’
  • [0234] The condition will not apply because ‘john’ and ‘malkovich’ are not adjacent in the input.
  • [0235] User-Input: ‘a john malk movie’
  • [0236] The condition will not apply because ‘malk’ does not match ‘malkovich’.
  • [0237] User-Input: ‘a john malkovic movie’
  • [0238] The condition will not apply because ‘malkovic’ is a substring match of ‘malkovich’.

[0239] The ‘, “, and/are special characters that should be referred to using %SINGLE_QUOTE %, %DOUBLE_QUOTE% and %BACK_SLASH% sequences.

[0240] Using Special Characters In String Condition

• • [0241] Condition: ‘%DOUBLE_QUOTE%malkovich%DOUBLE_QUOTE% ’
  • [0242] User-Input: ‘a “malkovich” movie’
  • [0243] The condition will apply.
    5.6.1.2.2 Files (/F)
    The condition applies if part of input matches one of the lines in a text file. By default, each entry in the text file can make a claim even if all its tokens are not found in the input.

[0244] The /F Condition

• • [0245] MN.txt:
  • [0246] sixth sense
  • [0247] being john malkovich
  • [0248] the wall
  • [0249] ---------------------------------------------------
  • [0250] Condition: /F ‘MN.txt’
  • [0251] User-Input: malkovich and sixth sense
  • [0252] The condition will apply and two claims will be made.
  • [0253] The claims (in order) would mark the following:
  • [0254] ‘malkovich’
  • [0255] ‘sixth sense’

[0256] A claim will be made on only those input tokens that are in order.

[0257] The /F Condition

• • [0258] MN.txt:
  • [0259] being john malkovich
  • [0260] ---------------------------------------------------
  • [0261] Condition: IF ‘MN.txt’
  • [0262] User-Input: john malkovich

[0263] The condition will apply and will make the claim: ‘john malkovich’

[0264] The /F Condition

• • [0265] MN.txt:
  • [0266] being john malkovich
  • [0267] ---------------------------------------------------
  • [0268] Condition: IF ‘MN.txt’
  • [0269] User-Input: malkovich john
  • [0270] The condition will apply and will make the claim: ‘malkovich’ (The claim on ‘john’ lost to the claim on ‘malkovich’).

[0271] The default behavior will change if token matchers (see Section 5.3.3, e.g. <exact>, <substring> . . . ) are applied to the /F condition. If token matchers are used then all tokens in the file entry must appear in the input adjacent and in order.

[0272] The /F Condition

• • [0273] MN.txt:
  • [0274] sixth sense
  • [0275] ---------------------------------------------------
  • [0276] Condition: <exact>1F ‘MN.txt’
  • [0277] User-Input: sense

[0278] The condition will not apply as ‘sixth’ does not appear in the input.

[0279] The /F condition

• • [0280] MN.txt:
  • [0281] sixth sense
  • [0282] ---------------------------------------------------
  • [0283] Condition: <exact>1F ‘MN.txt’
  • [0284] User-Input: sense sixth

[0285] The condition will not apply as ‘sixth sense’ does not appear in the input in the same order as the file.

[0286] The /F Condition

• • [0287] MN.txt:
  • [0288] sixth sense
  • [0289] --------------------------------------------------
    • [0290] Condition: <exact>‘MN.txt’
    • [0291] User-Input: sixth a sense

[0292] The condition will not apply as ‘sixth sense’ is not adjacent in the input.

5.6.1.2.3 Common Files

[0293] A common file may be provided for an agent network to modify the behavior of file conditions (/F). To prevent unwanted claims made by file conditions create a common file. The common file should contain a list of common words (e.g. the, as, is).

[0294] The Problem (Why We Need Common File)

• • [0295] Common file not provided:
  • [0296] MN.txt:
  • [0297] sixth sense
  • [0298] being john malkovich
  • [0299] the wall
  • [0300] ---------------------------------------------------
  • [0301] Condition: IF ‘MN.txt’
  • [0302] User-Input: the movies in Sunnyvale
  • [0303] The condition will apply and one claim will be made on token

[0304] ‘the’.

[0305] How Common File Will Help

• • [0306] Common file provided:
  • [0307] common.txt:
  • [0308] the
  • [0309] being
  • [0310] ---------------------------------------------------
  • [0311] Condition: /F ‘MN.txt’
  • [0312] User-Input: the movies in Sunnyvale
  • [0313] The condition will not apply.

[0314] The file condition will ignore the common words only if they are not adjacent to a non-common word.

[0315] Common Files

• • [0316] Common file provided:
  • [0317] Condition: /F ‘MN.txt’
  • [0318] User-Input: the wall
  • [0319] The condition will apply.
    5.6.1.2.4 Databases (/DB)

[0320] The condition applies if part of input matches one of the columns in a database. A database spec file (in text format) should be provided for the /DB condition. This spec file should contain the following information:

[0321] 1. JDBC driver

[0322] 2. JDBC server location

[0323] 3. Database name (or ODBC data source name)

[0324] 4. Table Name

[0325] 5. Column Name

[0326] 6. Login

[0327] 7. Password

[0328] Defining Spec File for JDBC Connection to Pointbase Using /DB

• • [0329] MS.spec:
  • [0330] com.pointbase.jdbc.jdbcUniversalDriver
  • [0331] jdbc:pointbase://192.168.0.26:1000/
  • [0332] movies
  • [0333] star
  • [0334] star_name
  • [0335] public
  • [0336] public
  • [0337] ---------------------------------------------------
  • [0338] Condition: /DB ‘MS.spec’

[0339] Defining spec file for JDBC connection to Microsoft Access using /DB

• • [0340] MS.spec:
  • [0341] sun.jdbc.odbc.JdbcOdbcDriver
  • [0342] jdbc:odbc:
  • [0343] movies
  • [0344] star
  • [0345] star_name
  • [0346] --------------------------------------------------
  • [0347] Condition: /DB ‘MS.spec’
    Known Issue:

[0348] The token matchers (e.g. <exact>, <substring>, . . . ) is not applicable to the /DB.

5.6.1.3 Number Terminal (/NUMBER)

[0349] The condition applies if a number token is found in the input (numbers are identified by the tokenizer).

[0350] You may also define a range for the /NUMBER condition.

[0351] Numbers are tokenized using the following rule:

<DIGIT>+[(COMMA|PERIOD)<DIGIT>+]+

[0352] Valid numbers:

• • [0353] 34
  • [0354] 34.5
  • [0355] 3,456
  • [0356] 3,456.56
    Known Issues:
    The following are also considered to be valid numbers:

[0357] 3.4.5

[0358] 23,3434,43

[0359] 3.4,5

• • [0360] There is no way to explicitly declare the format of a number (i.e. integer, positive integer, negative integer, real, scientific notation . . . ).
  • [0361] Ranges acceptable in /Number is limited to long integer values (±2³²) . . .
  • [0362] + and − signs are not claimed by operator /NUMBER
    5.6.1.4 Symbol Terminal (/SYMBOL)

[0363] The condition claims a single symbol in the input (numbers are identified by the tokenizer, refer to Section 5.4.1.1).

[0364] Symbol Terminal

• • [0365] Condition: /SYMBOL
  • [0366] User-Input: ‘@’
  • [0367] The condition will apply and the symbol @ will be claimed.

[0368] Symbol Terminal

• • [0369] Condition: /SYMBOL
  • [0370] User-Input: ‘#@%’
  • [0371] The condition will apply and the symbol # will be claimed.
    5.6.1.5 Delimiter Terminal (/DELIMITER)

[0372] (Not Available in Backward Compatibility Mode)

[0373] The condition claims a delimiter in the input (delimiters are identified by the tokenizer, refer to Section 5.4.1.1).

[0374] Delimiter Terminal

• • [0375] Condition: ‘blue’/DELIMITER ‘book’
  • [0376] User-Input: ‘blue book’
  • [0377] The condition will apply.
  • [0378] Claim: [‘blue’] [‘ ’] [‘book’ ].

[0379] Delimiters are most useful when used in conjunction with variables. Note that Blanks are added to the beginning and the end of all text inputs automatically and therefore the beginning and the end of input is always a delimiter.

[0380] Delimiter terminal at the beginning of the input

• • [0381] Condition: /DELIMITER ‘book’
  • [0382] User-Input: ‘book’
  • [0383] The condition will apply.
  • [0384] Claim: [‘ ’] [‘book’].
    5.6.1.6 Beginning of Input Terminal (/BOI)

[0385] (Not Available in Backward Compatibility Mode)

[0386] The condition claims the first character of the input that is always a blank space (blanks are added to the beginning and the end of all text inputs automatically).

[0387] BOI terminal

• • [0388] Condition: /BOI ‘a’
  • [0389] User-Input: ‘a’
  • [0390] The condition will apply.
  • [0391] Claim: [‘ ’] [‘a’].
  • [0392] User-Input: ‘b a’
  • [0393] The condition will not apply.
  • [0394] User-Input: ‘a b’;
  • [0395] The condition will apply.
  • [0396] Claim: [‘ ’] [‘a’].
    Important Notes:
  • [0397] The purpose of using /BOI should be to detect continuation (normally if the input depends on the previous input). Policies that detect continuation should not be referred in the policies that make relation between other policies.
  • [0398] It is recommended to always use <exists> operator along with the /BOI operators as normally the beginning delimiters themselves are not important.
  • [0399] This condition should only appear at the beginning of the policy condition (may follow the <exists> condition)
    5.6.1.7 End of Input Terminal (/EOI)

[0400] (Not Available in Backward Compatibility Mode)

[0401] The condition claims the last character of the input that is always a blank space (blanks are added to the beginning and the end of all text inputs automatically).

[0402] EOI terminal

• • [0403] Condition: /EOI ‘a’
  • [0404] User-Input:‘a’
  • [0405] The condition will apply.
  • [0406] Claim: [‘a’] [‘ ’].
  • [0407] User-Input: ‘a b’
  • [0408] The condition will not apply.
  • [0409] User-Input: ‘b a’
  • [0410] The condition will apply.
  • [0411] Claim: [‘a’] [‘ ’].
    Important notes:
  • [0412] The purpose of using /EOI should be to detect continuation (normally if the input depends on the next input). Policies that detect continuation should not be referred in the policies that make relation between other policies.
  • [0413] It is recommended to always use <exists> operator along with the /EOI operators as normally the ending delimiters themselves are not important.
  • [0414] This condition should only appear as the last operator in policy condition.
    5.6.1.8 Token Type Terminal (/TOKEN)

[0415] The condition applies if a user defined token type is found in the input. New token types could be defined in the tokenizer.

5.6.1.9 Check Condition (<check (agent, property, key; value)>):

[0416] Makes a claim only if an agent's property is equal to a specific value. This condition is especially useful for the AAOSA agents to know about the state of the application or device. For example the TV-agent in a TV/AV interface could use the <check> condition to know if the TV is on. If the TV is on and the user says ‘power on’ then the TV agent could generate the proper response. There are two types of properties that may be accessed through messaging:

[0417] a. Data property (basic objects)

[0418] b. Data store property (collection objects: hash tables, vectors, . . . )

[0419] Each agent must allow access to its data property by declaring it as a valid data property. The methods that should be sub-classed for this purpose are summarized in the following table:

[0420]

			Set
	Access permission	methods	message
Data	public Boolean	public void	<check
Property	IsValidDataProperty	setData	(agent,
	(String propertyName)	(String propertyName,	property;
		Object value)	value)>
		Object
		getData
		(String propertyName)
Data Store	public Boolean	public void	<check
Property	IsValidDataStoreProperty	setDataStoreElement	(agent,
	(String propertyName)	(String propertyName,	property,
		String propertyKey,	key;
		Object	value)>
		propertyValue)
		public Object
		getDataStoreElernent
		(String propertyName,
		String propertyKey)

[0421] All AAOSA agents have a STATE property that could be checked (STATE is a basic property).

[0422] The parameters of a check message, <check (agent, property, key; value)>, are:

Agent: The agent address that its property is to be checked. This parameter is optional. If omitted then an agent will “check” its own property.

Property: The name of the property to be checked.

Key: The key to the data store property (as a string). This parameter is optional. If omitted then an agent will “check” a basic property.

Value: The value that the property will be compared to (as a string).

[0423] Check Condition

• • [0424] P1:
  • [0425] Condition: ‘open’ {action: {execute: ‘door openned’,set(DOOR, ‘STATE’,“; ‘OPEN’)}}),
  • [0426] P2:
  • [0427] Condition: <check(DOOR,‘STATE’,“;‘OPEN’)>‘open’ (action: {execute: ‘door is already open!’}}
  • [0428] User-Input: ‘open’
  • [0429] If the state of the door is open then policy P2 will apply and when actuated it would reply with:‘door is already open!’

[0430] See section 6.2.6 and 6.2.7 for more information on set and get.

5.6.2 Reference Conditions

5.6.2.1 Policy Reference

[0431] The condition applies if another policy has claims. A policy name is a series of capital letters (‘A’ to ‘Z’), digits (‘0’ to ‘9’) or under score (‘_’) that begins with a capital letter. A policy can only refer to policies that are declared before it.

5.6.2.2 Agent Reference

[0432] The condition applies if the referenced agent has claims. The referenced agent must be a listener to the agent that owns the policy.

[0433] An agent is referred to using its address. An agent address has the following format:

[0434] agent-instance-name . agent-class @ domain

[0435] An agent could be referred to only if it's agent-instant-name would be a series of capital letters (‘A’ to ‘Z’), digits (‘0’ to ‘9’) or under score (‘_’) that begins with a capital letter.

[0436] Agent Reference

• • [0437] DOWN.com.MySubClassedAAOSA@x
  • [0438] All agents in the same domain may be referred to using only the agent-instance-name. By default all agents are made in domain x.
    5.6.2.3 Variables (?)

[0439] Variables behave and generate claims according to the following rules:

• • [0440] If the variable condition is bound by tokens on both sides of the condition, then all the tokens found between the boundary tokens are considered to be part of the variable and are added to the policy's claim. This type of variable condition is also known as an un-adjustable variable condition.

[0441] Variable Condition Bound from Both Sides

• • [0442] P1: ‘in’ ? ‘folder’
  • [0443] Input: in my java folder
  • [0444] The variable condition in the claims made by P1 is bound from left by the ‘in’ token and from right by the ‘folder’ token. Therefore, “my java” is identified as the variable part of the input and is added to the claim's focus..
  • [0445] If the variable condition is bound only on either the left or right side of the condition, then the leftmost/rightmost token of the variable part of the input is added to the policy's claim. The variable part of the input is also referred as a left/right “adjustable” variable

[0446] Variable Condition Bound from One Side

• • [0447] P1: ‘in’ ?
  • [0448] Input: in java folder
  • [0449] In this case the variable is bound on the left by the ‘in’ token and the variable part is identified as “right adjustable”. Per our rule, the “java folder” string is marked as the variable part of the input and “java” is added to the claim focus.
  • [0450] If a claim with a right (or left) adjustable variable is merged with another claim that does not have a variable part, then the variable part of the claim is adjusted by excluding all the tokens that are found from the beginning of the next claim focus.

[0451] Merging Variable Claims with Claims with No Variable Part.

• • [0452] P1: ‘a’ ?
  • [0453] P2: ‘b’
  • [0454] P3: P1<P2
  • [0455] Input: a x y z b r
  • [0456] In this case, P1's subclaim variable part consists of the string “x y z” and its focus consists of “a” and “x” (second rule applies). When merged, P3's focus consists of ‘a’, ‘x’ and ‘b’.
  • [0457] Claim list processing is performed as described in the policy reference. The variable length will be checked only after the appropriate checks for coverage, priority, ambiguity, connection weight, adjacency, focus size and restrictiveness are done.
  • [0458] If the variable condition does not mark any of the input, no claims are made.

[0459] No Claims are Made When the Input Contains No Variable Parts.

• • [0460] P1: ‘in’ ? ‘folder’
  • [0461] Input: in folder
  • [0462] Or
  • [0463] P1: ‘in’ ?
  • [0464] Input: folders that are in
  • [0465] In both of these examples the variable condition does not mark any of the input and no claims are generated.
  • [0466] When comparing two claims, any claims with no variables are selected over claims with variables

[0467] Claims With No Variables Win Over Claims with Variables.

• • [0468] P1: ‘a’ ?
  • [0469] P2: ‘a’ ‘b’
  • [0470] Input: a b
  • [0471] In this case, P2 will win over P1.
  • [0472] If two claims contain variables, then the claim with the greater number of variables wins.

[0473] Claims with greater number of variables win.

• • [0474] P1: ‘a’ ? ‘b’ ? ‘c’
  • [0475] P2: ‘a’ ? ‘c’
  • [0476] Input: a x b y c
  • [0477] In this example, P1 will be selected over P2.
  • [0478] If two claims have the same number of variables, then the claim with the smaller variable length wins

[0479] Claims with Smaller Variable Length Wins

• • [0480] P1: ‘a’ ? ‘b’
  • [0481] P2: ‘c’ ? ‘d’
  • [0482] Input: a x b c j k d
  • [0483] In this example, P1 is selected as it has the smallest variable length.
  • [0484] Variable conditions may have a name assigned to them. A named variable condition consists of the variable operator followed by a semicolon followed by the variable name. For example, [?:First] is a valid variable name. References to variable names are only valid within the actions of the policy where the variables are declared.

[0485] Named Variables

• • [0486] P1: ‘a’ ?:A
    • [0487] {action: {execute: ?:A}}
  • [0488] P2: P1 ‘b’ ?:A
    • [0489] {action: {execute: ?:A}}
  • [0490] Input: a x by
  • [0491] In this example, P2 will be selected as the best claim and the result of the actuation consists of ‘y’.
  • [0492] The use of cascading variables is illegal and its behavior is undefined and not supported.

[0493] Cascading Variables

• • [0494] P1: ‘in’ ???
  • [0495] The use of unbound variable conditions is illegal and its behavior is undefined and not supported.

[0496] Unbound Variables

• • [0497] P1: ?
    5.6.3 Unary Conditions:

[0498] Unary condition is an operation on one operand. There are six basic unary conditions:

• • [0499] Optional
  • [0500] Exists
  • [0501] Token matching
  • [0502] Unknown
  • [0503] Recursive
  • [0504] Tag
    5.6.3.1 Optional Condition ([operand]):

[0505] This condition will always make a claim. The claim made depends on the operand:

• • [0506] If the operand has a claim, then the optional condition will make the same claims as the operand.
  • [0507] If the operand has no claims the optional condition will claim null, an empty claim with a focus of zero.

[0508] Optional Condition

• • [0509] Condition: [‘actor’] ‘john malkovich’
  • [0510] User-Input: actor john malkovich
  • [0511] The condition will apply and will make the following claims:
  • [0512] ‘actor john malkovich’
  • [0513] ‘john malkovich’
  • [0514] User-Input: john malkovich
  • [0515] The condition will apply and will make one claim:
  • [0516] ‘john malkovich’

[0517] Policies should not be written in a way that they could make a null claim. For example, the following policies are not supported (although the SDK would not prevent them from being written):

[0518] Policy Conditions that Should be Avoided

• • [0519] P1: [‘a’]
  • [0520] P2: [‘a’] [‘b’]
  • [0521] P3: [‘a’& ‘b’ ]

[0522] Each of the above policies makes a null claim regardless of the input. An example of the bizarre behavior that would result is:

[0523] Avoiding Null Claims

• • [0524] P1: [‘a’]
  • [0525] P2: P1 & ‘b’
  • [0526] User-Input: b
  • [0527] P2 will make a claim on ‘b’ with no reference to the null claim made by P1 and with connection weight 0 (the & operator will be ignored when calculating the connection weight).
    5.6.3.2 Exists Condition (<exists> operand):

[0528] Checks to see if the operand has claims. If this is true, then the <exists>condition will make a null claim (an empty claim). If this is false, then the <exists> condition will not make a claim.

[0529] Exists Condition

• • [0530] P1:
  • [0531] Condition: ‘starring’ <exists> ‘siamak’
  • [0532] User-Input: starring siamak
  • [0533] The condition will apply, and will claim ‘starring’.
  • [0534] P1 condition will make the claim only if the word ‘starring’ appears in the input adjacent to claim(s) made by the token terminal ‘siamak’.
  • [0535] User-Input: starring
  • [0536] The condition will not apply.

[0537] If binary conditions such as adjacent, and (&), ordered (<) and combo (,) appear in the same policy as the <exists> condition, then they behave as if <exists> condition is making claims on the input. For example:

[0538] Exists Condition

• • [0539] P1:
  • [0540] Condition: ‘aaa’ <exists> ‘aaa’
  • [0541] User-Input: aaa aaa
  • [0542] The condition will apply and marks the first ‘aaa’ ([0 . . . 2]) as its claim.
  • [0543] User-Input: aaa
  • [0544] The condition will not apply, as there is no ‘aaa’ appears in the input before another ‘aaa’.

[0545] Note that the scope of <exists> condition is only the policy in which it appears.

[0546] Exists Condition

• • [0547] P1:
  • [0548] Condition: ‘aaa’ <exists> ‘aaa’
  • [0549] P2:
  • [0550] Condition: P1 ‘aaa’
  • [0551] User-Input: aaa aaa
  • [0552] The P2 condition will apply and will mark the first and second ‘aaa’ ([0 . . . 2] [4 . . . 6]) as its claim.

[0553] Policies should not be written in a way that they could claim null. That is the following policies are not supported (although the SDK would not prevent them from being written):

[0554] Policies that Should be Avoided

• • [0555] P1: <exists> ‘a’
  • [0556] P2: [‘a’] & <exists> ‘b’
  • [0557] P3: <exists> (‘a’ & ‘b’)

[0558] Each of the above policies makes a null claim regardless of the input. An example of the bizarre behavior that would result is:

[0559] Policy Conditions that Should be Avoided

• • [0560] P1: <exists>‘a’
  • [0561] P2: P1 & ‘b’
  • [0562] User-Input: b
  • [0563] P2 will make a claim on ‘b’ with no reference to the null claim made by P1 and with connection weight 0 (the & operator will be ignored when calculating the connection weight).

[0564] When using <exists>, an agent is checking against a part of the input that it is not going to claim. Therefore the agent must be aware of parts of the input that are possibly another agent's responsibility. This is against the agent oriented programming style where an agent should only care about its own domain and should not worry about other domains. Therefore <exists> should always be avoided if possible. There is usually a better way to write the policies or configure the agent network to avoid the usage of <exists>.

5.6.3.3 Token Matching Condition

[0565] This unary operator defines the type of token matching applied to token terminals and file terminals. There are 6 types of token matching:

<exact>

<substring>

<accent>

<accent-substring>

<accent-edit-difference>

[0566] For details on using these condition with combination to file terminal (/F) please refer to the section on file terminals.

5.6.3.3.1 <exact>

[0567] An input token matches a terminal token only if they are the same length and all their characters are exactly the same.

[0568] <Exact> Condition

• • [0569] P1:
  • [0570] Condition: <exact>‘malkovich’
  • [0571] User-Input: ‘malkovic’
  • [0572] Claim: malkovic
  • [0573] The condition will not apply.
    5.6.3.3.2 <substring>

[0574] Two tokens match only if there is an exact match or:

• • [0575] a) Both tokens are larger than 3 characters (this number can be changed in ParserParameters.xml).
  • [0576] b) The beginning characters must have an 80% match, starting with the first characters. This percentage can be changed in ParserParameters.xml

[0577] If the size of input token getting matched is less than the size of pattern, the input token will be claimed otherwise only the matched part of the input token will get claimed.

[0578] Substring Matching

• • [0579] P1:
  • [0580] Condition: <substring>‘malkovich’
  • [0581] User-Input: ‘malkovic’
  • [0582] The condition will apply (note that the length of user input is less than the pattern's)
  • [0583] Claim: malkovic
  • [0584] P1:
  • [0585] Condition: <substring> ‘malkovich’
  • [0586] User-Input:‘malkovichab’
  • [0587] The condition will apply (note that the length of user input is greater than the pattern's).
  • [0588] Claim: malkovich
  • [0589] P1:
  • [0590] Condition: <substring> ‘malkovich’
  • [0591] User-Input: ‘malkovi’
  • [0592] The condition will not apply because it does not satisfy the 80% match.
  • [0593] Claim: N/A
  • [0594] P1:
  • [0595] Condition: <substring> ‘malkovich’
  • [0596] User-Input: ‘alkovich’
  • [0597] The condition will not apply because the starting characters do not match.
  • [0598] Claim: N/A
    5.6.3.3.3 <accent>

[0599] Tokens are matched using a rule-based collator.

5.6.3.3.4 <accent-substring>

[0600] Similar to a substring matcher but <accent-substring> matches the characters using a collator.

5.6.3.3.5 <accent-edit-difference>

[0601] Matches two tokens using a rule based collator. The match allows missing or extra characters (less than a certain threshold currently defined in ParserParameters.xml). Tokens are matched only if they are larger than a certain length (currently defined in ParserParameter.xml).

5.6.3.3.6 Using Multiple Matchers

[0602] More than one token matching might be used to match terminal tokens. The matching will then be applied to the tokens one by one. If the first matching does not make a claim, the next matching in the list will be used.

[0603] Using Multiple Matches

• • [0604] P1
  • [0605] Condition: <exact , substring> ‘malkovich’
  • [0606] User-Input: ‘being john malkovic’
  • [0607] The condition will apply, and will mark the following: ‘malkovic’ (substring match)

[0608] The default matching used are: <exact, substring>.

[0609] Default Matches (<Exact, Substring>)

• • [0610] P1
  • [0611] Condition: ‘malkovich’
  • [0612] User-Input: ‘john malkovic’
  • [0613] The condition will apply, and will mark the following: ‘malkovic’ (substring match)

[0614] Token matching types could be also applied to file terminals (changing their default matchings)

[0615] Matching Types Applied to File Terminals

• • [0616] MN.txt:
  • [0617] sixth sense
  • [0618] being john malkovich
  • [0619] the wall
  • [0620] ---------------------------------------------------
  • [0621] Condition: <exact, substring>/F ‘MN.txt’
  • [0622] User-Input: malkovich and sixth sense
  • [0623] The condition will apply and only one claim will be made:
  • [0624] ‘sixth sense’

[0625] Each token matching type has a value, which shows how restrictive it is. The restrictive-ness values is a constant, predefined heuristically:

Exact (100)

Substring (60)

Accent (50)

Accent-Substring (85)

Accent-Edit-Difference (50)

5.6.3.3.7 Fast Matchers (<exact>, <substring>)

[0626] The matchers are categorized into fast and flexible matchers. The fast matchers are: <exact> and <substring>.

5.6.3.3.8 Flexible Matchers(<exact>, <substring>,<accent>, <accent-substring>, <accent-edit-difference>)

[0627] The flexible matchers include all fast matchers and the accent>, <accent-substring> and <accent-edit-difference> matchers. These matchers are not included into the development platform by default unless the parserParameter.xml would be changed to include them by replacing the following line:

<Policy:TokenMatchers value=“fast”/>

With:

<Policy:TokenMatchers value=“flexible”/>

Note: It is not recommended to use the flexible matchers as they have a very poor performance.

5.6.3.4 Unknown Condition (<unknown if missing> operand)—deprecated:

[0628] Checks if the operand has claims. If this is true it will make the claim(s). If this is false, it will change the state of the claim to unknown (i.e. the operand is unknown). If a claim with unknown is actuated the system can prompt the user for clarification. How this prompting works and the attributes of the policies involved are discussed in section 4 (Actions).

[0629] Unknown Condition

• • [0630] P1:
  • [0631] Condition: ‘starring’ <unknown if missing> MOVIESTAR
  • [0632] User-Input: starring siamak
  • [0633] The condition will apply. P1 will claim ‘starring’, and change the state of the claim to unknown.

[0634] Unknown Condition

• • [0635] P1:
  • [0636] Condition: ‘starring’<unknown if missing>MOVIESTAR
  • [0637] P2:
  • [0638] Condition: ‘starring’ <unknown if missing> <exists>MOVIESTAR
  • [0639] User-Input: starring bruce willis
  • [0640] P1 and P2 will both apply without changing the state of the claim.
  • [0641] P1 will claim the whole input but P2 will only claim ‘starring’.

[0642] The <unknown if missing> operator is deprecated and it is recommended to use other approaches for dialoging (refer to section 6 for more information).

5.6.3.5 Recursive Condition (operand+):

[0643] The recursive condition makes new claims by merging subsets of the claims made by the operand. Specifically, each claim made by the recursive condition is the result of merging claims that form a maximal disjoint subset of the set of claims made by the operand. Two claims are said to be disjoint if their focuses do not overlap (that is, the intersection of their focuses is null). A set of claims is disjoint if every claim in the set is disjoint to every other claim in the set. A set is maximal if it is not a subset of any other set.

[0644] +Condition

• • [0645] MN.txt:
  • [0646] sixth sense
  • [0647] being john malkovich
  • [0648] ---------------------------------------------------
  • [0649] Policy without Recursive Condition:
  • [0650] P1:
  • [0651] Condition: (/F ‘MN.txt’)
  • [0652] User-Input: ‘being john malkovich and’ ‘sixth sense’
  • [0653] The condition will apply and will make two claims.
  • [0654] The claims (in order) will mark the following:
    • [0655] 1. ‘being john malkovich’
    • [0656] 2. ‘sixth sense’
  • [0657] Policy with Recursive Condition:
  • [0658] P1:
  • [0659] Condition: (/F ‘MN.txt’)+
  • [0660] User-Input: ‘being john malkovich and ‘sixth sense’
  • [0661] The operand makes the two claims above. The disjoint subsets of the operand claims are {1} (the set containing claim 1), {2} (the set containing claim 2), and {1, 2} (the set containing claims 1 and 2). The sets {1} and {2} are not maximal because they are subsets of {1, 2}. Therefore, the recursive condition will make a claim by merging claims 1 and 2. The claim will mark the following:
    • [0662] 1. ‘being john malkovich’, ‘sixth sense’

[0663] +Condition

• • [0664] MN.txt:
  • [0665] fifth sense
  • [0666] sixth sense
  • [0667] being john malkovich
  • [0668] ---------------------------------------------------
  • [0669] P1: (/F ‘MN.txt’)+
  • [0670] User-Input =‘being john malkovich and sixth sense’ The condition will apply and will make two claims. The claims (in order) will mark the following:
    • [0671] 1. ‘being john malkovich’, ‘sixth sense’
    • [0672] 2. ‘being john malkovich’, ‘sense’
  • [0673] Note that a claim is not made by combining the operands's claims on ‘sixth sense’ and ‘sense’ because the two claims are not disjoint. Another way to look at this is that merging these two claims would make an ambiguity. The recursive condition is not allowed to make new claims that have ambiguities.

[0674] A policy condition should not reference a recursive condition.

[0675] Policies Containing Recursive Conditions Should not in General be Referenced by Other Policies. The Recursive Condition Does not Generate all Possible Inner-Products.

• • [0676] AB: ‘a b’
  • [0677] C: ‘c’
  • [0678] CD: ‘c d’
  • [0679] P1: (AB | C)+
  • [0680] RECURSIVE: (P1 | CD)+
    • [0681] 0 2 4 6
  • [0682] input: a b c d
  • [0683] claims made by P1 recursive operand:
    • [0684] 1. AB: a b [0.2]
    • [0685] 2. C: c [4]
    • [0686] 3. CD: c d [4.6]]
  • [0687] maximal disjoint subsets for AB and C:
    • [0688] {1,2}
  • [0689] claims made by P1:
    • [0690] 1. (AB, C): a b c [0.2.4]—best claim made by P1 Note that P1 does not propagage claims made by AB and C individually because the claims are each individually subsets of the maximal disjoint subset (1,2).
  • [0691] claims made by RECURSIVE:
    • [0692] 1. (AB, C): a b c [0.2.4]
    • [0693] 2. CD: c d [2.4]—best claim made by RECURSIVE

[0694] An Example of Referencing Recursive Conditions in a Policy that Might go Unnoticed.

• • [0695] P1: ‘a’ ‘b’+
  • [0696] Here the recursive condition is actually being referenced by the adjacent condition.

[0697] Be careful of the common mistake illustrated in the following example, in which A agent is downchain of Top agent:

[0698] Common Mistake in +Operand Usage

• • [0699] A agent's policies:
  • [0700] P1: ‘a’
  • [0701] TOP agent's policies:
  • [0702] P1: A+
  • [0703] User-input =‘a a a’
  • [0704] The condition in TOP agent will apply and will only claim the first ‘a’ in the input (default criterion)

[0705] It might be expected that the TOP agent in the above example should claim the whole input ([0 . . . 0] [2 . . . 2] [4 . . . 4]). The reason it does not is that Agent A passes only its best claim up to the TOP agent. In other words, the recursive condition (like all other conditions) does not affect how a down chain agent makes claims on the input. If multiple claims on character ‘a’ are required, then Agent A should have a recursive condition of its own:

[0706] Correct Usage of +Operands

• • [0707] A agent's policies:
  • [0708] P1: ‘a’
  • [0709] P2: P1+
  • [0710] TOP agent's policies:
  • [0711] P1: A+
  • [0712] User-input ‘a a a’
  • [0713] The condition in TOP agent will apply and will claim all ‘a’s in the input.

[0714] In the latter example it is not necessary to have the recursive condition in the TOP agent. However, a good practice is to use a “catch all” policy, which applies the recursive condition to all of an agent's policies and down chain agents.

[0715] When two claims are merged using the recursive condition (and similarly the combo condition) then the resulting claim will have a loose connection. Claims with loose connections will fail to merge to other claims using the grammatical operators (such as &,<and adjacent).

[0716] Incorrect Usage of +Operands

• • [0717] P1: ‘a’+
  • [0718] P2: P1 & ‘c’
  • [0719] Input: a a c
  • [0720] P2 will not apply.
    Performance Note: The performance of the recursive condition depends on the input and the claims made by the operand. The recursive condition has a built in time-out to limit the amount of time that will be spent in the condition. This time-out is currently set to twenty seconds. When the maximum allowed time has elapsed, the condition returns the set of claims generated up to that point. Each claim will indicate that it was made by a timed-out condition. This set will not necessarily include the best possible result. The algorithm starts by making claims that involve the best operand claim. The assumption is that these will most likely create the best overall claims.

[0721] Timing Out in Recursive Condition

• • [0722] P1: ‘a’
  • [0723] P2: P1+
  • [0724] User-input=‘a a a . . . a’
  • [0725] The recursive condition can handle about 180 ‘a’s in 20 seconds. If the number of ‘a’s goes above this, the condition will time out and return the results generated so far. The message ‘had enough in recursive condition’ will be logged in the err.txt file, and the resulting claim will be tagged as timed out.

[0726] Recommended usage of the recursive operator is only in the catch policy (described later in the reference).

5.6.3.6 Repeat Condition (^)

[0727] The repeat condition is used to repeat the application of the AND (&), ORDERED (<) or adjacent operators. The following table illustrates the behavior of each repeat operator:

[0728]

	Repeat operator	What it means
	A&{circumflex over ( )}B	A&B&B&B&B . . .
	A<{circumflex over ( )}A	A<B<B<B<B<B . . .
	A{circumflex over ( )}B	A B B B B B . . .

[0729] {circumflex over (+)} Operand

• • [0730] P1: ‘book’ | ‘toy’ | ‘shirt’
  • [0731] P2: P1 ‘and’ P1
  • [0732] User-Input: ‘book and toy and shirt’
  • [0733] Condition P2 will apply and will make two claims:
    • [0734] 1. ‘book and toy’
    • [0735] 2. ‘toy and shirt’.
  • [0736] Now consider replacing P2's condition:
  • [0737] P2: P1 ^ (‘and’ P1)
  • [0738] Condition P2 will apply and will make three claims:
    • [0739] 1. ‘book and toy and shirt’
    • [0740] 2. ‘book and toy’
    • [0741] 3. ‘toy and shirt’

[0742] &^ Operand

• • [0743] P1: ‘a’ &^ ‘b’
  • [0744] User-Input: ‘b b a b b x b’
  • [0745] Condition P1 will apply and will make the claim ‘b b a b b b’.

[0746] <^ Operand

• • [0747] P1: ‘a’<^ ‘b’
  • [0748] User-Input: ‘b b a b b x b’
  • [0749] Condition P1 will apply and will make the claim ‘a b b b’.

[0750] ^ Operand

• • [0751] P1:‘a’ ^ ‘b’
  • [0752] User-Input: ‘b b a b b x b’
  • [0753] Condition P1 will apply and will make the claim ‘a b b’.

[0754] Note that repeat condition cannot be applied to OR and COMBO conditions conceptually.

5.6.4 Tag Condition (<tag: >operand):

[0755] Tags claim(s) made by an operand. The tags may be accessed later by the check tag condition. Tag is used to classify claims. Classifying claims allows a policy to know if the claim belongs to it or not.

[0756] Tag Condition

• • [0757] MN.txt:
  • [0758] being john malkovich
  • [0759] ---------------------------------------------------
  • [0760] P1:
  • [0761] Condition: <tag: ‘movie-name’ >(/F ‘MN.txt’)+
  • [0762] User-Input: ‘john malkovich’
  • [0763] The condition will apply making one claim.
  • [0764] The claims (in order) would mark the following:
  • [0765] ‘being john malkovich’ (tag=‘movie-name’)

[0766] Using tags and check tags means that an agent has to be aware of policies of another agent (which could be a policy of an agent which is not an immediate down chain). This is against the agent oriented programming style where an agent should not care about the policies of another agent and should not be aware of any agent other than its immediate down chains. Therefore tags and check tags should be avoided if possible. There is usually a better way to write the policies or configure the agent network to avoid the usage of tags.

0.5.6.4.1 Check Tag Condition (<check tag:> operand):

[0767] Filters out all claims made by an operand that does not have a specific tag.

[0768] Check Tag Condition

• • [0769] MN.txt:
  • [0770] being john malkovich
  • [0771] MS.txt:
  • [0772] john malkovich
  • [0773] MOVIE agent policies:
  • [0774] P1:
  • [0775] Condition: <tag: ‘movie-name’> (/F ‘MN.txt’)+
  • [0776] P2:
  • [0777] Condition: <tag: ‘movie-star’> (/F ‘MS.txt’)+
  • [0778] CINEMA agent policies:
  • [0779] P3:
  • [0780] Condition: <check tag: ‘movie-star’> MOVIE
  • [0781] P4:
  • [0782] Condition: <check tag: ‘movie-name’> MOVIE
  • [0783] User-Input: ‘john malkovich’
  • [0784] The condition will apply, and CINEMA will make two claims.
  • [0785] The claims would mark the following:
  • [0786] ‘john malkovich’ belongs to P4
  • [0787] ‘john malkovich’ belongs to P3

[0788] Now that the claim is tagged the CINEMA agent knows which policy in MOVIE agent made the claims.

[0789] Using tags and check tags means that an agent has to be aware of policies of another agent (which could be a policy of an agent which is not an immediate down chain). This is against the agent oriented programming style where an agent should not care about the policies of another agent and should not be aware of any agent other than its immediate down chains. Therefore tags and check tags should be avoided if possible. There is usually a better way to write the policies or configure the agent network to avoid the usage of tags.

5.6.5 Binary Conditions

[0790] Binary condition merges claims made by two operands at the left and the right of a binary operator.

[0791] 5.6.5.1 OR Condition (operand1|operand2):

[0792] Will apply only if at least one of the left or right operands has claims.

[0793] | condition

• • [0794] P1:
  • [0795] Condition: ‘willis’ | ‘malkovich’
  • [0796] User-Input: ‘willis’
  • [0797] The condition will apply, and will claim willis as the input.
  • [0798] User-Input: ‘willis or malkovich’
  • [0799] The condition will apply, and will make two claims.
  • [0800] The claims (in order) would mark the following:
  • [0801] ‘malkovich’
  • [0802] ‘willis’
    5.6.5.2 AND Condition (operand1 & operand2):
    Will apply only if both left and right operands have claims.

[0803] AND Condition

• • [0804] P1:
  • [0805] Condition: ‘john’ & ‘malkovich’
  • [0806] User-Input: ‘malkovich whose first name is john’
  • [0807] The condition will apply, and will mark the following:
  • [0808] ‘malkovich’ ‘john’.
  • [0809] User-Input: ‘john’
  • [0810] The condition will not apply.

[0811] The AND condition will apply only to those claims that have no loose connections.

[0812] AND Condition on Claims with Loose Connections

• • [0813] P1:
  • [0814] Condition: ‘send’, ‘receive’
  • [0815] P2:
  • [0816] Condition: P1 & ‘email’
  • [0817] User-Input: send and receive email’
  • [0818] Condition P2 will apply, and will claim the following:
  • [0819] ‘receive email’
  • [0820] ‘send email’.
    5.6.5.3 ORDERED Condition (operand1<operand2):

[0821] Will apply only if both left and right operands have claims and the part of the input claimed by the left operand should come before the part of input claimed by right operand.

[0822] ORDERED Condition

• • [0823] P1:
  • [0824] Condition: ‘john’ <‘malkovich’
  • [0825] User-Input: ‘john whose family name malkovich’
  • [0826] The condition will apply, and will claim ‘john’ and ‘malkovich’.
  • [0827] User-Input: ‘malkovich whose first name is john’
  • [0828] The condition will not apply.

[0829] The ORDERED condition will apply only to those claims that have no loose connections.

5.6.5.4 ADJACENT Condition (operand1 operand2):

[0830] Will apply only if both left and right operands have claims, and the left operand claim appears just before (adjacent to) the right operands claim.

The claims made by left and right operands are merged, the resulting claim will be accepted only if the adjacency score of the merged claim is 0.

[0831] ADJACENT Condition

• • [0832] P1:
  • [0833] Condition: ‘john’ ‘malkovich’
  • [0834] User-Input: ‘john malkovich’
  • [0835] The condition will apply, and will claim the whole input.
  • [0836] User-Input: ‘john smith malkovich’
  • [0837] The condition will not apply. As the adjacency score of the merged claim is 1.

[0838] The ADJACENT condition will apply only to those claims that have no loose connections.

5.6.5.5 COMBO Condition (operand1, operand2):

[0839] Will try to join the left and right operands to make all combinations of ambiguous or non-ambiguous claims.

[0840] COMBO Condition

• • [0841] P1:
  • [0842] Condition: <exact> ‘johhn malkovich’ | <exact> ‘bruce willis’
  • [0843] P2:
  • [0844] Condition: <exact> ‘being johhn malkovich’ | <exact> ‘sixth sense’
  • [0845] P3:
  • [0846] Condition: P1, P2
  • [0847] User-Input: ‘bruce willis and john malkovich’
  • [0848] P3 will make three claims.
  • [0849] The claims (in order) are:
  • [0850] ‘john malkovich’ (ambiguous, belongs to P1 or P2), ‘bruce willis’ (belongs to P1)
  • [0851] ‘john malkovich’ (non-ambiguous, belongs to P1), ‘bruce willis’ (belongs to P1)
  • [0852] ‘john malkovich’ (non-ambiguous, belongs to P2), ‘bruce willis’ (belongs to P1)
  • [0853] ‘john malkovich’ (ambiguous, belongs to P1 or P2)
  • [0854] ‘john malkovich’ (non-ambiguous, belongs to P1)
  • [0855] ‘john malkovich’ (non-ambiguous, belongs to P2)
  • [0856] ‘bruce willis’ (belongs to P1)
    Note: This is the only condition that can make ambiguous claims.

[0857] Claims may not be merged together using a combo condition if the merge would cause ambiguity and one claim has a higher priority or a better connection.

[0858] When Priority Prevents Ambiguity

• • [0859] P1: ‘a’
  • [0860] P2: ‘a’ {priority: 1}
  • [0861] P3: P1,P2
  • [0862] Input: a
  • [0863] The result will not be ambiguous as the priority of claim made by policy P2 is higher thab the priority of policy P1.

[0864] A better connection is defined to be based on the weight of the worst operator or operand used in a claim. The operators in order of weight are: adjacent, <,&. All operands in a claim have the same weight as the adjacent operator except for operands coming from the inexact matches of a database agent or a variable condition which have a weight worse than & and better than the combo (that weight is shown in the claim view as an INEXACT or INEXACT or ˜).

[0865] When Connection Prevents Ambiguity

• • [0866] P1: ‘a’ ‘b’ ‘c’
  • [0867] P2: ‘a’ ‘b’ &‘c’
  • [0868] P3: P1,P2
  • [0869] Input: a b c
  • [0870] P3 will not make an ambiguous claim as P1's claim has a better connection (adjacent vs. &)

[0871] Note that the number of operators will not make any difference here:

[0872] When Connection Does not Prevent Ambiguity

• • [0873] P1: ‘a’ &‘b’&‘c’
  • [0874] P2: ‘a’ &‘b’ ‘c’
  • [0875] P3: P1,P2
  • [0876] Input: a b c
  • [0877] P3 will be ambiguous as P1's claim has the same worst operator as the P2's claim (both are &)

[0878] When two claims are merged using the combo condition (and similarly the recursive, +, condition) then the resulting claim will have a loose connection. Claims with loose connections will fail to merg to other claims using the grammatical operators (such as &, <and adjacent).

[0879] Incorrect Usage of Combo Condition

• • [0880] P1: ‘a’,‘b’
  • [0881] P2: P1 & ‘c’
  • [0882] Input: a b c
  • [0883] P2 will not apply.

[0884] The adjacency score of a claim made by a combo condition is not calculated directly from the focus of the claim (see adjacency score in Claim section). Instead it is calculated to be the sum of the adjacency scores of the sub-claims. For example, if P1 claims ‘cat’ and ‘mouse’ on the input ‘cat dog mouse’ and P2 claims ‘dog’, the adjacency score of (P1, P2) will be 1, whereas the adjacency score of (P1 & P2) will be 0. If P1 claims ‘cat’ on the input ‘cat and dog’ and P2 claims ‘dog’, the adjacency score of (P1,P2) will be 0, whereas the adjacency score of (P1 & P2) will be 1.

[0885] Recommended usage of combo operator is only in the catch policy (described later in the reference).

6 Actions

[0886] Actions transfers a claim to a standard format (e.g. an object containing XML)

6.1 Action types:

6.1.1 Action:

[0887] The action that can be carried out unambiguously. The fields are: Delegate To; Execute; Explain; and Ask.

• • [0888] Delegate to: This field is used to delegate the actuation of a claim to other agents or policies responsible for making the claim. If you use this field the other fields would be ignored.
  • [0889] Execute: The part that is ready to be executed by the application. This would be in a language of the application you're building the interface for (e.g. XML).
  • [0890] Explain: Human readable explanation of what was interpreted by the system (deprecated).
  • [0891] Ask: A question to be asked from the user to narrow down the result. The agent that asks the question gets priority (focus). The agent asking the question should be the same agent that could claim the answer (refer to section 6 for more information).

[0892] Ations

• • [0893] TV: [‘TV’] ‘on’
  • [0894] {title: ‘TV’}
  • [0895] {action: {execute: ‘TV ON!’} {explain: ‘You asked to turn the TV on.’}
  • [0896] VCR: [‘VCR’] ‘on’
  • [0897] {title: ‘VCR’}
  • [0898] {action: {execute: ‘VCR ON!’} {explain: ‘You asked to turn the VCR on.’}
  • [0899] HOME_ENTERTAINMENT: TV,VCR
  • [0900] {title: ‘HOME_ENTERTAINMENT’}
  • [0901] {action: delegate to TV, VCR}
  • [0902] {ambiguity action: delegate to TV, VCR}
  • [0903] User Input: TV on and VCR off
  • [0904] Actuation:
  • [0905] You asked to turn the TV on. You asked to turn the VCR on.
  • [0906] TV ON! VCR ON!
    6.1.2 Ambiguity:

[0907] The action that will be carried out when there is an ambiguity in the claim. This action item is only used to delegate actuation to the overlapping sub claims that have caused the ambiguity. The sub claims, which caused the ambiguity, would be actuated normally and their actuations would be put together to make the ambiguity choices.

• • [0908] Delegate to: This field is used to delegate the actuation of a claim to other agents or policies responsible for making the claim. If you use this field the other fields would be ignored.
  • [0909] Execute: The part that is ready to be executed by the application. This would be in a language of the application you're building the interface for (e.g. XML).
  • [0910] Explain: Human readable explanation of what was interpreted by the system (deprecated).
  • [0911] Choice: A question to be asked from the user to resolve the ambiguity. The choices should refer to the agents or policies that caused the ambiguity.

[0912] For example lets say the TV and VCR policies would have an overlapping claim that has been put together by HOME_ENTERTAINMENT policy:

[0913] Ambiguity

• • [0914] TV: [‘TV’] ‘on’
  • [0915] {title: ‘TV’}
  • [0916] {action: {execute:‘<TV value=on />’} {explain: ‘You asked to turn the TV on.’}
  • [0917] VCR: [‘VCR’] ‘on’
  • [0918] {title: ‘VCR’}
  • [0919] {action: {execute: <VCR value=on />} {explain: ‘You asked to turn the VCR on.’}
  • [0920] HOME_ENTERTAINMENT: TV,VCR
  • [0921] {title: ‘HOME_ENTERTAINMENT’}
  • [0922] {action: delegate to TV, VCR}
  • [0923] {ambiguity action: delegate to TV, VCR}
  • [0924] Which one do you mean?
  • [0925] You asked to turn the TV on. You asked to turn the VCR on.
    • [0926] 1. TV
    • [0927] 2. VCR

[0928] When the system receives the input: ‘on’. The HOME_ENTERTAINMENT claim will then be ambiguous (as the claims made by TV and VCR would overlap). So the actuation made by the HOME_ENTERTAINMENT would be based on actuations made by TV and VCR policies. The actuation would be a multi choice menu. The menu prompt would be the made by putting together the explain actions of the TV and VCR actuations, and the menu items would be the titles of TV and VCR policies.

[0929] The explain field is now being deprecated. Instead the execute field will replace the explain field (when it is not provided):

[0930] Ambiguity using Execute Field

• • [0931] TV: [‘TV’] ‘on’
  • [0932] {title: ‘TV’ }
  • [0933] {action: {execute: ‘TV ON!’}
  • [0934] VCR: [‘VCR’] ‘on’
  • [0935] {title: ‘VCR’}
  • [0936] {action: {execute: ‘VCR ON!’}
  • [0937] HOME_ENTERTAINMENT: TV,VCR
  • [0938] {title: ‘HOME_ENTERTAINMENT’}
  • [0939] {action: delegate to TV, VCR}
  • [0940] {ambiguity action: delegate to TV, VCR}
  • [0941] User-Input: On
  • [0942] System:
  • [0943] Which one do you mean?
  • [0944] <TV value=on /> <VCR value=on />
    • [0945] 1. TV
    • [0946] 2. VCR

[0947] The idea is that a scripting language would then take the interaction and make the proper prompt.

[0948] There are situations where there could be more than one questions asked for an ambiguity. For example the input bass in the network of FIG. 6 could generate ambiguity between FISH and DRUM or INSTRUMENTS and HOBBIES. The input ‘bass’ causes ambiguity in the HOBBIES agent (as bass could be a fish or a drum) and in the top agent (as bass can be a hobby or an instrument). Currently the system will find the source of the ambiguity and will only generate a question asking about that (in this case the source of ambiguity is if bass is a fish or a drum).

[0949] More than One Ambiguity

[0950]

	(TOP:
	″
	(HOBBIES, INSTRUMENTS) +
	″)
	(HOBBIES:
	″
	(FISH, DRUM) +
	″)
	(INSTRUMENTS:
	″
	(DRUM) +
	″)
	(DRUM:
	″
	(‘bass’) +
	″)
	(FISH:
	″
	(‘bass’) +
	″)
	User: bass
	System:
	Which one do you mean?
	1: FISH
	2: DRUM
	3: Ignore input
	Selection (choose one):

Known Issue:

[0951] There are network patterns that might lead to a too ambiguous situation. The following example demonstrates this situation. (See FIG. 7).

[0952] Too Ambiguous Error

[0953]

	(HOBBIES:
	“
	(INSTRUMENTS, DRUM) +
	”)
	(INSTRUMENTS:
	“
	(DRUM) +
	”)
	(DRUM:
	“
	(‘bass’) +
	”)
	User: bass
	System:
	Input too ambiguous. Please rephrase!

6.1.3 Unknown Action (Deprecated):

[0954] The action that will be carried out if the claim has unknown (there are missing information in the input). The same four fields are available.

• • [0955] Delegate to: This field is used to delegate the actuation of a claim to other agents or policies responsible for making the claim. If you use this field the other fields would be ignored.
  • [0956] Execute: The part that is ready to be executed by the application. This would be in a language of the application you're building the interface for (e.g. XML).
  • [0957] Explain: Human readable explanation of what was interpreted by the system (deprecated).
  • [0958] Ask: A question to be asked from the user to narrow down the result. The agent that asks the question gets priority (focus). The agent asking the question should be the same agent that could claim the answer.
    6.2 Action Building Blocks

[0959] Each field in the action forms (e.g. execute, explain, ask and choice) is created using variety of building blocks. When actuated each building block generates an output. These outputs would be put together to make the final action. Building blocks could be:

6.2.1 Strings

[0960] Outputs any information entered in quotes.

[0961] String Action Block

[0962]

P1:
‘bruce willis’
	{title: ‘movie star’}
	{action:
	{explain: ‘You asked for a movie star’ } }
User-Input: bruce willis
P1 will make a claim. If the claim would be delegated to policy P1 then
the action would be: ‘You asked for a movie star’.

[0963] 6.2.2 Star (*)

[0964] Outputs which part of the input was claimed by a policy.

[0965] Star Action Block

[0966]

P1:
	‘bruce willis’
	{title: ‘movie star’}
	{action:
	{execute: *}
User-Input: bruce willis
P1 will make a claim. If the claim would be delegated to policy P1 then
the action would be: ‘bruce willis’.

6.2.3 Variable (?)

[0967] Shows which part of the input was marked as a variable in a claim. The variable action corresponds to the variable condition in the policy with the same name.

[0968] Variable Action Block

[0969]

P1:
	‘starring’ ?:MOVIESTAR /DELIMITER
	{title: ‘movie star’}
	{action: delegate to P1}
	{action:
	{execute: ‘who is the movie star ’,
	?:MOVIESTAR ,‘ you are looking for?’} }
User-Input: starring siamak
P1 will make a claim. If the claim would be delegated to policy P1 then
the action would be:
Who is the movie star siamak you are looking for?

[0970] It is recommended to always use names with variables. However this is how multiple unnamed variables are handled:

[0971] Not Recommended Usage

[0972]

P1:
	‘send email from’ ? ‘to’ ?
	{action: delegate to P1}
	{action:
	{execute: ? } }
User-Input: send email from Siamak to Kristi
P1 will make a claim. If the claim would be delegated to policy P1 then
the action would be: Siamak Kristi

[0973] Note that variable trims the leading and trailing delimiters, but other delimiters are considered to be part of the variable. Multiple variables are trimmed after they are combined.

[0974] Variable Trimmings

[0975]

P1:
	‘being’ ? ‘.’
	{action: delegate to P1}
	{action:
	{execute: ‘var:’,?,‘.’ } }
User-Input: being  john  malkovich.
P1 will make a claim. If the claim would be delegated to policy P1 then
the action would be: var:john  malkovich.

6.2.4 Policy Reference

[0976] Used as a reference to an action part of another policy.

[0977] Policy Reference Action Block

[0978]

	P1:
	‘bruce willis’
	{title: ‘movie star’}
	{action:
	{execute: ‘<movie-star=’ , * , ‘</>}
	P2:
	‘starring’ P1
	{title: ‘movie name’}
	{action:
	{execute: P1} }
User-Input: starring bruce willis
P1 will make a claim. If the claim would be delegated to policy P2 then
the action would be delegated to P1
	(the final result would be <movie-star=bruce willis</>)

6.2.5 Agent Reference

[0979] Used when the action part of another agent should be used to build this element.

[0980] Agent Reference Action Block

[0981]

(In VOLUME agent)
P1:
DOWN
	{title: ‘movie name’}
	{action:
	{execute: ‘<volume=’ ,DOWN,‘ />’} }
(In DOWN agent, downchain of the Volume agent)
P1:
‘down’
	{title: ‘movie name’}
	{action:
	{execute: ‘down’} }
User-Input: down
Policy P1 in VOLUME agent will make a claim. If the claim would be
delegated to this policy then the action would be delegated to DOWN
agent (the final result would be <volume=down</>)

6.2.6 Set Message (Set (Agent, Property, Key; Value))

[0982] The condition, set (agent, property, key; value), will cause the agent to sends a message to set a property in another agent. There are two types of properties that may be accessed through messaging:

[0983] c. Data property (basic objects)

[0984] d. Data store property (collection objects: hash tables, vectors, . . . )

[0985] Each agent must allow access to its data property by declaring it as a valid data property. The methods that should be sub-classed for this purpose are summarized in the following table:

[0986]

	Access
	permission	Set method	Set message
Data	public Boolean	public void	<set (agent,
Property	IsValidData-	setData(	property;
	Property(String	String propertyName,	value)>
	propertyName)	Object value,
		ChainIdentifier
		chainID)
Data	public Boolean	public void	<set (agent,
Store	IsValidDataStore-	setDataStoreElement(	property,
Property	Property(String	String propertyName,	key; value)>
	propertyName)	String propertyKey,
		Object propertyValue,
		ChainIdentifier
		chainID)

[0987] All AAOSA agents have a STATE property that could be set (STATE is a basic property).

[0988] The parameters of a set message, set (agent, property, key; value), are:

Agent: The agent address that its property is to be set. This parameter is optional. If omitted then an agent will “get” its own property.

Property: The name of the property to be set.

Key: The key to the data store property (as a string). This parameter is optional. If omitted then an agent will “get” a basic property.

Value: The value that the property should be set to (as a string).

[0989] Set Action Block.

• • [0990] action: set (CLOCK, ‘TIME’; ‘12:30’)
    6.2.7 Get Message (<get (agent, property, key)>)

[0991] Sends a get message to an agent, and shows the value replied by that agent. There are two types of properties that may be accessed through messaging:

[0992] e. Data property (basic objects)

[0993] f. Data store property (collection objects: hash tables, vectors, . . . )

[0994] Each agent must allow access to its data property by declaring it as a valid data property. The methods that should be sub-classed for this purpose are summarized in the following table:

[0995]

	Access permission	Set method	Set message
Data	public Boolean	public Object	<get (agent,
Property	IsValidData-	getData(	property)>
	Property(String	String propertyName,
	propertyName)	ChainIdentifier
		chainID)
Data	public Boolean	public Object	<get (agent,
Store	IsValidDataStore-	getDataStoreElement(	property,
Property	Property(String	String propertyName,	key)>
	propertyName)	String propertyKey,
		ChainIdentifier
		chainID)

[0996] All AAOSA agents have a STATE property (STATE is a basic property).

[0997] The parameters of a get message, set (agent, property, key; value), are:

Agent: The agent address that it's property is to be set. This parameter is optional. If omitted then an agent will “get” its own property.

Property: The name of the property to be set.

Key: The key to the data store property (as a string). This parameter is optional. If omitted then an agent will “get” a basic property.

[0998] Get Action Block.

• • [0999] action: get(CLOCK, ‘TIME’)
    6.3 Default Delegation

[1000] Whenever the action part of a policy is left empty a default delegation would be used. By default actions are delegated to policies responsible for making the sub claims. That is the policy:

• • [1001] POLICY2: AGENT1,AGENT2, POLICY1
    Will be interpreted as:
  • [1002] POLICY2: AGENT1,AGENT2, POLICY1
    • [1003] {action: delegate to AGENT1, AGENT2, POLICY1}
    • [1004] {ambiguity action: delegate to AGENT1, AGENT2, POLICY1}
    • [1005] {unknown action: delegate to AGENT1, AGENT2, POLICY1}

[1006] The default delegation could be overridden by filling the action part. For example the following policy:

• • [1007] POLICY2: AGENT1,AGENT2, POLICY1
    • [1008] {action: {execute: *}}
      Will be interpreted as:
  • [1009] POLICY2: AGENT1,AGENT2, POLICY1
    • [1010] {action: {execute: *}}
    • [1011] {ambiguity action: delegate to AGENT1, AGENT2, POLICY1}
    • [1012] {unknown action: delegate to AGENT1, AGENT2, POLICY1}
      6.4 Actuation

[1013] Each policy can make an actuation by applying the action part to the claim it made. Actuation may be built by putting together other actuations (just like claims). Each actuation will have four arms: execute, explain, ask, and choice. Each arm will contain a list of strings or pointers to other actuations.

[1014] There is a difference when an actuation is converted to a string if the building blocks of the actuation are listed in one field or different fields. When building blocks are listed together there would be no space between each block that is converted to a string.

[1015] Actuation Example

[1016]

P1:
	‘aaa bbb ccc’
	{action:
	{execute: ‘aaa’, ‘bbb’, ‘ccc’}
User-Input: aaa bbb ccc
P1 will make a claim. If the claim would be delegated to policy P1 then
the action would be: aaabbbccc.

[1017] When building blocks are listed in different fields there would be a space inserted between each block that is converted to a string.

[1018] Actuation.

[1019]

P1:
	‘aaa bbb ccc’
	{action:
	{execute: ‘aaa’, ‘bbb’, ‘ccc’}
User-Input: aaa bbb ccc
P1 will make a claim. If the claim would be delegated to policy P1 then
the action would be: aaa bbb ccc.
Implementation note:
The space is actually the default join style. The idea is to have different join styles that could be set in the policy. For example AND joins, OR joins, XOR joins, . . .

7 Putting it all Together

[1020] The agents are normally composed of 3 types of policies:

7.1 Tokens:

[1021] The condition of these policies has no reference to any other agent. The policies are made using binary and unary operators on token conditions, file terminals or database terminals.

7.2 Grammars

[1022] The condition of these policies makes grammatical relationship between the policies in this agent and its down chain agents. These grammatical relationships are made by using &, |, <, optional and adjacent operators. All that can be part of one command should be combined using the &, <or adjacent operators.

7.3 Catch Policy

[1023] The catch policy of an agent is used to make the claims that no policies were written to deal with. That includes different combination of commands and ambiguities that may occur. The catchall policy includes a combo of references to all other policies and down chain agents of that agent followed by a + operator. A | (or) condition should be used instead of a combo between any two policies or down chain agents which should never make ambiguities. For example, assume agents A, B and C are all downchain of Top agent.

TOP agent policies:

P1: . . .

P2: . . .

. . .

CATCH_ALL: (P1, P2, . . . , A, B, C)+

[1024] The following is an example of how a user interface could be built for a store where books and toy in different colors could be bought.

[1025]

Step 1. Create the COLOR agent (See FIG. 8):
(TOKENS:
	“
	(‘red’|‘blue’|‘green’)
	{title:‘A color’}
	{action:
	{execute:‘<color’,*,‘/>’}}
	”),
(RELATION:
	“
	TOKENS {circumflex over ( )} (‘and’ TOKENS)
	{title:‘Colors’}
	”),
(CATCH:
	“
	(TOKENS, RELATION)+
	{title:‘Color’}
	”)
Step 2. Create the BOOK agent as an up chain of the COLOR agent
(FIG. 9):
(TOKENS:
	“
	‘book’
	{title:‘Book’}
	{action:
	{execute: ‘<book>?</book>’}
	{ask:‘Which book?’}}
	”),
(RELATION1:
	“
	COLOR
	{title:‘Book’}
	{action:
	{execute:‘<book> ‘,COLOR, ’ </>}}
	”),
(RELATION2:
	“
	TOKENS & COLOR
	{title:‘Book’}
	{action:
	{execute:‘<book>’,COLOR, ‘ </>’}}
	”),
(RELATION3:
	“
	COLOR TOKENS
	{title:‘Book’}
	{action:
	{execute:‘<book>’,COLOR, ‘ </>’}}
	”),
(CATCH:
	”
	(TOKENS, RELATION1, RELATION2,RELATION3)+
	{title:‘Book’}
	”)
Step 3. Create the TOY agent the same as the BOOK agent and join
BOOK and TOY agents as down chain agents of the STORE agent
(FIG. 10).
(CATCH:
	“
	(BOOK, TOY)+
	”)

8. Best Practices Guidelines for Agent Network Design

[1026] 1) Always include comments in your policies briefly describing why they are there and what they do. In general an observer should be able to understand the logic of why you have coded your agent the way you have. If it is too complex to understand, it is very likely that it needs some cleaning up.

[1027] 2) If there are more than 6 policies in an agent rethink using a single agent for all these policies. It may also be that the agent has too big a fan-out.

[1028] 3) Avoid too many agents reporting to a single agent (larger than 6 fan-out). Add agents to group down-chains into sub networks. Make sure the groupings correlate with the semantics of the application domain. Just as in menu structures, a big fan out is untidy and in our case they can also result in inefficient processing of policies that include operators like ^ or *.

[1029] Categorization is possible and quite natural. After all, this is how our minds work to enhance our memory. It is much harder to memorize 16 down chains for one agent than it is 4, each of which lead to another.

[1030] We should use a domain expert in this case to identify the categorization.

[1031] The merits of limiting the fan out can be summarized as:

• • [1032] Efficiency (memory and speed),
  • [1033] Better reusability,
  • [1034] Better Interactions (where top agent knows input belongs to it but doesn't know which down-chain to delegate it to).

[1035] As for the fan out, if there are many agents down-chain to one, it is very likely that there does exist a categorization for these concepts in the domain expert's lingo that we are missing and we should probably cover. If this is the case, then recategorizing and decreasing the fan out based on the domain classifications and the resulting modularity will make those categories more readily reusable, and the interactions with the application more manageable for the end users. It will also make the policies in the top agent more readable and tidy. This added modularity may also help the efficiency of the application where operators such as “&” or other firm operators are used between all down-chains. This is because it reduces the number of claims the up-chain agent to the top node will be receiving when a policy containing operators such as the “&” of the down chains fires.

[1036] 4) Avoid creating agents that do not represent the semantics of the application.

[1037] 5) Start each agents list of policies with policies that pick the tokens associated with this agent. Then follow with policies that describe the relationships. At the end, include catch-all policies.

[1038] TOKENS: The condition of these policies has no reference to any other agent. The policies are made using binary and unary operators on token conditions, file terminals or database terminals.

[1039] RELATIONS: The condition of these policies describe the relationships between the policies in this agent and its down chain agents. These grammatical relationships are made by using operators such as &, |, <, optional and adjacent. All that can be part of one command should be combined using these operators.

[1040] CATCHALLS: The catchall policy of an agent is used to make the claims that no policies were written to deal with. That includes different combination of commands and ambiguities that may occur. The catchall policy includes a combo of references to all other policies and down chain agents of that agent followed by a + operator. A | (or) condition should be used instead of a combo between any two policies or down chain agents which should never make ambiguities.

[1041] 6) Avoid using catch-alls extensively and try to cover them in Relations policies. For example try using the repeat operator (^) more often.

[1042] 7) Try not to repeat all of the contents of another policy in the following policies. It is inefficient and untidy:

[1043]

	Bad:
	TOKENS: ‘web’ | ‘wap’
	RELATIONS: (‘web’ | ‘wap’) & INDEX
	Good:
	TOKENS: ‘web’ | ‘wap’
	RELATIONS: TOKENS & INDEX

[1044] 8) Any policy on its own may make a claim. Do not have policies that may claim lone words that are not relevant to the agent:

DUMMY_TOKEN: ‘the’

[1045] In this case an agent, THE, should be created which claims ‘the’ but is never delegated to or referred to without constraining conditions around it.

[1046] 9) Avoid using tags. Using “tags” and “check tags” mean that an agent has to be aware of policies of another agent (which could be a policy of an agent that is not an immediate down chain). This is against the agent oriented design principle where an agent should not care about the policies of another agent and should not be aware of any agent other than its immediate down chains. Therefore “tags” and “check tags” should be avoided if possible. There is usually a better way to write the policies or configure the agent network to avoid the usage of tags.

[1047] 10) Avoid using <exists>

RELATIONS: <exists> ‘token’

[1048] When using <exists>, an agent is checking against a part of the input that it is not going to claim. Therefore the agent must be aware of parts of the input that are possibly another agent's responsibility. This is against the agent oriented design principle where an agent should only care about its own domain and not worry about other domains. Therefore <exists> should always be avoided if possible. There is usually a better way to write the policies or configure the agent network to avoid the usage of <exists>.

[1049] There are cases where using <exists> is appropriate as in the example below:

[1050] In this example, we have a top level FIND agent. Below FIND there is a FILETYPE agent and a FOLDER agent. FILETYPE has down-chain agents that recognize specifications for different kinds of files; FOLDER uses down-chain agents to identify specs for starting directories.

[1051] Now imagine a request like “java in web”. Both “java” and “web” are valid file types; both are valid directory nanes. What we wanted to do in FILETYPE is say that if we see a file spec followed by the word ‘in’, to see that as a stronger claim than one without it. Similarly, we want FOLDER to use ‘in’ to indicate that what follows may be a directory spec.

[1052] Clearly, we can't have both agents claiming ‘in’. But ‘in’ is important for both. So we use <exists> to give the policy with ‘in’ a higher priority.

[1053] 11) Avoid policies that may make a null claim:

TOKENS: [‘a’ ]

NULLTOKENS: [‘a’ ] I [‘b’ ]

INTERESTING_TOKENS: [‘a’ & ‘b’ ]

NOTOKENS: <exists>% ‘a’

WOWTOKENS: [‘a’] & <exists> ‘b’

OWTOKENS: <exists> (‘a’ & ‘b’)

9 Precedence table

[1054] The OPAL language guarantees that the operands of operators appear to be evaluated in a specific evaluation order, namely, from left to right.

[1055]

	Precedence	Operator type	Operator
	0	Terminals and	‘sring’
		references	/NUMBER,
			/SYMBOL,
			/TYPE,
			/F
			/DB,
			/IDB,
			<check ( . . . ) >,
			AGENT reference,
			POLICY reference,
			?,
			. . .
	1	Brackets	( operand )
			[ operand ]
			operand+
	2	Unary	<exists> operand
			<check . . . >
			<unknown . . > operand
	3	Binary adjacent	operand1 operand2
			operand1 {circumflex over ( )} operand2
	4	Binary ordered	operand1 < operand2
			operand1 < {circumflex over ( )} operand2
	5	Binary and	operand1 & operand2
			operand1 & {circumflex over ( )} operand2
	6	Binary or	operand1 | operand2
	7	Binary combo	operand1 , operand2
	8	Unary tag	<tag: . . . > operand
			<check tag: . . . > operand
	Notes:
	It is generally a good idea to use parentheses liberally in expressions involving mixed operators to avoid operator precedence problems.

10 Learning

[1056] A followup answer will be learned only if:

[1057] There would be a variable terminal (?) in the condition of the policy.

[1058] The agent asking the question would make a claim on the followup.

11 Claim Manipulation

[1059] The recursive operator (+) and most binary operators (adjacent, &, <,+ and combo) make their claims by merging other claims.

Merging claims:

Two claims C¹ and C² will merge if and only if one of the following conditions would hold:

• • [1060] 1. C_focus¹∩C_focus²=φ (if C¹'s focus does not intersect with C²'s focus)
  • [1061] 2. C_{loose-connection-count}¹=0 and
    • [1062] C_{loose-connection-count}²=0 and
    • [1063] C_focus¹C_focus² and
    • [1064] C_focus²C_focus¹ and
    • [1065] C_priority¹=C_priority² and
    • [1066] (C_connection¹=C_connection² or C_ambiguity¹>0 or C_ambiguity²>0)
  • [1067] 3. Conditions 1 and 2 hold for merging all claims that have been connected loosely to build C¹ and all subclaims that have been connected loosely to build C².
    Ambiguous Claims:
    A claim C made by merging C¹ and C² is ambiguous if their focus' overlap: C_focus¹∩C_focus^2≠φ
    12 Policies in BNF Notation
    12.1 BNF Notation

[1068] The following is the BNF notation used to describe the Policy's syntax:

::=Is interpreted as ‘consists of’ or ‘is defined as’.

( )+ Parenthesis followed by a plus sign indicate that the sequence in the parenthesis may be repeated more than one time.

( )* Parenthesis followed by a plus sign indicate that the sequence in the parenthesis may be repeated zero or more times.

˜( ) Parenthesis preceeded by a not sign indicate that all sequences except those in the parenthesis are legal.

[ ] Square Brackets State that the Sequence in the Brackets is Optional.

< > Names embedded in angle brackets are syntactic elements such as <integers>, <names> etc. All syntactic names will be defined i.e. they will appear on the left side of the ‘::=’ symbol in a grammar rule.

“ ” Characters embedded in double quotes are keywords or characters.

- A dash between two characters defines a range of characters.

For example “0”- “3” is “0” |“1” |“2” |“3”.

| A vertical bar is read ‘or’ and is used to separate alternatives.

[1069] Whenever a BNF notation is used as a keyword in the grammar it is preceded by an escape character: ‘\’.

12.2 Policy's BNF notation

[1070] Here is a BNF notation of the policy's grammar.

[1071]

policy ::=
	label:
	“\”“
	<condition>
	[“{” “title:” <title> “}”]
	[“{” “xml tag:” <string literal> “}”]
	[“{” “xml type:” <string literal> “}”]
	[“{” “priority:” <integer> “}”]
	[“{” “continuation:” (“join”|“replace”) “}”]
	[“{” “action:” <action>}]
	[“{” “ambiguity action:” <action> “}”]
	[“{” “unknown action:” <action> “}”]
	“\””;
<label> ::= [“A” − “Z”|“_” ([“A” − “Z” | “0” − “9” | “_” | “−”])*
<title> ::= <string_literal>
<integer> ::= [+|−] (“0” − “9”)+
<condition> ::= “(” <condition> “)”
<condition> ::= <ADJACENT_condition>
<condition> ::= <ORDERED_condition>
<condition> ::= <AND_condition>
<condition> ::= <OR_condition>
<condition> ::= <COMBO_condition>
<condition> ::= <OPTIONAL_condition>
<condition> ::= <TERMINAL_condition>
<condition> ::= <EXISTS>
<condition> ::= <TAG_condition>
<condition> ::= <CHECK_TAG_condition>
<condition> ::= <CHECK_condition>
<OPTIONAL_condition> ::= “[” <condition> “]”
<UNKNOWN_condition> ::= “<unknown if missing>” <condition>
<ADJACENT_condition> ::=	<condition> <condition> |
	<condition> “{circumflex over ( )}” <condition>
<ORDERED_condition> ::=	<condition> “<” <condition> |
	<condition> “<{circumflex over ( )}” <condition>
<AND_condition> ::=	<condition> “&” <condition> |
	<condition> “&{circumflex over ( )}” <condition>
<OR_condition> ::= <condition> “|” <condition>
<COMBO_condition> ::= <condition> “,” <condition>
<TERMINAL_condition> ::= <terminal>
<EXISTS_condition> ::= “<” “exists” “>” <condition>
<TAG_condition> ::=
	“<” “tag” “:” <string_literal> “>” <condition>
<CHECK_TAG_condition> ::=
	“<” “check” “tag” “:” <string_literal> “>” <condition>
<CHECK_condition> ::=
	“<” “check” “(” <agent_address> “,” <property_name> “,”
	<property_key> “;” <property_value> “)” “>” <condition>
<terminal> ::= <token_provider>
<terminal> ::= <number>
<terminal> ::= <symbol>
<terminal> ::= <agent_name>
<terminal> ::= <policy_name>
<terminal> ::= <variable>
<token_provider> ::=
	[“[” <matcher-list> “]”] “‘” <string_literal> “’”
<token_provider> ::=
	[“[” <matcher-list> “]”] /F “‘” <string_literal> “’”
<token_provider> ::=
	/DB “‘” <string_literal> “’”
<matcher-list> ::=
	“<” (<matcher> | (<matcher> “,” <matcher-list>)) “>”
<matcher> ::=
	“exact” | “substring” |
	“partial” | “accent” |“accent-edit-difference”
<number> ::= “/NUMBER” [ “(” <integer> “,” <integer> “)” ]
<symbol> ::= “/SYMBOL”
<agent_name> ::=
	[“A” − “Z”|“_”] ([“A” − “Z”|“0” − “9”| “_” | “−”])*
<policy_name> ::= (“/P” ([“0” − “9”])+)
<variable> ::= “?”
<string_literal> ::=
	“‘” (~([“\””,“\\”,“\n”,“\r”, “’”]) |
	<special_characters> )* “‘”
<special_characters> ::=
	%BACK_SLASH% | %SINGLE_QUOTE% |
	%DOUBLE_QUOTE% | %NEW_LINE%
<action> ::=
	[“{” “execute:” <action_element_list> “}”]*
	[“{” “ask:” <action_element_list> “}”]*
	[“{” “choice:” <action_element_list> “}”]*
	[“{” “explain:” <action_element_list> “}”]*
<action_element_list> ::=
	<variable_action_element> [“,” <action_element_list>]
<action_element_list> ::=
	<constant_action_element> [“,” <action_element_list>]
<variable_action_element> ::= “*”
<variable_action_element> ::= “?”
<variable_action_element> ::= <agent_name>
<variable_action_element> ::= <policy_name>
<variable_action_element> ::=
	“set” “(” [<agent_address> “,”] <property_name> “,”
	<property_key> “;” <property_value> “)”
<variable_action_element> ::=
“get” “(” [<agent_address> “,”] <property_name> “,”
<property_key> “)”
<constant_action_element> ::= <string_literal>
<property_name> ::= <string_literal>
<property_key> ::= <string_literal>
<property_value> ::= <string_literal>
<expression> ::= <string_literal>
<agent_address> ::=
	<agent name> [“.” <agent_class> “@” <agent_domain> ]
<agent_class> ::= <string_literal>
<agent_domain> ::= <string_literal>