Local Search

Local Search Algorithms

Background — So far we’ve systematically explored the search space with memory to get a path. But the path is irrelevant in many optimization problems (e.g., N-Queens, we just want the final board).

Local Search Algorithms: Keep a single “current” state and try to improve it.¹1. Because they don’t maintain a frontier or explored set, they operate in O(1) space.

• Uses little memory (usually constant)
• Finds reasonable solutions in large/infinite state spaces

Hill Climbing Search

aka: greedy local search

“Like climbing Everest in thick fog with amnesia”²2. just like me for real.

function HILL-CLIMBING(problem) returns a state that is a local maximum
    current \leftarrow MAKE-NODE(problem.INITIAL-STATE)
    loop do
        neighbor \leftarrow a highest-valued successor of current
        if VALUE[neighbor] \le VALUE[current] then return STATE[current]
        current \leftarrow neighbor

Note — Gets stuck easily in local maxima, ridges, and plateaus.³3. A ridge is a sequence of local maxima that is very difficult for greedy algorithms to navigate, like walking along the top of a mountain range.

Sideways moves (allowing neighbor value == current value) can help escape plateaus, but might cause infinite loops.

Simulated Annealing

Idea: Allow some bad (downward) moves to escape local maxima, but gradually decrease their frequency.

function SIMULATED-ANNEALING(problem, schedule) returns a solution state
    current \leftarrow MAKE-NODE(problem.INITIAL-STATE)
    for t = 1 to infinity do
        T \leftarrow schedule(t)
        if T = 0 then return current
        next \leftarrow a randomly selected successor of current
        \Delta E \leftarrow VALUE[next] \text{$-$} VALUE[current]
        if \Delta E \gt 0 then current \leftarrow next
        else current \leftarrow next only with probability e^{\Delta E / T}

Why? — Temperature (T) controls the probability of downward steps. High T means more random exploration. Low T means it acts like normal Hill Climbing.

Local Beam Search

Idea: Track k states simultaneously. Start with k randomly generated states.⁴4. It’s called “beam” search because instead of illuminating the whole tree (BFS) or one deep shaft (DFS), you shine a “beam” of width k down the most promising paths.

• At each step, generate all successors of all k states.
• If any is a goal, halt. Otherwise, select the k best successors from the entire pool and repeat.

Recall — This isn’t random-restart! Random-restart runs k independent searches. Beam search passes information between the branches since the k best states could all come from one superior parent.

Genetic Algorithms

A variant of stochastic beam search where successor states are generated by combining two parent states.

1. Population: Start with k randomly generated states (often represented as binary strings).
2. Fitness Function: Evaluation function that gives higher values to better states.
3. Selection: Choose pairs based on fitness probabilities.
4. Crossover: Pick a crossover point and combine the two parents to make a child string.
5. Mutation: Randomly flip some bits in the child string with a small, independent probability.

Searching with Partial Information

When an agent operates in an environment where information is incomplete, the search problem fundamentally changes. There are four main problem types based on the level of observability and determinism:

• Single-state problem: The environment is fully observable and deterministic. The agent knows exactly which state it is in.
• Sensorless (multistate) problem: The environment is entirely unobservable. The agent has no sensors and must reason about sets of states.
• Contingency problem: The environment is partially observable or nondeterministic. The agent must sense the world during execution.
• Exploration problem: The state space and transition models are unknown.

The key insight for dealing with missing information is that the agent must reason about belief states rather than physical states.⁵5. A belief state represents the agent’s current knowledge about the world, essentially grouping together all physical states that are indistinguishable given the sensor history.

A sensorless problem requires finding a pure sequence of actions that will coerce the world into the goal state no matter the starting position.

A contingency problem requires a tree-structured or conditional plan that branches based on sensor readings.