Formal trust building in the execution of partially trusted behaviors

• US 5,758,029 A
• Filed: 02/28/1996
• Issued: 05/26/1998
• Est. Priority Date: 02/28/1996
• Status: Expired due to Term

• Current Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Hall, Robert J.
• Primary Examiner(s): Downs, Robert W.
• Application Number:
  US08/608,228
• Time in Patent Office: 818 Days
• Field of Search: 395/76, 395/77, 395/51
• US Class Current: 706/46
• CPC Class Codes: G06F 21/53 by executing in a restricted environment, e.g. sandbox or secure virtual machine
• CPC Class Codes: G06F 2211/009 Trust
• CPC Class Codes: G06Q 10/10 Office automation; Time management

Abstract

A method for executing partially trusted behaviors using an automated assistant. The method employs a guarded execution mode which provides for the safe execution of partially trusted behaviors. Further, incremental trust growth is provided for allowing more behaviors to be executed autonomously by the automated assistant. Trust growth is accomplished through the use of a trust library. The method also employs trust reuse which provides for the reuse of individual trust library entries across behaviors which are proven to be erroneous by the automated assistant.

Claims

1. A method for increasing trust of an automated assistant executing a task on a computer system, said method comprising the steps of:

executing a behavior in a mode which employs a trust library containing a set of trusted responses;

receiving an input event during said execution of said behavior;

computing a response for said behavior which satisfies said input event; and

comparing said computed response with said set of trusted responses to determine whether a match occurs, and (a) if a match occurs, executing said computed response, otherwise (b) if no match occurs, validating said trust of said computed response for inclusion in said trust library, said validating being accomplished by computing a sound scenario generalization of said computed response.

2. The method of claim 1, wherein each trusted response of said set of trusted responses is represented as a trusted situation/action pair.

3. A method for use by an automated assistant executing on a computer system, said automated assistant performing a user task by employing a behavior which represents the knowledge used by said automated assistant to perform said task, said method comprising the steps of:

executing said behavior in a mode which employs a trust library containing a set of trusted situation/action pairs;

receiving an input event during said execution of said behavior, said input event and a present state of said behavior jointly defining a situation for processing by said behavior;

computing an action for execution by said behavior which satisfies said situation; and

comparing a situation/computed-action pair represented by said situation and said computed action with said set of trusted situation/action pairs to determine whether a match occurs, and (a) if a match occurs, executing said computed action, otherwise (b) if no match occurs, executing a predetermined response and

(i) computing a generalization of said situation/computed-action pair, said generalization computed using sound scenario generalization;

(ii) determining the acceptability of said computed generalization; and

(iii) adding said computed generalization to said trust library if found to be acceptable in said determining step.

4. The method of claim 3, wherein said behavior is represented as a reactive system.

5. The method of claim 4, wherein said reactive system is implemented using the BL.2 programming language.

6. The method of claim 3, wherein said determining step is a query to said user regarding the acceptability of said computed generalization.

7. The method of claim 3, wherein the initial said set of trusted situation/action pairs of said trust library is generated prior to said execution of said behavior using a simulated behavior environment.

8. The method of claim 3, wherein said behavior is defined using programming by demonstration.

9. The method of claim 3, wherein subsets of said set of trusted situation/action pairs are stored in said trust library as tuples, each said tuple having the form (s, e, v, x) where "s" is a state description of said trusted situation, "e" is an event schema of said trusted situation, "v" is a state variable associated with said state description, and "x" is a value for "V".

10. The method of claim 3 including the further step of:

debugging said behavior when the result of said determining step is that said computed generalization is unacceptable.

11. The method of claim 10 including the further steps of:

computing a second generalization of said situation/computed-action pair as a function of said debugged behavior; and

determining if said second generalization is contained in said trust library, and if so contained, adding said second generalization to a second trust library for use by said debugged behavior.

12. The method of claim 3, including the further step of:

generating during the course of said execution of said behavior a report which contains a description of any situations not covered by a situation/action pair in said trust library.

13. A method for use by an automated assistant executing on a computer system, said automated assistant performing a user task by employing a behavior which represents the knowledge used by said automated assistant to perform said task in conformance with user task parameters, said method comprising the steps of:

executing said behavior in a mode which employs a trust library containing a set of trusted situation/action pairs, said trusted situation/action pairs defining actions for said behavior which are known to be in conformance with said user task parameters;

receiving a plurality of input events during said execution of said behavior, each said input event and a present state of said behavior jointly defining a situation for processing by said behavior;

(a) computing an action for execution by said behavior which satisfies said situation;

(b) comparing a situation/computed-action pair represented by said situation and said computed action with said set of trusted situation/action pairs to determine whether a match occurs, and (1) if a match occurs, executing said computed action, otherwise (2) if no match occurs, executing a predetermined contingency behavior, and

(i) computing a generalization of said situation/computed-action pair,

(ii) determining the acceptability of said computed generalization, and

(iii) adding said computed generalization to said trust library if found to be acceptable in said determining step;

