one of the most used Technologies today is your Maps application you can plug in a starting point ending point and find the best route to optimize time distance cost and many other factors it's efficient convenient and ends up being a vital part of the modern world but behind these types of mapping applications are a lot of interesting computer science Concepts today we're going to dive into some of the algorithms that drive this technology specifically I want to build up to an intuitive presentation of one of these fundamental Al gorithms called AAR search which combines ideas from various approaches to solving such problems through our journey we'll interact with some of the core ideas in artificial intelligence and intelligence search in complex [Music] systems before we get into details let's start with how we even represent shortest path problems on a computer imagine you're in the US and youd like to find the shortest path to travel between two cities a nice way of modeling this problem is through a graph where each node is a city and the links or edges between cities can be thought of as imaginary roads these edges can have weights associated with them that can be interpreted as the cost it takes to travel between them whether that be distance time or some other metric now within the framework of this graph our problem becomes significantly more concrete given a a starting node and a goal node what's the best way to explore the graph and find the path of minimum distance between them imagine we were put back in a time before GPS and navigation how would we approach this problem well we might look at this graph and basically start going in a direction that gets us closer to the destination what we might do is assign every node in the graph an estimate of how close it is to our final goal we can do this by just Computing the straight line distance between each node and the goal State then we can pick the node that gets us closest to our destination until we reach it this approach is fundamentally a greedy algorithm for solving this problem the good thing about it is we end up finding a route and it's generally not going to be the worst possible path but as you can guess it's not the optimal path one problem with this approach is we don't really keep track of the cost it takes to Traverse the path all we care about is that we are getting closer to the goal the true optimal path here has to go through a node that doesn't get us as close to the goal as possible which our greedy algorithm just completely [Music] misses okay so back to the drawing board maybe let's see if we can solve a simpler version of the shortest path problem to get some insight suppose we have the following simple graph and we want to start here and get to this gold state our goal right now is to find some solution ution that guarantees finding the optimal path it's often helpful to work backwards we know the optimal path has to eventually reach the goal State looking at the goal State there are three options of reaching there from adjacent nodes now let's say some high power tells us the optimal path to each of these nodes given this information how would you decide what the optimal path is to the goal [Music] well we have three options to the goal and the optimal path is just going to be the minimum cost of the resulting paths this is a key idea the cost of an optimal path to some goal State can be broken down into separate parts we first take the optimal path from the start to each adjacent node of the goal then we add the cost of traversing from that adjacent node to the final goal and finally the minimum of these costs is the optimal path this applies to all parts of the graph so it implies that we should be able to incrementally build up the optimal path the next approach to solving this problem does exactly that at a high level if we wanted to find the optimal path from node 0 to node 8 we can incrementally build optimal paths the algorithm is very conservative in its expansion in that every time it reaches a node it's guaranteed to a found the optimal path to that node it continues until we find the optimal path to the state that we care about this approach is called uniform cost search and is guaranteed to find the shortest path between two nodes let's break down the details of how this works when we start off at node zero we've incurred no cost and we have two options of exploration what we can do is put these options in a queue and order the queue by the cost it takes to reach that node from the start this is often called a priority queue we'll then explore noes incrementally based on which one is taken off the queue first so here we explore three next the nice property here is that when we've taken a note off the queue we're guaranteed to have found the shortest path to that node and we continue this process from node three there are four nodes we haven't explored yet so we can put them into the queue and the total cost it would take to reach these nodes we then pop off the next node from the queue and proceed again the most important note here is that every time we pop off a node from the priority Q we found the shortest path to that node the algorithm slowly expands from the starting node and incrementally builds opal paths to intermediate nodes we continue this process until we pop off the goal state which gives us the optimal path from node 0 to node 8 this happens to have cost 7. 2 in this example uniform cost search is great in the sense that it guarantees finding an optimal solution but it does in a sense feel somewhat weird say for example we run it on a fairly large graph like the following we start in the center node and want to reach the node on the upper right as uniform cost search expands what intuitively looks a little strange here well imagine your starting point is Dallas and your goal is is New York and you ask a travel adviser on the best flight to New York if they told you they tried looking for a flight that went through Los Angeles you'd probably find a new travel advisor fundamentally it's just weird as a human to even consider exploring Los Angeles if we wanted to find the optimal route between Dallas and New York in a sense this goes back to our first intuitive greedy approach even though the greedy approach doesn't end up finding the optimal solution it actually ends up EXP a very small set of nodes before finding a path fundamentally the greedy approaches would never even bother going west in this graph so we have two approaches with different characteristics the greedy approach relies on an estimate of how close it's getting to the go without factoring in the cost of getting there it's generally not going to find an optimal path as a result but one nice thing about it is it finds a path relatively quickly the other approach uniform cost search is the polar opposite when it arrives at a node it is guaranteed to have found the optimal path to that node but as a result it uselessly explores parts of the graph that it really should not need to what we need is some Middle Ground here and that's where the brilliant idea of the AAR search algorithm comes into play to understand how this works let's formalize the difference between the two algorithms in uniform cost search we add notes to the priority CU based on the cost it took to arrive at the node it turns out that greedy search is fundamentally the same type of algorithm with one key difference we can still use a priority queue but this time instead of placing the node in the queue with the cost of arriving to the node we instead add it with the estimate of how long it takes to get to the goal this estimate can be something like the straight line path distance or more formally the ukan distance between nodes the algorithm for expanding nodes that have the lowest cost is fundamentally the same but how we calculate the cost is different quite elegant [Music] actually so given this what's a natural way we can find a middle ground between these two approaches what could we [Music] try well what if we combined information from the actual cost it takes to get get to a node and our estimate to the goal specifically let's now change the algorithm to calculate the cost associated with the node as the sum of the actual cost to arrive plus the ukian distance estimate to the goal let's run through it and observe the outcome initially only node zero is in the Q with a priority of seven determined by its turistic estimate h of 0 of 7 since we haven't covered any distance yet G of 0 remain zero after popping off node zero we add its neighbors 2 and three node 2 has a heris value of 4. 7 in AAR search the total weight considers the 2.
4 distance traveled to reach it resulting in 4. 7 + 2. 4 is = to 7.
1 similarly node 3 totals 2. 2 + 5. 4 equal to 7.
6 upon removing node 2 we add its neighbors notably node 5 right to the top of the Q due to its heris of 2. 8 adding the distance traveled so far 4. 4 gives us a total of 7.
2 node 5 is then DED and shortly thereafter we reach the goal what's remarkable here is that we find the optimal path while expanding significantly fewer nodes compared to uniform cost search this approach to solving the problem is called AAR search formerly AAR search in incorporates uniform cost search with an added heuristic in this example we used ukian distance as the heuristic and it happened to find the optimal Solution One neat way to visualize how this works is to imagine that theistic is a third dimension to the graph uniform cost search incorporates the actual distance between the nodes while theistic in a way tilts uniform cost search towards the goal state so we have an approach that is faster than uniform cost search the next natural question is whether it's guaranteed to find the optimal path well it definitely depends on the heuristic in the following graph we show the optimal path between Node 1 and 8 let's see how the choice of heuristic impacts finding the optimal path if our heuristic is literally a random number generator it's pretty easy to show that AAR search is not going to find an optimal solution but even on a large map with many nodes if I pick the ukian distance running the algorithm does actually end up giving the optimal path and it turns out that AAR search is optimal with some constraints on theistic let's play around and see if we can discover what sort of conditions are needed suppose instead of using ukian distance as a heris STI we instead Define Another Hero stick that takes something called The Manhattan distance the Manhattan distance is defined as a total vertical and horizontal distance that needs needs to be traversed between two points with the Manhattan distance as theistic do we think that a star search will find the optimal path well if we run through the algorithm what ends up happening is we find another path that is not optimal what went wrong here well it's actually not too difficult to dissect a problem if we go step by step the optimal solution involves making a decision between nodes four and five we should pick node 4 but when we use Manhattan distance we end up picking node 5 why if we look at the Q node 4 ends up having a higher cost than node 5 the Manhattan distance ends up actually overestimating the cost it takes to get from node 4 to the goal the ukan distance in contrast is always an underestimate that's by definition the ukian distance is the straight line path between two n no and every possible graph path between two nodes is guaranteed to be at least the ukian distance this brings up the topic of heris admissibility a heris STI is considered admissible if it's always an underestimate of the optimal path for AAR search to be optimal it must be the case that theistic is admissible AAR search as a whole is not too complicated of an algorithm the real tricky part of implementing AAR search in practice is finding reasonably good admissible her istics for example it's really easy to just set theistic to be zero which is technically admissible but if we do that a star search then reduces to just doing uniform cost search so we don't get any benefit of theistic on the opposite side of the spectrum the best admissible heris possible is just the actual optimal path between the two nodes but that's impractical because if we knew the optimal path between all the nodes what we even doing solving this problem it's important that hero sticks are relatively easy to compute finding the balance between these two extremes is the real art of implementing these algorithms in practice AAR search is the basis of most modern pathf finding algorithms in mapping applications looking back on what we did what I think is the most beautiful aspect of this algorithm is how it merges two seemingly diametric approaches to solving a problem one that is rigorous and careful and the other that is greedy and opportunistic in many ways the AAR search algorithm is a great story of combining computational rigor with human intuition and many of the most challenging problems in computer science require perspectives from both in this video we explored the fundamental algorithms used in today's mapping and navigation applications for those eager to delve deeper into various modern Technologies in an engaging visually driven format brilliant the sponsor for this video is an excellent excellent resource brilliant emphasizes learning through hands-on experience offering thousands of interactive lessons spanning math data analysis programming and AI personally I've been engrossed in brilliant's latest course series how technology Works which features outstanding interactive resources covering a wide range of captivating topics recently I found their new series on how llms work particularly intriguing this series breaks down tools like chat GPT from first principles providing Hands-On lessons where you interact directly with real language models you'll discover how these models predict the next word learn to customize their outputs and grasp the significance of training data the course is designed to make complex Concepts accessible fostering an environment that encourages exploration and experimentation I firmly believe that active engagement is key to mastering computer science Concepts and brilliant's approach exemplifies this philosophy to try everything brilliant has to offer for free for full 30 days visit brilliant.
