Example Problems

The real art of problem solving is in deciding the description of the states and the operators.

• The 8-puzzle

  

State: location of blank

Operator: blank moves left, right, up and down

Goal Test: match G

Path Cost: each step costs 1 so cost is length of path

• The 8-queens problem
  
  Aim of problem is to place 8 queens on chess board so none attacks another, diagram almost shows a solution, with only two queens attacking each other.

Can you work out the operators?

• Missionaries and cannibals - 3 missionaries and 3 cannibnals are stood on one side of a river with a boat. All 6 must cross the river, but the boat can only hold two people at once and the missionaries must never be left outnumbered at any point on either side.

State: (no. missionaries on left bank, no. cannibals on right bank, position of boat (1=left, 0=right))

Operator: 5 operators

Goal test: (0,0,0)

Path cost: number of crossings

Real Problems

• Route finding

• Travelling salesman
• Scheduling and planning
• Thereom proving
• VLSI layout
• Speech recognition
• Model based vision
• Robot navigation

Robot Path Planning and Configuration Space Representation

Start and goal positions must be identified alongside any obstacles

All possible robot positions must be identified, in this example we assume that the robot cannot rotate and then consider the path of a single point.

Now that the number of actions are finite the shortlisted paths can be narrowed to only be between these allowable nodes.

<<<Previous Next>>>