performing steps (a) and (b) in an iterative fashion to respond to each said input event of said plurality of input events received during said execution of said behavior; and

generating during the course of said execution of said behavior a report which contains a description of any situations not covered by a situation/action pair in said trust library.

14. A method for use by an automated assistant executing on a computer system, said automated assistant performing a user task by employing a behavior which represents the knowledge used by said automated assistant to perform said task, said method comprising the steps of:

executing said behavior in a mode which employs a trust library containing a set of trusted situation/action pairs;

receiving an input event during said execution of said behavior, said input event and a present state of said behavior jointly defining a situation for processing by said behavior;

computing an action for execution by said behavior which satisfies said situation; and

comparing a situation/computed-action pair represented by said situation and said computed action with said set of trusted situation/action pairs to determine whether a match occurs, and (a) if a match occurs, executing said computed action, otherwise (b) if no match occurs, executing a predetermined contingency behavior, and

(i) computing a generalization of said situation/computed-action pair;

(ii) determining the acceptability of said computed generalization; and

(iii) adding said computed generalization to said trust library if found to be acceptable in said determining step; and

generating during the course of said execution of said behavior a report which contains a description of any situations not covered by a situation/action pair in said trust library.

15. The method of claim 14, wherein said predetermined contingency behavior aborts said execution of said behavior.

16. The method of claim 14, wherein said predetermined contingency behavior queries said user to determine the acceptability of said situation/computed-action pair.

17. A method for use by an automated assistant executing on a computer system, said automated assistant performing a user task by employing a behavior which represents the knowledge used by said automated assistant to perform said task in conformance with user task parameters, said method comprising the steps of:

executing said behavior in a mode which employs a trust library containing a set of trusted situation/action pairs, said trusted situation/action pairs defining actions for said behavior which are known to be in conformance with said user task parameters;

receiving a plurality of input events during said execution of said behavior, each said input event and a present state of said behavior jointly defining a situation for processing by said behavior;

(a) computing an action for execution by said behavior which satisfies said situation;

(b) comparing a situation/computed-action pair represented by said situation and said computed action with said set of trusted situation/action pairs to determine whether a match occurs, and (1) if a match occurs, executing said computed action, otherwise (2) if no match occurs, executing a predetermined response and

(i) computing a sound scenario generalization of said situation/computed-action pair,

(ii) determining the acceptability of said computed generalization, and

(iii) adding said computed generalization to said trust library if found to be acceptable in said determining step; and

performing steps (a) and (b) in an iterative fashion to respond to each said input event of said plurality of input events received during said execution of said behavior.

18. An apparatus employed by an automated assistant executing on a computer system, said automated assistant performing a user task by employing a behavior which represents the knowledge used by said automated assistant to perform said, said apparatus comprising:

means for executing said behavior in a mode which employs a trust library containing a set of trusted situation/action pairs;

means for receiving an input event during said execution of said behavior, said input event and a present state of said behavior jointly defining a situation for processing by said behavior;

means for computing an action for execution by said behavior which satisfies said situation;

means for comparing a situation/computed-action pair represented by said situation and said computed action with said set of trusted situation/action pairs to determine whether a match occurs, and

(a) if a match occurs, executing said computed action, otherwise,

(b) if no match occurs, then

(i) computing a generalization of said situation/computed-action pair,

(ii) determining the acceptability of said computed generalization, and

(iii) adding said computed generalization to said trust library if found to be acceptable;

means for debugging said behavior when said computed generalization is unacceptable;

means for computing a second generalization of said situation/computed-action pair as a function of said debugged behavior; and

means for determining if said second generalization is contained in said trust library, and if so contained, adding said second generalization to a second trust library for use with said debugged behavior.

19. A method for increasing trust of an automated assistant executing a task on a computer system, said method comprising the steps of:

executing a behavior in a mode which employs a trust library containing a set of trusted responses;

receiving an input event during said execution of said behavior;

computing a response to be carried out by said behavior which satisfies said input event; and

comparing said computed response with said set of trusted responses to determine whether a match occurs, and (a) if a match occurs, executing said computed response, otherwise (b) if no match occurs, validating said trust of a set of untrusted responses, said validating step utilizing a sound scenario generalization to validate said trust of said set of untrusted responses, and said set of untrusted responses including said computed response.

20. The method of claim 19, wherein said set of trusted responses are trusted situation/action pairs.

21. The method of claim 19, comprising the further steps of:

debugging said behavior;

computing a second response as a function of said debugged behavior; and

determining if said second response is contained in said trust library, and if so contained, adding said second response to a second trust library for use by said debugged behavior.

22. The method of claim 19, wherein the initial said set of trusted responses is generated prior to said execution of said behavior using a simulated behavior environment.

23. The method of claim 19, wherein said automated assistant selects said behavior from a central source.

24. The method of claim 19, wherein said method includes the further step of:

executing a predetermined response when said computed response is found not to be in said set of trusted responses.

25. The method of claim 24, wherein said predetermined response aborts said execution of said behavior.

26. The method of claim 24, wherein said predetermined response performs a query to determine the acceptability of said computed response.