Goal-Based Agents and State Space Search

Goal-Based Agents

• Reflex agents use a mapping from states to actions
• Goal-based agents consist of problem-solving agents or planning agents

Types of Agents

• Reflex agents chooses an action based on the current percept
• Reflex agents don't consider the future consequences of actions
• Planning agents considers decisions based on hypothesized consequences of actions
• Planning agents must have a model of how the world evolves in response to actions
• Planning agents must formulate a goal

State Space Search

• Problems are solved by searching among alternative choices
• People contemplate various strategies to solve problems
• Chess players consider a few alternative moves
• Mathematicians choose from different strategies to find a proof for a theorem
• Physicians evaluate several possible diagnoses

How Human Beings Think

• Humans don't search the entire state space (exhaustive search)
• Only alternatives that experience has shown to be effective are explored
• Human problem-solving uses judgmental rules that limit the exploration of search space to portions that seem promising
• Judgmental rules are known as heuristics

Heuristic Search

• Heuristics are a strategy for selectively exploring the search space
• Heuristics guide the search along lines that have a high probability of success
• Heuristics employ knowledge about the nature of a problem to find a solution
• Heuristics don't guarantee an optimal solution but come close most of the time
• Humans use many heuristics in problem-solving

Search

• Search designing incorporates goal-based agents in fully observable, deterministic, discrete, known environments
• The agent must find a sequence of actions that reaches the goal
• The performance measure includes reaching the goal
• The measure also includes how "expensive” the path to the goal is

Search Problem Components

• Search problem components consist of initial state, actions, transition model, goal state, solution path, and path cost
• A transition model determines what state results from performing a given action in each state
• The path cost is the sum of non-negative step costs
• An optimal solution is the sequence of actions that gives the lowest path cost for reaching the goal

Romania Example

• A vacation in Romania starts in Arad with a flight leaving from Bucharest
• Initial state will be in Arad
• Actions consist of moving from one city to another
• If you go from city A to city B, you end up in city B
• The goal state is Bucharest
• Path cost is the sum of edge costs indicating total distance traveled

State Space

• Initial state, actions, and transition model define the state space of a problem
• State space is the set of all states reachable from the initial state by any sequence of actions
• State space can be represented as a directed graph where the nodes are states and links between nodes are actions

AI Problem Graph Theory

• An AI problem can be represented as a state space graph
• A graph is a set of nodes and links that connect them
• Graph theory includes labeled graphs, directed graphs, paths, rooted graphs, trees, parents, children, siblings, ancestors, and descendants

Goal-Based Agents

• Goal-based agents work towards a goal
• Goal-based agents consider the impact of actions on future states
• Agent’s job is to identify the action or series of actions that lead to the goal
• Search helps formalize possible solutions

Examples

• The 8-queen problem involves placing 8 queens on a chessboard
• The board placement should ensure no queen attacks any other horizontally, vertically, or diagonally
• Number of possible sequences to investigate equals 1.8 x 10^14

Problem Solving as Search

• Defining the problem consists of goal formulation and problem formulation

Problem Formulation

• Initial state: the state in which the agent starts
• States: all states reachable from the initial state by any sequence of actions i.e., the State space
• Actions: possible actions available to the agent
• For actions at a state "s", Actions(s) returns the set of actions that can be executed in state "s" (Action space)
• Transition model: a description of what each action does Results(s, a)
• Goal test: determines if a given state is a goal state
• Path cost: function that assigns a numeric cost to a path w.r.t. performance measure

Chess Board Example

• 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

8-Puzzle Example

• States: location of each of the 8 tiles in the 3x3 grid.
• Initial state: any state
• Actions: move left, right, up or down
• Transition model: a given state and an action, returns a resulting state
• Goal test: state matches the goal state
• Path cost: total moves, each move costs 1

Route Finding Example

• States: In City i.e. Los Angeles, San Francisco, Denver,...
• Initial state: In Boston
• Actions: Go New York, etc.
• Transition model:
  • Results (In (Boston), Go (New York)) = In(New York)
• Goal test: In(Denver)
• Path cost: path length in kilometers

Real-world Examples

• Route finding problem for map search requires directions to go from location to location using links or transitions
• Applications include tools for driving directions in websites and in-car systems

State Space vs. Search Space

• State space: a physical configuration
• Search space: a depiction using search trees or a graph of possible solutions
• Search tree models the sequence of actions
  • Root: initial state
  • Branches: actions
  • Nodes: results from actions
    • A node has: parent, children, depth, path cost, and associated state in the state space
• Expand: A function that given a node, creates all the children nodes

Search Space Regions

• Search space consists of the sections: explored, frontier, and unexplored
  • Explored: Closed List, Visited Set
  • Frontier: Open List, the Fringe
  • Unexplored
• The essence of search is moving nodes from unexplored to the frontier to explored
• The essence of search strategy is deciding the order of such moves
• Adopted color coding includes orange nodes for explored, grey nodes for the frontier, white nodes for unexplored, and black nodes are failures