Coursework for COMP5450M Knowledge Representation and Reasoning
Prolog Knowledge Base & Winograd Challenge
Due 10am, Friday 7th December, 2018
This coursework counts for 25% of the total marks for this module.
You may do this coursework in pairs.
Part I: 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 well known puzzle. The puzzle goes as follows:
Three frogs and three toads are lined up in the configuration illustrated in the Starting State figure below. The frogs are on the right and the toads on the left. By a series of valid amphibian moves you must transform the state to the Goal state, also illustrated below.
But the frogs and toads can only move in accordance with the following specification:
• Only one amphibian (i.e. frog or toad) can move at a time.
• Frogs can only move to the left and toads can only move to the right.
• Each move is ether a crawl or a hop.
• A crawl is a move to an adjacent empty space.
• A hop is a move to an empty space that is two spaces away from the starting space, such
that the space between the start and end of the hop is occupied by another amphibian.
• Frogs can only hop over toads and toads can only hop over frogs.
Starting State
Goal State
To solve this puzzle, you should use the bb planner.pl Prolog program. In order to config- ure it to solve this particular problem you will need to define the predicates initial state/1, goal state/1 and transition.
1
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.
• bb jugs.pl
https://swish.swi-prolog.org/p/bb_jugs.pl
This is an example file, which illustrates the use of the bb planner to solve a simple puzzle.
• frog+toad template.pl https://swish.swi-prolog.org/p/bb_frog+toad_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.
Mark Scheme
To answer the Frog and Toad puzzle question please complete the following steps:
a) Before completing the program, you will first need to work out a representation for pos- sible states that the frogs and toads can be in during the movement sequence. Give a specification and brief explanation of the representation you have devised for these states.
[3 marks]
b) Complete the frog+toad.pl program by adding definitions for the following predicates:
i) initial state/1 — declares the initial state of the scenario. [1 mark]
ii) goal state/1 — declares the goal state. [1 mark]
iii) transition/2 — specifies a relation between two states which is true if and only if it is possible for the first state to be transformed into the second. You must ensure that your transitions cover all the possible moves that can be made by any amphibian in any possible state. [6 marks]
c) Run the find solution predicate to find a valid sequence of moves from the starting state to the goal state.. Give the plan that is produced. [4 marks]
[15 marks total]
2
Part II: A 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. [2 marks]
iii. Comment on the repercussion of rules such as this so-called “genesis” rule for the problem of automated reasoning in general. [2 marks]
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]
3
(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 the 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]
4. Optional: Analysis of the Negation Implementation
Consider the treatment of negated rule premisses in the inference mechanism. The imple- mentation is simple and usually gives reasonable results. However, it is really a hack and can sometimes result in incoherent inferences being made. What can go wrong? Why does this occur?
[30 marks total]
4
Analysis
Formalisation
Evaluation
Discuss your chosen schema informally. Explaining what facts and reasoning principles would enable an intelligent agent (fluent in English) to disambiguate the sentence by attaching the correctreferencetothepronoun.(Youshouldwriteabout200-300wordsonthis.) [8marks]
Use the techniques of symbolic knowledge representation that you have learnt so far to give a formal specification of some facts and/or axioms that you consider to be key to resolving the reference in the case of your chosen Winograd schema. You may use standard first order logic or some other logic that you consider appropriate (e.g. temporal logic, tense logic, situation calculus or default logic). If you wish you can use different logical formalisms to analyse different aspects of the reasoning, but make sure that the meaning of each formula you give is clear. [10 marks]
Discuss the limitations of the formalisation you have specified. In particular, consider whether your representation would be sufficient to support solution of the schema prob- lem by a purely automatic theorem prover. In most cases I would expect the answer to be no, so you you will be explaining what is missing from your representation. (You should
Part III: Tackling the Winograd Schema Challenge
In answering this question you will be taking a small step towards addressing the Winograd Schema Challenge. The challenge was originally proposed by the pioneering AI researcher and computational linguist Terry Winograd. It has 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 refreshing your memory about the nature of the Winograd Schemas pick one of them that you find interesting and which you can fruitfully analyse, both informally and formally.
Do NOT pick the following schema! (Number 9 in the original schema set). I shall be examining this as an example to help you tackle this problem.
9. The large ball crashed right through the table because it was made of [steel/styrofoam]. What was made of [steel/styrofoam]? Answers: The ball/the table.
Write a short essay (3-4 pages including formulae) comprising the following sec- tions:
again write around 200-300 words).
[7 marks] [25 marks total]
5
Which Winograd problem should you choose?
You may consider any of the problems except number 9. As I mentioned above, I am using this as an example. I is best if you do one that is not do difficult. But there are a few that are a bit too easy, and it is probably better to do one that is too hard than too easy otherwise there won’t be so much to write about in the discussion and evaluation. I suggest you do not do 19 as that is rather easy. 13 may also be a bit too easy.
What to Submit
Full submission instructions will be given on the submission widget in Minerva.
6
Reviews
There are no reviews yet.