## Description

Heuristic search is a discipline under the larger umbrella in AI. Heuristic search algorithms find solutions to a variety of problems, including pathfinding, logistics, and scheduling. Most of the problems heuristic search is applied to are hard in the formal sense. This forces us to find new techniques to tackle larger problems and new domains — we can’t simply wait for improved

hardware to solve it for us. When developing new AI algorithms, understanding what has come before and why it fails to perform in a new domain is critical. In this talk, we’ll look at how algorithm visualization drove the development of state of the art AI algorithms for heuristic search.

### Key takeaways from the session:

- I hope to impress people with the idea that the first step to improving anything, even the state of the art in a field, is to build an intimate understanding of that thing.
- Second, that visualizations are an important tool in building an understanding of the behavior of a thing, in this case an algorithm.
- Finally, that AI isn’t science fiction. The simplest algorithms are accessible to anyone that wants to invest time in understanding how AI interacts with the world around us.

## About the speakers

As AI practice lead at SEP Jordan’s responsibilities include educating clients and peers about what AI can do, identifying complex problems AI can address in whole or in part, and incorporating AI into software products that make a difference for their users.

Prior to joining SEP, Jordan held roles as a research scientist for a startup, the Charles-Stark Draper Laboratory, and an R&D consultancy. In each of these positions, he did essentially the same thing: found and delivered feasible solutions to technically challenging problems that arise in a wide variety of domains and industries.

He completed his PhD in artificial intelligence at the University of New Hampshire in 2012. His research focused on using approximation and machine learning to solve problems known to be computationally intractable, such as automated planning and scheduling problems.

## Resources

Jordan Thayer

Hello there. I’m Jordan Thayer and I’m going to talk to you about how visualization improved artificial intelligence. So just to go through a brief outline of what the talk is, we’re going to start with, what is artificial intelligence? And then specifically, what is heuristic search, which is my research area within artificial intelligence. And then we’re going to show two ways in which visualizations helped us direct our research in artificial intelligence to get better performance. One is by looking at performance graphs and finding good promising research areas to investigate. And another was using visualizations of algorithm behavior to understand the bad behavior of one particular algorithm and develop a an improved version of that algorithm that had better performance, after which we’ll wrap up.

Jordan Thayer

So if you don’t make it through the whole talk, I just want to give you the the takeaway right here up front. Visualizations of algorithm behavior were fundamental to our ability to conduct research in heuristic search and to understand what it was that we had built, and if you are someone who builds systems or someone who does research, you should really build tools that help you understand the thing that you’re most interested in building. Be that visualizations or other techniques for understanding the underlying data because that’s the critical thing.

Jordan Thayer

So what is artificial intelligence? I argue that artificial intelligence is something that can sense its environment and plan for a desired outcome and execute that plan on its own. So here in this image, we see a number of things that I would consider to be artificial intelligence. From the extreme end we have data from Star Trek. Data is what we would call general artificial intelligence, something that we recognize as a human intelligence. And then we have more things commonly thought of as artificial intelligence from route planning to the robots that work on assembly lines and build many of the things that we interact with everyday. Alexa with with its ability to understand human speech and questioning, answering and get responses to query. And then on the very far end, we have the humble thermostat. And according to this definition, the thermostat is in fact intelligent, right? It can sense its environment. It has a thermometer and its environment is only concerned with the temperature, it has actions that it can take. It can crank the heat, it can turn on the AC, it can just coast and let the ambient environment change the temperature back towards the desired level. And I think that I hammer on the thermostat because artificial intelligence is really a spectrum of increasingly complex systems from the very, very simple system like the thermostat to the incredibly complicated things that we may never achieve, like general intelligence.

Jordan Thayer

In general, artificial intelligence can fall into a number of different categories. There’s machine learning, which I think many of us have heard of by now with its ability to classify images or find patterns and functions from data. There are systems that interact with the physical world like robots, but also optical character recognition tools, sentiment analysis tools, and things of that nature. There are whole fields of artificial intelligence devoted just to how we write down information and represent it programmatically. And then there’s the area I’m going to talk about today, which is search, heuristic search, in particular, with its ability to construct long range plans.

