AIMA Chapter 4 — Beyond Classical Search (Heuristics, Local Search, GA).

If Chapter 3 taught you how to search, Chapter 4 teaches you how to search like you actually know something. That is the whole pivot. Blind search methods such as BFS, DFS, uniform-cost search, and iterative deepening are beautifully general, but they waste enormous effort because they refuse to use clues from the problem domain. This chapter is the cure: we add informed guidance when we can, and when path details do not matter, we throw away the path entirely and focus on optimisation.

01 Why uninformed search eventually feels blind

Uninformed search algorithms are honest workers. They do exactly what the search discipline says, but they do not ask whether one node looks more promising than another. Breadth-first search says, “expand by depth.” Uniform-cost search says, “expand by cheapest path cost so far.” Depth-first search says, “follow one branch deeply.” None of them say, “this state seems closer to the goal, so maybe look here first.”

That is why the word blind is so useful. The algorithm is not stupid in a human sense. It is blind because it cannot see the shape of the remaining journey. It knows where it is. It may know how much it has already spent. But it does not know which frontier node is promising. So it often expands a mountain of irrelevant states before reaching the goal.

Imagine you are driving in a new city and you must reach a railway station. An uninformed method is like exploring roads without using a map, compass, distance sign, or landmark. You may still reach the station. In fact, with the right completeness guarantees, you eventually will. But you will likely waste time exploring side streets that obviously point away from the station.

The pain gets worse as state spaces grow. If the branching factor is b and the shallowest solution depth is d, then many blind searches have node counts growing like O(b^d). Exponential growth is the villain of half of AI. Even a modest branching factor becomes brutal when depth rises.

There is also a practical engineering reason why heuristics matter. In real systems, memory and time are limited. A theoretically complete algorithm that takes ten hours or ten gigabytes is not actually helpful if the application needs an answer in two seconds. Heuristics are what make search feel intelligent instead of merely exhaustive.

02 Heuristics: what h(n) really means

A heuristic function h(n) is an estimate of the remaining cost from node n to a goal. It is not the exact answer in general. If it were exact, search would be almost trivial. The whole point is that a cheap estimate can still be very useful.

In route finding, a classic heuristic is straight-line distance to the destination. In a sliding-tile puzzle, a classic heuristic is how far the tiles appear to be from where they belong. In scheduling, a heuristic may estimate how badly constraints are currently violated. The details change with the problem, but the philosophical role stays the same: give me a rough idea of how much work is still left.

The course note says the heuristic must be non-negative. That matters because costs in these textbook search formulations are assumed to be non-negative. A negative heuristic would mean, in effect, “I think you are less than zero cost away from the goal,” which is nonsense in ordinary shortest-path problems and would distort ranking badly.

The dream heuristic would satisfy h(n)=h^*(n) for every node. Then A* would go straight to the optimal solution with minimal wasted work. But exact future cost is usually as hard to compute as solving the original problem. So in practice heuristics are approximations that trade accuracy for speed.

Notice the asymmetry: g(n) is known, because it is the cost already paid to reach n. h(n) is guessed, because the future has not been explored yet. Informed search is really about deciding how much trust to place in a known past versus an estimated future.

03 Greedy best-first search: use only the guess

Greedy best-first search ranks nodes only by the heuristic:

This is why it feels so tempting. It always asks, “Which frontier node looks closest to the goal right now?” That often gets you somewhere very quickly. If the heuristic is decent, the search seems laser-focused.

But the greediness is also the weakness. Greedy best-first does not care how expensive the path so far has already been. If a node looks close to the goal, greedy search loves it even if reaching that node required a very silly detour. This is the textbook warning: using only h(n) can make the algorithm fast, but it can also make it myopic.

In the Romania map example, the goal is Bucharest. Suppose we start at Arad and use straight-line distance to Bucharest as the heuristic. The values commonly used in AIMA are: Arad 366, Sibiu 253, Timisoara 329, Zerind 374, Fagaras 176, Rimnicu Vilcea 193, Pitesti 100, Bucharest 0, and so on.

