wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> efficient agent
        
(Message started by: howard roark on Jan 24^th, 2009, 11:32am)

Title: efficient agent
Post by howard roark on Jan 24^th, 2009, 11:32am

Suppose there is an agent which moves from location to location along an assembly line, where the locations are indexed by the integers 0, . . . ,N or 0, . . .infinity.

The delay in moving from location i to location j is |i - j|. The agent is given a location to go to, does its work, then is assigned the next location (which may be the same), and so on. After it has completed its work, it can either stay there or return to location 0 before it is given the next location. Because there is significant time between assignments, there is no delay when returning to 0 between assignments.

The probability of being assigned location i is pi, and each assignment is made independently from any previous assignments.

Assume that the distribution is such that there is a finite expected delay when starting from location 0.

A policy is a rule which tells the robot whether to stay at location i or return to location 0, for all i.

An optimal policy is one which minimizes the expected delay at each location. Optimal policies need not be unique.

1)Suppose the probabilities are pi =((3/4)^i)/4
Give an optimal policy.
2)Show that for any probability distribution, there is an optimal policy of the form: the robot stays if it is at a location <= L, and returns to 0 if it is at a location > L, for some L >= 0.

Title: Re: efficient agent
Post by 1337b4k4 on Jan 28^th, 2009, 12:25am

From a position k, the expected distance from k X_k is

E(X_khttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_i=0^inf|k-i|p_i which is http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_i=0^k(k-i)p_i + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_i=k+1^inf(i-k)p_i. The difference between adjacent terms E(X_k+1) - E(X_k) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif₀^kp_i - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k+1^infp_i = 1 - 2*http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k+1^infp_i. This value is monotonically increasing and starts out at -1+2p₀ and approaches 1 as k goes to infinity. Thus, we see that E(X_k) is a value which will decrease monotonically while cdf(k) < .5, and increase monotonically afterward, with the difference between adjacent terms approaching 1. Thus we see although E(X_k) may become smaller than E(X₀) for a while, but it will eventually start increasing and grow and stay larger than E(X₀) at some point, x. So for those values of k less than x, it would be optimal to stay there, and for values greater than x, it would make sense to go back to 0.

It seems that the only case in which multiple optimal solutions could occur is if p₀ = 1/2. Then if there are k contiguous integers i starting at 1...k where p_i = 0, there will be 2ⁱ⁺¹ optimal solutions, as the difference between adjacent values of E(X_k) won't change from 0 to k+1, and an optimal strategy for every one of those integers could choose between staying or returning to 0.