CSE about AI

imour33

SearchIntro1.pdf

Home >Computer Science homework help >CSE about AI

Artificial Intelligence

Problem solving and search

(introduction)

“In which we look at how an agent can decide what to do by systematically

considering the outcomes of various

sequences of actions that it might take.”

“In which we see how an agent can find a sequence of actions that achieves its

goals, when no single action will do.”

Problem Solving

• Problem-solving agent

– A kind of goal-based agent that decides what to

do by finding sequences of actions that lead to

desirable states

• But what is a “problem”?

• What is a “solution”?

Romania Example

• Imagine agent in Arad, Romania (on holiday)

– Performance measure could be

• Sightsee, eat good food, enjoy nightlife, etc.

• Suppose have nonrefundable ticket to fly out of Bucharest tomorrow

– Agent now adopts goal of getting to Bucharest on time

• Courses of action that do not reach Bucharest on time can be rejected

– Simplifies decision making

• “Goals help organize behavior by limiting objective that agent is trying to achieve”

Problem-Solving Agents

• [Step 1] Formulate goal

– Based on current situation

– Goal: a set of states in which the goal is satisfied

• Actions cause transitions between world states

– Need to find sequence of actions to get to goal

• [Step 2] Formulate problem

– Decide what actions and states to consider, given a goal

– Decide how to quantify best solution

– Need higher level of detail, else becomes intractable

– Organize actions and states (graph structure, map)

How find best sequence (path) of actions?

Problem-Solving Agents

• [Step 3] Search

– Process of looking for best action sequence (to reach goal)

– Input: formulated problem

– Output: solution (as action sequence)

• [Step 4] Execution phase

– Execute recommended actions

• [Step 5] Find a new goal (repeat)

Note: “offline” problem solving – Complete knowledge of problem and solution

Romania Example

• On holiday in Romania, currently in Arad

• Flight leaves tomorrow from Bucharest

• [Step 1] Formulate goal

– Be in Bucharest

• [Step 2] Formulate problem

– States: various cities

– Operators: drive between cities

– Best solution: shortest time

• [Step 3] Search: find solution

– Sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest

Romania

Oradea

Zerind

Arad

Timisoara

Lugoj

Mehadia

Debreta Craiova

Sibiu

Rimnicu Vilcea

Fagaras

Pitesti

Bucharest

Giurgiu Eforie

Urziceni

Hirsova

Vaslui

Iasi

Neamt

Environment

• Static

– Formulating and solving problem in a fixed environment

• Fully observable

– All states knowable

• Discrete

– Cities are nodes, actions are links

• Deterministic

– No randomness assumed

• Agent

– Single

Well-Defined

Problems and Solutions

• A problem is defined by four items

– Initial state

• “In Arad”: In(Arad)

– Actions/Operators available to agent

• Successor function for state x:

SUCCESSOR-FN(x) = <action, successor> pairs

SUCCESSOR-FN( In(Arad) ) =

{< Go(Sibiu), In(Sibiu) >, < Go(Zerind), In(Zerind)>,

< Go(Timisoara), In(Timisoara)>}

State

Space

Well-Defined

Problems and Solutions (con’t) – Goal test

• Determines whether a given state is a goal state

• Explicit: In(Bucharest)

• Implicit (property): “Checkmate”

– Path cost

• A path is sequence of states connected by actions

• Used to check if one solution path is better than another

• Assigns numeric cost to each path

– Should reflect performance measure

– Example: Additive → sum of distances (time), number of operators executed, etc.

– Example: Multiplicative → product of probabilities

• A solution is a sequence of operators leading from the initial state to a goal state

– Optimal solution has lowest path cost

Selecting a State Space

• Real world is absurdly complex

– State space must be abstracted for problem solving

• Consider route planning GPS system in car

• Abstract state

– Set of real states, “In Arad”

• Abstract action/operator

– Complex combination of real actions

– “Arad  Zerind” complex set of possible routes, detours, rest stops compressed into “change of location”

• Abstract solution

– Set of real paths that are solution in real world

– “Arad  Sibiu  Fagara  Bucharest”

Example Problems

• “Toy” problem

– Intended to illustrate or exercise various problem-

solving methods

– Given a concise, exact description

– Useful for comparing performance of algorithms

• Real-world problem

– Solutions people actually care about

– Tend not to have universal description

• Not everyone agree on problem description

Toy Problem: Vacuum World

L R

S S

• States:

• Initial state:

• Actions:

• Goal test:

• Path cost:

