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

  1. Goal formulation: decide what to achieve
  2. Problem formulation: decide which states and actions to consider
  3. Search: find a sequence of actions, uninformed if there is no extra knowledge, informed if there is
  4. 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

ProblemStatesActionsGoal testPath cost
Romania routecity you are indrive along a highwayin Bucharestsum of distances
Vacuum worldagent location and dirt in 2 squares (8 states)left, right, suckno dirt anywhere (states 7, 8)1 per action
8-puzzletile locations ( states)move blank left, right, up, downmatches goal layout1 per move
8-queens0 to 8 queens on boardadd a queen to an empty square8 queens, none attackednot 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.