Jordan Thayer

So what is heuristic search other than a particular topic under the umbrella of artificial intelligence? Well, this is an example of a heuristic search problem. Here we see I find myself in a two dimensional grid world. I’m in the cell here on the center left and I would like to reach the frosty beverage on the upper right. In this world, I have the ability to take actions. I can move in the cardinal directions. In my original location, I can only move up and down. I can’t move to the west, because that would take me off the map. And I can’t move east because it would put me in this block cell right here.

Jordan Thayer

Heuristic search problems have goals. In this case, the goal is to arrive at the beer. And the plan that would take me to it is represented by this green line here. So that would be you know, down, right, right, up, up. That’s the full plan of action from my starting location to the goal location. You can think of heuristic search as sort of inducing a tree over a state space of the problem.

Jordan Thayer

So here’s a here’s a different heuristic search problem. I’m in some starting location. I want to reach a goal in the upper right. And I consider all possible plans of length one coming out from the starting state, right. The plan in which I move up and the plan in which I move to the right. And we repeat this, on and on and on generating this very, very large tree, right? So here’s the plan, which I move up and up again, here’s the plan in which I move up and then down, right, and then right again, right and then left. And you can imagine that as we expand out this tree, eventually, if there is a solution to the problem, we will encounter it.

Jordan Thayer

And heuristic search is largely concerned with the problem of how do I efficiently enumerate the portion of this tree which is necessary to find a solution and prove certain properties about it? So obviously, we wouldn’t be excited about heuristic search if it was only capable of solving problems on a three by three grid. You and I can see how to solve that problem immediately. It’s not particularly interesting if an algorithm can do it for us too.

Jordan Thayer

Here is heuristic search path planning on a much, much larger instance. It’s still a grid navigation problem. What we’re trying to do is we’re trying to navigate from the center left here to the center right over here. And what we’re looking at is a visualization of the expansion order of the search algorithm. So like, like before, cells that are in white are cells that we can pass through. The cells that are in black are cells that are blocked. And then there’s coloration from yellow to red. Yellow cells were expanded very early in the search process near the root of that tree that we saw before. And as you move from yellow to red, you see that you’re seeing nodes that are expanded later and later and later in the process.

Jordan Thayer

So what we see here in terms of the behavior of the search algorithm is it starts near the start state, and then it radiates out in the sort of conical flame from there towards the goal state. So we’re actually looking at the performance of a heuristic search algorithm called A* search. And it has this property where it starts near the starting state, expands towards the goal, and uses what’s called a heuristic, sort of an estimate of cost to go, to draw its attention towards the goal state. It’s one of the most famous algorithms in heuristic search.

Jordan Thayer

So stepping away from the visualization of expansion, I’m going to go to performance graphs and talk about how performance graphs showed us some promising opportunities for developing new algorithms and how I wrote my first research paper on optimistic search.

Jordan Thayer

So Weighted A* and A* actually are, are very similar algorithms. Weighted A* is A* with some weighting, applying more importance to the heuristic function. So here’s Weighted A* run with a weight of one. It’s exactly like A*. As we increase the weight, the focus of the search towards that goal state increases, right? We’ve thinned out the flame and drawn it towards a point more. And this is a weight of I think about 1.5. Here we see it with a weight of two. Now the conical shape is almost gone. And we’ve just got this directed path. As we increase the weight even more, that path gets thinner and thinner. So there’s less than the search space that Weighted A* needs to explore in order to find a solution and prove some interesting properties of it.

Jordan Thayer

So just to reiterate, right, this is many, many, many more nodes, or more paths considered than this, which is far more paths considered than this, and so on and so forth. And that results in a reduction in the time it takes to find solutions.

Jordan Thayer

So here we see the performance of Weighted A* on a common benchmark problem for heuristic search. The 15 puzzle of the sliding tile puzzle as you might have heard it called before. On the x axis, we have the sub optimality bound that’s the weight in Weight A*. And on the y axis, we’re looking at the total CPU time consumed to find a solution. So you know, here’s about a second, thenths of seconds, hundreds of seconds milliseconds. Up here, we’re talking about minutes.

