Search Strategies and Algorithms Review

Artificial Intelligence Search Agents

• Goal-based agents work towards a goal.
• They consider the impact of actions on future states.
• Agents' job: identify the action(s) that lead to the goal.
• Search through possible solutions is formalized.
• Examples include: mazes, the 8-queen problem, and 8-puzzles.

Goal-based Agents

• Reflex agents use mappings from states to actions.
• Goal-based agents encompass problem-solving and planning agents.

Problem Solving as Search

• Define the problem through:
  • Goal formulation
  • Problem formulation
• Solving the problem as a two-stage process:
  • Search (mental or offline exploration of possibilities)
  • Execute the solution found

Problem Formulation

• Initial state: the state in which the agent starts.
• States: all states reachable from the initial state by any sequence of actions (state space).
• Actions: possible actions available to the agent. Actions(s) returns the set of actions executable in state s (action space).
• Transition model: A description of what each action does (Result(s, a)).
• Goal test: determines if a given state is a goal state.
• Path cost: function to assign a numeric cost to a path, relative to performance measure.

Examples

• The 8-queen problem: Place 8 queens on a chessboard so no queen attacks another horizontally, vertically, or diagonally. 64 * 63 * 62 ... 57 = 1.8 x 10^14 possible sequences to investigate.

• 8-puzzles:

  • States: all arrangements of 0 to 8 queens on the board.
  • Initial state: no queen on the board.
  • Actions: add a queen to any empty square.
  • Transition model: updated board.
  • Goal test: 8 queens on the board with none attacked.
  • Examples of initial and goal states provided.

• States: location of each of the 8 tiles on the 3x3 grid.

• Initial state: any state

• Actions: Move Left, Right, Up, or Down

• Transition model: given a state and an action, returns resulting state

• Goal test: state matches the goal state?

• Path cost: total moves, each move costs 1.

Search Problems

• A search problem consists of:

  • A state space.
  • A successor function (with actions, costs).
  • A start state.
  • A goal test.
  • A solution is a sequence of actions (a plan) that transforms the start state to a goal state.

• Example: Traveling in Romania

  • State space: cities (e.g., Arad, Bucharest).
  • Successor function: roads, cost = distance.
  • Start state: Arad.
  • Goal test: state == Bucharest?

State Space Graphs and Search Trees

• State space graph: a mathematical representation of a search problem.

  • Nodes: abstracted world configurations (e.g. in game)
  • Arcs: successors (action results)
  • Single occurrence of a state (once! only one)

• Search tree: a "what if" tree of plans and their outcomes.

  • Start state is the root node.
  • Children correspond to successors.
  • Nodes show states, but correspond to plans that achieve those states.

• For most problems you can't build the entire tree.

• Illustrative examples given for both trees and graphs

Search Examples

• Demonstrates the search procedures for specific examples such as a maze or the 8-puzzle.

General Tree Search

• Function: TREE-SEARCH(problem, strategy)
  • Initializes the search tree with the initial problem state
  • Loops until no more candidates for expansion, returns failure.
  • Selects a leaf node for expansion according to strategy and return corresponding solution if node contains goal state
• Important elements:
  • Fringe: collection of nodes waiting to be expanded
  • Expansion strategy: method for choosing which node to expand next from fringe
  • Exploration strategy

Review

• Summary of topics covered.

Definitions

• Agent: an entity that perceives its environment and acts upon it.
• State: a configuration of the agent and its environment.
• Actions: choices that can be made in a state (e.g., move left).
• Transition model: description of the state produced by action a, in state s
• State space: the set of all states reachable from the initial state by any sequence of actions.
• Goal test: determines whether a current state is a goal state
• Path cost: the numerical cost associated with a given path in the state space.
• Node: data structure storing current state, parent node, the action taken to reach current state, cost from initial state to node, and depth (number of steps)

Approach (Search Methods)

• Start with a frontier (usually a queue) containing the initial state.
• Repeat these operations (until the frontier is empty):
  • Remove a node from the frontier
  • If the removed node’s state is the goal state, return the solution
  • Otherwise, expand the node, and add the resulting nodes to the frontier.

Revised Approach (Search Methods)

• Start with a frontier containing initial state.
• Start with an empty explored set.
• Repeat these operations (until the frontier is empty):
  • Remove a node from the frontier.
  • If the removed node's state is the goal state, return solution.
  • Add the removed node to the explored set.
  • Expand the removed node, add resulting NEW nodes to the frontier ONLY IF they are NOT already present in the in frontier or explored set.

Search in Details

• Key components for well-defined problems and solutions.
  • Initial state
  • Actions
  • Successor function
  • Goal test
  • Path cost
• Examples of simple problem types, including vacuum world, 8-queens, 8-puzzle, and route-finding.