COMP30024 Artificial Intelligence
Week 2 Problem Sheet Solutions
• These are not unique, complete (and definitely not optimally pedagogical) solutions. there are other, likely better ways of deriving these results and the way you prefer is to some extent an aesthetic judgement.
• Students: If you want to attain any benefit from the problems you should make a genuine attempt at them before you see the solutions.
Copyright By PowCoder代写 加微信 powcoder
Comments/corrections are as always greatly appreciated by the teaching team.
1. [T], [∗] Introduce yourselves to the other students in the group.
Exercise left to the reader.
2. Agent behaviour/types [T] Decide whether each of the following statements is true or false. Support your answer with appropriate examples/counterexamples. Consider how the agent type influences your answer.
(a) Anagentthatsensesonlypartialinformationaboutthestatecannotbeperfectlyrational.
False – rationality refers to optimality of decisions according to some performance measure conditioned upon the evidence provided by the percept sequence, in addition to whatever prior knowledge the agent has.
(b) There exist task environments in which no pure reflex agent can behave rationally.
True – pure reflex agents cannot maintain a history of past actions/percepts, so any environment where optimality requires conditioning on the previous state(s) satisfies this criterion.
(c) Suppose an agent selects its action uniformly at random from the set of possible actions. There exists a deterministic task environment in which this agent is rational.
True – consider the situation where all actions taken yield the same reward.
(d) An agent which chooses the action with the highest expected value under the performance measure is superior to all other agents in the long run.
’Highest expected value’ was left deliberately ambiguous as a discussion point. If we assume this refers to maximization of the total cumulative performance measure in the future, then the agent is optimal by definition. If this instead refers to the immediate reward observed at each stage, choosing the action with the highest expected value at the current timestep is greedy, and may be suboptimal, as aficionados of dynamic programming can attest – sometimes it is necessary to sacrifice immediate reward for long- term optimality. The interested reader may wish to investigate the Bellman optimality principle, beyond the scope of the course.
(e) Every agent is rational in an unobservable environment.
False – it is possible to build in prior knowledge into an agent about acceptable behaviour in the absence of observations. An agent lacking this prior knowledge may take subop- timal actions in an unobservable environment.
3. Tabulation [T] Assume the agent function is represented as a table – for every possible percept sequence, we explicitly specify the appropriate action to take.
(a) Is tabulation of the agent function possible for continuous percepts?
No, but for most problems it suffices to discretize the input data to an appropriate level of granularity.
(b) Let P be the (finite) set of possible percepts, and T be the maximum length of a percept sequence. Find an upper bound on the total number of entries in this table in terms of |P| and T.
This problem reduces to enumerating all possible percept sequences – this provides an upper bound as percept sequences may be related to one another via symmetry. Each time step t introduces |P|t possible percept sequences, leading to a upper bound of Tt=1|P|t entries that must be tabulated in the lookup table.
(c) Do you think this is a good idea in general?
The branching factor of chess is estimated to be around |P| ∼ 35. After about 50 moves the size of the required table approaches the number of atoms in the observable universe – no physical agent in this universe will have the space to store the table.
4. Environment Properties [T] For each of the following activities, characterize the task en- vironment in terms of its properties: Multiple possible answers, depending on assumptions made.
(a) Playing soccer.
Partially observable, stochastic, sequential, dynamic, continuous, multi-agent.
(b) Shopping for used books on the internet.
Partially observable, deterministic, sequential, static, discrete, single agent. This can be multi-agent and dynamic if we buy books via auction, or dynamic if we purchase on a long enough scale that book offers change.
(c) Bidding on an item at an auction.
Fully observable, stochastic (assuming non-rational actors), sequential, static, discrete, multi-agent.
5. Agent Architectures [T] For each of the environments in Figure 1, determine what type of agent architecture is most appropriate.
Again here, the answers will depend on your assumptions, which you should clearly state.
• Medical diagnosis: utility-based (due to competing goals)
• Satellite image analysis: simple reflex agent (mainly pattern matching)
• Part-picking: goal-based (needs to reason about a sequence of actions that will achieve goal of holding desired part; other answers possible)
• Refinery controller: utility-based (no single goal state, instead there is one or more objectives to be maximised)
• English tutor: goal-based (goals correspond to concepts to be learned by the student, and there are many ways of teaching those concepts). Alternatively utility-based using some sort of metric of academic achievement.
6. Agent programs/functions
(a) Do agent functions exist which cannot be implemented by any agent program? If yes, give a counterexample.
Yes – if the agent function requires solving an undecidable problem – e.g. suppose the agent function required one to solve a Diophantine equation or decide whether an arbi- trary Turing machine halts. Then there is no agent program capable of implementing this agent function.
(b) Suppose we keep the agent program fixed but speed up the machine by a factor of two. Does this change the agent function? Will your answer change depending on the environment type?
Depends on the program and the environment. If the environment is dynamic, this speedup may allow the agent to act sooner to choose choosing different, better actions. For static environments the agent function is unchanged.
7. Non-determinism [∗] The vacuum environment introduced in Russell/Norvig, Chapter 2.1 was deterministic. in the previous exercise were deterministic. Discuss possible agent pro- grams for each of the following stochastic versions:
(a) Murphy’s law: 25% of the time, the Suck action fails to clean the floor if it is dirty and deposits dirt onto the floor if the floor is clean. How is your agent program affected if the dirt sensor gives the wrong answer 10% of the time?
The agent should continue sucking until it is satisfied with high probability that the square is clean. This probability can be quantified using the recursive posterior updates that will be the focus of Week 11 of the course. Note the tradeoff between sucking until the agent is satisfied that the current square is clean with high probability and moving
Chapter 2 Intelligent Agents
Agent Type
Medical diagnosis system
Satellite image analysis system
Part-picking robot
Refinery controller
Interactive English tutor
Performance Measure
Healthy patient, reduced costs
Correct categorization of objects, terrain
Percentage of parts in correct bins
Purity, yield, safety
Student’s score on test
Environment
Patient, hospital, staff
Orbiting satellite, downlink, weather
Conveyor belt with parts; bins
Refinery, raw materials, operators
Set of students, testing agency
Display of questions, tests, diagnoses, treatments
Display of scene categorization
Jointed arm and hand
Valves, pumps, heaters, stirrers, displays
Display of exercises, feedback, speech
Touchscreen/voice entry of symptoms and findings
High-resolution digital camera
Camera, tactile and joint angle sensors
Temperature, pressure, flow, chemical sensors
Keyboard entry, voice
Unobservable
Single-agent Multiagent
Single-agent vs. multiagent: The distinction between single-agent and multiagent en- vironments may seem simple enough. For example, an agent solving a crossword puzzle by itself is clearly in a single-agent environment, whereas an agent playing chess is in a two- agent environment. However, there are some subtle issues. First, we have described how an entity may be viewed as an agent, but we have not explained which entities must be viewed as agents. Does an agent A (the taxi driver for example) have to treat an object B (another vehicle) as an agent, or can it be treated merely as an object behaving according to the laws of physics, analogous to waves at the beach or leaves blowing in the wind? The key distinction is whether B’s behavior is best described as maximizing a performance measure whose value depends on agent A’s behavior.
Figure 2.5 Examples of agent types and their PEAS descriptions.
Figure 1: Examples of agent types and associated environemnts.
pteorfocrlmeaancoetmhera,supreo.tFenultliyalolbysedrivratbyleseqnuvairoensm-enthtsearweaciotninvegniteinmtebeactauesaecthesaqgueanrtenemeday need to not maintain any internal state to keep track of the world. An environment might be partially
be determined by some heuristic method.
observable because of noisy and inaccurate sensors or because parts of the state are simply
(b) Small children: At each time step, each clean square has a small chance of becoming
missing from the sensor data—for example, a vacuum agent with only a local dirt sensor
dirty. Can you come up with a rational agent design for this case?
cannot tell whether there is dirt in other squares, and an automated taxi cannot see what other
drivers are thinking. If the agent has no sensors at all then the environment is unobserv- aablseq.uOanremisigdhitrthyinikntchraetaisnesumchocnaosetsonthiecalglyenwt’sitphligthteistihmopeelseisnsc,ebuit, awsawseladsistcucslesained, so the Crhaatpiotenra4l,sthtreaatgeegnyt’sisg,otaolscmoanydsuticltlbaeTacrhaiveveallbilneg,sSoamletsimeasnwoivtherceartlalinsqtyu.ares.
In this case, the agent should keep touring the squares indefinitely. The probability that
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com