capitulo 3a - búsquedas
Post on 03-Jun-2018
218 Views
Preview:
TRANSCRIPT
-
8/12/2019 Capitulo 3a - Bsquedas
1/50
INGENIERA ELECTRNICA YTELECOMUNICACIONES
REDES NEURONALES
UNIVERSIDAD DE CUENCAECUADOR
1
Ing. Kenneth S. Palacio Baus, MSc.kenneth.palacio@ucuenca.edu.ec
2014
Captulo 3:
Solving problems by searching
-
8/12/2019 Capitulo 3a - Bsquedas
2/50
OutlineOutlineProblem-solving agentsProblem typesProblem formulation
Solving problems by searching
Basic search algorithms
2
2014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
3/50
ProblemProblem--solving agentssolving agentsSolving problems by searching
Remember:
Intelligent agents are supposed to maximize their performancemeasure.
This cha ter describes one kind of oal-based a ent.
2014 kenneth.palacio@ucuenca.edu.ec
We limit ourselves to the simplest kind of task environment, forwhich the solution to a problem is always:
A fixed sequence of actions .
We will use the concepts of asymptoticcomplexity --O( ) notation-- andNP-completeness.
Investigar
3
-
8/12/2019 Capitulo 3a - Bsquedas
4/50
ProblemProblem--solving agentssolving agentsSolving problems by searching
Goal formulation , based on the current situation and theagents performance measure, is the first step in problem solving.
2014 kenneth.palacio@ucuenca.edu.ec
Problem formulation is the process of deciding what actionsand states to consider, given a goal.
4
-
8/12/2019 Capitulo 3a - Bsquedas
5/50
ProblemProblem--solving agentssolving agentsSolving problems by searching
2014 kenneth.palacio@ucuenca.edu.ec 5
-
8/12/2019 Capitulo 3a - Bsquedas
6/50
Example: RomaniaExample: RomaniaOn holiday in Romania; currently in Arad.Flight leaves tomorrow from Bucharest
Formulate goal :
be in Bucharest
Solving problems by searching
Formulate problem : states : various cities actions : drive between cities
Find solution : sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest
6
2014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
7/50
Example: RomaniaExample: RomaniaSolving problems by searching
7
2014 kenneth.palacio@ucuenca.edu.ec
Suppose the agent has a map of Romania. The point of a map is toprovide the agent with information about the states it might get itself intoand the actions it can take.
-
8/12/2019 Capitulo 3a - Bsquedas
8/50
Example: RomaniaExample: RomaniaSolving problems by searching
An agent with several immediate optionsof unknown value can decide what to doby first examining future actions that
82014 kenneth.palacio@ucuenca.edu.ec
eventually lead to states of known value.
The environment is known, so the agent
knows which states are reached by eachaction.
-
8/12/2019 Capitulo 3a - Bsquedas
9/50
Example:Example: RomaniaRomaniaWellWell--defined problems anddefined problems andsolutionssolutions
Solving problems by searching
A problem can be defined formally by fivecomponents:
92014 kenneth.palacio@ucuenca.edu.ec
1. The initial state that the agent starts in.For example, the initial state for our agent
in Romania might be described asIn(Arad).
-
8/12/2019 Capitulo 3a - Bsquedas
10/50
Example:Example: RomaniaRomaniaWellWell--defined problems anddefined problems andsolutionssolutions
Solving problems by searching
2. A description of the possible actions available to the agent.Given a particular state s, ACTIONS(s) returns the set of actionsthat can be executed in s. We say that each of these actions is
102014 kenneth.palacio@ucuenca.edu.ec
.
For example, from the state In(Arad), the applicable actions are{Go(Sibiu),Go(Timisoara),Go(Zerind)}.
3. A description of what each action does; the formal name for thisis the transition model , specified by a function RESULT(s,a) thatreturns the state that results from TRANSITION MODEL doingaction a in state s.
-
8/12/2019 Capitulo 3a - Bsquedas
11/50
Example:Example: RomaniaRomaniaWellWell--defined problems anddefined problems andsolutionssolutions
Solving problems by searching
We also use the term successor to refer to any statereachable SUCCESSOR from a given state by a singleaction.
112014 kenneth.palacio@ucuenca.edu.ec
For example, we haveRESULT( In(Arad), Go(Zerind)) = In(Zerind).
Together, the initial state, actions, and transition model implicitly
define the state space of the problem the set of all statesreachable from the initial state by any sequence of actions.The state space forms a directed network or graph in which thenodes are states and the links between nodes are actions.
-
8/12/2019 Capitulo 3a - Bsquedas
12/50
Example:Example: RomaniaRomaniaWellWell--defined problems anddefined problems andsolutionssolutions
Solving problems by searching
4. A path in the state space is a sequence of states connected by asequence of actions.
122014 kenneth.palacio@ucuenca.edu.ec
The goal test , which determines whether a given state is a goalstate.
Sometimes the GOAL TEST is an explicit set of possible goalstates, and the test simply checks whether the given state is oneof them.
The agents goal in Romania is the singleton set{In(Bucharest)}..
-
8/12/2019 Capitulo 3a - Bsquedas
13/50
Example:Example: RomaniaRomaniaWellWell--defined problems anddefined problems andsolutionssolutions
Solving problems by searching
A path cost function that assigns a numeric cost to each path.The problem-solving agent chooses a cost function that reflects itsown performance measure.
132014 kenneth.palacio@ucuenca.edu.ec
or t e agent try ng to get to uc arest, t me s o t e essence, so t e cost oa path might be its length in kilometers.
The step cost of taking action a in state s to reach state s isdenoted by c(s, a, s ).
-
8/12/2019 Capitulo 3a - Bsquedas
14/50
Example:Example: RomaniaRomaniaWellWell--defined problems anddefined problems andsolutionssolutions
Solving problems by searching
5. Asolution to a problem is an action sequence that leads from
142014 kenneth.palacio@ucuenca.edu.ec
.
Solution quality is measured by the path cost function, and anoptimal solution has the lowest path cost among all solutions.
-
8/12/2019 Capitulo 3a - Bsquedas
15/50
ProblemProblem types:types:Properties of the environmentProperties of the environment
Deterministic, fully observable single-state problem Agent knows exactly which state it will be in; solution is a sequence So, each action has exactly one outcome.
Non-observable sensorless problem (also called
conformant roblem
Solving problems by searching
Agent may have no idea where it is; solution is a sequence
Non-deterministic and/or partially observablecontingency problem
percepts provide new information about current state solution is a contingent plan or a policy often interleave search, execution
Unknown state space exploration problem
152014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
16/50
Solving problems by searching
Example: vacuum worldExample: vacuum world
162014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
17/50
Solving problems by searching
Example: vacuum worldExample: vacuum world
172014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
18/50
Single-state, start in #5.Solution?
Solving problems by searching
Example: vacuum worldExample: vacuum world
182014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
19/50
Single-state, start in #5.Solution? [Right, Suck]
Sensorless, start in{1,2,3,4,5,6,7,8} e.g.,
Solving problems by searching
Example: vacuum worldExample: vacuum world
g t goes to , , , Solution?
192014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
20/50
Example: vacuum worldExample: vacuum worldSensorless, start in{1,2,3,4,5,6,7,8} e.g.,Rightgoes to { 2,4,6,8}Solution?[Right,Suck,Left,Suck]
Solving problems by searching
Contingency Nondeterministic: Suckmay
dirty a clean carpet Partially observable: location, dirt at current location. Percept: [L, Clean],i.e., start in #5 or #7
Solution?
202014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
21/50
-
8/12/2019 Capitulo 3a - Bsquedas
22/50
SingleSingle--state problem formulationstate problem formulationA problem is defined by four items:
1. initial state e.g., "at Arad
2. actions or successor function S(x)= set of actionstate pairs e.g., S(Arad) ={, }
Solving problems by searching
3. goal test , can be explicit, e.g., x = "at Bucharest" implicit, e.g., Checkmate(x)
4. path cost (additive) e.g., sum of distances, number of actions executed, etc. c(x,a,y)is the step cost , assumed to be 0
A solution is a sequence of actions leading from the initial state to agoal state
222014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
23/50
Selecting a state spaceSelecting a state spaceReal world is absurdly complex
state space must be abstracted for problem solving
(Abstract) state = set of real states
(Abstract) action = complex combination of real actions
" "
Solving problems by searching
. ., , ,rest stops, etc.
For guaranteed realizability, any real state "in Arad must get tosome real state "in Zerind
(Abstract) solution = set of real paths that are solutions in the real world
Each abstract action should be "easier" than the original problem
232014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
24/50
Vacuum world state space graphVacuum world state space graph
Solving problems by searching
states?actions?goal test?path cost?
242014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
25/50
Vacuum world state space graphVacuum world state space graph
Solving problems by searching
states? integer dirt and robot location
actions? Left, Right, Suckgoal test? no dirt at all locationspath cost? 1 per action
252014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
26/50
Example: The 8Example: The 8--puzzlepuzzleSolving problems by searching
states?actions?goal test?path cost?
262014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
27/50
Example: The 8Example: The 8--puzzlepuzzleSolving problems by searching
states? locations of tilesactions? move blank left, right, up, downgoal test? = goal state (given)
path cost? 1 per move
[Note: optimal solution of n-Puzzle family is NP-hard]
272014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
28/50
Example:Example: The 8The 8--puzzlepuzzleSolving problems by searching
282014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
29/50
Example: robotic assemblyExample: robotic assemblySolving problems by searching
states? : real-valued coordinates of robot jointangles, parts of the object to be assembled
actions?: continuous motions of robot jointsgoal test? : complete assemblypath cost? : time to execute
292014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
30/50
Some RealSome Real--world problemsworld problemsSolving problems by searching
Touring problems
Traveling sales person problem (TSP)
302014 kenneth.palacio@ucuenca.edu.ec
Robot navigation
Automatic assembly sequencing
-
8/12/2019 Capitulo 3a - Bsquedas
31/50
SearchSearch algorithmsalgorithmsThe process of looking for a sequence ofactions that reaches the goal is calledsearch.
Solving problems by searching
A search algorithm takes a problem asinput and returns a solution in the formof an action sequence.
Once a solution is found, the actions it recommends canbe carried out. This is called the execution phase.
312014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
32/50
Tree search algorithmsTree search algorithmsA solution is an action sequence, sosearch algorithms work by consideringvarious possible action sequences.
Solving problems by searching
The possible action sequences starting at the initialstate form a search tree with the initial state at theroot;
The branches are actions and the nodes correspond tostates in the state space of the problem
322014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
33/50
-
8/12/2019 Capitulo 3a - Bsquedas
34/50
Tree search exampleTree search exampleSolving problems by searching
342014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
35/50
Tree search exampleTree search exampleSolving problems by searching
352014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
36/50
Tree search exampleTree search exampleSolving problems by searching
362014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
37/50
Tree search exampleTree search exampleSolving problems by searching
372014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
38/50
Implementation: general tree searchImplementation: general tree search
Solving problems by searching
382014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
39/50
Implementation: general tree searchImplementation: general tree search
Solving problems by searching
392014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
40/50
Implementation: general tree searchImplementation: general tree search
Solving problems by searching
Search-Tree includes the path from Arad to Sibiu andback to Arad again!
We say that In(Arad) is a repeated state in the searchtree, generated in this case by a loopy path.
402014 kenneth.palacio@ucuenca.edu.ec
Loops can cause certain algorithms to fail, makingotherwise solvable problems unsolvable.
Fortunately, there is no need to consider loopy paths.
Loopy paths are a special case of the more generalconcept of redundant paths, which exist whenever there ismore than one way to get from one state to another.
-
8/12/2019 Capitulo 3a - Bsquedas
41/50
Tree search exampleTree search exampleSolving problems by searching
412014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
42/50
Implementation: general tree searchImplementation: general tree search
Solving problems by searching
Theres never any reason to keep more than onepath to any given state, because any goal statethat is reachable by extending one path is alsoreachable by extending the other.
422014 kenneth.palacio@ucuenca.edu.ec
Algorithms that forget their history are doomedto repeat it.
The way to avoid exploring redundant paths is to
remember where one has been.
-
8/12/2019 Capitulo 3a - Bsquedas
43/50
Implementation: general tree searchImplementation: general tree search
Solving problems by searching
We augment the TREE-SEARCH algorithm with a datastructure called the explored set (also known as theclosed list ), which remembers every expanded node.
Newly generated nodes that match previously generatednodesones in the explored set or the frontiercan be
432014 kenneth.palacio@ucuenca.edu.ec
scar e ns ea o e ng a e o e ron er.
-
8/12/2019 Capitulo 3a - Bsquedas
44/50
Implementation: general tree searchImplementation: general tree search
Solving problems by searching
442014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
45/50
Graph searchGraph searchSolving problems by searching
452014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
46/50
Implementation: general tree searchImplementation: general tree search
Solving problems by searching
462014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
47/50
Implementation: general tree searchImplementation: general tree search
Solving problems by searching
472014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
48/50
Implementation:Implementation: statesstates vs. nodesvs. nodesSolving problems by searching
482014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
49/50
Implementation:Implementation: statesstates vs. nodesvs. nodes
A state is a (representation of) a physical configurationA node is a data structure constituting part of a searchtree includes state , parent node , action , path cost g(x),depth
Solving problems by searching
The Expand function creates new nodes, filling in thevarious fields and using the SuccessorFn of theproblem to create the corresponding states.
492014 kenneth.palacio@ucuenca.edu.ec
-
8/12/2019 Capitulo 3a - Bsquedas
50/50
Implementation:Implementation: statesstates vs. nodesvs. nodesSolving problems by searching
Given the components for a parent node, it is easy to see how tocompute the necessary components for a child node.
The function CHILD-NODE takes a parent node and an actionand returns the resulting child node:
502014 kenneth palacio@ucuenca edu ec
top related