KBAI CS 7637/4635, OMS/PE CS 7637 Ashok Goel
Spring 2015
Mid-Term Examination
Assigned Monday, February 23rd, 2015
Due Sunday March 1, 2015, by 11:59 pm AOE.
This is a take-home examination.
This means that you can consult any book, video, website, etc.
Indeed, some questions may require more than a little thinking; some may also require a little research.
However, your answers must be your own work: you may not consult any person.
Please answer any 5 of the 7 questions below. Please indicate at the top of your submission which 5 questions you have chosen to answer. Please also indicate where each answer begins very clearly alongside it.
Note that your entire exam may not be graded by the same grader. Feel free to refer back to your earlier answers, but make it clear when you are doing so as the person grading a particular question may not have otherwise read the earlier answer.
All questions carry equal weight.
All seven questions are based on the following short story.
It is 2030 AD now and robots are everywhere. Many of the robots are intelligent, some with human-level intelligence, and a few, it is said, even have human-like intelligence. A handful of robots of the new RC900 series, the gossip has it, are also creative, with a mischievous sense of humor, though apparently few humans have actually met one of them yet.
The Thorne family looked into the room again through its one small window. They had just moved into the house and were still unfamiliar with some of the provisions left by the previous owner. And, there it was, the robot, clearly a new buy, but small in size, sitting by itself in a little corner, almost as if in repose. The room itself was quite barren, save a table in a corner and electrical wires hanging from the middle of the ceiling where a fan once used to hang.
The Thorne family soon got tired of silently watching the robot. “Why isn’t he moving?” asked Doug, the 7 year old.
“He doesn’t even talk!” added Sally Jr. helpfully, who at 9, had the advantage of more than two years of experience.
“May be it is not working any more” said Sally Sr.
But Duke was not so sure: just once he thought the robot’s eyes had moved and met his own. Or was he just imagining it? He did not share the thought with the children. No point exciting the family.
“Come, let us have dinner. The robot will still be here” implored Sally Sr. and the Thorne family followed her away.
The robot’s gaze followed the retreating family for just a moment. Then it got up, moved the table to the center of the room, climbed the table, reached the electrical wires hanging from the ceiling, charged itself to full, climbed down from the table, moved it right back to where it was originally, went to its corner and slid back into its former pose.
The Thorne family did not know it yet, but they soon will be among the first humans to meet a robot of the RC900 series, intelligent, creative, impish. The lucky ones!
The questions on this test are intended to build a design of the robot’s mind that produces the behaviors observed in the story.
All questions use the representation of propositional logic.
Example1:
Sentence in English: The robot climbed the table. Translation into propositional logic: Climb-Up (Robot, Table)
Example 2:
Sentence in English: The table is in a corner of the room. Translation into propositional logic: Location (Table, Room_Corner2)
Thus, we can specify the percepts, the actions, the initial and goal states, in this microworld as well-formed formulae in propositional logic. If you have not watched the video on logic or completed the corresponding required reading, you may want to do so now before you start the exam. Please build on propositional logic as the basic knowledge representation in answering all questions.
Question 1: Specify the STRIPS planning operators for this microworld: Walk, Push_Table, Climb-Up, Climb_Down, Grasp_Wire, Charge. Here is an example:
Climb_Up:
Precondition: Location (Robot, On_Floor) Postcondition: Location (Robot, Next_to_Wires)
Question 2: Now consider a subset of the planning problem: in the initial state the robot is in one corner and the table is in another corner of the room; in the goal state robot is charged (and we don’t care about the final location of the robot or the table – the planning stops once the robot is charged).
Show how a STRIPS like planner can form a plan to achieve the above goal.
Question 3: Rule-based reasoning is another method the robot could have used to address this situation. Invent rules for this microworld. Here is an example in English (you want to use propositional logic in your answer):
Rule: If the Electrical wire is too high to reach and a Table is in a corner, Then Push the Table to beneath the wires and Climb on the Table.
Given the rules such as the one shown above, show how rule-based reasoning would address Q2.
Question 4: Case-based reasoning is yet another method for explaining the behavior of the robot. Invent the case for addressing Q2. You may build on your answer to Q2 to compile the case. Show its contents and indices.
Now given the above case in robot’s memory, show how given the new situation of the full planning problem (the robot is not only charged, but also the robot and the table are in their old corners), the robot retrieves and adapts the old case to address Q2.
Question 5: Suppose that one of the various rules in your answer to Q3 is missing so that the robot cannot use rule-based reasoning. Modify your answer to Q3 to show how this will lead to an impasse.
Now invent a case from which the missing rule can be learned and show how the rule-based reasoner can complete its reasoning.
Question 6: Let us suppose that the robot did not initially have the concept of a Table. However, its previous owner taught the concept by giving some examples one at a time in the order shown here:
Positive Example: (Table (Top Flat)
(Legs 4) (Material Wood))
Negative Example: (Table (Top Flat)
(Legs 3) (Material Wood))
Positive Example: (Table (Top Flat)
(Legs 4) (Material Metal))
Let us suppose that the robot has background knowledge that wood and metal are both solid materials. Invent generalization and specialization heuristics for incremental concept learning this domain.
Now show how the robot will learn the concept of a table from these examples.
Question 7: Now suppose that the robot does not have the knowledge required by the above questions. Thus, it doesn’t have the cases or the rules or even the STRIPS planning technique. How might the robot then accomplish the goal of Q2? Illustrate. (Hint: if the robot does not have access to knowledge-based methods, it may resort to general-purpose methods such as Generate and Test.)