Jordan Thayer

So you can see that as we crank up the weight or the bounded Weighted A* the amount of time that we’re requiring to find the problem drops off precipitously.

Jordan Thayer

But there’s this other thing that we care about in heuristic search. It’s not just the time to find solutions. It’s the cost of the solution, sometimes the we’ve called it the sub optimality mound over here, and I’m not going to get into detail about that. But it’s the guaranteed difference between the cost of the solution found and the optimal solution to the problem, the cheapest possible solution to the problem as a factor of the cheapest solution. So here we see the performance of Weighted A* on another problem. And we see that as we increase the sub optimality mound, the final solution cost relative to A* does increase but it increases far slower than the theoretical guarantee. Right? So any bounded sub optimal algorithm has to stay underneath this Y equals X line. And Weighted A Star grows, but it doesn’t grow as quickly as this line grows. And what that showed us in terms of these performance graphs was that there’s this gap here, right? I could have run Weighted A* with a way, way bigger weight, and still been guaranteed and still have been underneath the bound in most cases.

Jordan Thayer

And wouldn’t it be nice on this performance graph over here to be able to get the performance of a bound of four or five, and have the guarantee of the bound of two, right? Wouldn’t it be nice to for shorten this curve in this way, such as I got those better performance guarantees earlier if the solutions that I returned are already good enough. And so we set out to build an algorithm that exactly played with this idea once we noticed it from the performance graphs. And that algorithm is called optimistic search. The notion is that you run Weighted A* with a weight way higher than the bound, so, W, the weight in Weighted A* serves as both the waiting on the heuristic and the guarantee of quality the bound. So we’re just going to ratchet that way, way up. And then we’re going to prove that the solution we found was within the bounds that we actually wanted in the first place.

Jordan Thayer

And then we added some, we added an escape hatch in the algorithm, which is, hey, by the way, if you get bit by this thing, where maybe the solution you find in the first case isn’t within the bound, here’s some magic to help fix that if that situation arises. So we call that algorithm optimistic search, it was optimistic in the sense that we were going to run Weighted A* with a weight higher than the bound and we were going to optimistically assume that the solution we found was sufficiently good. In many cases it was. At the time, 2008, optimistic search was the new state of the art and bounded sub optimal heuristic search.

Jordan Thayer

So here’s a performance graph from that paper. We’re loking at the difference between A* as problem size increases, you can see this exponential growth. Weighted A* also has exponential growth. And optimistic search suffers from exponential growth as well. But you notice that it grows slower than Weighted A* and A*. And this is for the same can parameterization of Weighted A* in optimistic search. On the other hand, the solution cost of optimistic search does grow faster, as problem size increases relative to the cost of A* then Weighted A* and this is exactly what you would expect. We did after all ratchet up the weight in order to get these improved performance guarantees.

Jordan Thayer

So if we look at the expansion order of optimistic search, this is what happens. So this is the same sort of flame graph we were looking at before. Problem is the same, we’d like to navigate from the center left to the center, right. And you can see that there’s this, it’s exactly like one of the Weighted A* images we saw before, in fact, right? There’s this thin yellow to orange to red thread that runs through the center of the problem. That’s the Weighted A* search with the high bound value with the weight way, way bigger than the bound that we intend to prove. So we get some solution. And then we come back here and expand nodes as if we’re a limited version of A*, and do some work to prove that the solution was in the bound. So this is basically an image of the algorithm behaving exactly as we would have expected it to behave given the way it was designed. And that was pretty cool.

Jordan Thayer

So when we went to present, optimistic search for the first time we were giving this talk to a body of our peers at the International Conference on Automated Planning and Scheduling. And as often happens during these talks, right, you give the talk and then someone asks questions afterwards. And in this case, it was a gentleman who had developed an algorithm called A* Epsilon, way back in the 80s. So this was 2008, so nearly 30 years prior, and he said you know, I had this other improvement on Weighted A*. Why didn’t you compare against it?

Jordan Thayer

