Exercises

1. What knowledge representation schemes met so far are most suited to the forms of reasoning discussed in the lectures?
   1. Discuss how they might deal with Incompleteness, inconsistency, change and and non-monotonic default reasoning.
   2. What knowledge forms are totally inadeaquate for uncertain reasoning?

2. Rewrite the President Nixon example using abnormal predicates.

3. Use circumscription to resolve the President Nixon example.

4. Consider the problem of deciding which clothes to wear using knowledge such as:
   • Wear casual clothes unless they are not clean or important meeting occurs today.
   • Wear a Sweater if it is cold.
   • The winter is usually cold.
   • Wear shorts if it's warm.
   • The summer is usually warm.
   1. Contrsuct a JTMS network to represent these facts.
   2. Try to solve the problem In winter do I wear shorts?
   3. Answer the question What shal I wear today (You may assume that the system knows the time of year).

5. Construct as JTMS and ATMS to represent the following
   1. If you have spots and a temperature you have measles.
   2. If you have a runny nose then unless it is hay fever season you have a cold.

6. Show how a JTMS could be used to faciltate constraint satisfaction problems and in particular cryptarithmetic puzzles.

7. Show how an ATMS could be used to faciltate constraint satisfaction problems and in particular cryptarithmetic puzzles.

8. Design a depth first based algorithm to search or label a JTMS.

9. Design a breadth first based algorithm to search or label an ATMS.

10. Use an ATMS to solve the following car diagnostic problem.

    You may assume the following:

    • If the battery is OK and the headlight bulbs are OK then the headlights will work.
    • If the battery is OK and the starter is OK then the engine will start.

    Find explanations as to why:

    • The engine won't start but the headlights work.
    • the headlights won't work but the car starts.

1. Implement the Search Alogorithms described in this lecture in LISP and/or C. Comment on how suited each language would be for each type of search?

2. How suited would PROLOG be in implementing the search algorithms. Comment on how this might be done and what difficulties might exist.

3. Discuss the relative merits of depth first and breadth first searching methods. What memory overheads exist? How might searches be affected?

   Suggest some applications to which each is best suited.

4. Steepest ascent hill climbing uses the basic Hill climbing algorithm but chooses the best successor rather than the first successor that is better. How will this improve matters?

5. When will Hill climbing searches fail? Do Steepest ascent hill climbing always find solutions? How might some problems be overcome in the search?

6. List 3 differences between simulated annealing and simple hill climbing methods.

7. List examples where hill climbing and best first search behave (a) similarly (b) differently.

8. Write an alogorith to perform a breadth first search for a graph making sure your algorithm works when a singls node is generated at more than one level of the graph.

9. When would best first search be worse than a simple breadth first search?

10. Trace the constraint satisfaction procedure to solve the following cryptarithmetic problem:

    
             CROSS
            +ROADS
            -------
            DANGER

11. Discuss how constraint satisfaction might work it implemented its search strategy via:
    • depth first search
    • breadth first search
    • best first search

1. Assume the following facts:
   • Steve only likes easy courses.
   • Computing courses are hard.
   • All courses in Sociology are easy.
   • ``Society is evil'' is a sociology course.

   Represent these facts in predicate logic and answer the question?

   What course would Steve like?

2. Find out what knowledge representation schemes are used in the STRIPS system.

1. Discuss how procedural methods may be used to solve the following problems:
   • Natural Language Understanding
   • The Games of Nim and Kalah (see last years notes for rules).
   • Path Planning type tasks.

1. Construct CD representation of the following:
   1. John begged Mary for a pencil.
   2. Jim stirred his coffee with a spoon.
   3. Dave took the book off Jim.
   4. On my way home, I stopped to fill my car with petrol.
   5. I heard strange music in the woods.
   6. Drinking beer makes you drunk.
   7. John killed Mary by strangling her.

2. Try capturing the differences between the following in CD:
   1. John slapped Dave, John punched Dave.
   2. Sue likes Prince, Sue adores Prince.

3. Rewrite the script given in the lecture so that the Bank robbery goes wrong.

4. Write a script to allow for both outcome of the Bank robbery: Getaway and going wrong and getting caught.

5. Write a script for enrolling as a student.

6. Find out about how MARGIE, SAM and PAM are implemented. In particular pay attention to their reasoning and inference mechanisms with the knowledge.

7. Find out how the CYCL language represents knowledge.

8. What are the two levels of representation in the constraints of CYC?

9. Find out the relevance of Meta-Knowledge in CYC and how it controls the interpretations of knowledge.

10. Find out what levels of concepts CYC has in its ontology.
    1. Where should the following concepts be placed in this ontology
       • dog
       • court case
       • South Wales Echo
       • Wales
       • Pint of Brains Dark
       • The Open Golf Championship.