Search and problem solving · Introduction to AI

Most AI problems, at their heart, are search problems. You have a starting state. You have a goal state. You have a set of legal moves that take you from one state to another. The system’s job is to find a sequence of moves that gets it from the start to the goal — and, ideally, the best such sequence.

That description sounds abstract. The example is not. It is how Pathao gets your rider from Thamel to your house in Bhaktapur.

The vocabulary of search

Before we look at algorithms, let us fix four words. We will use them for the rest of the chapter.

State. A snapshot of where you are. For a route, it is an intersection. For chess, it is a board position. For a sudoku, it is the partly-filled grid.
Action. A legal move from one state to another. Take a road. Move a pawn. Write a number into a cell.
Goal. The state you are trying to reach. Bhaktapur. Checkmate. A fully-filled grid.
Cost. How expensive an action is. Kilometres travelled. Minutes spent. Moves played.

Almost every classical AI problem fits this mould. Once you can write a problem in these four terms, you can apply a search algorithm to it.

Two ways to walk a map

Imagine you are standing at a junction in Thamel. You can see three roads. Each of those roads ends at another junction with its own three roads. After a few steps, the number of possible paths explodes. How do you decide which one to walk down?

There are two simple strategies, both worth knowing because everything more sophisticated is a refinement of one of them.

Breadth-first search (BFS). Walk one step down every road. Then walk one more step down every road that leads from those. Then one more. You explore the map in widening rings around the start. You are guaranteed to find the goal at the smallest number of steps away — but if the map is huge, you will use a lot of memory remembering every road you have partially walked.

Depth-first search (DFS). Pick one road, walk it as far as it goes. If it dead-ends, back up, and try the next road. You explore the map in long thin tendrils. You use very little memory — you only need to remember the path you are currently on — but you may walk for hours down a dead-end before realising it.

BFS is patient and thorough. DFS is committed and forgetful. Neither, on its own, is enough for a city like Kathmandu.

Kathmandu has, roughly, tens of thousands of road segments. Bhaktapur is one specific intersection. A blind BFS from Thamel would explore every road within one kilometre, then every road within two, then every road within three, before it ever pointed itself east toward Bhaktapur. By the time it finishes, your rider has gone home for daal-bhaat.

The problem is that BFS and DFS don’t know which direction the goal is in. They walk roads in whatever order the data structure happens to hold them. We need a way to tell the algorithm: Bhaktapur is east. Prefer roads that go east.

That hint is called a heuristic, and the next section is about what happens when we give the algorithm one.

What Pathao is actually doing

When a Pathao rider opens the app in Naxal at 6pm with a destination in Patan, the system is running a search algorithm on a graph. The states are intersections. The actions are road segments. The cost is expected travel time, taking into account historical traffic patterns and live information about which roads are jammed right now.

The algorithm is not BFS. It is not DFS. It is some variant of A* — the algorithm we will meet in the next section — running on a graph of every road in the valley, in milliseconds, on a server in Singapore. The route it returns is not “the shortest path.” It is “the cheapest path according to the cost function the engineers chose.” If the cost function emphasises distance, you get short routes. If it emphasises time, you get fast routes. If it emphasises rider earnings, you get something else entirely.

Knowing what cost function is in use is part of being AI-literate. The route is an answer to a precise question — and the choice of question is a human decision.

When the problem looks nothing like a road map

The trick of classical AI is to notice when a problem can be framed as search, even when it doesn’t look like one. Three quick examples:

Scheduling. A school timetable is a search problem. States are partial timetables. Actions are “assign this teacher to this period.” The goal is a fully-filled timetable with no conflicts. The cost is whatever the principal wants to minimise — for instance, the number of teachers asked to come on Saturday.
Logistics. A delivery company planning the day’s drops is searching for an ordering of stops that minimises driving time. The states are partial routes; the actions are “add this stop next.”
Puzzle solving. Filling a sudoku, untangling a Rubik’s cube, finding an exit from a maze — all search problems with very different state spaces.

If you can describe the problem in our four words — state, action, goal, cost — there is, somewhere, a search algorithm that can attack it.

Check your understanding

Quick check

—

Breadth-first search (BFS) and depth-first search (DFS) differ primarily in which way?

The order in which they explore states from the start
Whether they use memory
The programming language they require
The hardware they need to run