23RO2015 ARTIFICIAL INTELLIGENCE IN ROBOTICS
Module 2
- State Space Search
- Solving problems by searching
- Uninformed Search
- Informed search and exploration
- Constraint satisfaction problems
- Adversarial search
SOLVING PROBLEMS BY SEARCHING
Problem-Solving Agents:
GOAL FORMULATION: based on the current situation and the agent’s performance
measure, is the first step in problem solving.
Problem formulation is the process of deciding what actions and states to consider, given a
goal.
Well-defined problems and solutions
A problem can be defined formally by five components:
• initial state
• a description of possible actions
• the transition model
• the goal test
• a path cost function
Initial state:
– The state the agent starts in.
– Example: In(Garage)
Actions:
– What the agent can do.
– Each possible action is applicable for a state s, if an ACTION(s) function lists them in a
sequence of states.
– { Leave(Garage), Go(Street), Turn(Right)}
● Transition Model:
– A description of each action.
– Specified by a function, RESULT(s, a).
● Returns state when action a is performed in a state s.
– A successor is any state reachable from any given state through one action.
RESULT(In(Garage), Go(Street)) = In(Street)
– Initial state, actions, and transition model define the problem's state space.
– forms a graph of states (nodes) connected by actions (edges).
– A path in the state space is a sequence of states connected by a sequence of actions.
● Goal test:
– Figures if a state is a goal state.
– If the goal is to be at the store, then the goal set could just be { At(Store) }
– That set could contain more than one goal state.
path cost function:
– assigns a numeric value to each path.
– a problem-solving agent will pick a desirable cost function.
– The step cost for taking an action is denoted: c(s, a, s')
– Returns the cost of getting from state s, using action a, to get to state s'.
Types of Search Problem
- Uninformed Search (Blind Search)
- Breadth First Search
- Uniform Cost Search
- Depth first Search
- Depth Limited Search
- Iterative deeping depth first search
- Bidirectional Search
- Informed Search (Heuristics Search)
- Best first Search/Greedy Search
- A* Search
- AO* algorithm
- Problem Reduction
- Hill Climbing
Uninformed Search Strategies
Breadth-first search is a simple strategy in which the root node is expanded first, then
all the successors of the root node are expanded next, then their successors, and so on.
Comparing uninformed search strategies
● Comparison for tree-search versions.
● For graph searches, main differences:
– dfs is complete for finite space spaces
– the space and time complexities get limited by
state space size.
INFORMED (HEURISTIC) SEARCH STRATEGIES
[Link]- first Search/ Greedy Search
➢ Best-first search is an instance of the general TREE-SEARCH or GRAPH-SEARCH
algorithm in which a node is selected for expansion based on an evaluation function, f(n).
➢ The evaluation function is construed as a cost estimate, so the node with the lowest
evaluation is expanded first.
➢ The implementation of best-first graph search is identical to that for uniform-cost search
Always selects the path which appears best at that moment.
• Combination of DFS & BFS
• Heuristic function h(n) <= h*(n) and h(n) = heuristic cost;h*(n) = estimated cost
• Implemented by priority queue.
• Advantage:
• Can switch between BFS & DFS by gaining the advantages of both the algorithm.
• More efficient than BFS & DFS.
• Disadvantage:
• Sometimes behave as an unguided depth-first search in worst case scenario.
• Can get stuck in a loop as DFS
Each state in a CSP is defined by an assignment of values to some or all of the
variables,
{Xi =vi,Xj = vj , . . .}
An assignment that does not violate any constraints is called a consistent or
legal assignment.
A complete assignment is one in which every variable is assigned, and
a solution to a CSP is a consistent, complete assignment.
A partial assignment is one that assigns values to only some of the variables.
A single variable (corresponding to a node in the CSP network) is node-
consistent if all
the values in the variable’s domain satisfy the variable’s unary constraints.
A variable in a CSP is arc-consistent if every value in its domain satisfies the
variable’s
binary constraints.
The simplest type is the unary constraint, which restricts the value of a single
variable.
A binary constraint relates two variables. For example, SA = NSW is a binary
constraint.
Adversarial search
Adversarial search is a search, where we examine the problem which arises when we try to
plan ahead of the world and other agents are planning against us.
Formalization of the problem:
A game can be defined as a type of search in AI which can be formalized of the following
elements:
•Initial state: It specifies how the game is set up at the start.
•Player(s): It specifies which player has moved in the state space.
•Action(s): It returns the set of legal moves in state space.
•Result(s, a): It is the transition model, which specifies the result of moves in the state
space.
•Terminal-Test(s): Terminal test is true if the game is over, else it is false at any case. The
state where the game ends is called terminal states.
•Utility(s, p): A utility function gives the final numeric value for a game that ends in
terminal states s for player p. It is also called payoff function. For Chess, the outcomes are a
win, loss, or draw and its payoff values are +1, 0, ½. And for tic-tac-toe, utility values are
+1, -1, and 0.
Game tree:
A game tree is a tree where nodes of the tree are the game states and Edges of the tree are
the moves by players. Game tree involves initial state, actions function, and result
Function.
Example: Tic-Tac-Toe game tree:
The following is the game-tree for tic-tac-toe game. Following are some key points of the
game:
•There are two players MAX and MIN.
•Players have an alternate turn and start with MAX.
•MAX maximizes the result of the game tree
•MIN minimizes the result.
•From the initial state, MAX has 9 possible moves as he starts first. MAX place x and
MIN place o, and both player plays alternatively until we reach a leaf node where one
player has three in a row or all squares are filled.
•Both players will compute each node, minimax, the minimax value which is the best
achievable utility against an optimal adversary.
•Suppose both the players are well aware of the tic-tac-toe and playing the best play.
Each player is doing his best to prevent another one from winning. MIN is acting against
Max in the game.
•So in the game tree, we have a layer of Max, a layer of MIN, and each layer is called
as Ply. Max place x, then MIN puts o to prevent Max from winning, and this game
continues until the terminal node.
•In this either MIN wins, MAX wins, or it's a draw. This game-tree is the whole search
space of possibilities that MIN and MAX are playing tic-tac-toe and taking turns
alternately.
adversarial Search for the minimax procedure works as follows:
•It aims to find the optimal strategy for MAX to win the game.
•It follows the approach of Depth-first search.
•In the game tree, optimal leaf node could appear at any depth of the
tree.
•Propagate the minimax values up to the tree until the terminal node
discovered.
Alpha-Beta Pruning
•Alpha-beta pruning can be applied at any depth of a tree, and sometimes it not
only prune the tree leaves but also entire sub-tree.
•The two-parameter can be defined as:
• Alpha: The best (highest-value) choice we have found so far at any point
along the path of Maximizer. The initial value of alpha is -∞.
• Beta: The best (lowest-value) choice we have found so far at any point
along the path of Minimizer. The initial value of beta is +∞.
The main condition which required for alpha-beta pruning is:
α>=β
Key points about alpha-beta pruning:
•The Max player will only update the value of alpha.
•The Min player will only update the value of beta.
•While backtracking the tree, the node values will be passed to upper nodes
instead of values of alpha and beta.
•We will only pass the alpha, beta values to the child nodes.
Incase from D, interchange value of 2 & 14… then the other branches will be
pruned
DFS