# Calculating probability of discovery

I have a planner that can evaluate N arbitrary states, and calculate their fitness. The domains it evaluates have no explicit "end state", so it has an infinite horizon.

What are good methods for calculating when it should stop evaluating states?

My current approach is to estimate the probability of the next evaluation being the next "best" state, and to stop if this probability falls below a certain threshold.

e.g. After evaluating each state, I increment a counter, and after a new best fitness if found, I reset that counter, resulting in a sequence like:

steps = [0, 1, 2, 0, 1, 2, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4]


I can then iterate over this and form a simple discrete probability of each step preceding the next best fitness:

from collections import defaultdict
counts = defaultdict(int)
totals = defaultdict(int)
for step,next in zip(steps, steps[1:]):
counts[step] += next == 0
totals[step] += 1
for k in sorted(counts.keys()):
print k,counts[k],totals[k],'%.2f' % (counts[k]/float(totals[k]),)


resulting in:

0 0.43
1 0.00
2 0.50
3 0.00
4 0.00
5 0.00
6 0.00
7 0.00
8 0.00
9 0.00
10 1.00


How do I take these discrete probabilities and form a general approximation for the probability of P(next step is the best | current step since last best) given an arbitrary step integer (especially for high step counts I may not have reached)?

-
Can we assume that the states are in a random order, and that the fitness of a particular state is independent of where it falls in the sequence? –  jbowman Jan 3 '12 at 16:55
@jbowman, Not really. The states are evaluated in the order of fittest-first (i.e. an A-star search), so where a state falls in the sequence is highly dependent on its fitness. –  Cerin Jan 3 '12 at 18:27
I'm obviously not understanding something - if the states are evaluated in order of fitted first, don't you find the best fitness at the first step? So the probability of the next evaluation being the next "best" state is zero for all subsequent evaluations? –  jbowman Jan 3 '12 at 19:03
The next state evaluated is always more fit than all the other states in the queue, but it's not necessarily more fit than the most fit states seen in the past. Think of it like someone searching for buried treasure. Say they dig 10 holes, and find \$10 in one of them. Then they dig 10 more holes in the areas adjacent to the one where they found the \$10, but out of those they only find \$5. They then dig 10 more holes in the next adjacent areas, etc. How far should they keep digging before giving up? If they suddenly find \$11, how does that effect their decision to dig? –  Cerin Jan 3 '12 at 20:16