Dependency graph generation in a networked system

Patent metadata

Field	Value
Publication number	US-10679622-B2
Application number	US-201816010089-A
Country	US
Kind code	B2
Filing date	Jun 15, 2018
Priority date	May 1, 2018
Publication date	Jun 9, 2020
Grant date	Jun 9, 2020

Abstract

Conversations are modeled using dependency graph data structures to facilitate the interaction of users with automated assistants when performing actions performed by computing services. An automated assistant may utilize a dependency graph data structure to guide or otherwise control a human-to-computer dialog session with a user, e.g., by generating one or more outputs or prompts that are presented to the user on a computing device operated by that user, and may thereby enable efficient use of technical hardware.

First claim

What is claimed is:

1. A system to update response data in a networked system, comprising:
a data processing system comprising one or more processors and memory, the one or more processors execute a natural language processor, fulfillment engine, and a digital component selector to:
receive, by the natural language processor, a first input audio signal detected by a sensor at a first client device;
parse, by the natural language processor component, the first input audio signal to identify a request in the first input audio signal;
select, by the fulfillment engine, an action based on the request in the first input audio signal and a dependency graph data structure based on the action, the dependency graph data structure comprising:
a first node and a second node each identifying a respective assistant method and including a parameter to fulfill the action, a directed edge connecting the first node and the second node and that identifies at least one parameter generated by the respective assistant method, and a digital component node comprising a digital component parameter;

receive, by the natural language processor, a second input audio signal detected by the sensor at the first client device;
parse, by the natural language processor component, the second input audio signal to identify a response parameter in the second input audio signal;
update, by the fulfillment engine, the parameter of the first node based on the response parameter and the digital component parameter based on the response parameter;
select, by the digital component selector, a digital component based on the digital component parameter of the at least one digital component node; and
transmit, via the interface, the digital component to the first client device and the dependency graph data structure to a computing service to fulfill the request based on the dependency graph data structure.

2. The system of claim 1 , wherein the dependency graph data structure comprises a second plurality of nodes each identifying a respective action method that accesses the computing service.

3. The system of claim 1 , comprising:
the natural language processor to:
receive a third input audio signal detected by the sensor at the first client device;
parse the third input audio signal to identify a second response parameter in the third input audio signal;

the fulfillment engine to invalidate the parameter of the first node based on the second response parameter parsed from the third input audio signal.

4. The system of claim 1 , comprising:
the natural language processor to:
receive a third input audio signal detected by the sensor at the first client device;
parse the third input audio signal to identify a second response parameter in the third input audio signal;

the fulfillment engine to:
invalidate the parameter of the first node based on the second response parameter parsed from the third input audio signal; and
select at least one assistant method to execute based on the invalidated parameter of the first node.

5. The system of claim 4 , comprising:
the fulfillment engine to update the digital component parameter responsive to the invalidated parameter of the first node.

6. The system of claim 4 , comprising:
the fulfillment engine to invalidate the parameter of the second node responsive to invalidation of the parameter of the first node.

7. The system of claim 6 , wherein the second node is dependent on the first node.

8. The system of claim 1 , wherein the second node in the dependency graph data structure identifies a second action method that calls the computing service to obtain intermediate data for use in performing the action.

9. The system of claim 1 , wherein the first node in the dependency graph data structure identifies a first assistant method that includes a first prompt that requests a response parameter.

10. The system of claim 1 , comprising:
a natural language generator to generate an output signal to request the response parameter based on a first prompt included in the first node in the dependency graph data structure.

11. The system of claim 1 , comprising the fulfillment engine to update a parameter of a first node of the plurality of nodes without requesting the parameter from the user.

12. A method to update response data in a networked system, comprising:
receiving, by a natural language processor, a first input audio signal detected by a sensor at a first client device;
parsing, by the natural language processor component, the first input audio signal to identify a request in the first input audio signal;
selecting, by the fulfillment engine, an action based on the request in the first input audio signal and a dependency graph data structure based on the action, the dependency graph data structure comprising:
a first node and a second node each identifying a respective assistant method and including a parameter to fulfill the action, a directed edge connecting the first node and the second node and identifying at least one parameter generated by the assistant method, and a digital component node comprising a digital component parameter;
receiving, by the natural language processor, a second input audio signal detected by the sensor at the first client device;
parsing, by the natural language processor component, the second input audio signal to identify a response parameter in the second input audio signal;
updating, by the fulfillment engine, the parameter of the first node based on the response parameter and the digital component parameter based on the response parameter;
selecting, by the digital component selector, a digital component based on the digital component parameter of the at least one digital component node; and
transmitting, via the interface, the digital component to the first client device and the dependency graph data structure to a computing service to fulfill the request based on the dependency graph data structure.

13. The method of claim 12 , wherein the dependency graph data structure comprises a second plurality of nodes each identifying a respective action method that accesses the computing service.

14. The method of claim 12 , comprising:
receiving, by the natural language processor, a third input audio signal detected by the sensor at the first client device;
parsing, by the natural language processor, the third input audio signal to identify a second response parameter in the third input audio signal;
invalidating, by the fulfillment engine, the parameter of the first node based on the second response parameter parsed from the third input audio signal.

15. The method of claim 12 , comprising:
receiving, by the natural language processor, a third input audio signal detected by the sensor at the first client device;
parsing, by the natural language processor, the third input audio signal to identify a second response parameter in the third input audio signal;
invalidating, by the fulfillment engine, the parameter of the first node based on the second response parameter parsed from the third input audio signal; and
selecting, by the fulfillment engine, at least one assistant method to execute based on the invalidated parameter of the first node.

16. The method of claim 15 , comprising:
updating, by the fulfillment engine, the digital component parameter responsive to the invalidated parameter of the first node.

17. The method of claim 15 , comprising:
invalidating, by the fulfillment engine, the parameter of the second node responsive to invalidation of the parameter of the first node and the second

Assignees

• Google Llc

Inventors

• Bharadwaj Amit

Classifications

• G10L2015/225

  Feedback of the input speech · CPC title

• G10L15/1822

  Parsing for meaning understanding · CPC title

• G10L15/063

  Training · CPC title

• G10L15/22 Primary

  Procedures used during a speech recognition process, e.g. man-machine dialogue · CPC title

• G06F40/56

  Natural language generation · CPC title