CMPUT 366 F20: Search
James Wright & Vadim Bulitko
September 8, 2020
CMPUT 366 F20: Search
1
Lecture Outline
Basic search
PM 3.1-3.4
CMPUT 366 F20: Search 2
Recap: Dimensions
Dimension
Static vs. sequential action Goals vs. complex preferences Episodic vs. continuing
State representation scheme Perfect vs. bounded rationality Uncertainty: states/dynamics Interaction: offline vs online Number of agents
Grid pathfinding
Chess
History of human kind
CMPUT 366 F20: Search
3
Search: Motivation
Easier to recognize a solution than to compute it
For fully-observable, deterministic, offline, single-agent problems, search exploits this property
Agent searches internal representation to find solution All computation is purely internal to the agent
Environment is fully deterministic, so no need for observations, just remember actions
Formally represent as searching a directed graph for a path to a goal state Very general: many AI problems can be represented in this form, and the same algorithms can solve them all
CMPUT 366 F20: Search 4
State Space
A state describes all the relevant information about a possible configuration of the environment
Markov assumption: How the environment got to a given configuration doesn’t matter, just the current configuration
A state is an assignment of values to one or more variables A single variable called “state”
x and y coordinates, temperature, battery charge, etc.
Actions change the environment from one state to another
CMPUT 366 F20: Search 5
Search Problem (State-space Problem)
A set of states
A start state
A set of actions available at each state
A successor function that maps from a state to a set of next states A goal function that returns true when a state satisfies the goal
CMPUT 366 F20: Search 6
In-class Exercise: Search Problem
For the problem on the right, define:
A set of states
A start state
A set of actions available at each state
A successor function that maps from a state to a set of next states
A goal function that returns true when a state satisfies the goal
I will visit break-out rooms around sampling teams’ work
https://www.growingwiththeweb.com/2012/06/ a- pathfinding- algorithm.html
CMPUT 366 F20: Search
7
Another example: DeliveryBot
DeliveryBot wants to get from outside room 103 to inside room 123
CMPUT 366 F20: Search 8
DeliveryBot as a Search Problem
DeliveryBot wants to get from outside room 103 to inside room 123
CMPUT 366 F20: Search 9
In-class Exercise: A Vacuum-cleaning Bot
A set of states
A start state
A set of actions available at each state
A successor function that maps from a state to a set of next states
A goal function that returns true when a state satisfies the goal
I will sample teams’ work
Two rooms, one cleaning robot
Each room can be clean or dirty
Robot has two actions:
clean: makes the room the robot is in clean
move: moves to the other room
CMPUT 366 F20: Search
10
Solving Search Problems: Intuition
Consider the start state
Consider each state that can be reached from a previously considered state
Stop when you consider a goal state
CMPUT 366 F20: Search 11
Directed Graphs
A directed graph is a pair G = (N, A) N is a set of nodes
A is a set of ordered pairs called arcs
Node n2 is a neighbour of n if there is an arc from n to n2
(n,n2) ∈ A
A path is a sequence of nodes (n,n2,…,nk) with (ni−,ni) ∈ A
A solution is a path (n,n2,…,nk) from a start node n to a goal node nk
Synonyms:
node = vertex
arc = edge
CMPUT 366 F20: Search 12
Search Graph
We can represent any state space problem as a search graph:
Nodes are the states
Neighbours are the successors of a state
add one arc from state n to each of n’s successors
(optional) label each arc with the action that leads to the successor state
CMPUT 366 F20: Search 13
DeliveryBot: Search Graph
CMPUT 366 F20: Search 14
Generic Graph Search Algorithm
Given a graph, start nodes, and goal, incrementally explore paths from the start nodes
Maintain a frontier of paths that have been explored
As search proceeds, the frontier expands into the unexplored nodes until a goal is encountered
The way the frontier is expanded defines the search strategy
CMPUT 366 F20: Search 15
Generic Graph Search Algorithm
CMPUT 366 F20: Search 16
Search Problem with Costs
How can we express preferences on solutions? use weighted directed graphs:
add costs to each arc: cost(ni−, ni)
k
solution cost is the sum of its arcs’ costs: cost(n, . . . , nk) = cost(ni−, ni)
An optimal solution is one with the lowest cost How general is this?
i=2
CMPUT 366 F20: Search
17
DeliveryBot: Weighted Search Graph
CMPUT 366 F20: Search 18
Recap
Many AI tasks can be represented as search problems
A single generic graph search algorithm can then solve them
with lots of fine print
A search problem consists of states, actions, start states, a successor function, a goal function
Optimizing solution quality can be addressed by labelling arcs of the search graph with costs
In the following lectures we will explore efficient search algorithms
CMPUT 366 F20: Search 19
Homework: Search Graph for Tic-Tac-Toe
Start building a search graph for the problem on the right
Nodes are the states
Neighbours are the successors of a state
add one arc from state n to each of n’s successors
label each arc with the action that leads to the successor state
We will revisit this in the next class
https://en.wikipedia.org/ wiki/Tic- tac- toe
CMPUT 366 F20: Search
20