Mini-Project 2 Probabilistic Search (and Destroy) Solution

The purpose of this Mini-Project is to model your knowledge/belief about a system probabilistically, and use this belief state to e ciently direct future action.







The Problem: Consider a landscape represented by a map of cells. The cells can be of various terrain types (‘ at’, ‘hilly’, ‘forested’, ‘a complex maze of caves and tunnels’) representing how di cult they are to search. Hidden somewhere in this landscape is a Target. Initially, the target is equally likely to be anywhere in the landscape, hence starting out:

P(Target in Celli) =
1
:
(1)
# of cells






This represents your prior belief about where the target is. You have the ability to search a given cell, to determine whether or not the target is there. However, the more di cult the terrain, the harder is can be to search - the more likely it is that even if the target is there, you may not nd it (a false negative). We may summarize this in terms of the false negative rates:




P


i


i
8
0:1
if Celli
is at




































(Target not found in Cell




Target is in Cell ) =

0:3
i
is hilly
(2)







if Celli










<














j



0:7
if Cell
is forested






































































0:9
if Celli
is a maze of caves

























:








The false positive rate for any cell is taken to be 0, i.e., P (Target found in CellijTarget not in Celli) = 0. Whatever the result of a search, however, it does provide some useful information about the location of the target, lowering the likelihood of the target being in the searched cell and raising the likelihood of it being in others.




If you nd the target, you are done. The goal is to locate the target in as few searches as possible by utilizing the results of the observations collected.




Implementation: Maps may be generated in the following way: for a 50 by 50 grid, randomly assign each cell




a terrain type, ( at with probability 0:2, hilly with probability 0:3, forested with probability 0:3, and caves with probability 0:2). Select a cell uniformly at random, and identify this as the location of the target. Note, this information is going to be stored and available in your program, but you cannot use it to determine which cell to check at any time.


























































1
Department of Computer Science - Rutgers University
































































Figure 1: A simple 10 x 10 map with indicated target.




Separately, construct a 50 x 50 array of values representing your current belief state, the probability given everything you’ve observed so far that the target is in a given cell, i.e., at time t




Belief[Celli] = P (Target in Cellij Observations through time t) :
(3)
Note, at time t = 0, we have Belief[Celli] = 1=2500.




At any time t, given the current state of Belief, determine a cell to check by some rule and search it. If the cell does not contain the target, the search will return failure. If the search does contain the target, the search will return failure or success with the appropriate probabilities, based on the terrain type. If the search returns failure, for whatever reason, use this observation about the selected cell to update your belief state for all cells (using Bayes). If the search returns success, return the total number of searches taken to locate the target.







A Stationary Target



Given observations up to time t (Observationst), and a failure searching Cell j (Observationst+1 = Observationst^ Failure in Cellj ), how can Bayes’ theorem be used to e ciently update the belief state, i.e., compute:



P (Target in CellijObservationst ^ Failure in Cellj ) :
(4)



Given the observations up to time t, the belief state captures the current probability the target is in a given cell. What is the probability that the target will be found in Cell i if it is searched:



P (Target found in CellijObservationst)?
(5)



Consider comparing the following two decision rules:



{ Rule 1: At any time, search the cell with the highest probability of containing the target.




{ Rule 2: At any time, search the cell with the highest probability of nding the target.




For either rule, in the case of ties between cells, consider breaking ties arbitrarily. How can these rules be interpreted / implemented in terms of the known probabilities and belief states?




For a xed map, consider repeatedly using each rule to locate the target (replacing the target at a new, uniformly chosen location each time it is discovered). On average, which performs better (i.e., requires less searches), Rule 1 or Rule 2? Why do you think that is? Does that hold across multiple maps?




2
Department of Computer Science - Rutgers University










Consider modifying the problem in the following way: at any time, you may only search the cell at your current location, or move to a neighboring cell (up/down, left/right). Search or motion each constitute a single ‘action’. In this case, the ‘best’ cell to search by the previous rules may be out of reach, and require travel. One possibility is to simply move to the cell indicated by the previous rules and search it, but this may incur a large cost in terms of required travel. How can you use the belief state and your current location to determine whether to search or move (and where to move), and minimize the total number of actions required? Derive a decision rule based on the current belief state and current location, and compare its performance to the rule of simply always traveling to the next cell indicated by Rule 1 or Rule 2. Discuss.



An old joke goes something like the following:



A policeman sees a drunk man searching for something under a streetlight and asks what the drunk has lost. He says he lost his keys and they both look under the streetlight together. After a few minutes the policeman asks if he is sure he lost them here, and the drunk replies, no, and that he lost them in the park. The policeman asks why he is searching here, and the drunk replies, "the light is better here".




In light of the results of this project, discuss.







A Moving Target



In this section, the target is no longer stationary, and can move between neighboring cells. Each time you perform a search, if you fail to nd the target the target will move to a neighboring cell (with uniform probability for each). However, all is not lost - whenever the target moves, surveillance reports to you that the target was seen at a Type1 x Type2 border where Type1 and Type2 are the cell types the target is moving between (though it is not reported which one was the exit point and which one the entry point.




Implement this functionality in your code. How can you update your search to make use of this extra information? How does your belief state change with these additional observations? Update your search accordingly, and again compare Rule 1 and Rule 2.




Re-do question 4) above in this new environment with the moving target and extra information.












































































3