Automata learning and intelligent tertiary searching for stochastic point location

摘要

Consider the problem of a robot (learning mechanism or algorithm) attempting to locate a point on a line. The mechanism interacts with a random environment which essentially informs it, possibly erroneously, which way it should move. The first reported paper to solve this problem (Oommen 1997) presented a solution which operated in a discretized space. In this paper we present a new scheme by which the point can be learnt using a combination of various learning principles. The heart of the strategy involves performing a controlled random walk on the underlying space and then intelligently pruning the space using an adaptive tertiary search. The overall learning scheme is shown to be epsilon-optimal. Just as in the case of the results presented in Oommen (1997) the application of the solution in nonlinear optimization has been alluded to. In a typical optimization process the algorithm has to work its way toward the maximum (minimum) using local information. However, the crucial issue in these strategies is that of determining the parameter to be used in the optimization itself. If the parameter is too small the convergence is sluggish. On the other hand, if the parameter is too large, the system could erroneously converge or even oscillate. The strategy presented here can be utilized to determine the best parameter to be used in the optimization.