- 2070 Magh · 2+6 marks
Why searching; production system
Short answer
Searching is necessary because many AI problems lack direct solutions and require exploring a state space. A production system uses IF-THEN rules, working memory, and a control strategy; for example, the water jug problem is solved by rules for filling, emptying, and pouring until reaching the goal state (2,0).
Why is searching necessary in AI? Explain the role of production system with a suitable example.
Why searching is necessary in AI
- Most AI problems (puzzles, planning, route finding, game playing, scheduling) have no direct formula or algorithm that gives the answer. We must explore possible sequences of actions to find one that reaches the goal.
- The problem is represented as a state space (states, operators, initial state, goal). Finding a solution means searching a path from the initial state to a goal state.
- The state space is usually huge (combinatorial explosion), so we need systematic search to avoid missing solutions, and heuristic search to avoid examining everything.
- Search also finds the best (optimal) solution when several solutions exist.
Production system
A production system is a model of computation in which the problem-solving knowledge is encoded as IF-THEN rules (productions) and applied by a control strategy until the goal is reached.
Components
- Production rules: a set of condition → action pairs, e.g. "IF the 4 L jug is not full THEN fill it".
- Working memory / global database: the current state of the problem; rules read and change it.
- Control strategy: decides which applicable rule to fire when several match (conflict resolution), e.g. first match, priority, most specific rule; and decides the search order (depth-first, breadth-first, heuristic) with backtracking.
+---------------+ match +---------------+
| Rule base |--------->| Conflict set |
| (IF..THEN..) | +-------+-------+
+---------------+ | select (control)
^ update v
+------+--------+ fire +---------------+
| Working memory|<---------| Chosen rule |
+---------------+ +---------------+
Role: separates knowledge (rules) from control, so rules can be added or removed without changing the program; it gives a natural way to carry out state-space search; it is the basis of expert systems (MYCIN, OPS5) and rule-based reasoning; it supports reasoning and explanation by recording the rules fired.
Example: water jug problem
There are a 4 L jug (x) and a 3 L jug (y), both empty. Goal: exactly 2 L in the 4 L jug, state (2, y).
| No. | Condition | Action |
|---|---|---|
| 1 | x < 4 | (x, y) → (4, y) fill 4 L jug |
| 2 | y < 3 | (x, y) → (x, 3) fill 3 L jug |
| 3 | x > 0 | (x, y) → (0, y) empty 4 L jug |
| 4 | y > 0 | (x, y) → (x, 0) empty 3 L jug |
| 5 | x + y ≥ 4 and y > 0 | (x, y) → (4, y − (4 − x)) pour 3 L into 4 L until full |
| 6 | x + y ≥ 3 and x > 0 | (x, y) → (x − (3 − y), 3) pour 4 L into 3 L until full |
| 7 | x + y ≤ 4 and y > 0 | (x, y) → (x + y, 0) pour all of 3 L into 4 L |
| 8 | x + y ≤ 3 and x > 0 | (x, y) → (0, x + y) pour all of 4 L into 3 L |
Solution (rules fired): (0,0) →R2→ (0,3) →R7→ (3,0) →R2→ (3,3) →R5→ (4,2) →R3→ (0,2) →R7→ (2,0). Goal reached.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Searching: BFS vs DFS comparison · Artificial Intelligence, chapter 3 · asked 5×
- System concept and production system model · Industrial Engineering and Management, chapter 1
- Three phase system; role of aggregate phase · Concrete Technology and Masonry Structure, chapter 2
- Production room 27 × 45 m twin 36 W tubes · Industrial Power Distribution and Illumination, chapter 7 · asked 4×
- Deadlock; necessary conditions with examples · Operating System, chapter 7