Problem Solving with Mazes and Crayon

I want to talk about a few differ­ent ap­proaches to gen­eral prob­lem solv­ing (for hu­mans). It turns out that they can all be ap­plied to mazes, so I’ll use some dis­ney-themed mazes to illus­trate each ap­proach.

We’ll start off with some tra­di­tional path-search al­gorithms (DFS, BFS, heuris­tic). Next, we’ll talk about how these al­gorithms can fall short for ev­ery­day prob­lem solv­ing. Then we’ll move on to the in­ter­est­ing part: two tech­niques which of­ten work bet­ter for ev­ery­day prob­lem solv­ing, and lend some in­ter­est­ing in­sights when ap­plied to mazes.

I’ll as­sume no tech­ni­cal back­ground at all, so if you’ve seen some of this stuff be­fore, feel free to skim it.

DFS and BFS

You have a maze, with a start point and an end point, and you are search­ing for a path through it. In al­gorithms classes, this prob­lem is called “path search”.

The very first path search al­gorithms stu­dents typ­i­cally learn are depth-first search (DFS) and breadth-first search (BFS). Here’s DFS, ap­plied to the Pinoc­chio maze above:

Ba­si­cally, the DFS rule is “always take the right-most path which you haven’t already ex­plored”. So, in the Pinoc­c­chio maze, we start out by turn­ing right and run­ning un­til we hit a wall (the first “x”). Then we turn around and go back, find an­other right turn, and hit an­other dead end. Turn around again, con­tinue…

That’s depth-first search. We go as far as we can down one path (“depth-first”) and if we hit a dead end, we turn around, back up, and try an­other path.

Breadth-first search, on the other hand, tries all paths in par­allel:

In this snap­shot, we’ve hit three dead ends, and we have four sep­a­rate “branches” still ex­plor­ing the maze. It’s like a plant: ev­ery time BFS hits an in­ter­sec­tion, it splits and goes both ways. It’s “breadth-first”: it ex­plores all paths at once, keep­ing the search as wide as pos­si­ble.

There’s lots more to say about these two al­gorithms, but main point is what they have in com­mon: these are brute-force meth­ods. They don’t re­ally do any­thing clever, they just crawl through the whole maze un­til they stum­ble on a solu­tion. Just try­ing out paths at ran­dom will usu­ally solve a maze about as quickly as DFS or BFS (as long as you keep track of what you’ve already tried).

Let’s be smarter.

Heuris­tic Search

A hu­man solv­ing a maze usu­ally tries to work their way closer to the end. If we’re not sure which way to go, we take the di­rec­tion which points more to­ward the goal.

For­mal­iz­ing this ap­proach leads to heuris­tic search al­gorithms. The best-known of these is A*, but we’ll use the more-hu­man-in­tu­itive “greedy best-first” search. Like breadth-first search, best-first ex­plores mul­ti­ple paths in par­allel. But rather than brute-force search­ing all the paths, best-first fo­cuses on paths which are clos­est to the goal “as the bird flies”. Dis­tance from the goal serves as an heuris­tic to steer the search.

Here’s an ex­am­ple where best-first works very well:

By ag­gres­sively ex­plor­ing the path clos­est to the goal, Pluto reaches his bone with­out hav­ing to ex­plore most of the maze.

But heuris­tic search comes with a catch: it’s only as good as the heuris­tic. If we use straight-line dis­tance from the goal as an heuris­tic, then heuris­tic search is go­ing to work well if-and-only-if the solu­tion path is rel­a­tively straight. If the solu­tion path wig­gles around a lot, es­pe­cially on a large scale, then heuris­tic search won’t help much. That’s what hap­pens if we ap­ply best-first to the Pinoc­chio maze:

… the best-first solu­tion in this case is al­most iden­ti­cal to DFS.

Gen­eral Prob­lem Solving

In AI, path search is used to think about solv­ing prob­lems in gen­eral. It turns out all sorts of things can be cast as path search prob­lems: puz­zles, plan­ning, and of course nav­i­ga­tion. Ba­si­cally any prob­lem whose solu­tion is a se­quence of steps (or can be made a se­quence of steps).

What do our maze-solv­ing al­gorithms look like in a more gen­eral prob­lem-solv­ing con­text?

Brute-force search is, well, brute-force search. It’s try­ing ev­ery pos­si­ble solu­tion un­til you hit on one which works. If we use the ran­dom var­i­ant, it’s ran­domly try­ing things out un­til you hit some­thing which works. I do not recom­mend solv­ing prob­lems this way un­less they are very small, very sim­ple prob­lems.

Heuris­tic search is more like how most peo­ple solve prob­lems, at least in ar­eas we aren’t fa­mil­iar with. We’ll have some heuris­tics, and we’ll try stuff which the heuris­tics sug­gest will work well.

