15-780: Graduate AILecture 2. A*, Spatial Search Geoff Gordon (this lecture)Ziv Bar-Joseph TAs Geoff Hollinger, Henry LinAdminSlides on web siteMatlab tutorial next Tue (5-6 NSH 1507)Please send your email address to TA Henry Lin (thlin at cs), who is compiling a class email listPlease check the website regularly for readings (for Lec. 1–2, Ch. 1–4 of RN)ReviewTopics coveredWhat is AI? (Be able to discuss an example or two)Types of uncertainty & corresponding approachesHow to set up state space graph for problems like the robotic grad student or path planningTopics coveredGeneric search algorithm & data structuresSearch methods: be able to simulateBFS, DFS, DFIDHeuristic searchWhat are advantages of each?ProjectsProject ideasPlan a path for this robot so that it gets a good view of an object as fast as possibleProject ideasDo something cool w/ Lego Mindstormsplan footstep placementsplan how to grip objectsA* SearchHeuristic search looking badHeuristic search looking badGeneric searchS = { start } M = ∅While (S ≠ ∅)x ← some element of S, S ← S \ xCheckSolution(x)For y ∈ neighbors(x) \ MS ← S ∪ {y}M = M ∪ {x}A* search: Open listImplement S with priority queueS.insert(x, P)S.pop()and maybe S.test_member(x)Like heuristic searchbut priority calculated differently (more below)A* search: Path costsFor both priority and closed list, maintain path cost function g(x)g(x) = best cost to reach x so faror ∞ if no path from start to x found yetWhen pushing y, set g(y) = g(x) + c(x,y)if g(y) finite, smaller of old and new valuesA* search: Closed listImplementation of M: use g(x) and SIf g(x) finite, x must be either open or closedSo, M = { g(x) finite ∧ x ∉ S }This is where we’d use S.test_member(), but it will turn out we can be slightly smarterA* search: PriorityWhen calling S.insert(x, P)Set P = f(x) ≡ g(x) + h(x)h(x) = heuristic estimate of distance from x to goal (just like in heuristic search)f(x) = estimate of cost of path through xIdea: focus on nodes that might yield short pathsGeneric searchS = { start } M = ∅While (S ≠ ∅)x ← some element of S, S ← S \ xCheckSolution(x)For y ∈ neighbors(x) \ MS ← S ∪ {y}M = M ∪ {x}Add to SInitialize MUpdate MM checkA* searchRemove and return an element of xS = { start } g(x) = ∞ (∀x)While (S ≠ ∅)x ← S.pop()CheckSolution(x)For y ∈ neighbors(x)g(y) = min(g(y), g(x) + c(x,y))If g(y) decreased, S.insert(y, g(y)+h(y))Admissible heuristicA* has nice theoretical properties if h is admissibleThat is, h(x) ≤ true distance from x to goalE.g., crow-flies distance in a mazeIntuition: make a path look better, we examine it earlier, maybe waste some work. Make it look worse, we might miss it entirely, find a bad solution.A* exampleA* exampleNode costsPath costsMore complicated A* exampleOptimal Solution End-effector Trajectory Probability of Obstacle Appearing Probability of Obstacle AppearingSolution CostState ExpansionsFigure 10: Environment used in our second experiment, along with the optimal solution and the end-effector trajectory (withoutany dynamic obstacles). Also shown are the solution cost of the path traversed and the number of states expanded by each ofthe three algorithms compared.other words, by adding a fixed value to the key of each newstate placed on the queue, the old states are given a rela-tive advantage in their queue placement. When a state ispopped off the queue whose key value is not in line withthe current bias term, it is placed back on the queue with anupdated key value. The intuition is that only a small num-ber of the states previously on the queue may ever makeit to the top, so it can be much more efficient to only re-order the ones that do. We can use the same idea when !decreases (from !oto !n, say) to increase the bias term by(!o− !n) · maxs∈OP ENh(sstart, s). The key value of eachstate becomeskey(s) = [min(g(s), rhs(s)) + ! · h(sstart, s) + bias,min(g(s), rhs(s))].By using the maximum heuristic value present in the queueto update the bias term, we are guaranteeing that each statealready on the queue will be at least as elevated on the queueas it should be relative to the new states being added. It isfuture work to implement this approach but it appears to bea promising modification.Finally, it may be possible to reduce the effect of un-derconsistent states in our repair of previous solution paths.With the current version of AD*, underconsistent states needto be placed on the queue with a key value that uses an un-inflated heuristic value. This is because they could reside onthe old solution path and their true effect on the start statemay be much more than the inflated heuristic would suggest.This means, however, that the underconsistent states quicklyrise to the top of the queue and are processed before manyoverconsistent states. At times, these underconsistent statesmay not have any effect on the value of the start state (forinstance when they do not reside upon the current solutionpath). We are currently looking into ways of reducing thenumber of underconsistent states examined, using ideas veryrecently developed (Ferguson & Stentz 2005). This couldprove very useful in the current framework, where much ofthe processing is done on underconsistent states that may notturn out to have any bearing on the solution.ConclusionsWe have presented Anytime Dynamic A*, a heuristic-based,anytime replanning algorithm able to efficiently generate so-lutions to complex, dynamic path planning problems. Thealgorithm works by continually decreasing a suboptimal-ity bound on its solution, reusing previous search efforts asmuch as possible. When changes in the environment areencountered, it is able to repair its previous solution incre-mentally. Our experiments and application of the algorithmto two real-world robotic systems have shown it to be a valu-able addition to the family of heuristic-based path planningalgorithms, and a useful tool in practise.AcknowledgmentsThe authors would like to thank Sven Koenig for fruitfuldiscussions. This work was partially sponsored by DARPA’sMARS program. Dave Ferguson is supported in part by anNSF Graduate Research Fellowship.ReferencesBarbehenn, M., and Hutchinson, S. 1995. Efficient searchand hierarchical motion planning by dynamically maintain-ing single-source shortest path trees. IEEE Transactions onRobotics and Automation 11(2):198–214.Barto, A.; Bradtke, S.; and Singh, S. 1995. Learning toAct Using Real-Time Dynamic