Recall from the agents topic: agent = ARCHITECTURE + PROGRAM, and the program implements the agent function. The four standard program structures, in order of increasing sophistication: 1. SIMPLE REFLEX AGENT Selects actions on the basis of the CURRENT PERCEPT ONLY, ignoring the percept history. function SIMPLE-REFLEX-AGENT(percept) returns an action persistent: rules, a set of condition-action rules state ← INTERPRET-INPUT(percept) rule ← RULE-MATCH(state, rules) action ← rule.ACTION return action Implemented as CONDITION-ACTION RULES (also called if-then rules, situation-action rules, or productions): if car-in-front-is-braking then initiate-braking if location = A and status = Dirty then Suck ✔ simple, fast, needs almost no memory ✔ genuinely correct for some problems ✘ WORKS ONLY IF THE ENVIRONMENT IS FULLY OBSERVABLE. A decision that depends on anything not in the current percept cannot be made. ✘ PRONE TO INFINITE LOOPS. In a partially observable environment a reflex agent can cycle forever, because it has no memory of having tried something. THE VACUUM EXAMPLE THAT SHOWS THE LIMIT: if the agent's percept is only [status] — it cannot sense its location — then on [Clean] it must choose Left or Right with no information. A DETERMINISTIC reflex agent will loop forever; RANDOMISING the choice escapes the loop and is, remarkably, a rational improvement. A randomised simple reflex agent can outperform a deterministic one, which is a genuinely surprising result and a favourite exam point. 2. MODEL-BASED REFLEX AGENT (a "state" agent) Maintains INTERNAL STATE — a representation of the part of the world it cannot currently see — to handle PARTIAL OBSERVABILITY. function MODEL-BASED-REFLEX-AGENT(percept) returns action persistent: state, the agent's conception of the world transition_model, how the world changes sensor_model, how the world is reflected in percepts rules, a set of condition-action rules action, the most recent action state ← UPDATE-STATE(state, action, percept, transition_model, sensor_model) rule ← RULE-MATCH(state, rules) action ← rule.ACTION return action THE TWO KINDS OF KNOWLEDGE the update needs: TRANSITION MODEL how the world evolves independently of the agent, and how the agent's own actions affect it SENSOR MODEL how the state of the world is reflected in the agent's percepts TOGETHER THEY CONSTITUTE A MODEL OF THE WORLD, and an agent using one is called MODEL-BASED. WHY IT MATTERS: a taxi cannot see the car beside it while changing lanes, so it must REMEMBER that the car was there a moment ago. Overtaking requires memory of what is no longer visible. ✘ IT IS RARELY POSSIBLE TO DETERMINE THE CURRENT STATE EXACTLY. The internal state is a BEST GUESS, and the agent must act on uncertainty rather than knowledge.

