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


2.3 Small and Large Actors

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

  1. The actor calculates the relative probabilities of all output signals.
  2. The actor stochastically selects an output signal 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 the relative probabilities of all output signals. For example, to adaptively select an output signal from a set of 16 output signals, the small actor has to perform 16 evaluations of a relative probability function. Figure 2.4 illustrates this situation.

emitting an output signal in an action choice state of a small actor

Figure 2.4: emitting an output signal in an action choice state of a small actor

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

To speed up selecting output signals by an actor, QSMM 1.15 introduces the concept of large actor. If the weights (or the relative profile probabilities) of output signals of a large actor are equal, the number of relative probability function evaluations performed by the large actor is not equal to the number of its output signals but is approximately equal to the product of the logarithm of that number and a logarithm base. Large actors provide fast selection of an output signal when the number of output signals is large or even huge; the only limitation is the amount of memory available for storing the control structures of a large actor.

The adaptivity of behavior of a large actor (as well as small one) depends on a relative probability function used, that is, on a function that returns the relative probability of selecting a signal. The default function used by a large actor can provide moderate efficiency in solving certain kinds of problems, for example, the identification of a current environment state. Developers unsatisfied with results produced using that function can provide a custom function via corresponding API calls.

A large actor performs fast stochastic selection of output signals by using trees containing nodes controlled by a small actor. The following entities correspond to every tree node:

  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; it selects an output signal for that state.
  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.

Figure 2.5 illustrates this tree structure. Indexed letters “s” denote intermediate action choice states, and indexed letters “a” denote intermediate output signals.

emitting an output signal in an action choice state of a large actor

Figure 2.5: emitting an output signal in an action choice state of a large actor

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

  1. Assign: current intermediate action choice state = the current action choice state of the large actor.
  2. Adaptively generate an output signal for the current intermediate action choice state by a small actor associated with the large actor. This operation requires calculating the relative probabilities of all output signals (typically a few ones) for the 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 the current intermediate action choice state to an intermediate action choice state corresponding to the intermediate output signal and go to step 2.

Thus, using a tree represented in Figure 2.5, the adaptive selection of an output signal from a set of 16 output signals requires only 8 evaluations of a function returning the relative probability of a signal. A taller binary tree would provide the adaptive selection of an output signal from a set of 256 output signals using 16 evaluations of the function.

The structure of the tree affects the weights 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 adaptively generate output signals. Using a Huffman tree built for a specific list of output signal weights, emitting output signals with greater weights requires the same or a smaller number of relative probability function evaluations compared to emitting output signals with 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]