Truth be told we had. So we had compared against A* Epsilon. But in the domains in which we the domains for which we were concerned, its performance wasn’t comparable with Weighted A*. It was just generally dominated. And we explained that we said, you know, we didn’t investigate it. And for many domains, we found that its performance was unacceptably bad, in fact, worse than A* for bounds for bounds greater than one, and far worse than Weighted A* in many domains. And we don’t understand that behavior perfectly yet. But we do know that we have the correct implementation because we managed to replicate your results in the domains of your consideration. So that’s, you know, that’s not a satisfying solution to say, empirically I know this doesn’t work. But I don’t understand why.

Jordan Thayer

So what we did was we said, well, we can’t go on not understanding why this worked. Let’s build some tools to understand how A* Epsilon behaves, and maybe we can figure out what’s all what’s up with that bad behavior. So, A* Epsilon is a bounded suboptimal algorithm much much like Weighted A*. It does this neat thing where it maintains multiple orderings over the nodes. So it has this concept of an open list in which all partial solutions that it’s considering are stored, and they’re sorted on an estimate of their total cost. In fact, a lower bound of their total cost. And then of this open list, it builds a focus group to consider more rigorously called focal and those nodes are sorted in their order of closeness to a goal or estimated closeness to a goal. So roughly, A* Epsilon expands that node which it knows it can prove is within the bound, and which it thinks is as close to a solution as possible. And if you’re a bounded suboptimal search researcher, this is really attractive because it’s optimizing exactly the thing you would normally like to optimize. Find solutions within the bounds as quickly as possible. And all else being equal, there’s this intuition that solutions that are near to completion are easy to complete. So that would give you the as quickly as possible part.

Jordan Thayer

Unfortunately, this isn’t so with A* Epsilon. It has this weird aberrant behavior for certain bounds. And that’s what we’re seeing here. So this, this tulip-like graph is an expansion order visualization of A* Epsilon. Again, we start the search in the center left here, and we expand all the way out to the center right. And you can see that there’s this very, very thin thread at the start. And then there’s this flame like shape of A* that starts about midway through the graph. So what’s happening is A* Epsilon quickly reaches into the center of the graph, but then has to expand a whole bunch of nodes to find a relatively good completion of the path. In order to prove that a solution is within the bounds. Basically it, you can kind of see it here in this weird dog laying and down, it makes some suboptimal choices, sorry, it makes some expensive choices right in here, and it has to recover those in there. If you look at the performance graphs of A* Epsilon, you see this behavior sort of more pointedly but you don’t see why it’s happening.

Jordan Thayer

So here is a comparison of A* Epsilon versus an algorithm we’ll talk about in a second explicit estimation search on a dock robot problem, moving shipping containers around a dock yard. You can see that as the bound is increased, so as we allow more and more expensive solutions relative to optimal, A* Epsilon fails to improve which is exactly not the behavior that you want to see out of a bounded suboptimal search algorithm. But in other domains, like the sort that it was proposed on A* Epsilon does improve smoothly.

Jordan Thayer

So why is that? Well, it’s, in fact, it’s because of the focal ordering and the open ordering that A* Epsilon uses. So it turns out, I believe this is the next slide. Yeah. So here’s the problem. A* Epsilon can prove or within the bound right now, and then it reorders those nodes based on their nearness to the goal. So what happens is, we take some node off of focal, we generate its children and we throw them back on the open list, and maybe they make it on the focal maybe they don’t. But the problem is, is that frequently, they don’t. See how the green node here is the cheapest node on open. And it’s not the best node on focal. We’re going to expand this red node here. So what’s going to happen is we’re going to expand a node on focal, and none of its children are going to make it onto the focal list. Again, their their heuristic estimates are slightly wrong. So their overall cost rises a little bit. And they no longer meet the criteria to move from this list to this list.

Jordan Thayer

So what happens is we end up flushing this queue to expand the children of this node. We can’t cover, we can’t cover the ground from this node to the goal, even though the search is saying, well, we think this node is within the bound, and we’d like to pursue it to completion. And that tension between being able to prove something is bounded and the conflict in that ordering and the ordering on nearness to solution causes the bad behavior in A* Epsilon.

