======================================
I N T E G R A T E D    E L I C I T O R
======================================

This file is a description of Integrated Elicitor, which combines
the following three algorithms.

() Search Elicitor: It uses best-first search to identify high-utility
questions. For each question, it considers possible answers, and uses
Improver to evaluate the utility of each answer.

() Heuristic Elicitor: It evaluates the probabilistic impact of each
uncertain value on the schedule score, and uses these impacts as
utility estimates.

() Auxiliary Elicitor: It uses simple heuristics to evaluate question
utilities; it is much less accurate than the other two algorithms.


-= Search Elicitor =-

Search Elicitor inputs a set of candidate questions, and evaluates
each of them separately. It first calls Optimizer to construct a
near-optimal schedule, and then uses this schedule for evaluating
questions. This initial optimization is essential; the use of Search
Elicitor with an unoptimized schedule does not give useful results.

When evaluating a question, Search Elicitor begins with a rough lower
and upper bounds on its utility, and then gradually narrows these
bounds during its search. We use four parameters that determine when
to terminating the search.

() Per-question time: The time limit for evaluating one question. When
Elicitor reaches this limit, it terminates the evaluation of the
current question.

() Low utility: If the utility of a question is below this value,
Elicitor rejects it; this value must be nonnegative. When the upper
utility bound becomes no larger than the low-utility value, Elicitor
terminates the evaluation of the current question.

() High utility: If the utility of a question is above this value,
Elicitor considers it important; this value must be no smaller than
the low importance. When the lower utility bound becomes no smaller
than the high-utility value, Elicitor terminates the evaluation of the
current question.

() Utility ratio: The upper limit on the ratio of the upper utility
bound to the lower bound that represents an "accurate" estimate; this
value must be strictly greater than 1.0. When the ratio of the upper
bound to the lower bound becomes no larger than the utility ratio,
Elicitor terminates the evaluation of the current question.

We also use a parameter that controls the invocation of Improver:

() Improvement time: The time limit given to Improver, when Search
Elicitor calls it to improve the schedule for a specific answer.

After evaluating all questions, Search Elicitor sorts them in the
decreasing order of importance. The sorted list of questions consists
of three parts.

() Beginning: The beginning of the list includes all "unknown" values,
in the same order as in the input of Search Elicitor. Thus, we
consider "unknown" values most important; this approach is temporary,
until developing means of evaluating "unknown"s.

() Middle: The middle of the list includes all "important" questions,
in the same order as in the input of Search Elicitor.

() End: The end of the list includes all other questions that have not
been rejected, in the decreasing order of their lower utility bounds.


-= Integration of elicitors =-

The Integrated Elicitor algorithm combines Search Elicitor, Heuristic
Elicitor, and Auxiliary Elicitor. It uses the following parameter,
in addition to the five parameters for Search Elicitor:

() Input size for Search Elicitor: The number of questions evaluated
by Search Elicitor. We use it to control the trade-off between the
accuracy and speed of Integrated Elicitor.

The main steps of Integrated Elicitor are as follows.

() Step 1: Invoke Heuristic Elicitor, which identifies all uncertain
values that affect the schedule utility, and sorts them in the
decreasing order of their estimated utilities.

() Step 2: Invoke Search Elicitor to re-evaluate the efficiency of the
most important questions. For example, if the "input size" parameter
for Search Elicitor is 100, then we take the first 100 questions from
the list produced by Heuristic Elicitor, and invoke Search Elicitor to
evaluate these 100 questions.

() Step 3: Construct a list of questions sorted in the decreasing
order of their importance. The beginning of this list consists of the
questions selected by Search Elicitor, in the order determined by
Search Elicitor; it does not include the rejected questions. The rest
of the list is the remaining questions selected by Heuristic Elicitor,
in the order determined by Heuristic Elicitor; it includes the
questions rejected by Search Elicitor.

() Step 4: Invoke Auxiliary Elicitor to rank the questions that are
not yet in the list, and append them to the end of the list, in the
order determined by Auxiliary Elicitor.


-= Real-time and batch processing =-

We may use Integrated Elicitor in real-time mode or batch mode. The
real-time mode is for selecting questions during the interactive war
games, which requires reasonably fast evaluation of questions. The
batch mode is for evaluating questions during the batch learning,
which allows slower and more accurate evaluation. We define different
parameter values for these modes; the following table is a tentative
suggestion for parameter values.

                         Real-time    Batch
Per-question time (sec)    2.0        10.0
Low utility                0.00       0.00
High utility               0.01       0.01
Utility ratio              2.0        1.5
Improvement time (sec)     0.2        1.0
Input size for             20         100
  Search Elicitor