3. GOAL-BASED AGENT Knowing the current state is not always enough to decide what to do — at a junction the taxi can turn left, right or go straight, and the right choice depends on WHERE IT IS TRYING TO GET TO. So the agent holds GOAL INFORMATION describing situations that are desirable, and combines it with the model to choose actions that achieve the goal. · often requires SEARCH and PLANNING (the whole of ACtE0902) to find an action sequence, because the goal may be many steps away · FUNDAMENTALLY DIFFERENT from the reflex agent: it considers the FUTURE — "what will happen if I do this?" and "will that make me happy?" ✔ MORE FLEXIBLE than a reflex agent, because the knowledge supporting its decisions is EXPLICIT and can be MODIFIED. Change the destination and the behaviour changes; a reflex agent would need its rules rewritten. THIS IS THE KEY ADVANTAGE AND THE STANDARD EXAM POINT: if it starts to rain, a model-based reflex agent's braking rules must all be revised by hand, whereas a goal-based agent's model is updated once ("wet roads reduce braking effectiveness") and every decision adapts. ✘ a goal is BINARY — achieved or not. It cannot express "this outcome is better than that one", or trade off conflicting objectives. 4. UTILITY-BASED AGENT Goals alone are not enough for high-quality behaviour. Many action sequences reach the destination; some are quicker, safer, cheaper or more comfortable. A UTILITY FUNCTION maps a state (or a sequence of states) onto a REAL NUMBER describing the associated degree of happiness. · where goals give a binary distinction, utility gives a CONTINUOUS MEASURE, so the agent can compare outcomes · it handles the two cases goals cannot: CONFLICTING GOALS, where only some can be achieved — utility specifies the trade-off (speed vs safety) SEVERAL UNCERTAIN GOALS, none of which is certain — utility weighs importance against likelihood of success · under uncertainty a rational utility-based agent chooses the action that maximises the EXPECTED UTILITY of the outcomes: EU(a) = Σ P(outcome | a) × U(outcome) WORKED — one junction, three agents: the taxi can take a motorway (fast, small crash risk) or a slow safe road. REFLEX AGENT has no notion of destination; the question is unaskable GOAL-BASED AGENT both routes reach the destination, so both satisfy the goal; it has no basis for choosing, and will pick arbitrarily UTILITY-BASED compare expected utilities. Say the motorway saves 20 minutes but carries a 0.1% crash probability, and the utility of 20 minutes is +20 while a crash is −50,000: EU(motorway) = 0.999 × 20 + 0.001 × (−50,000) = 19.98 − 50 = −30.02 EU(slow road) = 0 → TAKE THE SLOW ROAD. And note that the answer flips if the crash utility is −10,000 instead: 0.999 × 20 + 0.001 × (−10,000) = 19.98 − 10 = +9.98 → take the motorway. THE UTILITY NUMBERS ARE THE POLICY. Choosing them is a value judgement the designer makes, not a fact the agent discovers — which is the same responsibility as choosing the performance measure. 5. THE LEARNING AGENT — orthogonal to the four above; any of them can be made to learn. FOUR COMPONENTS: LEARNING ELEMENT makes improvements PERFORMANCE ELEMENT selects external actions — this is the entire agent as described above CRITIC gives feedback on how the agent is doing against a fixed PERFORMANCE STANDARD, and tells the learning element what to change PROBLEM GENERATOR suggests EXPLORATORY actions that will lead to new and informative experiences THE CRITIC IS ESSENTIAL AND ITS STANDARD MUST BE EXTERNAL AND FIXED. If the agent could modify its own performance standard, it would learn to lower it — which is the reward- hacking failure from the agents topic, arriving from the inside. THE PROBLEM GENERATOR IS WHY A LEARNING AGENT DELIBERATELY DOES SUBOPTIMAL THINGS: exploring costs short-term performance and buys long-term knowledge, which is the exploration/exploitation trade-off.

THE SELECTION TABLE — the practical summary: USE A SIMPLE REFLEX AGENT WHEN the environment is fully observable, the correct action depends only on the current percept, and the rules are few → a thermostat, a spam filter on a single message, a collision-avoidance stop USE A MODEL-BASED AGENT WHEN the environment is partially observable, so decisions depend on what is no longer visible → lane changing, tracking a moving object, any system that must remember USE A GOAL-BASED AGENT WHEN the right action depends on a desired future state, and reaching it takes several steps → route planning, puzzle solving, robot navigation USE A UTILITY-BASED AGENT WHEN several outcomes satisfy the goal and they differ in quality, or goals conflict, or outcomes are uncertain → any real scheduling or resource-allocation problem, and essentially every deployed decision system ADD LEARNING WHEN the environment is unknown or changes, or hand-coding the knowledge is infeasible HOW THE AGENT REPRESENTS STATE — a distinction that cuts across all four structures and determines what the agent can reason about: ATOMIC REPRESENTATION each state is a black box with no internal structure. All the algorithm can do is compare two states for equality. → used by the basic search algorithms of ACtE0902 FACTORED REPRESENTATION a state is split into a fixed set of VARIABLES or ATTRIBUTES, each with a value. → used by constraint satisfaction, propositional logic, Bayesian networks and most machine learning STRUCTURED REPRESENTATION a state contains OBJECTS, each with attributes, and RELATIONSHIPS between them. → used by first-order logic, relational databases, knowledge graphs and natural language understanding THE PROGRESSION IS ONE OF EXPRESSIVENESS AGAINST COST: a more expressive representation can capture more compactly — one first-order sentence can say what would need a million propositional ones — but reasoning with it is harder. THIS TRADE-OFF RECURS THROUGHOUT THE SUBJECT, and it is the same expressiveness/tractability tension the knowledge representation section is built around.