Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
A problem solving agent is a goal based agent that considers the expected outcomes of different action sequences leading to states of known value, and picks the best one (shortest or cheapest journey from A to B).
Design Steps
- Goal formulation: decide what to achieve
- Problem formulation: decide which states and actions to consider
- Search: find a sequence of actions, uninformed if there is no extra knowledge, informed if there is
- Execution: follow the recommended route
Well-Defined Problem
A problem is specified by:
- initial state, e.g. "at Arad"
- action set (successor function), the available actions and their next states
- state space, all states reachable from the initial state
- goal test, explicit (e.g. "at Bucharest") or an abstract property
- path cost , the sum of step costs along the path
A solution is a path (sequence of operators) from the initial state to a state that passes the goal test.
Examples
| Problem | States | Actions | Goal test | Path cost |
|---|---|---|---|---|
| Romania route | city you are in | drive along a highway | in Bucharest | sum of distances |
| Vacuum world | agent location and dirt in 2 squares (8 states) | left, right, suck | no dirt anywhere (states 7, 8) | 1 per action |
| 8-puzzle | tile locations ( states) | move blank left, right, up, down | matches goal layout | 1 per move |
| 8-queens | 0 to 8 queens on board | add a queen to an empty square | 8 queens, none attacked | not needed |
Real world versions: network routing, robot navigation, travel planning, and touring problems like the travelling salesperson (visit each city once, shortest tour).
Cost of Problem Solving
Where:
- search cost: time and memory to find the solution (generating and expanding nodes)
- execution cost: resources used to carry out the solution path
There is a trade-off: search a long time for the optimal solution, or a shorter time for a "good enough" one. Anytime search interleaves searching and acting.
How a search algorithm is judged is set out in Search Strategy Evaluation.