5 Assumption handling

5.5 Random and arbitrary decisions

It is clearly useful for rules to be able to specify that a random choice is to be made. In SDML, such facilities must be declarative and logically consistent. A primitive randomNumber is provided, which behaves as if it retrieves from an infinite database associated with each agent and time period of the simulation, containing all terms (except those containing variables) and corresponding random numbers in the range zero to one. It is implemented by generating a random number the first time a particular term is specified, and returning the same number if the same term is used again. Thus, evaluating the same clause from within the same rulebase at the same time period yields the same bindings, and the facility works even in a partition containing cycles. Every time a different random number is required, a different term, specifying what the number corresponds to, must be specified.

Sometimes, it is required to choose one of several possibilities, any of which could be true. This can be done by generating a sorted list of the possibilities (using an assumable clause), and indexing this list by a random number generated using the randomNumber primitive and converted to an integer in the appropriate range. However, some choices may cause conflicts between assumptions for which there is no valid resolution, and this method does not allow other choices to be tried.*1

An alternative approach is to use backward chaining rules to specify the possible choices and a primitive (called randomChoice) to randomly select one of the choices. The primitive can generate an assumption corresponding to each possibility, and randomly resolve the assumptions so that only one of them is true. Validities can be used to optimise this primitive by randomly choosing one to assume true and backtracking if this leads to contradictions. The primitive must be defined in such a way that if the same assumption context is encountered again, the same choice is made.

The first rule in figure 9 specifies that all low natural numbers are possible choices, and the second rule specifies that one of the possible choices, randomly selected, is the natural choice. An additional term (in this case the symbol natural) is used as an argument of the possibleChoice and randomChoice clauses to identify the choice, so that different choices can be specified in the same rulebase (as with randomNumber).

When a fair random choice is required, it is necessary to fire all applicable backward chaining rules completely to determine all possible choices, and there must be a chance for the random choice to be changed if new possibilities are discovered after the assumption context was first encountered. Sometimes an arbitrary choice, which need not be selected randomly, is required. If the first possibility discovered is adequate, then a lot of time can be avoided investigating other possibilities. Unlike with the Prolog "cut", however, backtracking can be used to make other choices if required. In SDML, arbitrary choices can be made by simply using the arbitraryChoice primitive instead of randomChoice.

It may be noted that arbitrary choices can be made in SDML, without using arbitraryChoice, by attempting to fire the rules in figure 7 for example. The rule in figure 10 specifies that a low natural number is the natural choice unless there is a different natural choice. If validities are used, an assumption corresponding to the first natural number retrieved is assumed true, which prevents other assumptions from being made. The arbitraryChoice primitive is merely a more efficient mechanism to make such decisions.

Arbitrary choices can be affected by criteria such as rule ordering and the order in which data is retrieved from databases. It could be argued that such facilities should not be provided in a strictly declarative language. However, arbitrary decisions only affect the order in which resolutions are found. If backtracking is used, then the same final states of the databases will be obtained irrespective of ordering (if rule firing terminates).*2 For some problems, arbitrary choices enable one solution to be found much faster, and one solution is often sufficient.

Efficient Forward Chaining for Declarative Rules in a Multi-Agent Modelling Language - 16 FEB 95

[Next] [Previous] [Up] [Top] [Contents]

Generated with CERN WebMaker