From Arad, greedy best-first sees these immediate options: Sibiu with h=253, Timisoara with h=329, Zerind with h=374. Since 253 is smallest, it expands Sibiu. From Sibiu it sees Fagaras with h=176 and Rimnicu Vilcea with h=193, so it prefers Fagaras because 176 looks closer. From Fagaras it can reach Bucharest directly, so it happily goes there.

The route found is Arad → Sibiu → Fagaras → Bucharest, with total path cost 140+99+211=450. The problem is that this is not optimal. A cheaper route exists: Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest, with cost 140+80+97+101=418.

Textbooks sometimes say greedy best-first is “not complete or optimal.” The spirit of that sentence is important. In large or infinite spaces, greedy can chase deceptive hints forever or cycle unless repeated-state handling is used. On a finite graph with a proper closed list it may terminate, but the algorithm still lacks the robust guarantees that make A* famous.

So why study greedy best-first at all? Because it captures a useful extreme. It shows the power of heuristic guidance in its purest form. It is also a strong baseline: when a rough answer fast is more valuable than a guaranteed optimal answer, greedy-style methods are often attractive.

04 A*: the sweet spot between past cost and future estimate

A* search fixes the biggest flaw in greedy search by combining two quantities:

Here g(n) is the exact cost from the start state to n, and h(n) is the estimated cost from n to a goal. So f(n) estimates the total cost of a full solution path going through n.

This is the brilliance of A*. It does not ignore the past like greedy search, and it does not ignore the future like uniform-cost search. It balances both. A frontier node with a very cheap past but terrible future may lose. A frontier node with a great-looking future but wildly expensive past may also lose. The winner is the node with the most promising total story.

The moment students really get A* is usually the moment they stop treating g and h as symbols and start hearing their voices. g says, “How much have you already spent?” h says, “How much do you still expect to spend?” A* asks both before making a move.

Why does this help? Because shortest-path problems are about total cost, not closeness in some vague sense. Greedy search over-trusts the estimate. Uniform-cost search distrusts all estimates and pays for that with extra expansion. A* is the compromise that often gives the best of both worlds.

05 The full Romania A* trace, carefully

Let us do the standard Arad-to-Bucharest example properly because this one example explains half the chapter. We use straight-line distance to Bucharest as the heuristic. The relevant road distances are:

• Arad → Sibiu = 140, Arad → Timisoara = 118, Arad → Zerind = 75
• Sibiu → Fagaras = 99, Sibiu → Rimnicu Vilcea = 80, Sibiu → Oradea = 151
• Rimnicu Vilcea → Pitesti = 97, Rimnicu Vilcea → Craiova = 146
• Fagaras → Bucharest = 211
• Pitesti → Bucharest = 101

The heuristic values are: Arad 366, Sibiu 253, Timisoara 329, Zerind 374, Fagaras 176, Rimnicu Vilcea 193, Oradea 380, Pitesti 100, Craiova 160, Bucharest 0.

Step 1: expand Arad. Its successors are:

• Sibiu: \(g=140\), \(h=253\), \(f=393\)
• Timisoara: \(g=118\), \(h=329\), \(f=447\)
• Zerind: \(g=75\), \(h=374\), \(f=449\)

The smallest f is Sibiu with 393. So A* expands Sibiu next.

Step 2: expand Sibiu. Relevant new successors:

• Fagaras: \(g=140+99=239\), \(h=176\), \(f=415\)
• Rimnicu Vilcea: \(g=140+80=220\), \(h=193\), \(f=413\)
• Oradea: \(g=291\), \(h=380\), \(f=671\)

The frontier now contains Rimnicu Vilcea 413, Fagaras 415, Timisoara 447, Zerind 449, Oradea 671. So A* expands Rimnicu Vilcea next.

