[Artificial Intelligence] Solving problems by Searching (1)

• Solving problems by Search (1)
• Solving problems by Search (2)

Problem Solving

• The 8-Puzzle:
  • 3 x 3 board with eight numbered tiles and a blank space

• Cryptarithmetic Problem

• Assign a decimal digit to each of the letter in such a way thatanswer to the problem is correct.
• If the same letter occurs more than once, it must be assigned same digit each time.
• No two different letters may be assigned same digit

2.1 Well-defined problems and solution

• Basic elements of a problem definition: states and actions
  • Initial state
  • Operator: description of an action in terms of which state will be reached by carrying out the action in a particular state
  • Goal test: agent can apply a single state description to determine if it is a goal state.
    • explicit set of possible goal states
    • specified by abstract property
  • Path cost function: a function that assigns a cost to a path
• State space: set of all states reachable from the initial state by any sequence of actions.
• Path: any sequence of actions leading one state to another.
• Solution : a path from the initial state to goal state

2.2 Example Problems

The 8-Puzzle

: 3 x 3 board with eight numbered tiles and a blank space

• States: a state description specifies the location of each of the eight tiles.
• Operators: blank moves left,right,up or down
• Goal test: state matches the goal configuration
• Path cost: each step costs 1. path cost is the length of the cost

Search Tree for the 8 puzzle problem

• States: a state description specifies the location of robot, sensory input values
• Operators: move north, south, east, west
• Goal test: state matches the goal location
• Path cost: each step costs 1 Path cost is the length of the path

Robot in a Two Dimensional Grid World

• Boundary
• Solid object
• The robot senses whether the eight surrounding cells are free for it to occupy

• Large, unmovable objects(obstacles)
• Move from start state to the goal state avoiding obstacles
• Robot is able to sense whether or not the eight cells surrounding it are free
• Sensory inputs: s1, s2, …, s8. Either 0 or 1, 0 if cell is free
• Four actions - move north, south, east, west

• States: a state description specifies the location of robot, sensory input values
• Operators: move north, south, east, west
• Goal test: state matches the goal location
• Path cost: each step costs 1. Path cost is the length of the path

Travelling Salesperson Problem

• Each city must be visited exactly once.
• The aim is to find shortest path.
• In Romania Map
• State: in Oradea, visited {Arad, Sibiu}

2.3 Search Tree and Graph

• Find a path from Arad to Bucharest
  • initial state Arad
  • after expanding Arad
  • after expanding Sibiu

Tree search example

• Generating Action Sequences
  • Apply operators to the current state => generate new set of states. : Expanding state
  • Choose a state
  • Test if this is a goal state
  • If it is not expand it.
  • Choosing → testing → Expanding
• The choice of which state to expand first is determined by the search strategy

• To formalize a little we can define four criteria used to measure search strategies
  • Completeness : Is the strategy guaranteed to find a solution?
  • Time Complexity : How long does it take to find a solution?
  • Space Complexity : How much memory does it take to perform the search?
  • Optimality : Does the strategy find the optimal solution where there are several solutions?

Graph

Graph Notation

• Consists of nodes
• Connected by arcs
• Directed arc
• Nodes: states
• Arcs: operators
• Parent node
• Child node
• Edges: undirected graph
• Directed tree: each node(except one) has exactly one parent
• Root node

• Node in the tree having no successors: leaf node
• Depth of node: 0 for root node
  • depth(node) = depth(parent) + 1
• Undirected tree is an undirected graph in which there is one and only one path along edges between any pair of nodes
• If all nodes except leaf nodes have the same number b of successors, b is called branching factor of the tree

• A sequence of nodes $(n_1, n_2, \dots, n_k)
  • Path of length $k-1$ from node $n_1$ to $n_k$ • If a path exists from node $n_i$ to $n_j$, then $n_j$ is accessible from node $n_i$ • C(a): cost of an arc a • Cost of a path between two nodes: sum of the costs of all of the arcs connecting nodes on the path • Optimal path: path having minimal cost