Jordan Thayer

So after we had figured that out with the expansion order visualizations, we said, well, maybe we can rehabilitate this. Maybe we can refine the rules a little bit. And we developed an algorithm called explicit estimation of search to do that. So just like A* Epsilon, we have an open list ordered on best F. So sort of the here’s the lower bound on optimal solution costs for the space. And then we built another list called Best f hat, which is the same notion, but it’s not a bound anymore. It’s our best effort guess at the optimal solution cost for the problem. And then the focal list is built on top of it. So the notion is now not, it’s the node that we can prove is within the bounds that we think is closest to the goal. It is, of those nodes, we believe to be within the bound, which is closer to the goal. And that difference between proof and belief is what gave us the better performance and explicit estimation search. So again, we have the open list sorted on F. And then we have the F hat list and you can see that the nodes are radically differently ordered here right like this, this bluish purple node it gets kicked to the end, red and green a reverse.

Jordan Thayer

That’s not all that surprising. But the the tension between the ordering of f hat and the ordering of focal is no longer as tight or as contentious as the ordering of open and focal because we’re not dealing with lower bounds, we’re dealing with best case estimates. So, in general, when a node comes off a focal, it’s more likely that its children make it back on, especially if our total estimate of our most accurate estimate of solution cost is better than a lower bound, which often it is because we’re not constrained to underestimate.

Jordan Thayer

So this is a visualization of explicit estimation search expanding the same or solving the same grid pathfinding problem that we just had A* Epsilon solve, right. So again, we’re starting in the center left, we want to navigate to the center right. And you see that rather than darting into the center and having that weird tulip shape, instead what we do is we have an expansion order like a protracted A* just like we did for optimistic search very, very early on, right? All of these nodes are yellowish starting to turn towards orange, then after we’ve, that portion of the search really raises the lower bound on optimal solution cost to an acceptable level, such that within the bound, we think we can pursue a solution to completion, right? And we go out here and we expand some of this. And here in this area of the space, the algorithm loses faith a little bit. It has to shore up its bound a bit, but not a lot, right, just a couple of nodes around the edge, and then it manages to drill towards the end.

Jordan Thayer

So by understanding what it was A* Epsilon was doing, we were able to tweak the rule set just a little bit. And that small difference in rules led to WAY WAY better performance overall. This algorithm was published in 2012. And it was at the time of its publication, the best performing algorithm in bounded sub optimal search at least according to the benchmark set that we had evaluated on. So, just to come back to these performance graphs right, EES is explicit estimation search and we see for domains on which A* Epsilon is totally non performance, we are absolutely dominating it by several orders of magnitude in terms of performance. And for domains in which A* Epsilon already performed well, the domains for which it was implemented effectively, we find that we are often better than it. And as the bound gets very, very high, of course, there’s no separation in the confidence intervals between the two performance graphs. So, we can’t really conclude anything other than they perform comparably at high weights or high bounds. And here are tight bounds, EES has some advantage.

Jordan Thayer

So, just to wrap things up, when I was starting my PhD and doing these, doing this research of algorithm behavior, I spent a lot of the startup time there developing plotting tools to show algorithm performance and to record algorithm performance. And to, and many, many hours building these visualization tools for grid search so that I could see the expansion order of algorithms. I, at the time, felt that that was sort of, you know, a waste of time. I was building this for presentations, and only for presentations, just to convince people that weren’t heads down in the research of what was going on. But that was totally wrong.

Jordan Thayer

I never did more effective work in the entirety of my PhD than I did when I was building those plotting tools and those visualization tools, because those were the things that allowed me to understand what it was I was building, where it performed well, where it performed poorly. And understanding where it performed well showed me some very, very useful avenues of research to pursue further. And where it performed for really helped me design new algorithms that avoided the pitfalls of my previous work and other’s previous work.

Jordan Thayer

So if you are someone who does research or who builds systems, I encourage you very strongly to sit down and think about how you can build tools to help you understand the things that you’re working on, because that understanding is critical to building effective systems. Thank you all very much for your attention.

Transcribed by https://otter.ai