Step 3: expand Rimnicu Vilcea. New useful successors:

• Pitesti: \(g=220+97=317\), \(h=100\), \(f=417\)
• Craiova: \(g=220+146=366\), \(h=160\), \(f=526\)

The frontier is now Fagaras 415, Pitesti 417, Timisoara 447, Zerind 449, Craiova 526, Oradea 671. So the next node is Fagaras.

Step 4: expand Fagaras. This generates Bucharest with

Now the frontier is Pitesti 417, Timisoara 447, Zerind 449, Bucharest 450, Craiova 526, Oradea 671. Even though Bucharest has been found, A* does not stop yet because a cheaper route to Bucharest may still exist via a lower-f frontier node. That is the subtle but crucial detail students often miss.

Step 5: expand Pitesti. This generates another route to Bucharest:

Now the frontier contains Bucharest 418, Timisoara 447, Zerind 449, the older Bucharest 450, Craiova 526, Oradea 671. The lowest node is Bucharest 418, so A* selects it next and stops. The returned path cost is 418, which is optimal.

The expansion order in this trace is Arad, Sibiu, Rimnicu Vilcea, Fagaras, Pitesti, Bucharest. That order is memorable because it shows the exact point where A* diverges from greedy best-first. Greedy liked Fagaras and then jumped straight to Bucharest with total cost 450. A* let Fagaras be explored, but because it still tracked the total story using g+h, it kept the Pitesti route alive and eventually preferred the 418 path.

06 Admissibility: a heuristic that never lies upward

A heuristic is admissible if it never overestimates the true remaining cost:

So an admissible heuristic is optimistic. It may be exact. It may be too low. But it may not be too high. The estimate can under-promise, never over-promise.

Why is that the right condition for A* tree search? Because A* uses g+h as an estimate of solution cost through a node. If h never overshoots, then f(n) never overshoots the true best solution cost through n. That means an optimal path cannot be unfairly hidden behind an inflated estimate.

In the Romania example, straight-line distance to Bucharest is admissible because a road route cannot be shorter than the physical straight-line route between two cities. Roads bend and detour; they do not magically tunnel through space to beat Euclidean geometry. So straight-line distance is a lower bound on actual travel cost.

There is a famous proof idea behind A* tree-search optimality. Let the optimal goal cost be C^*. For any node n on an optimal path, admissibility implies f(n)=g(n)+h(n) \le g(n)+h^*(n)=C^*. So A* will keep seeing at least one frontier node on the optimal path with f \le C^*. Any suboptimal goal has path cost greater than C^*, hence larger f. Therefore A* cannot choose a suboptimal goal before the optimal one.

The punchline is simple: admissibility protects optimality in tree search because the heuristic does not exaggerate what remains.

07 Consistency: the triangle inequality version of trust

For graph search, admissibility alone is not the whole story. The stronger property is consistency, also called monotonicity. A heuristic is consistent if for every node n and every successor n',

This is a triangle inequality for heuristics. It says: your estimate from n to the goal cannot be more than the cost of stepping to a neighbor plus the estimate from that neighbor to the goal.

Why does that matter? Because it makes the A* evaluation value nondecreasing along a path. If n' is a successor of n, then

So once you move forward, f never drops. This is extremely convenient. It means that when A* graph search removes a node from the frontier for expansion, the path cost to that node is already the best possible one. No future route can sneak in later with a cheaper g.

Every consistent heuristic is admissible. You can show this by repeatedly applying the consistency inequality along an optimal path from n to a goal. Since the heuristic at the goal is zero, the chain collapses to h(n)\le h^*(n). But the reverse is not always true: an admissible heuristic may still be inconsistent.

That “not vice versa” line matters. A heuristic may never overestimate the full remaining cost, yet still violate local triangle inequalities between neighbors. When that happens, A* graph search can run into the re-expansion problem.

08 Why consistency matters in graph search: the re-expansion problem

