A Hierarchical Learning Scheme for Solving the Stochastic Point Location Problem

General Information

Read the publication: A Hierarchical Learning Scheme for Solving the Stochastic Point Location Problem .

Title: A Hierarchical Learning Scheme for Solving the Stochastic Point Location Problem.
Author(s): Anis Yazidi, Ole-Christoffer Granmo, B. John Oommen, and Morten Goodwin.
Published date: June 2012.
Published at: The 25th International Conference on Industrial, Engineering & Other Applications of Applied Intelligent Systems 2012

Abstract


This paper reports a novel hierarchical search based solution to the Stochastic-Point Location (SPL) problem. A robot (Learning Mechanism or algorithm) is attempting to locate a point on a line. The mechanism interacts with a random environment which essentially informs it, possibly erroneously, if the unknown parameter is on the left or the right of a given point. The first pioneering work [6] on the SPL problem presented a solution which operates a one-dimensional controlled random walk in a discretized space to locate the unknown parameter. The primary drawback of the latter scheme is the fact that the steps made are always very conservative. If the step size is decreased the scheme yields a higher accuracy, but the convergence speed is correspondingly decreased.

In this paper we introduce the Hierarchical Stochastic Searching on the Line (HSSL) solution. The HSSL solution is shown to provides orders of magnitude faster convergence compared to the original SPL solution reported in [6]. The heart of the HSSL strategy involves performing a controlled random walk on a discretized space structured as a binary tree. The overall learning scheme is shown to be optimal if the effectiveness p of the environment is greater than the golden ratio conjugate [4]. The strategy presented here can be utilized to determine the best parameter to be used in the optimization. The solution has been both analytically analyzed and simulated, with extremely fascinating results.

The author of this document is:
Morten Goodwin
E-mail address is:
morten.goodwin circle-a uia.no
Phone is:
+47 95 24 86 79