Integer (discrete) dirt and robot locations

Any state

(Left, Right, Vacuum)

All squares clean

Additive, each step costs 1 (???)

Validity?

Toy Problem: The 8-puzzle

5 4

6 1 8

7 3 2

1 2

7 6 5

Start State Goal State

• States:

• Initial state:

• Actions:

• Goal test:

• Path cost:

Integer (discrete) locations of each tile and blank

Any state

(Left, Right, Up, Down)

Matches goal configuration

Additive, each step costs 1

Validity?

In-Class Exercise

• Have 2 empty water jugs

– One is 3 gallon capacity, other is 7 gallon capacity

• Can “add to” or “pour from” a jug

– “Add water” by pouring from other jug, or by filling from a faucet

– Can “empty jug” down drain

– Must completely fill (no spill-over) and empty jug

• e.g., pouring a full jug-7 into an empty jug-3 leaves 4 gallons left in jug-7 and 3 gallons in jug-3

• GOAL: have exactly one gallon of water in smaller jug

In-Class Exercise

• States: ?

• Initial state: ?

• Actions: ?

• Goal test: ?

• Path cost: ?

In-Class Exercise • States:

<gal-jug3, gal-jug7>

• Initial state:

<0, 0>

• Actions:

pourYintoX(jugX, jugY)

Valid: jugY is not full, jugX is not empty

Result: jugY = jugX+jugY or full. jugX = empty or remainder

emptyJug(jugX)

Valid: jugX is not empty

Result: jugX = 0

fillFromFaucet(jugX)

Valid: jugX is not full

Result jugX = X

• Goal test:

<gal-jug3=1, gal-jug7=X>

• Path cost:

Additive, each step costs 1?

In-Class Exercise

• One Solution

INIT: <gal-jug3=0, gal-jug7=0)

fillFromFaucet(jug7) <gal-jug3=0, gal-jug7=7)

pourYintoX(jug3,jug7) <gal-jug3=3, gal-jug7=4)

emptyJug(jug3) <gal-jug3=0, gal-jug7=4)

pourYintoX(jug3,jug7) <gal-jug3=3, gal-jug7=1)

emptyJug(jug3) <gal-jug3=0, gal-jug7=1)

pourYintoX(jug3,jug7) <gal-jug3=1, gal-jug7=0)

Real-World Problems

• Route-finding/planning

– GPS navigation, airline travel

• Internet search

• Robot navigation

• Configuration layout

• Etc.

Searching For Solutions

• Have formulated problem, now need to solve it

• Search through state space

– Using search tree

• Search node

– Initial state

– Test if already goal state!!!

• Expand current state

– Apply successor function to generate new states

• Which state to examine (and expand) next?

– Use search strategy

Searching for Solutions

• Basic idea:

– Offline, simulated exploration of state space by

generating successors of already-explored states

• Expanding states

– Continue choosing, testing, and expanding until

find a solution

– Choice of which state to expand first (each

time) determined by the search strategy

Romania

Oradea

Zerind

Arad

Timisoara

Lugoj

Mehadia

Debreta Craiova

Sibiu

Rimnicu Vilcea

Fagaras

Pitesti

Bucharest

Giurgiu Eforie

Urziceni

Hirsova

Vaslui

Iasi

Neamt

General Search Example

Arad

General Search Example

SibuZerind Timisoara

Arad

General Search Example

Zerind Timisoara

Arad

OradeaArad Rimnicu

Vilcea Fagaras

Sibu

Need to use a search strategy to choose which state to expand

(Will discuss different strategies next lecture)

General Search Example

Zerind Timisoara

Arad

OradeaArad Rimnicu

Vilcea

Sibu

Sibu Bucharest

Fagaras

General Search Example

Zerind Timisoara

Arad

OradeaArad Rimnicu

Vilcea

Sibu

Sibu Bucharest

Fagaras

Goal

Measuring Performance

• Completeness

– Does it find a solution when one exists?

• Optimality

– Is it the solution with lowest path cost?

• Time complexity

– How long does it take to find a solution?

• Space complexity

– How much memory is needed to perform the search?

Main Types of Search

• Uninformed search

– Given no information about problem (other

than its definition)

• Informed search

– Given some idea of where to look for solutions

Summary

• Before searching for solutions, must formulate goal and problem

• A problem consists of

– Initial state

– Actions/Operators (successor function)

– Goal test function

– Path cost function

• Toy vs. real-world problems

– Many real world problems can fit into state space model

• Search strategy needed to select states to examine

– Have different performances