Graph search is different from tree search because the same state can be reached through multiple paths. If you close a node too early, assuming its best path cost is already known, you might accidentally block a later, better route to that same state.

With a consistent heuristic, this problem goes away because the first time a node is expanded, it already has the cheapest possible g. So a closed list is safe. But with an admissible yet inconsistent heuristic, a later path might reach a previously expanded node more cheaply, forcing the algorithm to reopen or re-expand it.

That is the re-expansion problem in one sentence: inconsistency can make A* discover a better route to an old node after the node was already processed.

Conceptually, inconsistency means the heuristic landscape contains “downward surprises.” You move to a child and suddenly the estimated total future becomes much smaller than before, more than the edge cost should allow. That breaks the neat monotone structure A* relies on.

In practice, many standard heuristics used in textbooks and classical planners are designed to be consistent, precisely because consistent heuristics make implementation cleaner. But knowing why consistency is valuable is more important than memorising that it is valuable.

09 Measuring heuristic quality: effective branching factor

Saying “heuristic A is better than heuristic B” sounds intuitive, but we need a way to compare them. One useful measure is the effective branching factor, written b^*. It is defined indirectly by the equation

Here N is the number of nodes generated by the search to find a solution at depth d. The idea is: if the search had behaved like a uniform tree with branching factor b^*, it would have generated the same number of nodes.

Why is this useful? Because it compresses the practical impact of the heuristic into one number. Lower is better. If b^* is close to 1, the heuristic is nearly perfect: the algorithm is essentially following one narrow path instead of exploding into many branches. If b^* is close to the real branching factor, the heuristic is not buying you much.

Effective branching factor is especially handy when comparing heuristics for the same problem family, such as different heuristics for the 8-puzzle. If one heuristic consistently reduces b^*, it means the search is doing less wasted exploration.

10 Where good heuristics come from, part 1: relaxed problems

The most elegant source of heuristics in AIMA is the idea of a relaxed problem. You take the original problem and remove constraints, making it easier. Because the relaxed problem is easier, its optimal solution cost is less than or equal to the real one. That immediately gives you an admissible heuristic.

The logic is lovely. If I loosen the rules, the problem cannot become harder. So the cost under relaxed rules is a lower bound on the real cost. Lower bounds are exactly what admissible heuristics need.

The 8-puzzle is the classic teaching example. In the real puzzle, a tile can move only into the adjacent blank square. Now relax that in two different ways.

Misplaced tiles: h_1

Suppose we relax the rules so that a tile may move directly to its goal square in one move, regardless of where the blank is. Then the number of misplaced tiles becomes an estimate of how many moves remain. This is the heuristic h_1.

If three tiles are out of place, then at least three tile-fixing actions are needed in the relaxed world, and certainly no fewer than that in the real world. So h_1 is admissible.

Manhattan distance: h_2

Now use a less relaxed version: allow a tile to move to any adjacent square, even if the blank is not correctly positioned for that exact move. Then the cost for one tile to reach its goal is simply the Manhattan distance between current and goal coordinates: horizontal distance plus vertical distance. Summing this over all tiles gives the heuristic h_2.

This heuristic is also admissible, because in the real puzzle each tile must at least travel that many grid steps. The blank constraints and tile interactions can only make the real problem harder, not easier.

The beautiful comparison is that h_2 dominates h_1. For every state, h_2(n) \ge h_1(n). Why? Because every misplaced tile contributes at least 1 to Manhattan distance, and tiles already in place contribute 0 to both. So Manhattan distance is never smaller and is often larger. That means it is more informative while remaining admissible.

There is a standard theorem attached to this: if heuristic h_a dominates heuristic h_b and both are admissible, then A* using h_a expands no more nodes than A* using h_b apart from tie-breaking details. That is why everybody prefers Manhattan distance over misplaced tiles for the 8-puzzle.

