This thesis explores a variation of the state space search problem, moving target search. The objective for the problem solver, placed in a search space and subjected to severe time constraints, is to catch a moving target. This thesis presents new methods for doing moving target search. One algorithm, Forgetful Depth-First Search, adapts the well-known Depth-First algorithm to this problem domain. Also, a search technique called Marking quickly acquires general knowledge about the search space. These methods are discussed and compared with other known methods. Experimental results show that Forgetful Depth-First Search and Marking give good performance and are better than previous methods. |