Coursework for COMP5450M Knowledge Representation and Reasoning
Prolog Knowledge Base & Winograd Challenge
Due 10am, Friday 6th December, 2019
This coursework counts for 25% of the total marks for this module.
You may do this coursework in pairs.
Part A: Creating Prolog Knowledge Base
For this part of the assignment you will create a Knowledge Base (KB) formulated as a Prolog program. As a starting point, you are given the program brandons kb.pl, which contains an example knowledge base (expressed as a set of facts and a set of inference rules) as well as a simple but quite powerful inference mechanism. You can get to it via the following url:
https://swish.swi-prolog.org/p/brandons_kb.pl
You should examine the program and run it in SWISH (some other Prolog), before attempting the questions. In order to modify the code you need to copy it using the fork option in the SWISH “Save new version” dialogue, that you get to by choosing “Save …” on the drop down “File” menu. You should rename your version to username kb.pl.
1. Initial Experimentation
This question involves making some small extensions to the given KB. However, your answers to this part should be written in your hard-copy report submission, not as a program file (code submission is only required for Q2).
(a) Specify a rule which enforces the condition: “Cats hate all dogs except puppies”. (Ensure that your rule gives the expected inferences.) [2 marks]
(b) Specify a relational composition rule that will enable the implied fact
[rex, is grandfather of, champ] to be inferred from the KB. [2 marks]
(c) A programmer is considering adding the following “genesis” rule to the KB:
rule( genesis, [[X, is, dog]] ==> [fatherof(X), is, dog] ).
Add this rule to the KB and run the inference mechanism, before answering these questions:
i. What is the meaning/purpose of this rule? [2 marks] ii. Explain what happens when the inference system is run with this rule present and why it could be problematic. [2 marks]
(d) Consider the function of the weak negation operator + that can be applied to premisses of a rule. A weakly negated premiss takes the form +[r, … ] and means that the rule can only be applied if the fact [r, … ] is not in the database. This can be useful but can lead to unforseen behaviour of the inference system when rule are reordered or further rules are added. Explain how this can happen. [2 marks]
1
2. Making your own Knowledge Base
To answer this question you must replace the simple example facts and rules with a more substantial KB of your own devising (you will probably want to keep the ‘logic’ rules for subclass reasoning).
Preparation: You must chose a domain for your KB. This should be focused enough so that it has a distinctive vocabulary of key concepts, relations and specific facts; but also substantial enough that moderately complex inference rules are required to draw relevant and interesting conclusions. I suggest you do a bit of experimentation with adding new information to the current KB before deciding on the domain your want to work on. Feel free to ask whether the domain seems suitable. Most domains should be fine, but I might possibly suggest narrowing or widening the domain.
Your answer to this question will be in the form of a submission of the actual code of your modified username kb.pl file. This code should be pasted into your hard-copy report and also submitted as a separate file via the VLE.
The mark allocation for your KB will be divided up as follows:
(a) The fact predicates. Your fact predicates should involve all key properties and relations of the domain. The relevant concept hierarchy should be specified via the subclass relation, so that all subclass relations are either directly asserted or deriv- able by the inference mechanism. A selection of significant and/or illustrative facts concerning specific entities should also be given. [5 marks]
(b) The rule predicates. Within the restricted scope of your chosen domain and the limited time available, you should aim to give inference rules that are as comprehensive as possible. Generally applicable rules are preferable to those that are very specific. More credit will be given for diversity of rules than for large numbers of very similar
rules. [5 marks]
3. Discussion of your KB
In your hard-copy report answer the following questions:
(a) Write an overview of your KB in about 200 words. This should describe the scope of the domain and briefly discuss the power and limitations of the inference rules you have specified. [4 marks]
(b) Pick out what you consider to be two of the most interesting inferences that are gener- ated by your system. Choose cases such that each illustrates a different aspect of your rule system. In each case explain the rules that are used to generate the inference. (3
marks each)
[6 marks]
2
Part B: Solving a Planning Problem using Prolog
For this question, you will complete the coding of a Prolog program, which uses Prolog’s search capabilities to find the solution to a complex river crossing puzzle.
Preliminaries
As a starting point for answering this question, three program files are provided on the SWISH Prolog system. These are:
• bb planner.pl https://swish.swi-prolog.org/p/bb_planner.pl This Prolog program implements a simple breadth-first planner program.
• Several examples of using bb planner are provided:
– A coin payment problem: https://swish.swi-prolog.org/p/bb_coin_payment.pl – A measuring jugs problem: https://swish.swi-prolog.org/p/bb_jugs.pl
– An arithmetic challenge: https://swish.swi-prolog.org/p/bb_countdown.pl
• bb river crossing template.pl https://swish.swi-prolog.org/p/bb_river_crossing_template.pl
This is a template for you answer file. You should copy it by selecting “Save” from the File menu. Then rename it by entering a new name, which should be username frog+toad.pl where username is your actual University of Leeds username. Then press the ‘Fork’ button on the right of the name entry box. Then press the ‘Fork Program’ button at the bottom of the dialogue window.
The Puzzle
A family consisting of father, mother, two girls and two boys are travelling together with a po- liceman and a thief. The group are on one side of a river, which they need to cross. Fortunately, there is a ferry boat (on the same side of the river as the group) which they can use to get across.
Unfortunately, the family are somewhat dysfunctional. The father always argues with either of the daughters, unless the mother is present; and the mother always argues with either of the sons, unless the father is present. And of course the thief needs to be kept an eye on by the policeman.
In precise terms, the ferry boat can only be used in accordance with the following conditions:
1. The ferry boat can carry no more than 2 people. It can cross with either one or two people on board.
2. Only the adults (mother, father, policeman and thief) can operate the ferry boat, so there must be at least one adult on the boat for every river crossing.
3. The father cannot be left with either or both of the daughters without the mother.
4. The mother cannot be left with either or both of the boys without the father.
5. The thief cannot be left with any family members unless the policeman is also present. (The thief can be completely alone.)
To solve this problem you need to find a series of crossing actions which will transfer all people in the group from one side of the river to the other.
An interactive animation of the puzzle can be found at the following web site, so you may wish to try solving the puzzle yourself:
https://www.pedagonet.com/Fun/flashgame185.htm
Warning: It’s pretty difficult!
3
To answer this coursework question, you must use Prolog to solve this puzzle. To solve the problem you will need to define the following predicates and thereby create a program that can generate a solution to the puzzle:
• initial state/1 — You need to add a fact of the form initial state( term ) asserting that term is a representation of the initial state. [1 mark]
• goal state/1 — You also need to specify the goal state, using the same style of representation you used for the initial state. [1 mark]
• equivalent states/2 — you need to define a binary predicate that is true when its arguments are representations of the same state. If all states have a unique representation, you can just define this as holding when the state representations match exactly.
• transition/2 and legal state/1 — You need to specify a predicate transition( S1, S2 ) which is true when state S2 can be reached directly from state S1 by carrying out some possible action. You may specify a further filter on possible transitions by specifying a legal state/1 predicate. It is possible to write the code in different ways which differ with respect to how much of the transition specification is captured by transition/2 and how much is handled by legal state/1. Thus, one mark will be given for the definitions of both of these. [10 marks]
• :- find solution — With these predicates defined, calling find solution/0 should generate a
solution to the puzzle.
[3 marks]
4
Part C: Investigating the Winograd Challenge
To answer this question you need to find out about the Winograd Schema Challenge and demonstrate some insight into both how it might be solved using techniques of Knowledge Representation and logical reasoning..
The challenge was originally proposed by the pioneering AI researcher and computational linguist Terry Winograd. It has more recently been revisited and promoted by Hector Levesque, a well-known exponent of logic-based AI techniques and Ernie Davis, a specialist in logical formulations of commonsense reasoning. (Winograd Schemas were also covered in one of the KRR module lectures.)
Have a look at Ernie Davis’ web page at:
• http://www.cs.nyu.edu/davise/papers/WinogradSchemas/WS.html
Web page all about the Winograd Schema Challenge with links to schema sets and other relevant information.
• https://cs.nyu.edu/faculty/davise/papers/WinogradSchemas/WSCollection.html
This is Ernie Davis’ original collection of 150 Winograd schemas. (For some reason it says 146 at the top of the page, but there are actually 150.) I shall use the numbering of this set to refer to the schemas.
• https://cs.nyu.edu/faculty/davise/papers/WinogradSchemas/WSCollection.xml
This is an XML version of the original Winograd schemas, which is less densely formatted than the previous version and may be a bit easier to read.
After finding out about the Winograd Challenge and studying some of the schemas, write a short essay of about 1500 words divided into the following sections:
• What is the Winograd Challenge? [5 marks] Explain what the Winograd Challenge is and why it is significant for Artificial Intelligence.
• Can KRR Succeed? [5 marks] Explain ways in which KRR and logic techniques can solve or help to solve a Winograd Schema problem. You must give one or two specific examples in which you describe the reasoning involved and explain how this can be solved by a KRR representation. If possible give formulae that encode the content and/or related information associated with a schema and inference steps that could lead to a solution. You don’t need to give a full solution! Just explain one or two inference steps that could contribute to a solution.
• Or will KRR Fail? [5 marks] Explain why finding the solution to a Winograd Schema using any computational algorithm may be very hard. Give one or two examples where resolving an Winograd Schema using logic-based KRR techniques seems to be particular and explain why the difficulty arises. You should refer to specific schemas and point to particular problems in formulating the reasoning in a KRR system. To do this you may want to refer to the various reasoning systems you have learned about.
5
Part D: Probabilistic Reasoning using ProbLog
You are asked to program a robot from the robotics lab of the University of Leeds to navigate in the School of Computing and perform various everyday-life tasks to facilitate people in the School. The robot can navigate within specific places and do actions depending on its capabilities. A graph shown below illustrates the locations which are accessible from the robot as well as the actions which can be performed in every place, e.g. making coffee can be done by accessing the kitchen and getting the cup and the coffee.
Accessible places are denoted with a blue circle, i.e. node, and actions in every place are shown with a red node. The blue directed arrow edges denote the pathway for accessing different locations, and the red arrow edges show which and with what sequence actions can be performed in every location. Parsing the graph is performed with consideration of the edges’ direction. The number in bold at every node is the node’s ID.
However, not all locations are easy to access, and not all tasks are simple to perform. A normalized difficulty metric is applied for each location and action. Such metric is shown on the edges of the graph, demonstrating the probability of success in accessing a location, through the corresponding edge, when the goal node is a location node, and in performing the task if the goal node is an action node. Please mind that the probabilities on the graph are not relative, but absolute, (i.e. outgoing) probabilities of a node do not necessarily need to sum to 1.
In order to perform an activity, the robot will first need to move to the appropriate location. But here is some chance that the robot might have a faulty motor. Hence, there is 0.9 chance of the motor to start. If the motor does not start the robot cannot move between locations. However, if the motor does start it will be ok for the whole duration of movement. Of course, when the robot reaches the appropriate location it will need to stop before performing an action. But there is also a problem that the robot some- times goes mad and refuses to stop. The motors will always stop if the robot doesn’t go mad, which has a chance of 0.01. For every activity successfully performed the motors need to be able to start and to stop.
0.6
4 0.8 1 0.2 5
LONG LAB 0.8 ROOM 0.6
STAIRS
0.9 3 0.8 12 0.5 2
0.8
6
DEC-10
KITCHEN microwave KITCHEN food
0.3 0.6 0.6
13 8 0.6 9 7
0.9
clean dishes
open get cabin biscuits
teach robotics
0.7
11
0.5 10 get
cup
make coffee
6
Please read carefully and answer the questions below.
1. Write the ProbLog program by providing the facts as illustrated in the graph figure and the appro- priate rules which simulate the scenario described above.
Please use the following predicates:
move(x, y) action(x, y) activity(x, y) start motor stop motor gone mad
moving from node x to node y
doing an action from node x to node y performing an activity from node x to node y starting motor of robot
stopping motor of robot
robot going mad
Submit your code as a separate file called activity graph.txt.
2. Find the probability of success for every activity listed below by using the ProbLog framework.
Assume that the robot always starts from the Robotics Lab (LAB). [2 marks] (a) attend the robotics module
(b) clean dishes
(c) microwave food
(d) get some biscuits
3. Describe analytically for the following activities, how the answers from the ProbLog framework are be derived, by parsing the graph yourself and calculating the probabilities of success.
[3 marks]
(a) attend the robotics module (b) microwave food
(c) make coffee
[1 mark] [2 marks] [2 marks]
Example We will now show an example of how to compute the probability of entering the Long Room area analytically. In this example we do not consider the probability of the motors of the robot being faulty.
From the graph there are two ways to enter the Long Room area:
• going from the Lab(1) to the Long Room(4), directly, or
• going from the Lab(1) to the Kitchen(2), and then to the Long Room(4).
The robotic agent can traverse the path 1 → 4 with success with probability 0.8. Also, the robotic agent can traverse the path 1 → 2 → 4 with probability 0.9 ∗ 0.6 = 0.54. Hence, the probability of going from the Lab(1) to the Long Room(4) is the probability of traversing at least one of the paths, thus we have 1−[(1−P(1 → 4))∗(1−P(1 → 2 → 4))] = 0.908.
ProbLog Editor
For writing code using the ProbLog framework use the online Editor found here. Through this editor you cannot save nor upload your file so please make sure you save your code in an external text file. To run your code set the editor’s setting to Inference and press the Evaluate button to see the results of your queries.
What to Submit
Full submission instructions will be given on the submission widget in Minerva.
7
[70 marks total]
Reviews
There are no reviews yet.