We can go one step further. If h_1 and h_2 are both admissible, then h(n)=\max(h_1(n),h_2(n)) is also admissible. It dominates both. This “take the max of admissible heuristics” trick is one of those small textbook ideas that is incredibly reusable. If you have several safe lower bounds, use the strongest one at each state.

11 Where good heuristics come from, part 2: pattern databases, landmarks, learning

Relaxed problems are the cleanest story, but not the only story. Modern heuristic design uses several powerful ideas.

Pattern databases

A pattern database precomputes exact costs for a subproblem and stores them in a lookup table. For example, in the 15-puzzle you may focus only on a subset of tiles, ignoring the rest. Solve all possible configurations of that subset offline, store their exact move counts, and then use the table during search.

This is so effective because it turns expensive reasoning into cheap memory lookup. During the actual A* run, the heuristic value is almost instant. For large puzzles and Rubik’s cube solvers, pattern databases were a huge breakthrough because they provided very strong admissible heuristics.

Landmarks

Another idea is to choose fixed anchor states, sometimes called landmarks, and precompute distances to or from them. Then triangle-inequality style reasoning gives lower bounds between arbitrary states and goals. If a state is far from a landmark that the goal is near, that fact can certify that the state is not as close to the goal as it first looks.

Learned heuristics

In modern AI, we often learn heuristics from data. You solve many training instances, then train a model such as a neural network h(s,\theta) to predict remaining cost or distance-to-go. That predicted value can guide A* or greedy search.

The benefit is flexibility. Hand-designed heuristics are hard for messy domains. A learned model can capture patterns that are awkward to code manually. The cost is that learned heuristics do not automatically satisfy admissibility or consistency. If you need guarantees, you must either constrain the learner or accept that you are trading some theory for practical power.

There is a deeper lesson here: heuristics are knowledge representation. Whether you derive them from geometry, relaxed rules, precomputed tables, or data, you are encoding insight about the structure of the problem.

12 IDA*: when you want A* guidance without A* memory

One of A*’s big weaknesses is memory use. It stores a frontier and often a closed set, which can explode in large problems. Iterative Deepening A*, or IDA*, addresses this by borrowing the memory discipline of depth-first search.

Instead of limiting search by depth, IDA* limits search by f=g+h. It performs a depth-first traversal but refuses to go beyond a current f-cutoff. If no solution is found, it increases the cutoff and repeats.

So the control structure looks like iterative deepening, but the threshold is heuristic cost rather than depth. The first cutoff is usually the f value of the start node. On each pass, the next threshold is typically the smallest f value that exceeded the previous threshold.

That is why IDA* appears in domains like sliding-tile puzzles. A* may run out of memory long before it runs out of ideas. IDA* revisits nodes across iterations, but its memory profile is dramatically smaller.

13 When the path does not matter: why local search exists

Until now, search has mostly meant finding a path from start to goal. But many important problems do not care about the path at all. If I am arranging eight queens on a chessboard so none attack each other, I do not care about the sequence of intermediate boards. I care only about the final legal arrangement. If I am tuning hyperparameters, designing a circuit, or assigning exam schedules, the journey is disposable; the final configuration is the product.

That shift changes everything. When only the final state matters, you do not need to maintain a full search tree of partial paths. You can treat the problem as a landscape of candidate states, each with an objective value, and simply try to move toward better states.

Sometimes the objective is framed as maximisation: higher is better, like a score or utility. Sometimes it is framed as minimisation: lower is better, like error, cost, or number of conflicts. These are equivalent after a sign change, so textbooks freely switch between “climb the hill” and “descend into the valley.”

This is why local search often uses very little memory. You keep one state, or a small set of states, and repeatedly improve them. That makes local search appealing in enormous spaces where explicit tree search would be ridiculous.

14 Landscape thinking: local maxima, plateaus, ridges

The most useful mental model for local search is the state-space landscape. Imagine every possible state as a point on a surface, and the objective value as altitude. Good states are high if we are maximising, or low if we are minimising. The search process is a walk on this terrain.

