1、AI as the Design of Agents,Tuomas Sandholm Carnegie Mellon University Computer Science Department,= a unifying view for the bag of techniques that AI encompasses,An agent and its environment,How to design an intelligent agent?,Definition: An agent perceives its environment via sensors and acts in th
2、at environment with its effectors.Hence, an agent gets percepts one at a time, and maps this percept sequence to actions (one action at a time)Properties: Autonomous Interacts with other agents plus the environment Reactive to the environment Pro-active (goal-directed),Examples of agents in differen
3、t types of applications,Examples of agents,Definition of ideal rational agent,Ideal Rational Agent: For each possible percept sequence, such an agent does whatever action is expected to maximize its performance measure, on the basis of the evidence provided by the percept sequence and whatever built
4、-in knowledge the agent has.,What do you think? Is this an acceptable definition?,Not looking left when crossing the street: If I dont see a car coming from the left, it is rational to cross the street?,No. Should also consider taking information gathering actions.,Agents strategy,Agents strategy is
5、 a mapping from percept sequence to action How to encode an agents strategy? Long list of what should be done for each possible percept sequence vs. shorter specification (e.g. algorithm),WARNING: Might not get what you ask for in the performance measure,Cleaning robot Pick up as much trash as possi
6、ble Vehicle route optimization Maximize utilizations = Driving fully loaded Capitalizing on oddities in tariff list = Renegotiation Dont include solution method in the criterion,agent = architecture + program,Physical agents vs. software agents (software agents = softbots),This course concentrates o
7、n the program,function SKELETON-AGENT (percept) returns actionstatic: memory, the agents memory of the worldmemory UPDATE-MEMORY(memory,percept)action CHOOSE-BEST-ACTION(memory)memory UPDATE-MEMORY(memory, action)return action,On each invocation, the agents memory is updated to reflect the new perce
8、pt, the best action is chosen, and the fact that the action was taken is also stored in the memory. The memory persists from one invocation to the next.,Skeleton agent,Input = Percept, not historyNOTE: Performance measure is not part of the agent,Examples of how the agent function can be implemented
9、,Table-driven agent Simple reflex agent Reflex agent with internal state Agent with explicit goals Utility-based agent,More sophisticated,function TABLE-DRIVEN-AGENT (percept) returns actionstatic: percepts, a sequence, initially emptytable, a table, indexed by percept sequences, initially fully spe
10、cifiedappend percept to the end of perceptsaction LOOKUP(percepts, table)return action,An agent based on a prespecified lookup table. It keeps track of percept sequence and just looks up the best action,1. Table-driven agent,ProblemsHuge number of possible percepts (consider an automated taxi with a
11、 camera as the sensor) = lookup table would be hugeTakes long time to build the tableNot adaptive to changes in the environment; requires entire table to be updated if changes occur,2. Simple reflex agent,Differs from the lookup table based agent is that the condition (that determines the action) is
12、 already higher-level interpretation of the percepts Percepts could be e.g. the pixels on the camera of the automated taxi,function SIMPLE-REFLEX-AGENT(percept) returns actionstatic: rules, a set of condition-action rulesstate INTERPRET-INPUT (percept)rule RULE-MATCH (state,rules)action RULE-ACTION
13、rulereturn action,A simple reflex agent works by finding a rule whose condition matches the current situation (as defined by the percept) and then doing the action associated with that rule.,First match. No further matches sought. Only one level of deduction.,Simple reflex agent,Table lookup of cond
14、ition-action pairs defining all possible condition-action rules necessary to interact in an environment e.g. if car-in-front-is-breaking then initiate breaking Problems Table is still too big to generate and to store (e.g. taxi) Takes long time to build the table No knowledge of non-perceptual parts
15、 of the current state Not adaptive to changes in the environment; requires entire table to be updated if changes occur Looping: Cant make actions conditional,3. Reflex agent with internal state,Reflex agent with internal state ,function REFLEX-AGENT-WITH-STATE (percept) returns actionstatic: state,
16、a description of the current world staterules, a set of condition-action rulesstate UPDATE-STATE (state, percept)rule RULE-MATCH (state, rules)action RULE-ACTION rulestate UPDATE-STATE (state, action)return action,A reflex agent with internal state works by finding a rule whose condition matches the
17、 current situation (as defined by the percept and the stored internal state) and then doing the action associated with that rule.,Encode “internal state of the world to remember the past as contained in earlier perceptsNeeded because sensors do no usually give the entire state of the world at each i
18、nput, so perception of the environment is captured over time. “State” used to encode different “world states” that generate the same immediate perceptRequires ability to represent change in the world with/without the agentone possibility is to represent just the latest state, but then cannot reason
19、about hypothetical courses of actionExample: Rodney Brooks Subsumption Architecture. Main idea: build complex intelligent robots by decomposing behaviors into a hierarchy of skills, each completely defining a complete percept-action cycle for one very specific task. For example, avoiding contact, wa
20、ndering, exploring, recognizing doorways, etc. Each behavior is modeled by a finite-state machine with a few states (though each state may correspond to a complex function or module). Behaviors are loosely-coupled, asynchronous interactions,Reflex agent with internal state ,4. Agent with explicit go
21、als,Agent with explicit goals ,Choose actions so as to achieve a (given or computed) goal = a description of desirable situations. e.g. where the taxi wants to goKeeping track of the current state is often not enough need to add goals to decide which situations are goodDeliberative instead of reacti
22、veMay have to consider long sequences of possible actions before deciding if goal is achieved involves considerations of the future, “what will happen if I do?” (search and planning)More flexible than reflex agent. (e.g. rain / new destination) In the reflex agent, the entire database of rules would
23、 have to be rewritten,5. Utility-based agent,Utility-based agent ,When there are multiple possible alternatives, how to decide which one is best?A goal specifies a crude destination between a happy and unhappy state, but often need a more general performance measure that describes “degree of happine
24、ss”Utility function U: State Reals indicating a measure of success or happiness when at a given stateAllows decisions comparing choice between conflicting goals, and choice between likelihood of success and importance of goal (if achievement is uncertain),Properties of environments,Properties of env
25、ironments,Accessible (observable) : The agents sensory apparatus gives it access to the complete state of the environmentDeterministic: The next state of the environment is completely determined by the current state and the actions selected by the agentSubjective non-determinism- Limited memory (pok
26、er)- Too complex environment to model directly (weather, dice)- InaccessibilityEpisodic: The agents experience is divided into independent “episodes,” each episode consisting of agent perceiving and then acting. Quality of action depends just on the episode itself, because subsequent episodes do not
27、 depend on what actions occur in previous episodes. Do not need to think ahead,Properties of environments ,Static: If the environment can change while the agent is deliberating, then the environment is dynamic; otherwise its static. Discrete: There are a limited number of distinct, clearly defined p
28、ercepts and actions we say that environment is discrete.,Dynamic,Need to worry about time,Need to observe while deliberating,procedure RUN-ENVIRONMENT (state, UPDATE-FN, agents, termination)inputs: state, the initial state of the environmentUPDATE-FN, function to modify the environmentagents, a set
29、of agentstermination, a predicate to test when we are donerepeatfor each agent in agents doPERCEPTagent GET-PERCEPT(agent,state)endfor each agent in agents doACTIONagent PROGRAMagent (PERCEPTagent)endstate UPDATE-FN(actions, agents, state)until termination (state),Running the agents and the environment,
