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

• US 7,742,591 B2
• Filed: 04/20/2004
• Issued: 06/22/2010
• Est. Priority Date: 06/30/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Paek, Timothy, Horvitz, Eric J.
• Primary Examiner(s): Al Aubaidi; Rasha S
• Assistant Examiner(s): Nguyen; Khai N
• Application Number:
  US10/827,873
• Publication Number:
  US 20040264672A1
• Time in Patent Office: 2,254 Days
• Field of Search: 379/265.01, 379/265.11, 707/3, 714/46
• US Class Current: 379/266.01
• 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. A computer comprising a memory and a processor, the memory tangibly embodying the following components executable by the processor to facilitate an automated call routing system:

an automated call routing component to direct calls to one of a spoken dialog system or an operator;

a decision determining component associated with the automated call routing component that, upon receiving the calls determines, based in part on a decision model, a probability that the calls are likely to fail when serviced by the spoken dialog system;

a queuing determining component to determine, based in part on a queuing model, a busyness state of the operator; and

a component that integrates the decision model and the queuing model to balance the costs between directing the calls to the operator, based on the determined busyness of the operator, and directing the calls through the spoken dialog system, based on the determined probability that the calls will fail, to determine whether to route the calls to the operator.

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(alξ

), 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:

$\underset{a}{\arg <br><br><br><br>\max }<br><br><br><br>\mathrm{EU}<br><br><br><br>\left(a❘<br><br>\mathrm{\xi <br><br>}\right)=\underset{a}{\arg <br><br><br><br>\max }<br><br>\underset{<br><br>h}{\overset{}{\sum <br><br>}}<br><br><br><br>P<br><br>\left(H=h❘<br><br>\mathrm{\xi <br><br>}\right)<br><br>u<br><br>\left(a,h\right)$

wherein u (a, h) expresses a utility of taking action a when a state of the world is h.

4. The system of claim 1, the decision model further comprising a variable d to denote an action of dispatching a call, a variable S to denote the plurality of possible outcomes of the automated call routing system, which, corresponds to a variable Failure, a variable O denote a state of one or more operators, which is one of 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:

$\mathrm{UE}<br><br>\left(d\right)=\underset{S}{\overset{}{\sum <br><br>}}<br><br><br><br>\underset{O}{\overset{}{\sum <br><br>}}<br><br><br><br>P<br><br>\left(S,O❘<br><br>d\right)<br><br>u<br><br>\left(d,S,O\right)<br><br>\mathrm{EU}<br><br><br><br>\left(d\right)<br><br>\mathrm{\Sigma <br><br>}<br><br><br><br>\mathrm{\Sigma <br><br>}$

where P(O|S, d), is a likely state of a call center queue;

P(S), is a likely outcome of a call routing system; and

u(d, S, O), is a utility of dispatching a call when the one or more operators may or may not be busy and the automated call routing system may or may not be failing.

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 μ

a 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:

$\begin{array}{c}P<br><br>\left(O❘<br><br>S,d\right)=<br><br>P<br><br>\left(n\ge <br><br>z\right)\\ P<br><br>\left(O❘<br><br>S,d\right)=<br><br>\left(1-\underset{n=0}{\overset{z}{\sum <br><br>}}<br><br><br><br>P_n\right)\end{array}$

where n represents a number of callers, and Pn is a closed form solution for multiple servers.

12. The system of claim 1, at least one of the decision model and the queuing model further describes 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,SO)≅

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:

$\mathrm{AverageSavings}=\frac{\underset{n}{\sum <br><br>}<br><br><br><br>❘<br><br>\mathrm{ec}<br><br>\left(d\right)-\mathrm{ec}<br><br>\left(⫬<br><br>d\right)❘<br><br>}{n}$

where cc is an expected cost.

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 program storage medium readable by a computer having a memory and a processor, the medium tangibly embodying one or more programs of instructions executable by the computer to implement a system that facilitates call routing, comprising:

means for interacting with a caller through an automated dialog;

means for automatically directing a call made by the caller to an operator of a plurality of operators based on a conclusion from a decision-theoretic analysis; and

means for performing the decision theoretic analysis, the decision-theoretic includes an analysis for determining, based on a probability that the call is likely to fail when answered by the interacting means, whether dispatching the call to an operator of the plurality of operators minimizes support costs for an enterprise comprising the plurality of operators.

20. A method for automatic call management, comprising:

determining a decision-theoretic model for a call routing system that predicts a likely outcome of a call when directed to a spoken dialog system using real-time, extractable features for optimal decision making wherein a variable d denotes an action of dispatching a call to an operator of a plurality of operators, a variable S denotes possible outcomes of the call routing system which corresponds to a variable Failure, a variable O denotes a state of one or more operators, which is one of busy or not busy;

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

automatically directing calls to at least one of an organization member or an operator when calls are likely to fail when dealt with by the spoken dialog system such that an expected utility of the action d given a state of the operator O, as predicted based on the queuing model, and call routing system S exceeds that of a dialog action a of the spoken dialog system, as predicted by the decision-theoretic model and described by the following equation;

∀

<sub>a≠

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

EU(a|S,O], hence mitigating costs for an organization comprising the plurality of operators.

21. The method of claim 20, 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.

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

$\underset{a}{\arg <br><br><br><br>\max }<br><br><br><br>\mathrm{EU}<br><br>\left(a❘<br><br>\mathrm{\xi <br><br>}\right)=\underset{a}{\arg <br><br><br><br>\max }<br><br>\underset{h}{\overset{}{\sum <br><br>}}<br><br><br><br>P\left(H-h❘<br><br>\mathrm{\xi <br><br>}\right)<br><br>u<br><br>\left(a,h\right)$

wherein u(a,h) expresses a utility of taking action a when a state of the world is h.

23. The method of claim 20, 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.

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

25. The method of claim 24, the queuing model determines operator load via estimated parameters in accordance with an M/M/s queue, which denotes a queue in which an arrival process and a service process are memoryless.

26. A program storage medium readable by a computer having a memory and a processor, the medium tangibly embodying one or more programs of instructions executable by the computer to facilitate an automated call routing system, comprising:

an automated call routing component to direct calls to one of a spoken dialog system or a live operator of a plurality of live operators;

a decision determining component associated with the automated call routing component to determine, based in part on a decision model;

when the calls are likely to fail when dealt with by the spoken dialog system, and

based on a balance of costs between directing the calls to the live operator and directing the calls through the spoken dialog system, whether the calls should be transferred to the live operator such that an expected utility of an action d, given a state of the live operator O and call routing system S, exceeds an expected utility of a dialog action a of the spoken dialog system and described by the following equation;

∀

<sub>a≠

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

EU(a|S,O)], wherein d denotes an action of dispatching a call to the live operator, S denotes possible outcomes of the call routing system, which, corresponds to a variable Failure, the variable O denotes a state of the plurality of live operators, which is one of busy or not busy; and

a queuing determining component to determine, based in part on a queuing model, a busyness state of the live operator, the decision model is integrated with the queuing model balance the costs between directing the calls to the live operator and directing the calls through the spoken dialog system, the decision model and the queuing model optimize individualized costs and utilities, including user frustration or minimizing a caller'"'"'s time.