This picture immediately explains why local methods can struggle. The landscape may have multiple hills. Some are global maxima, the truly best solutions. Others are local maxima, which look perfect if you only inspect immediate neighbors.

A plateau is a flat region where many neighboring states have the same value. The algorithm has no gradient telling it which way is better. A ridge is a narrow ascending structure where the best path requires coordinated sideways and upward movement; single-step local moves may fail to follow it.

Once you start seeing optimisation as geography, most local-search behavior becomes intuitive instead of magical. Algorithms differ mainly in how stubbornly they follow the local gradient and whether they allow escapes.

15 Hill climbing: beautifully simple, frequently trapped

Hill climbing is probably the simplest local-search algorithm. From the current state, look at the neighbors. Move to the best one. Repeat until no neighbor is better.

The steepest-ascent version checks all successors and chooses the highest-valued one. There are lighter variants too, but the idea is always the same: take a local improving step.

This makes hill climbing fast and memory-light. It often produces decent solutions quickly. In huge optimisation spaces, that alone can be valuable. But its failure modes are famous.

• Local maxima: every neighbor is worse, but a much better region exists elsewhere.
• Plateaus: all neighbors are equal, so progress stalls.
• Ridges: progress requires a sequence of coordinated moves, but single greedy steps cannot line up correctly.

The 8-queens problem makes this very concrete. If we represent a board by placing one queen in each column and define the objective as the negative number of attacking pairs, hill climbing often improves quickly but then freezes at a board that is close to a solution yet not actually valid.

Several fixes are standard. Random-restart hill climbing simply runs hill climbing many times from different random initial states. This sounds crude, but it is surprisingly powerful because if each run has some nonzero chance of success, repeated restarts amplify that chance. Stochastic hill climbing chooses randomly among uphill moves instead of always taking the steepest one, which can reduce over-commitment to one immediate gradient. Random-walk variants occasionally accept sideways or even worse moves, which helps cross plateaus and avoid getting stuck.

The bigger lesson is that local search usually wins not through one perfect run, but through a good balance between improvement and escape.

16 Simulated annealing: let the search get worse on purpose

Simulated annealing is the chapter’s answer to hill climbing’s stubbornness. It is inspired by metallurgy: if you heat a metal and cool it slowly, atoms can settle into lower-energy, less defective structures. If you cool too quickly, the structure freezes with defects.

Translate that to search. The current state has some objective value. Normally we love better moves. But simulated annealing sometimes accepts worse moves too, with a probability that depends on how much worse they are and on a temperature parameter T.

A common expression is

If the new state is better, accept it. If it is worse, maybe still accept it. When the temperature is high, the algorithm is adventurous and forgiving. When the temperature is low, it becomes picky and conservative. As T \to 0, the method approaches pure hill climbing because worse moves almost never survive.

The cooling schedule is everything. If you lower the temperature too fast, the method becomes greedy too early and gets trapped just like hill climbing. If you lower it too slowly, the search may wander forever or simply take impractical time. The theorem that simulated annealing can reach the global optimum with probability 1 requires a slow enough schedule, but “slow enough” in theory can be painfully slow in practice.

This gap between theorem and engineering is important. Simulated annealing is not magic. It is a controlled compromise between exploration and exploitation. Good performance depends on careful temperature initialization, decay rate, stopping conditions, and neighborhood design.

Still, conceptually it is one of the most beautiful algorithms in the chapter because it makes a powerful point: greed is not always rational. Sometimes intelligence means being willing to step backward so that a much better region becomes reachable.

17 Local beam search: many guesses, one shared conversation

Local beam search keeps k states at once instead of just one. At each iteration, it generates all successors of all k current states and then keeps the best k among the whole pool.

