weakstrong tatanunknownlocation SearchingaknownundirectedgraphGfortreasure Examples.pdf

Online exploration and navigation Many problems in Algorithms and AI can b e cast as sea rching a known environment of some unknown typ e in order to reach a known destination unknown Yardsticks Generality what kinds of situations can you handle low high What is your p erformance measure weak strong Examples Searching a known undirected graph G fo r treasure t at an unknown lo cation Minimize max timetoreach Traveling Sales t man Problem Given a prior P minimize E timetoreach P Traveling Deliveryman problem Minimi ze max timetoreachsho rtestpath t general fo rm of cowpath problem Eg lo oking fo r a hole in a fence Examples contd Searching an unknown graph G to reach a goal at unknown lo cation G is undirected minimiz e distance as function of jG j depthrstsearch G is undirected minimiz e distance roughly as function of how many no des BFS would visit approximate BFS without telep o rtation G is directed with probabilistic transitions goal is to visit t as frequently as p ossible Markov Decision Pro cesses Qlearnin