[SOLVED] -anser-set-programming COMP4418, 2017 Assignment 2

COMP4418, 2017 Assignment 2

Due: 14:59:59pm 04 October (Week 10)

Late penalty: 10 marks per day

Worth: 15%

This assignment consists of five questions.

1. [20 Marks] (Answer Set Programming)
A clique of a graph is a set of vertices C that are all adjacent to each other. That is, for a graph withverticesV andundirectededgesE{{x,y}|x,yV},acliqueisasetCV suchthatfor allxC andyC,ifx=y,then{x,y}E. Ak-clique isacliqueofsizek,thatis,|C|=k.

1. (a) Write an ASP program that decides the k-Clique problem:
   Input: AgraphwithverticesV andedgesEV V,andanaturalnumberk0. Problem: decide if there is a k-clique.

   Assume the input parameters V , E, k are encoded in ASP in the form of a unary predicate v, a binary predicate e, and a constant symbol k, respectively. Use a unary predicate c to represent the vertex cover C. Your program should have no more than two rules.

2. (b) Use an ASP solver1 to determine how many k-cliques the graph has for k {3, 4, 5, 6}. Hint: the number of 2-cliques is 11.

35 6 12

4

a :- notb,notc. b :- nota,notc. c :- nota,notb. d :- a.

d :- b. d :- c.

Determine stable models of this program. For every candidate interpretation S, specify the reduct PS. Give your solution in a table of exactly (!) the following form and order:

1For instance, you can download the Clingo ASP solver from https://potassco.org/ and run your program with clingo const k=k -n 0 clique.lp or ./clingo const k=k -n 0 clique.lp where k N is the size of the clique.

2. [20 Marks] (Answer Set Programming) Consider the following logic program P.

1

2

3. [20 Marks] (Reasoning about Knowledge) Suppose all you know is the KB

x(P(x) x = #1 x = #2) x(P(x) Q(x))

1. (a) Determine the set of known instances of P (x) Q(y), that is, all pairs of standard names

   (n1,n2) {#1,#2,#3,}{#1,#2,#3,} such that OKB |= K P(n1)Q(n2) .

2. (b) DetermineRES[KB,(P(x)Q(y))].

   You may simplify the resulting formula to eliminate true and false.

4. [20 Marks] (Limited Belief)

Consider the knowledge base

(F C) (C U).

1. (a) Bring this knowledge base into proper+ form.

   Let KB denote the resulting proper+ knowledge base.

2. (b) Determine the minimal k 0 such that OKB | Kk (F U C) hold?
3. (c) Determinetheminimalk0suchthatOKB|Kk(FU)hold?

5. [20 Marks] (Reasoning about Action)
Suppose we have a domestic service robot cleaning up our house. It has a box, and into that box it can put objects. The robot can also shake the box to test whether something is in it. Finally it can move the box and its contents to other locations. We assume that in reality, the box does contain some object, but the robot does not know that. This scenario is modelled by the following basic action theory:

0 = {xInBox(x)} dyn = { Poss(a) true

SF(a) (a = shakeBox xInBox(x))
[a]InBox(x) a = putInBox(x) InBox(x)
[a]location(x) = y (a = moveBox(y) InBox(x)) (y a = moveBox(y) location(x) = y)}

Prove or disprove the following projection problems using regression:

(a) 0 dyn |= x[putInBox(x)]InBox(x)
(b) 0 dyn |= y[moveBox(y)]x(InBox(x) location(x) = y)

(c) 0 dyn Odyn |= [shakeBox]KxInBox(x) (d) 0 dyn Odyn |= [shakeBox]xKInBox(x)

You may abbreviate putInBox by p, moveBox by m, shakeBox by s, InBox by I, and location by l for better readability.

Submission

You will need to answer the questions in a file named assn2.pdf Submit using the command: give cs4418 assn2 assn2.pdf

The deadline for this submission is 14:59:59pm 04 October. 3

Late Submissions

In case of late submissions, the maximum available mark is reduced by 10 points for each day late. No extensions will be given for the assignment (except in case of illness or misadventure).

Academic Honesty and Plagiarism

All work submitted for assessment must be your own work. Assignments must be completed individually. We regard copying of assignments, in whole or part, as a very serious offence. Be warned that:

• the submission of work derived from another person, or jointly written with someone else will, at the very least, result in automatic failure for COMP4418 with a mark of zero;
• allowing another student to copy from you will, at the very least, result in a mark of zero for your own assignment; and
• severe or second offences will result in automatic failure, exclusion from the University, and possibly other academic discipline.

  Collaborative work in the form of think tanking is encouraged, but students are not allowed to derive solutions together as a group during such discussions. Students are also warned not to send solution fragments of the assignments to each other in any form (e.g. as email or listings). In addition, copy- ing/purchasing of solutions that is available on the web is also not permitted. Students are strongly advised to protect their work. Do not leave your terminal/computer unattended, or leave printouts at the printer for others to take. Read the study guide carefully for the rules regarding plagiarism.

4