That means the states are not independent. They communicate implicitly through selection. If one state discovers a promising region, several of the next generation’s states may come from that region, concentrating search effort there. This is why local beam search is not the same as running k independent hill climbers. Independent restarts do not share discoveries. Beam search does.

The advantage is diversity with coordination. The downside is that the beam can collapse: if many top successors all come from the same region, the search may lose coverage and become redundant. Stochastic beam search reduces this by choosing the next k states probabilistically according to fitness rather than deterministically taking the top k. That preserves some variety and prevents over-clustering.

Beam ideas sit conceptually between hill climbing and population-based methods like genetic algorithms. You already see the shift from “one current state” to “a group of candidate states evolving over time.”

18 Genetic algorithms: search by evolution

Genetic algorithms, or GAs, take the population idea seriously. Instead of improving one state, they maintain a population of k candidates, usually encoded as strings called chromosomes. Each candidate gets a fitness score measuring how good it is for the task.

A standard generation cycle has four ideas:

1. Selection: choose parents, biased toward higher fitness.
2. Crossover: combine parent strings to create children.
3. Mutation: randomly perturb a small part of a child.
4. Replacement: form the next generation and repeat.

Selection can be done by roulette-wheel sampling, where probability is proportional to fitness, or tournament selection, where a few candidates compete and the best wins. Crossover usually cuts the parent strings at a random point and swaps suffixes. Mutation flips a bit or changes a gene with low probability. Mutation is small but essential because it injects novelty and prevents the population from becoming genetically identical too early.

For 8-queens, one convenient encoding is a length-8 vector where the position in the vector is the column and the value is the row of the queen in that column. For example, [4,6,8,2,7,1,3,5] means the queen in column 1 is in row 4, the queen in column 2 is in row 6, and so on. Fitness can be defined as the number of non-attacking pairs, or the negative number of conflicts.

You may also see binary or decimal encodings in demonstrations. The exact encoding matters because crossover only makes sense if useful partial structures survive and combine meaningfully. This leads to the famous building blocks hypothesis: good solutions are assembled from smaller, useful schemata that evolution can discover and recombine.

Genetic algorithms do not guarantee global optimality. They can converge prematurely, lose diversity, or waste effort if representation and fitness are poorly designed. But in huge, ugly, discontinuous search spaces, they are often attractive precisely because they do not need gradients or delicate mathematical structure. They just need a way to evaluate candidate quality.

19 Online search and LRTA*: acting before you know the world

Most search algorithms in the earlier chapters assume an offline planning setting: the agent knows the transition model and can compute a whole plan before acting. But what if the agent does not know the map? What if the environment is partly unknown or changes as the agent explores?

That is where online search enters. The agent must act, observe, update its knowledge, then act again. It is learning the environment while operating inside it. This is closer to how robots and many real-world systems actually behave.

LRTA* stands for Learning Real-Time A*. The basic idea is that the agent uses current heuristic estimates to choose actions but also updates those estimates from experience so the heuristic becomes more accurate over time. When it discovers that a state was more costly than expected, it raises the heuristic estimate accordingly.

This is powerful because the agent does not wait for a full perfect plan. It behaves now, learns now, corrects now. That makes online search essential in unknown or dynamic environments where complete precomputation is impossible or pointless.

The mental shift is important. Offline search asks, “What is the best plan?” Online search asks, “Given what I know right now, what should I do next, and how should I revise my beliefs after I see the result?”

20 A quick comparison table you can revise from

Before wrapping the chapter together, it helps to place the major methods side by side. Students often remember formulas but forget the use-case story. This table is the missing bridge: it tells you what each method optimises, what information it trusts, and what failure mode usually appears first.

