CSC 411 Lecture 4 Outline of Last Lecture I. Agent Typesa. Simple reflex agentsb. Model-based reflex agentsc. Goal-based reflex agentsd. Utility-based agentse. Learning agentsII. Statesa. Atomicb. Factoredc. StructuredOutline of Current Lecture I. Problem Solving by Searchinga. Searchb. What is a problem?c. Goal testingCurrent LectureProblem solving by searchingExample- Assume solving an equation:o 3x+2 = 11- Challenging? Give to preschoolers, and they will search to find a solutionSolving problems by searching- Some problems have a straightforward solutiono Just apply a known formula, or follow a standardized procedure Example: solution of the linear or quadratic equationso Hardly a sign of intelligence- More interesting problems do not have a straightforward solution, and they require searchThese notes represent a detailed interpretation of the professor’s lecture. GradeBuddy is best used as a supplement to your own notes, not as a substitute.o More than one possible alternative needs to be explored before the problem is solvedo The number of alternatives to search among can be very large, even infinite- Exampleso Route finding/traveling salesmano Tile puzzleo N-queens problemA search problem- Is defined by:o A search space: the set of objects among which we search for the solution Ex. Routes connecting two cities, different N-queen configurationso A goal condition: what are the characteristics of the object we want to find in thesearch space?Search- Search (process): the process of exploration of the search space- Efficiency of the search depends on:o Search space and its sizeo Method used to explore (traverse) the search spaceo Condition to test the satisfaction of the search objectiveWhat’s a problem?- States: nodes in the graph- Initial state: where the agent starts- Actions: what the agent can do (in a given state)- Transition model: a mapping from actions to states (e.g., a bubble diagram, transition function)o A successor is a state reachable from a given state by one actiono The state space is the set of all states reachable from the initial state by any sequence of actionso A path is a sequence of states connected by actions- Goal test: a test whether a given state is a goal state- Path cost: an assignment of cost to a patho Typically the sum of step costs for actions on a pathCreate abstraction of complex problem to use this model- States- Initial state- Actions- Transition model- Goal state- (Path cost)Example: Romania- States: all the cities- Initial state: Arad- Actions: travel to neighboring cities- Transition model: roads- Goal state: Bucharest- (Path cost: total distance)Example: Vacuum- States: configurations of clean/dirty blocks and vacuum location (8 states for 2 blocks)- Initial state: whole room is dirty, vacuum at some location- Actions: left, right, suck, no operation- Transition model: mapping of which action leads to which state (e.g., on dirty block  suck  block is clean, move to different state)- Goal state: whole room is clean, vacuum at any