CS代考 Overview of tutorials – cscodehelp代写
Overview of tutorials
COSC1127/1125 Artificial Intelligence
School of Computing Technologies Semester 2, 2021
Prof. ̃a
Tutorial No. 1 Introduction to Search
Unlike the projects, tutorial sheets will cover the conceptual and theoretical parts of the course. Tutorials will be directly related to the two Take Home Exercises. In addition, they will provide the foundational learning to under- stand and execute your solutions to the practical projects. In other words, tutorials are VERY IMPORTANT and you should not, you must not, disregard them. We expect you to execute every single tutorial sheet to completion.
You are allowed (and indeed, encouraged) to work together in groups to complete the worksheets that are provided for you. Always keep in mind, though, that seeing an understanding how someone solved a problem does not imply you know the content to the expected level, so that you can solve similar problems by yourself.
During 1hr tutorial sessions, the tutor will showcase/demonstrate some of the questions during tutorial sessions. The tutor will also answer questions and provide advice, but it is expected that you have attempted to solve the problems on your own, or together with your fellow students.
Some solutions to each tutorial sheet will be distributed in the following week of the tutorial of question. By then you should have finished the tutorial sheet. The aim of the solution template we provide is not that you simply “have them” for “collection” purposes. If you see a solution without having given a fair try to the questions, then the aim of the tutorial sheet was not achieved. The objective of the solution is for you to contrast against your tries/solutions.
The course will use the famous Russell & Norving ”Artificial Intelligence: A Modern Approach”. You will have online access to the book via RMIT Library here.
So, let us start with the first tute sheet! GOOD LUCK!
PART1: Videos&Discussion……………………………………………………………… (a) Open Discussion: What is Artificial Intelligence?
(b) Watch this videos:
i. Holy Grail of AI: https://youtu.be/tlS5Y2vm02c
ii. Humans Need Not Apply: https://youtu.be/7Pq-S557XQU
iii. Artificial Intelligence early history: https://youtu.be/8_fOmPzzm-o iv. The long-term future of AI: https://youtu.be/CK5w3wh4G-M
PART2: Agents………………………………………………………………………….. These questions can be answered by looking at Chapter 2 in the book (or doing some research on the web…)
(a) Define in your own words the following terms: i. Agent
1
COSC1127/1125 – AI
Tutorial 1: Introduction to Search
Page 2 of 7
Solution: An entity that perceives and acts; or, one that can be viewed as perceiving and acting. Essentially any object qualifies; the key point is the way the object implements an agent function. (Note: some authors restrict the term to programs that operate on behalf of a human, or to programs that can cause some or all of their code to run on other machines on a network, as in mobile agents.)
ii. Agent function
iii. Agent program
iv. Rationality
v. Autonomy
vi. Reflex agent
Solution: An agent whose action depends only on the current percept. vii. Model-based agent
viii. Goal-based agent
Solution: An agent that selects actions that it believes will achieve explicitly represented goals. ix. Utility-based agent
x. Learning agent
Solution: An agent whose behavior improves over time based on its experience. (b) Explain the concept of performance measure in intelligent agents.
(c) Explain the concept of a utility function in intelligent agents.
Solution: A utility function is used by an agent to evaluate how desirable states or histories are.
(d) What is the difference between the performance measure and utility function?
(e) Compare the following task environments:
Solution: A function that specifies the agent’s action in response to every possible percept se- quence.
Solution: A program which, combined with a machine architecture, implements an agent function. In our simple designs, the program takes a new percept on each invocation and returns an action.
Solution: A property of agents that choose actions that maximize their expected utility, given the percepts to date.
Solution: A property of agents whose behavior is determined by their own experience rather than solely by their initial programming.
Solution: An agent whose action is derived directly from an internal model of the current world state that is updated over time.
Solution: An agent that selects actions that it believes will maximize the expected utility of the outcopme state.
Solution: Performance measure is the criterion for ’success’ and is objective: it is used by an outside observer to evaluate how successful an agent is.
Solution: In our framework, the utility function may not be the same as the performance measure; furthermore, an agent may have no explicit utility function at all, whereas there is always a performance measure.
RMITAI2021(Semester2)-SebastianSardin ̃a Exercise2continuesonthenextpage…
COSC1127/1125 – AI Tutorial 1: Introduction to Search Page 3 of 7
i. Fully observable vs. partially observable ii. Single-agent vs. multi-agent
iii. Deterministic vs. nondeterministic vs. stochastic iv. Episodic vs. sequential
v. Static vs. dynamic
vi. Discrete vs. continuous
vii. Know vs. unknown
Solution: Find the comparison of the above task environments in the book section 2.3.2
PART3: Search…………………………………………………………………………..
These questions can be answered by looking at Chapter 3 in the book (or doing some research on the web…)
(a) Define in your own words the following terms: state, state space, search tree, search node, goal, action, successor function, and branching factor.
Solution: A state is a situation that an agent can find itself in. We distinguish two types of states: world states (the actual concrete situations in the real world) and representational states (the abstract descriptions of the real world that are used by the agent in deliberating about what to do).
A state space is a graph whose nodes are the set of all states, and whose links are actions that transform one state into another.
A search tree is a tree (a graph with no undirected loops) in which the root node is the start state and the set of children for each node consists of the states reachable by taking any action.
A search node is a node in the search tree.
A goal is a state that the agent is trying to reach.
An action is something that the agent can choose to do.
A successor function described the agent’s options: given a state, it returns a set of (action, state) pairs, where each state is the state reachable by taking the action.
The branching factor in a search tree is the number of actions available to the agent.
(b) What’s the difference between a world state, a state description, and a search node? Why is this distinction useful?
Solution: A world state is how reality is or could be. In one world state we’re in Arad, in another we’re in Bucharest. The world state also includes which street we’re on, what’s currently on the radio, and the price of tea in China. A state description is an agent’s internal description of a world state. Examples are In(Arad) and In(Bucharest). These descriptions are necessarily approximate, recording only some aspect of the state.
We need to distinguish between world states and state descriptions because state description are lossy abstractions of the world state, because the agent could be mistaken about how the world is, because the agent might want to imagine things that aren’t true but it could make true, and because the agent cares about the world not its internal representation of it.
Search nodes are generated during search, representing a state the search process knows how to reach. They contain additional information aside from the state description, such as the sequence of actions used to reach this state. This distinction is useful because we may generate different search nodes which have the same state, and because search nodes contain more information than a state representation.
(c) Consider this problem: We have one 3 litre jug, one 5 litre jug and an unlimited supply of water. The goal is to be able to drink exactly one litre. Either jug can be emptied or filled, or poured into the other.
For this problem give:
RMITAI2021(Semester2)-SebastianSardin ̃a Exercise3continuesonthenextpage…
COSC1127/1125 – AI Tutorial 1: Introduction to Search Page 4 of 7
i. An appropriate data structure for representing a state.
ii. The initial state.
Solution: The initial state is (0, 0).
iii. All the final goal state(s).
iv. A specification of the operators (or actions) which includes the preconditions that must be satisfied before the operator can be used and the new state generated.
Solution: Therepresentationofthestatecanbesimply:(nL,nR),wherenListhenumberoflitres in the 3 litre jug, and nR is number of litres in the 5 litre jug.
Solution: The goal states are (1, n) or (n, 1), for any number n, as we just need to get some jug with exactly one litre.
Solution: (Note: this is a partial solution) Operators could be (using FOL sentences):
F ill(X )
Action: fill jug X
Precondition: jug X is not full
State generated: jug X is full – (3, nR) or (nL, 5)
Pour(X,Y)
Action: pour jug X into jug Y until either X is empty or Y is full Precondition: jug X is not empty and jug Y is not full
State Generated: (nL′, nR′) where,
• R→L:nL′ =min(nL+nR,3)andnR′ =max(0,nl+nR−3),or • L→R:nR′ =min(nR+nL,5)andnL′ =max(0,nL+nR−5).
Empty(X)
Action: …. Precondition: …. Stategenerated: ….
Here, the preconditions are not entirely necessary. For example, emptying an empty jug, results in the same state as emptying a full jug and in this case, including preconditions only serves to reduce the size of the search space by removing pointless operations.
v. Draw the full state space.
Solution:
RMITAI2021(Semester2)-SebastianSardin ̃a Exercise3continuesonthenextpage…
COSC1127/1125 – AI Tutorial 1: Introduction to Search Page 5 of 7
2,4 3,3 1,5 1,0
2,3 0,3 0,1 1,2
3,0 0,0 0,5 3,1
2,2 1,3
2,0 3,5 3,2 0,4
1,1
2,1 3,4
0,2 2,5
State transition labels:
FX fill jug X
EX empty jug X
PXY pourjugXintojugY
Note: For clarity, not all state transition labels are not shown on this diagram, usually you should show all state transition labels above all arcs. Observe also that states that cannot be reached from the initial state, such as (1,4), are still part of the full state space. If you are not going to show inaccessible states, you should explicitly state so.
1,4
vi. What is the solution to the problem.
Solution: (0,0) → (3,0) → (0,3) → (3,3) → (1,5) → (1,0)
vii. How did you find that solution? Would a computer be able to find it the same way? Explain either
way. If not, how would you make an algorithm to find a solution given the search space?
Solution: If you just found it by “matching” a path connecting (0, 0) to any state (1, n) or (n, 1), then it will probably be difficult to do with an algorithm, as it is not systematic approach. An algo- rithm would have to “visit” nodes in a systematic, regular, complete, and hopefully non-redundant manner.
Check Jonathon’s nice Python solution jug problem.py via a simple random search. What would you change there to make it non-random and systematic? How would you change it so as not to need a depth bound?
(d) Does a finite state space always lead to a finite search tree? How about a finite state space that is a tree?
(e) Consider the problem of getting from Arad to Bucharest in Romania. For this problem give: i. Search state descriptions.
Solution: Finite state can yield an infinite state if there are loops in the state space; if the state space is a tree then there are no loops and the search tree will be finite
RMITAI2021(Semester2)-SebastianSardin ̃a Exercise3continuesonthenextpage…
ER
FL
PRL
COSC1127/1125 – AI Tutorial 1: Introduction to Search Page 6 of 7
Solution: A possible search state description could be (⟨city⟩, g(n)), where g(n) is the total path cost to that node. (Note that the real search state in a search algorithm will also contain the link to the parent of the state node, but we omit it here.)
ii. Initial State.
Solution: (Arad,0) iii. Final goal search states.
Solution: (Bucharest, g(n)), where g(n) is total path cost from Arad to Bucharest. iv. Operators (or actions).
Solution: Only one operator exists (using FOL sentences):
Go(X,Y)
Action: travel from city X to city Y
Precondition: currently in city X and city X has an edge connecting it to city Y State generated: in city Y – (Y, g′(n)), where g′(n) = g(n) + distance(X, Y ).
The reason Go(X) is not used, is that it does not take into account the fact that we must travel between connected cities.
Using your representation, how would you build a “search tree” starting from state “Arad”?
(f) Michelle is a turtle owner and model train enthusiast. After a long day studying for her AI test, she went to check on her turtle, Fredrick, and was surprised to find him missing. She looked around her apartment and spotted him sitting on top of her model train as it made its way around the room. The layout of her apartment is shown below (note: Frederick’s cage is also located in the bottom left square). In each timestep Michelle can move one square up/down/left/right, and Frederick will ride the train one square anticlockwise along the track. If Michelle and Frederick are in the same square, she can pick him up. Can you help her to recover Frederick and return him to his enclosure?
RMITAI2021(Semester2)-SebastianSardin ̃a Exercise3continuesonthenextpage…
COSC1127/1125 – AI Tutorial 1: Introduction to Search Page 7 of 7
For this problem give:
i. An appropriate data structure for representing a state.
Solution: Your turn!
ii. The initial state.
Solution: Theinitialstateis(0,0,4,2,0).
iii. All the final goal state(s).
Solution: Your turn!
iv. A specification of the operators (or actions) which includes the preconditions that must be satisfied
before the operator can be used and the new state generated.
Solution: Your turn!
v. How many possible states are there?
vi. What is a solution to the problem?
(g) WhyissearchanimportanttechniqueinAIandCS?Whenwouldyouusesearchandwhenyouwouldn’t? Give concrete examples and reasons.
Solution: Your turn!
(h) You say more? Lots of cool exercise in RN book, chapter 3….
End of tutorial worksheet
Solution: Your turn! Start by splitting the state space into two: either Alice is carrying Frederick or she is not.
Solution: (Note: this is a partial solution)
Actions: ….
States sequence: (0,0,4,2,0) → (0,1,4,3,0) → (0,2,4,4,0) → (0,3,3,4,0) → (0,4,2,4,0) → (1,4,1,4,0) → …. → (0,1,0,1,1)
→ (0,0,0,0,1)
RMIT AI 2021 (Semester 2) – ̃a