Method	Main score	Best for	Main strength	Main weakness
Greedy best-first	h(n)	Fast rough routing	Strong directional focus	Can be badly suboptimal
A*	g(n)+h(n)	Least-cost path search	Optimal with the right heuristic	Heavy memory use
IDA*	f-cutoff DFS	Huge path spaces with tight memory	Memory efficient	Repeats work across iterations
Hill climbing	Best local neighbor	Quick optimisation	Very cheap and simple	Gets stuck locally
Simulated annealing	Objective + temperature	Rugged landscapes	Can escape local optima	Cooling schedule is delicate
Local beam	Best k states	Parallel local improvement	Shared discovery across states	Beam collapse
Genetic algorithm	Population fitness	Huge black-box spaces	Diversity and recombination	Needs careful encoding and tuning

21 How all the chapter pieces fit together

Chapter 4 looks broad on first read because it mixes A*, hill climbing, annealing, beam search, genetic algorithms, and online methods. But there is one clean thread holding it all together: blind expansion is too expensive, so we need guidance. The only thing that changes is the source and style of guidance.

In heuristic path search, the guidance is an estimate of remaining cost. In local search, the guidance is the objective value of neighboring states. In genetic algorithms, the guidance is fitness over a population. In online search, the guidance is a heuristic that gets repaired as the world reveals itself.

Once you see that, the chapter stops feeling like a list of algorithms and starts feeling like a family portrait. Every algorithm is asking some version of the same question: “How can I avoid wasting effort on hopeless parts of the space?”

• Greedy best-first search uses only h(n), so it is often fast but can be spectacularly shortsighted.
• A* uses f(n)=g(n)+h(n), which balances known path cost with estimated remaining cost.
• Admissibility protects A* tree search; consistency is the stronger condition that makes A* graph search clean and safe with a closed list.
• Heuristics become stronger when they are closer to the true cost while still staying admissible; dominance and the max trick are practical tools.
• Relaxed problems, pattern databases, landmarks, and learned models are major heuristic sources.
• IDA* trades repeated work for much smaller memory use.
• Local search is for optimisation problems where only the final state matters, not the route.
• Hill climbing is simple but trap-prone; simulated annealing escapes by accepting worse moves with temperature-controlled probability.
• Beam search and genetic algorithms use multiple candidates in parallel, sharing information across a population.
• Online search matters when the agent must act in an unknown environment and improve estimates from experience.

22 References and extra reads

If you revise from only one source, make it the textbook first. But this chapter becomes much easier once you see the same ideas from two or three angles.

• Russell, Norvig. Artificial Intelligence: A Modern Approach, 4th ed. Chapter 4 for the canonical textbook treatment of heuristic search, local search, and online search.
• Hart, Nilsson, Raphael. The original A* paper, useful if you want to see why optimality and admissibility are treated so carefully.
• Pearl. Classic work on heuristic search for deeper intuition about heuristic quality and effective branching factor.
• Practical puzzle-search literature. Read about pattern databases for the 15-puzzle and Rubik’s cube if you want to see admissible heuristics become industrial-strength.
• Modern optimisation notes. Any serious tutorial on simulated annealing, evolutionary algorithms, or beam search helps connect the AIMA chapter to real optimisation workloads.

23 Chapter 4 cheatsheet

24 Quick FAQ before you close the chapter

Why doesn’t A* stop the moment it first generates the goal?

Because a cheaper route to that same goal may still exist through another frontier node with smaller f. In the Romania example, Bucharest is first generated through Fagaras at cost 450, but later reached through Pitesti at cost 418.

If consistency implies admissibility, why do we even talk about admissibility separately?

Because admissibility is the core lower-bound property that explains optimality for tree search, while consistency is the stronger local condition that makes graph-search behavior especially clean. The distinction helps you understand exactly which guarantee depends on which assumption.

When should I choose local search over A*?

Choose local search when the path itself is irrelevant and the state space is huge. Choose A* when the path matters and you need a shortest or least-cost route under an explicit model.

Are genetic algorithms just random search with fancy biology words?

No. They are stochastic, but not structureless. Selection amplifies fitter candidates, crossover recombines partial structures, and mutation maintains diversity. Their success depends heavily on representation, fitness design, and parameter tuning.