Next: , Previous: , Up: Adaptive Probabilistic Mapping   [Contents][Index]


2.2 Small and Large Actors

The most time-consuming operation frequently performed by an actor is stochastic emitting an optimal output signal. The only actor type that was implemented in QSMM before version 1.15 is small actor. A small actor performs the operation of stochastic emitting an optimal output signal in the following steps:

  1. Relative probabilities of all output signals that could be emitted are calculated.
  2. An optimal output signal to emit is chosen stochastically according to those relative probabilities using a random number generator.

From the standpoint of computer implementation, the most time-consuming is the first step when the actor calculates relative probabilities of all possible output signals. For example, to choose an optimal output signal from a set of 16 output signals, the small actor has to perform 16 evaluations of a relative probability function. This situation is illustrated in Figure 2.2.

Emitting an output signal in an action choice state of small actor

Figure 2.2: Emitting an output signal in an action choice state of small actor

The time necessary to complete sequential execution of this calculation process is the sum of time periods necessary for calculating the value of a relative probability function for every output signal. While calculating the value of a relative probability function can be time-expensive on account of performing many arithmetic operations, access to statistics storage required for fetching their input values adds significant time overhead to the calculation process.

To speed up emitting output signals by an actor, in QSMM version 1.15, the concept of large actor had been introduced. The number of relative probability function evaluations performed by a large actor is not equal to the number of its output signals but is equal to the product of the logarithm of that number and the logarithm base. Large actors provide fast stochastic selection of an output signal when the number of output signals is large or even huge. The only limitation is the amount of available memory for storing control structures of the large actor.

Efficiency in solving a problem by a large actor (as well as by small one) depends on a relative probability function used, i.e. on a function that returns the relative probability of signal emitting. The default function used by a large actor can provide moderate efficiency in solving certain kinds of problems, e.g. the identification of current environment state. Those developers, who are unsatisfied with results produced using that function, can supply a custom function via corresponding API calls.

A large actor supports fast stochastic choice of output signals by using a tree that contains nodes controlled by a small actor. With every tree node, the following entities are associated:

  1. An action choice state: either root one or intermediate one. The root action choice state is the current action choice state of the large actor. Being in that state, the large actor needs to choose an optimal output signal.
  2. A small array of relative probabilities of output signals (this array typically contains a few elements). Those output signals are either output signals of the large actor or intermediate output signals. To every intermediate output signal there corresponds an intermediate action choice state located at a deeper hierarchy level.

Tree structure is illustrated in Figure 2.3, where indexed letters “s” represent intermediate action choice states, and indexed letters “o” represent intermediate output signals.

Emitting an output signal in an action choice state of large actor

Figure 2.3: Emitting an output signal in an action choice state of large actor

A large actor performs the operation of stochastic emitting an optimal output signal by the following algorithm:

  1. Assign the current action choice state of the large actor to current intermediate action choice state.
  2. Stochastically generate an optimal output signal for current intermediate action choice state by a small actor associated with the large actor. This operation requires calculating relative probabilities of all output signals (typically a few ones) that correspond to current intermediate action choice state.
  3. An output signal generated in step 2 can be either an intermediate output signal or an output signal of the large actor. If the output signal is the one of the large actor, then finish.
  4. Change current intermediate action choice state to one that corresponds to the intermediate output signal and go to step 2.

Thus, using a tree, represented in Figure 2.3, choosing an optimal output signal from a set of 16 output signals requires only 8 evaluations of a function that yields the relative probability of signal emitting. A taller binary tree would provide the selection of an optimal output signal from a set of 256 output signals using 16 evaluations of the function.

The structure of the tree affects the weights (or, in other words, the relative profile probabilities) of output signals of a large actor and the speed of emitting those signals by the large actor. Large actors use n-ary Huffman trees to stochastically generate optimal output signals. Using a Huffman tree built for a given list of output signal weights, emitting output signals having greater weights requires the same or smaller number of relative probability function evaluations compared with emitting output signals having lesser weights.

Although having much the same API, small and large actors are not fully interchangeable. There are specifics of using actors of every type.


Next: , Previous: , Up: Adaptive Probabilistic Mapping   [Contents][Index]