One com­mon ver­sion of heuris­tic search in real-world prob­lem solv­ing is bab­ble and prune: brain­storm lots of ran­dom ideas, then pick out a few which seem promis­ing based on heuris­tics. Lather, rinse, re­peat. This goes by many names; in de­sign, for ex­am­ple, it’s called “flare and fo­cus”. It’s like e-coli path search: flail around, run in a ran­dom di­rec­tion, and if it looks like it’s work­ing, keep go­ing. Other­wise, flail around some more and run in a new di­rec­tion.

The prob­lem with any heuris­tic search is that it’s only as good as our heuris­tic. In par­tic­u­lar, most heuris­tics are “lo­cal”: like the straight-line dis­tance heuris­tic, they’re bad at ac­count­ing for large-scale prob­lem struc­ture. Without some knowl­edge of large-scale prob­lem struc­ture, lo­cal heuris­tics will lead us down many dead ends. Even­tu­ally, when we find the “right” solu­tion, we re­al­ize in hind­sight that we weren’t re­ally solv­ing the right prob­lem, in some in­tu­itive sense — more on that later.

Up­ping our Game

So we have al­gorithms which cor­re­spond to blindly flailing about (brute force), and we have al­gorithms which roughly cor­re­spond to how hu­mans solve many prob­lems (heuris­tics). But the real goal is to come with bet­ter ways for us hu­mans to solve prob­lems. We need to up our game.

For sin­gle-shot prob­lem solv­ing, it’s tough to do bet­ter than heuris­tic path search. One way or an­other, you have to ex­plore the prob­lem space.

But in the real world, we more of­ten face mul­ti­ple prob­lems in the same en­vi­ron­ment. We have jobs, and our jobs are spe­cial­ized. It’s like need­ing to find paths be­tween many differ­ent pairs of points, but all in the same maze. In this con­text, we may be able to in­vest some effort up-front in bet­ter un­der­stand­ing the prob­lem space (e.g. the maze) in or­der to more eas­ily solve prob­lems later on.

(Tech­ni­cal note: here, the usual text­book path­find­ing al­gorithms are not so good. All-pairs path search tries to ex­plic­itly rep­re­sent dis­tances be­tween each pair of points, which is out of the ques­tion for real-world high-di­men­sional prob­lem solv­ing.)

Bottlenecks

Here’s an in­ter­est­ing way to look at the Pinoc­chio maze:

Note that the high­lighted walls have ex­actly one gap in them. If Pinoc­chio wants to get from one side of the high­lighted walls to the other, then he has to go through that gap.

This ob­ser­va­tion lets us break the origi­nal prob­lem up into two parts. First, Pinoc­chio needs to get from the start to the gap. Next, he has to get from the gap to the end. Dur­ing the first half, he can com­pletely ig­nore all of the maze above the high­light; dur­ing the sec­ond half, he can com­pletely ig­nore all of the maze be­low the high­light.

This is a bot­tle­neck: it’s a sub­prob­lem which must be solved in or­der to solve the main prob­lem.

Once we have iden­ti­fied a bot­tle­neck, we can use it in con­junc­tion with other search al­gorithms. For in­stance, rather than run­ning heuris­tic search on the full maze, we can use heuris­tic search to get Pinoc­chio to the gap in the wall, and then run a sec­ond heuris­tic search from the gap to the end. This will do at least as well as the origi­nal heuris­tic search, and usu­ally bet­ter.

Even more pow­er­ful: un­like search meth­ods, a bot­tle­neck can be re-used for other prob­lems. It’s a prop­erty of the prob­lem space, not the prob­lem it­self. If Pinoc­chio is start­ing any­where in the top half of the maze, and needs to get any­where in the bot­tom half, then the same bot­tle­neck ap­plies. It can even be use­ful to know about the bot­tle­neck when we don’t need to solve it for the prob­lem at hand; con­sider this maze:

Hav­ing iden­ti­fied the bot­tle­neck, we can see at a glance that the en­tire bot­tom half of the maze is ir­rele­vant. If Anna crosses the gap, sooner or later she’ll have to turn around and come back out again in or­der to reach Elsa. In other words: know­ing about a bot­tle­neck you don’t need to solve is use­ful, be­cause you can avoid it.

Bot­tle­necks in Real-World Problems

Note that, in or­der for the bot­tle­neck to add value on top of heuris­tic search, the bot­tle­neck should be some­thing which the heuris­tic search would not effi­ciently solve on its own. For in­stance, if we’re us­ing a straight-line-dis­tance heuris­tic in a maze, then a bot­tle­neck is most use­ful to know about if it’s not­n­ear the straight line be­tween start and finish. If there’s a bot­tle­neck we must cross which is way out to the side, then that’s a use­ful bot­tle­neck to know about.

