Problem Solving and Search (COMP30024 W2)

Problem-solving agents

Based on the percept and the environment, find out what action it should take.

This is offline problem solving; online problem solving involves acting without complete knowledge of the problem and solution.

Example: Romania (travel planning)

Holiday in Romania; currently in Arad. Flight leaves tomorrow from Bucharest.

• Steps to take
  • Formulate goal: be in Bucharest
  • Formulate problem: states - various cities / operators (actions) - drive between cities
  • Find solution: sequence of cities (i.e. Arad, Sibiu, Fagaras, Bucharest)
• Single-state problem formation
  • “single state”: Environment is completely observable, we know which city we are currently in. (read the road sign, etc.)
  • A problem is defined by four items:
    • *initial state*: e.g. “at Arad”
    • *actions* (or successor function S(x))
      • A graph defines all possible actions
      • Sometimes refered to as “operators”
      • e.g. Arad to Zerind, Arad to Sibiu, etc.
    • *goal test*, can be
      • explicit: exact state. e.g. x = “at Bucharest”
      • implicit: properties of rule to apply. e.g. “in the west border of Romania”, Checkmate in chess
    • *path cost* (additive): e.g. sum of distances, number of actions executed, etc.
  • A solution is a sequence of actions leading from the initial state to a goal state

• Selecting a state space State space must be abstracted for problem solving, to make the problem sufficiently realistic.

  • (abstract) state = set of real states
    • e.g. Being in Arad = being in lots of different distincts in Arad
  • (abstract) action = complex combination of real actions
    • e.g. “Arad → Zerind” represents a complex set of possible routes, detours, rest stops, etc.
    • For guaranteed realizability, any real state “in Arad” must get to some real state “in Zerind”.
    • Each abstract action should be “easier” than the original problem.
  • (abstract) solution = set of real paths that are solutions in the real world
• Example: The 8-puzzle
  • States: integer locations of the tiles (ignore intermediate positions)
  • Actions: move blank left, right, up, down (ignore unjamming etc.)
  • Goal test: goal state (given)
  • Path cost: 1 per move
  • Optimal solution of n-Puzzle family is NP-hard.
• Example: robotic assembly
  • States: real-valued coordinates of robot joint angles, parts of the object to be assembled.
    • The robot joint and the object part locations are specified as real continuous values
  • Actions: continuous motions of robot joints
  • Goal test: complete assembly with no robot included
    • final coordinates of the part components (not the state of the robot)
  • Path cost: time to execute
    • How long it takes to move each joint
    • Made simultaneously or sequentially?

Search algorithms

• General Search

  

  • Offline, simulated exploration of state space by generating successors of already-explored states (a.k.a. expanding states)
  • Example: getting from Arad to Bucharest
    • Comments
      1. It is possible to have loops
         • links are bidirectional; need to test and keep track to avoid infinite loops
      2. State space in this problem: 20 cities, but size of the tree can be infinite
         • State space != size of the search tree

• Implementation of search algorithms

  • States vs. nodes
    • A node is a data structure constituting part of a search tree, which includes parent, children, depth, path cost g(x)
    • A state is a (representation of) physical configuration (does not have parent, children, etc.)
  • The EXPAND function creates new nodes, filling in various fields and using OPERATORS (or ACTIONS) of problem to create the corresponding states.

• Search strategies

  • A strategy is defined by picking the order of node expansion
  • Strategies are evaluated along the following dimensions:
    • completeness: does it always find a solution if one exists?
    • time complexity: number of nodes generated/expanded
    • space complexity: maximum number of nodes in memory
    • optimality: does it always find a least-cost solution?
  • Time and space complexity are measured in terms of:
    • b - maximum branching factor of the search tree (i.e. angles of robot arm)
    • d - depth of the least-cost solution
    • m - maximum depth of the state space (may be infinite)