微信客服：xiaoxionga100
微信客服：ITCS521
CS6360-cs6360 advanced ai代写
时间：2023-02-13
CS6360课程是一门关于教育技术的课程，旨在帮助学生了解如何利用技术来提高教育效果。课程将涵盖使用教育技术的各种方法，包括在线学习平台、智能教学软件和移动学习应用程序。学生还将学习如何评估和设计有效的教育技术方案，以满足学生的不同需求和学习风格。通过这门课程，学生将获得使用教育技术提高教育效果的实践知识和技能。
G. Biswas CS 6360 Advanced AI (Spring 2023) Max Points: 100
HW 2
Due: February 15, 2023 (at midnight)
General Instructions:
If anything is ambiguous or unclear….
1. Discuss possible interpretations with your TA and the instructor
2. Make assumptions, state them explicitly, and then use them to work out the problem
3. Send e-mail to your TA or instructor if you need additional clarifications.
Remember you can have general discussions with your classmates to understand the
problem, but you are required to work out the solutions on your own. All submitted work must
be your own. Please refer back to the Honor code to ensure you do not violate it.
Submissions must be electronic, as pdf or word files, and be made through Brightspace.
1. GraphPlan (25 points)
(a) Consider the problem of putting on one’s shoes and socks, as discussed in class. Generate the
Planning Graph for this algorithm. Apply the backward search algorithm to the graph and
show the solution obtained. From the planning graph compute the total number of valid
solutions for the problem.
(b) GraphPlan can backtrack during its second phase while searching backwards from the goals
through the planning graph. Explain, in words and with a simple example, why GraphPlan
needs to backtrack in its backwards search.
(c) If GraphPlan cannot find a solution during the backwards search, does this mean that the
problem is not solvable? If so, explain why. If not, explain what GraphPlan can do to find a
solution in such cases.
2. Nonlinear Planners. (25 points)
(a) Consider a planning problem in which the objective is to interchange the values of two variables
1 and 2.
Initial state: 0 = {(1, 3),(2, 5), (3, 0)}.
Goal state: = {(1, 5), (2, 3)}.
Available operator (action): (,,,) :(, ),(,) : ¬(, ),(,)
The figure below shows a partial plan generated by the POP algorithm.
(i) How many different threats are there?
(ii) How many children (immediate successors) would this partial plan have?
(iii) How many different solution plans can be reached from this partial plan?
(iv) How many different nonredundant solution plans can be reached from this partial plan?
(v) If we start the POP algorithm running from this plan can it ever find any redundant
solutions?
(vi) Trace the operation of the POP algorithm starting from this plan, along whichever
execution trace finds the solution that has the smallest number of actions.
3. Hierarchical Task Network (HTN) ( )
Consider the following “painting” problem
We have a can of red paint (1) and a can of blue paint (2)), two paint brushes (1, 2) and four
unpainted blocks (1, 2,2,4). We want to paint 1 and 2 red, and 3 and 4 blue.
The classical formulation of the problem is shown below:
0 = {(1), (2), (1, ), (2, ),ℎ(1),ℎ(2),
(1),(2),(1),(2),(3),(4),
(1), (2),(3),(4)}
= {(1, ), (2, ), (3,), (4,)}
− ℎ(, ,)
: ℎ(), (), (,)
: ¬(), (,)
(, ,)
: (), ℎ(), (,)
: ¬(), (,), ¬(,)
(a) In the paint operator, what is the purpose of the effect ¬(,)?
Convert the “painting” problem above into a total-order STN (Simplified Task Network)
problem.
Let’s add the following atoms to the initial state:
(1, ), (2, ),(3,), (4,)
The initial task network is = < 1(),1(),1(),1() >. The
operators are unchanged but there is one method:
ℎ1(, , ,)
: 1()
: − (,)
: (, , ), (, ,)
(b) How many different possible solutions are there?
(c) How many method and operator applications will a depth-first implementation of TFD (Total-
order Forward Decomposition) do in the best case? In the worst case?
(d) Can the domain description be modified to make the worst case more efficient? Show how
and explain.
(e) To introduce partial ordering into the planning problem, suppose we redefine the initial task
network to be = ({1,2,3,4},∅), where = (), 1 ≤ ≤ 4.. What problem
occurs when we do this, and how can it be fixed?
4. Monte Carlo Tree Search ( ).
Explain the Monte Carlo Rapid Action Value Estimation (MC-RAVE) algorithm clearly in your
own words, but referring to the paper by Gelly and Silver (2011). (You may refer to other sources
too, but if you do, please acknowledge the references).
Be sure to clearly explain the All-moves-as-First (AMAF) heuristic and what role it plays in
enhancing the selection step of the MCTS algorithm.
Also, clearly explain RAVE’s approach to generalizing over subtrees (d) Is there is a unique
solution at which this minimum is realized?
HW 2
Due: February 15, 2023 (at midnight)
General Instructions:
If anything is ambiguous or unclear….
1. Discuss possible interpretations with your TA and the instructor
2. Make assumptions, state them explicitly, and then use them to work out the problem
3. Send e-mail to your TA or instructor if you need additional clarifications.
Remember you can have general discussions with your classmates to understand the
problem, but you are required to work out the solutions on your own. All submitted work must
be your own. Please refer back to the Honor code to ensure you do not violate it.
Submissions must be electronic, as pdf or word files, and be made through Brightspace.
1. GraphPlan (25 points)
(a) Consider the problem of putting on one’s shoes and socks, as discussed in class. Generate the
Planning Graph for this algorithm. Apply the backward search algorithm to the graph and
show the solution obtained. From the planning graph compute the total number of valid
solutions for the problem.
(b) GraphPlan can backtrack during its second phase while searching backwards from the goals
through the planning graph. Explain, in words and with a simple example, why GraphPlan
needs to backtrack in its backwards search.
(c) If GraphPlan cannot find a solution during the backwards search, does this mean that the
problem is not solvable? If so, explain why. If not, explain what GraphPlan can do to find a
solution in such cases.
2. Nonlinear Planners. (25 points)
(a) Consider a planning problem in which the objective is to interchange the values of two variables
1 and 2.
Initial state: 0 = {(1, 3),(2, 5), (3, 0)}.
Goal state: = {(1, 5), (2, 3)}.
Available operator (action): (,,,) :(, ),(,) : ¬(, ),(,)
The figure below shows a partial plan generated by the POP algorithm.
(i) How many different threats are there?
(ii) How many children (immediate successors) would this partial plan have?
(iii) How many different solution plans can be reached from this partial plan?
(iv) How many different nonredundant solution plans can be reached from this partial plan?
(v) If we start the POP algorithm running from this plan can it ever find any redundant
solutions?
(vi) Trace the operation of the POP algorithm starting from this plan, along whichever
execution trace finds the solution that has the smallest number of actions.
3. Hierarchical Task Network (HTN) ( )
Consider the following “painting” problem
We have a can of red paint (1) and a can of blue paint (2)), two paint brushes (1, 2) and four
unpainted blocks (1, 2,2,4). We want to paint 1 and 2 red, and 3 and 4 blue.
The classical formulation of the problem is shown below:
0 = {(1), (2), (1, ), (2, ),ℎ(1),ℎ(2),
(1),(2),(1),(2),(3),(4),
(1), (2),(3),(4)}
= {(1, ), (2, ), (3,), (4,)}
− ℎ(, ,)
: ℎ(), (), (,)
: ¬(), (,)
(, ,)
: (), ℎ(), (,)
: ¬(), (,), ¬(,)
(a) In the paint operator, what is the purpose of the effect ¬(,)?
Convert the “painting” problem above into a total-order STN (Simplified Task Network)
problem.
Let’s add the following atoms to the initial state:
(1, ), (2, ),(3,), (4,)
The initial task network is = < 1(),1(),1(),1() >. The
operators are unchanged but there is one method:
ℎ1(, , ,)
: 1()
: − (,)
: (, , ), (, ,)
(b) How many different possible solutions are there?
(c) How many method and operator applications will a depth-first implementation of TFD (Total-
order Forward Decomposition) do in the best case? In the worst case?
(d) Can the domain description be modified to make the worst case more efficient? Show how
and explain.
(e) To introduce partial ordering into the planning problem, suppose we redefine the initial task
network to be = ({1,2,3,4},∅), where = (), 1 ≤ ≤ 4.. What problem
occurs when we do this, and how can it be fixed?
4. Monte Carlo Tree Search ( ).
Explain the Monte Carlo Rapid Action Value Estimation (MC-RAVE) algorithm clearly in your
own words, but referring to the paper by Gelly and Silver (2011). (You may refer to other sources
too, but if you do, please acknowledge the references).
Be sure to clearly explain the All-moves-as-First (AMAF) heuristic and what role it plays in
enhancing the selection step of the MCTS algorithm.
Also, clearly explain RAVE’s approach to generalizing over subtrees (d) Is there is a unique
solution at which this minimum is realized?