Another way to word this: the ideal bot­tle­neck is not just a sub­prob­lem which must be solved. It’s a max­i­mally difficult sub­prob­lem, where difficulty is based on the origi­nal heuris­tics.

This is how we usu­ally rec­og­nize bot­tle­necks in real-world prob­lems. If I’m a pro­gram­mer try­ing to speed up some code, then I time each part of the pro­gram and then fo­cus on the sec­tion which takes longest: the slow­est part is the “most difficult” sub­prob­lem, the limit­ing fac­tor for perfor­mance. If I want to im­prove the through­put of a fac­tory, then I look for whichever step cur­rently has the low­est through­put. If I’m de­sign­ing a tool or a product, then I start by think­ing about the most difficult prob­lem which that product needs to solve: once that’s figured out, the rest is eas­ier.

Per­son­ally, I find a lot of “shower in­sights” come this way. I’m think­ing about some prob­lem, mul­ling over the hard­est part. I fo­cus in on the hard part, the bot­tle­neck it­self, for­get about the broader con­text… and sud­denly re­al­ize that there’s a re­ally nice solu­tion to the bot­tle­neck in iso­la­tion. What’s hard with the origi­nal heuris­tic of­ten be­comes easy when we fo­cus on the bot­tle­neck it­self, and ap­ply bot­tle­neck-spe­cific heuris­tics.

In a maze, a bot­tle­neck way to the side is hard us­ing the straight-line dis­tance to the finish as an heuris­tic. But if we aim for the gap in the wall from the start, then it’s eas­ier.

To find the “right” solu­tion, fo­cus on the right prob­lem. That’s what bot­tle­necks are all about.

Chunking

Let’s go back to the Anna and Elsa maze. Here’s an equiv­a­lent way to rep­re­sent the bot­tle­neck we high­lighted in that maze:

Half the maze is or­ange, the other half is green, and the two touch at ex­actly one point: the green dot, right where we iden­ti­fied a bot­tle­neck. If we want to go from an or­ange point to an­other or­ange point, then we only need to worry about the or­ange part of the maze. If we want to move be­tween or­ange and green, then we must cross the green point.

Here, we’ve “chun­ked” the maze into two pieces, and we can think about those two pieces more-or-less in­de­pen­dently. Here’s chunk­ing on the Pinoc­chio maze, with a few more col­ors:

For Pinoc­chio to get to school, he must start in the yel­low chunk and get to the or­ange chunk. We can only get from yel­low to or­ange via green, so the color path must be yel­low → green → or­ange (and we can ig­nore the blue part of the maze en­tirely). The origi­nal maze is bro­ken into three parts, one within each color chunk, and each prob­lem can be solved sep­a­rately.

(Side ques­tion: there’s at least one more-hu­man-in­tu­itive way to ap­ply chunk­ing to mazes. Can you figure it out?)

Once we’ve rep­re­sented the maze us­ing col­ored chunks, and once we know how to use that in­for­ma­tion, we can use it to move be­tween any two points in the maze. “Lo­cal” moves, within the same color chunk, can ig­nore all the other chunks. Larger-scale travel can fo­cus first on the se­quence of color moves — es­sen­tially a path through a larger-scale, more ab­stracted maze — and then zoom in to find paths within each chunk. Ideally, we choose the chunks so that an heuris­tic works well within each piece.

This is ac­tu­ally how hu­mans think about mov­ing around in space. Our men­tal map of the world con­tains five or six differ­ent lev­els, each one more gran­u­lar than the last. When plan­ning a path, we start with the high­est-ab­strac­tion-level map, and then zoom in.

More gen­er­ally, ex­perts in a field pro­cess in­for­ma­tion more effi­ciently by chunk­ing things to­gether into more ab­stract pieces. Ex­pert chess play­ers don’t think in terms of in­di­vi­d­ual pieces; they think in terms of whole pat­terns and how they in­ter­act. For a hu­man, this is ba­si­cally what it means to un­der­stand some­thing.

Conclusion

I fre­quently see peo­ple tackle prob­lems with tools which re­sem­ble heuris­tic path search — e.g., a brain­storm­ing ses­sion, fol­lowed by pick­ing out the most promis­ing-sound­ing ideas.

I think a lot of peo­ple just don’t re­al­ize that there are other ways to tackle a prob­lem. It’s pos­si­ble to look at prop­er­ties of the prob­lem space — like bot­tle­necks or chunks — be­fore propos­ing solu­tions. Th­ese are (some of) the pieces from which un­der­stand­ing is built, and when they work, they al­low much more effi­cient and el­e­gant ap­proaches to prob­lems.