Computer Science › Section L · Artificial intelligence › Topic L.3

Reasoning: production systems and search

An agent that knows where it stands still has to work out what to do next. Production systems give many reasoning problems one shared shape, turning them into a search for a path, and heuristics make that search fast enough to be useful.

Deciding what to do next

A robot has read the tiles of an eight-puzzle: eight numbered tiles and a blank in a 3 by 3 frame, where a tile next to the blank can slide into it. Its goal is 1 2 3 / 4 5 6 / 7 8 _, rows top to bottom, _ for the blank. Could it store the answer for every starting position? A computer search shows 181,440 arrangements reachable from the goal, exactly half of the 9! = 362,880 ways to place the pieces, some needing 31 moves. Real problems are far bigger, so machines must reason out solutions.

Production systems

Many reasoning problems share one structure, a production system, with three parts. 1. States, each a possible situation, including a start state and one or more goal states; for the puzzle, a state is an arrangement of tiles. 2. Productions, or rules, each turning one state into another, often with preconditions; here, sliding a tile into the blank, allowed only if the tile is next to it. 3. A control system, the logic that decides which applicable production to use at each step so that a goal is reached. Designing the control system is the real work.

State graphs and other problems

Draw each state as a node and each production as an arrow to the state it produces: this directed graph is the state graph. The states, productions and preconditions form the problem space. Solving the problem means finding a path from the start to a goal. The view is general: in chess the states are board positions and the productions legal moves, of which White has 20 at the start; in logical reasoning the states are sets of known statements and the productions inference rules, as with resolution in 'Declarative programming'. State graphs are usually too large to draw: a way of thinking, not a structure to build.

Worked example: forward chaining with rules

Expert systems, such as MYCIN, built at Stanford in the 1970s to advise on bacterial infections, are production systems whose productions are if-then rules. Plant-care rules: R1, if leaves yellow and soil wet, then overwatered; R2, if overwatered, then water less; R3, if leaves yellow and soil dry, then underwatered; R4, if underwatered, then water more. Known facts: leaves yellow, soil wet. 1. Cycle 1: only R1 has all its conditions met; it adds overwatered. 2. Cycle 2: R2 applies and adds 'water less'. 3. Cycle 3: no rule adds anything new, so the system stops with the advice to water less. Working from facts towards conclusions is forward chaining; Prolog works backwards from a goal instead.

Search trees and breadth-first search

A control system explores the state graph by building a search tree. The root is the start state, and a node's children are the states one production away, leaving out any move that undoes the one before. Breadth-first search builds the tree layer by layer, so the first goal it reaches needs the fewest moves. From 1 3 _ / 4 2 6 / 7 5 8 the layers hold 2, 4, 8 and 16 nodes, and the goal appears at depth 4, after 31 nodes in all. Parent links let the solution be recovered: walk up from the goal stacking each move, then pop them to replay in order.

Why search trees explode

If every node has b children, depth d holds about \(b^d\) nodes. With b = 3 and d = 20 that is about 3.5 billion. Chess is far worse: in 1950 Claude Shannon estimated roughly \(10^{120}\) possible games. Depth-first search, which follows one path as deep as it can before backing up, needs much less memory, but it can wander down long, useless paths and does not guarantee the shortest solution, so it is often depth-limited. Both are blind, treating every option alike; people do better by trying the most promising first.

Heuristics

A heuristic is a quick estimate of how far a state is from the goal. A useful one is a reasonable estimate, so it ranks states sensibly, and cheap to compute, or the time saved in searching is lost in calculating. Two classic puzzle heuristics are the number of misplaced tiles and the Manhattan distance, the sum over all tiles of how many rows plus columns each is from its home square. Manhattan is better informed: a tile three squares from home needs at least three moves. Neither overestimates, since each move shifts one tile one square.

Worked example: two heuristics for one state

State: 5 1 3 / 4 2 6 / 7 8 _. 1. Misplaced tiles: 5 sits where 1 belongs, 1 where 2 belongs and 2 where 5 belongs; the rest are home, so the count is 3. 2. Manhattan distance: tile 5 is one row and one column from home, 2; tiles 1 and 2 are each one square away, 1 each. Total 4. 3. True cost: breadth-first search finds the shortest solution takes 10 moves. 4. Conclusion: both underestimate, Manhattan less so. Cycling three tiles round a loop also needs the blank to travel, which neither counts.

Best-first search and A*

Greedy best-first search always expands the leaf with the smallest estimate. It often heads almost straight for the goal with a far smaller tree than breadth-first search, but because it looks only at the estimated remaining cost it can be lured onto a route that is long overall. The A* algorithm, described in 1968, fixes this by expanding the leaf with the smallest \(f = g + h\), where g is the actual cost of reaching it and h the estimate of the rest. If h never overestimates, called admissible, A* searching a tree like ours is guaranteed to find a cheapest path; a version that never revisits a state also needs h consistent, never dropping by more than a step's cost.

Worked example: greedy best-first versus A*

Roads: S to A costs 3, A to G 7, S to B 5, B to G 3. Estimates of the distance to G: h(S) = 5, h(A) = 2, h(B) = 3. 1. Greedy: A's estimate beats B's (2 against 3), so expand A, reaching G by S, A, G at cost 3 + 7 = 10. 2. A*: f(A) = 3 + 2 = 5 and f(B) = 5 + 3 = 8, so expand A first, adding G with f = 10. 3. B, at 8, now beats G at 10, so expand B, adding G with f = 5 + 3 = 8. 4. That G is now smallest, so A* stops with S, B, G at cost 8. Check: every estimate is admissible: 5 ≤ 8, 2 ≤ 7, 3 ≤ 3.

Common mistakes to avoid

First, confusing the state graph, the full conceptual map, with the search tree, the part actually built. Second, letting the search undo its previous move, wasting nodes. Third, expecting greedy best-first search to find the cheapest route, when the S, A, G route shows it can be fooled. Fourth, giving A* a heuristic that overestimates, which removes its guarantee. Fifth, choosing a heuristic so costly that blind search would be quicker.

Key takeaways

A production system has states, productions with preconditions, and a control system that chooses among them; its state graph turns reasoning into finding a path, and expert systems chain if-then rules the same way. A search tree is the explored part of the graph. Breadth-first search finds a fewest-move solution but grows like b^d; depth-first saves memory without that guarantee. A heuristic estimates the remaining cost and should be sensible and cheap. Greedy best-first expands the smallest h; A* expands the smallest g + h; searching a tree with an admissible h, it finds a cheapest path.

Flashcards

Flashcard

Production system

States, productions (rules with preconditions) and a control system

A common shape for reasoning problems.

Test your understanding

Question 1 of 5

What is the Manhattan distance of the eight-puzzle state 1 2 3 / 7 _ 6 / 5 4 8, with goal 1 2 3 / 4 5 6 / 7 8 _?

Question 2 of 5

Leaf P has path cost g = 4 and estimate h = 5; leaf Q has g = 8 and h = 2. Which leaf does A* expand next?

Question 3 of 5

In a production system for the eight-puzzle, which of these is a production?

Question 4 of 5

A search tree has 3 children for every node. About how many nodes does it have at depth 5?

Question 5 of 5

Using rules R1 to R4 from the forward-chaining example, what advice follows from the facts 'leaves yellow' and 'soil dry'?

← Previous topicNext topic →