Recently, I implemented the state space algorithm in Racket. It's a simple algorithm that can ﬁnd a goal state in n-dimensional Euclidean space. All one needs is a computable function, a starting domain, and a goal value.
How does it work?
For example, let's say we want to ﬁnd an input for cosine that gives us one of the zeros for the domain 0 to 2π. Of course, there's no need to use the algorithm in this case. We could look at a unit circle and ﬁnd that applying cosine with the value 3π/2 gives us zero. Alternatively, the value of π/2 works just as well. Shortly, we'll discover how the algorithm will nondeterministically return one of these two zeros–and in this case, we don't favor either state. Any zero will do.
The main idea of the algorithm is to tighten the domain around a state that satisﬁes the goal. This process is done iteratively. Every crank, the code will generate K random guesses for a goal-satisfying state within the current domain. The K parameter has to be any positive integer, but you get to choose it. I recommend trying different values for K to see how that affects the outcome.
The best state out of the set of K–i.e. the guess that gives an output closest to the goal–will be set aside. This guess is selected by ﬁnding the K range value that minimizes the formula below. Note that y is the guess and yg is the goal value.
Obviously, in the beginning, the best state is likely far off from the goal state. The chance to generate a satisﬁable guess increases as the domain shrinks around a goal-satisfying state, which happens every iteration.
To get this new domain, there are a few steps to follow. First, let's ﬁnd the average of the absolute values of the differences of the K range values and the goal value, which we'll call u.
Next, we'll need a so-called epsilon value to scale our new domain. To compute it, use the following formula:
The numerator is the absolute value of the difference of the best K range value and the goal–which we computed earlier. The denominator is the u we just computed. So, you should only be plugging in numbers here.
Finally, insert our prerequisite work into this formula to generate the new domain. Note that the x is the best state out of the set of K states. The b is the end value of the current domain; the a is the beginnning of the domain.
The algorithm will thus generate K range values and use the best one to create the new domain for the next iteration. We'll continue this process until one of the generated guesses is within an error bound that we choose.
Astute readers may have noticed that this is a variation of a beam search. According to Wikipedia, beam search is a heuristic search algorithm that explores a graph by expanding the most promising node in a limited set. In this case, our “graph” is the domain. Thus, we are working over a continuous space rather than a discrete space; however, since we can effectively reduce the search space, the algorithm works. Well, works is fudgey term. I believe that the algorithm can sometimes fail to ﬁnd a solution since it isn't mathematically guarenteed to converge the domain around a goal-sastifying state. Increasing the K parameter should help–more guesses increases the chance of one them being good.
Here is the code for my complete solution. As a reminder, the algorithm is looking for a zero of the cosine function for the domain 0 to 2π. To note, K is set to 3, and the error bound is set to .01.
(struct domain (x y))
(define (state-space fn goal [domain (domain 0 (* 2 pi))] [k 3] [error-bound .01])
(let loop ([x 0] [min (domain-x domain)] [max (domain-y domain)])
[(within-bound? (fn x) goal error-bound) x]
(define k-values (gen-k-values k min max))
(define best-value (select-best-value k-values fn goal))
(define-values (new-min new-max) (gen-new-bound k-values best-value goal min max))
(displayln (format "~a < ~a < ~a" new-min best-value new-max))
(loop best-value new-min new-max)])))
(define (gen-k-values k min max)
(define dist (uniform-dist min max))
(for/list ([ii k])
(define (select-best-value k-values fn goal)
(argmin (lambda (x) (abs (- goal (fn x)))) k-values))
(define (gen-new-bound k-values best-value goal min max)
(define errors (map (lambda (x) (abs (- goal x))) k-values))
(define avg-error (average errors))
(define e (/ (abs (- best-value goal)) avg-error))
(define term (* e (/ (- max min) 2)))
(values (- best-value term) (+ best-value term)))
(define (within-bound? y goal error-bound)
(define diff (- goal y))
(<= (abs diff) error-bound))
(define (average xs (return /))
(if (empty? xs)
(return 0 0)
(average (cdr xs)
(lambda (sum len)
(return (+ sum (car xs))
(+ len 1))))))
(state-space cos 0))
For a single run, I got a state value of about 1.566, which is close to π/2. Since π/2 is one of the valid zeros, the algorithm's outcome is what we expected. You should keep in mind that it's possible to get a state value near 3π/2, the other zero. Consider running the algorithm multiple times to get a feel for how things work.