Queue-theoretic models for ideal integration of automated call routing systems with human operators

• US 20040264672A1
• Filed: 04/20/2004
• Published: 12/30/2004
• Est. Priority Date: 06/30/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Horvitz, Eric J., Paek, Timothy
• Granted Patent: US 7,742,591 B2
• Time in Patent Office: Days
• US Class Current: 379/221.03
• CPC Class Codes: G10L 15/26 Speech to text systems G10L15/08 takes precedence
• CPC Class Codes: H04M 2201/14 Delay circuits; Timers
• CPC Class Codes: H04M 3/527 Centralised call answering arrangements not requiring operator intervention
• CPC Class Codes: H04M 3/54 Arrangements for diverting calls for one subscriber to another predetermined subscriber based on the calling party profile H04M3/42059; based on location H04M3/42348; based on presence H04M3/42365; to voice mail H04M3/53308
• CPC Class Codes: H04Q 2213/13072 Sequence circuits for call signaling, ACD systems
• CPC Class Codes: H04Q 2213/1337 Operator, emergency services
• CPC Class Codes: H04Q 2213/13378 Speech recognition, speech analysis
• CPC Class Codes: H04Q 3/64 Distributing or queueing

Abstract

The present invention relates to queue-theoretic models for integration of automated call routing systems with human operators. Organizations are increasingly turning to spoken dialog systems for automated call routing to reduce call center costs. To maintain quality service even in cases of failure, these systems often resort to ad-hoc rules for dispatching calls to a human operator. The present invention provides queue-theoretic methods that provide a modeling and simulation capability in support of decisions about the staffing of call-handling centers based on the frequency of incoming calls and the competency of automated dialog systems. The methods include a procedure for identifying when callers should be transferred to operators. The procedure integrates models that predict when a call is likely to fail using spoken dialog features with queuing models of call center volume and service time.

Claims

1. An automated call routing system, comprising:

an automated call routing component to direct calls;

a decision model associated with the automated call routing component to determine when the calls are likely to fail; and

a queuing model to determine a busyness state of an operator, the decision model and the queuing model balance costs between directing the calls to the operator and directing the calls through the automated call routing component.

2. The system of claim 1, the decision model employs a maximum expected utility (MEU), which states that an action A=a is selected that maximizes an expected utility, EU(a/ξ

, wherein ξ

denotes background information and a variable H represents possible states of the world.

3. The system of claim 2, the decision model is optimized according to the following equation:

4. The system of claim 3, the decision model further comprising a variable d to denote an action of dispatching a call, a variable S to denote possible outcomes of a call routing system, which, corresponds to a variable Failure, a variable O denote a state of one or more operators, which may be busy or not busy.

5. The system of claim 4, the decision model is adapted to dispatch a call to an operator when an expected utility of d, given a state of the operator O and call routing system S, exceeds that of a dialog action a and described by the following equation:

∀

<sub>a≠

d</sub>[EU(d|S,O)>

EU(a|S,O)].

6. The system of claim 5, the decision model with respect to a dispatch d, applies a definition of conditional probability to obtain:

7. The system of claim 6, the decision model accounts for effects of other dialog actions taken by the call routing system that remain within the system, and is formulated as:

P(O|S,d)P(S)=P(O|d)P(S).

8. The system of claim 1, the queuing model employs at least two parameters:

λ

, an average arrival rate into a call center, and μ

, an average service time to complete a call when an operator receives it.

9. The system of claim 8, the average arrival rate and the average service time are modeled according to a Poisson process.

10. The system of claim 8, the queuing model determines operator load via estimated λ

and μ

parameters in accordance with an M/M/s queue, which denotes a queue in which an arrival process is “

memory-less,”

a service process “

memory-less,” and

the number of servers is z.

11. The system of claim 10, further comprising a determination of a likelihood that all operators are busy in a call center if a call is dispatched for an M/M/z queue as follows:

12. The system of claim 1, at least one of the models further describe a utility of a dialog action a given an operator state O and system state S as approximately decomposed as follows:

u(a,S,O)≅

u(a,S)+u(a,O).

13. The system of claim 12, if a=d, or dispatch to an operator, then, a cost function is described as:

c(d,S,O)≅

CustCost(t+W)+OpCost·

z.

wherein t is a time a caller has spent in an automated system, and W is a “

dwell time,”

which includes a time waiting in line and time being served.

14. The system of claim 13, further comprising a future cost determination of remaining in a system for an estimated amount of time longer than t.

15. The system of claim 14, t is determined via Gaussian models.

16. The system of claim 1, further comprising an average cost savings function described as follows:

17. The system of claim 1, further comprising a component to at least one of monitor an average rate of dispatch, and adjust an average rate of arrival in the queuing model.

18. The system of claim 1, the models applied to optimize individualized costs and utilities, including user frustration or minimizing a caller'"'"'s time.

19. A computer readable medium having computer readable instructions stored thereon for implementing at least one of the call routing component and the models of claim 1.

20. A system that facilitates call routing, comprising:

means for interacting with a caller;

means for automatically directing the caller to a user; and

means for performing a decision theoretic analysis, the decision-theoretic includes an analysis for determining when callers are to be dispatched to an operator in order to minimize support costs at an enterprise level.

21. A method for automatic call management, comprising:

determining a decision-theoretic model to model spoken dialog for a call routing system;

determining a queuing model to model the call routing system; and

automatically directing calls to at least one of an organization member and an operator in order to mitigate costs for an organization.

22. The method of claim 21, the decision-theoretic model employs a maximum expected utility (MEU), which states that an action A=a is selected that maximizes an expected utility, EU(a/ξ

), wherein ξ

denotes background information.

24. The method of claim 21, the queuing model employs at least two parameters:

λ

, an average arrival rate into a call center, and μ

, an average service time to complete a call when an operator receives it.

25. The method of claim 24, the average arrival rate and the average service time are modeled according to a Poisson process.

26. The method of claim 25, the queuing model determines operator load via estimated λ

and μ

parameters in accordance with an M/M/s queue, which denotes a queue in which an arrival process is memoryless, and a service process memoryless.

23. The method of claim 23, the decision-theoretic model is optimized according to the following equation: