PE1-6.1 Intelligent Agents & Search Algorithms

What this is and why it exists

Search is the oldest idea in this field and still the clearest. Describe the problem as states and the moves between them, then explore that space in an intelligent order.

Everything in this topic is one question. Which state do you look at next?

The vocabulary

• Agent — something that perceives its environment and acts on it.
• Performance measure — the statement of what counts as acting well.
• State — one configuration of the problem.
• Action — a move from one state to another.
• Frontier — the set of states discovered but not yet expanded.
• Expand — generate the states reachable from a given state.
• Complete — guaranteed to find a solution if one exists.
• Optimal — guaranteed to find the cheapest solution.
• Heuristic — an estimate of the remaining cost from a state to a goal.
• Admissible heuristic — one that never overestimates that remaining cost.

The mental model

Start with the honest framing the outline asks for. The current state of the field is worth reading carefully, because it is a good inoculation against the popular account. Systems do specific things well, and they fail in ways their successes do not suggest. The distance between a demonstration and a deployed system is large.

An agent is anything that perceives and acts. Two things make that abstraction useful rather than empty.

The first is the performance measure. Without a statement of what counts as acting well, there is no way to say whether an agent worked. The measure should describe the outcome you want, not the behaviour you imagine produces it. An agent optimising the second will satisfy it in ways you did not intend.

The second is the environment. Is it fully or partly observable? Do actions have certain effects? Does it change while the agent deliberates, and are there other agents in it? Those properties decide which techniques apply at all, so they are settled before any algorithm is chosen.

Problem formulation is most of the work and it is a skill rather than a fact. Choose what a state is, what actions are available, what it costs to take one, and what counts as a goal. A well chosen state description makes the search small. A poor one makes the same problem intractable, and no algorithm recovers from that.

Now the strategies, and the uninformed ones differ only in the order they take states from the frontier.

Depth-first goes as deep as it can before backtracking. It needs very little memory, because it holds only the current path and the alternatives along it. It is not optimal, and on an infinite or very deep space it can go down forever.

Breadth-first expands everything at one depth before going deeper. It finds the shallowest solution, so with uniform costs it is optimal, and it is complete. Its memory grows with the number of states at the current depth, which grows exponentially, and that is what makes it unusable on large problems.

Uniform cost expands the cheapest path so far rather than the shallowest. That makes it optimal when actions have different costs, which is the case breadth-first cannot handle.

Two refinements follow. Depth-limited search is depth-first with a cap, which stops the infinite descent and may miss a solution deeper than the cap. Iterative deepening runs depth-limited search with a limit of one, then two, then three, and so on.

That looks wasteful and is not, which is the surprise worth understanding. Repeating the shallow levels sounds expensive. But the number of states grows exponentially with depth, so the last level contains most of the whole search. Repeating everything above it adds a modest fraction. The result gets breadth-first's completeness and optimality with depth-first's memory, and that combination is why it is the standard uninformed choice.

Informed search uses an estimate of what remains. Greedy best-first expands whichever state looks closest to the goal by that estimate. It is fast and it is not optimal. It ignores what has already been spent getting there, so it can walk confidently into a long detour.

A star fixes exactly that by adding the two together: the cost already incurred to reach a state, plus the estimated cost remaining from it. Expanding the smallest total balances both concerns, and it is the most used search algorithm in the field.

The condition on the estimate turns the algorithm from a recipe into something you can reason about. It must be stated precisely. An admissible heuristic never overestimates the true remaining cost. It may underestimate, by any amount, including estimating zero everywhere.

Get that exactly right, because a good heuristic is a different statement. Admissibility is what guarantees optimality, and it says nothing about how close the estimate is. A heuristic that always returns zero is admissible and useless: the search still finds the best answer and explores almost everything doing it. A heuristic that is usually accurate and occasionally too high is informative and gives no guarantee at all.

What you should now be able to explain or do

Say why a performance measure must describe outcomes rather than behaviour. Name the environment properties that decide which techniques apply. Formulate a problem as states, actions, costs and a goal. Compare the uninformed strategies on completeness, optimality, time and memory, and explain why iterative deepening is not wasteful. State admissibility exactly and say what it does and does not guarantee.

Check yourself