COMP4418, 2019–Assignment 2
Due: 17:59:59pm Friday 8 November (End of Week 8)
Worth: 15%.
This assignment consists of three parts. The first two parts require programming in ASP. The third part requires written answers only. Each part is worth the same amount.
In the Answer Set Programming parts, we will assume that the input directed graph (V,E) is ex- pressed with predicates vertex and edge, that the input parameter is given as the constant size, and that the computed output will be expressed using a predicate select. The programs for the first and second parts should be stored in files named independent.lp and feedback.lp respectively. See the file petersen.lp for an example test graph and the comments in it for examples of desired output. As part of the marking, the programs for the first and second parts might be tested on graphs of small size and on graphs of relatively large size. A correct program that works on small graphs but does not scale to larger graphs will be awarded partial marks.
Part 1
Given a graph (V, E) an independent set is a set of vertices I ⊆ V such that no pair of vertices in V is adjacent. Develop an ASP program that outputs an independent set of size given as parameter. Use the unary predicate select/1 to indicate which set of vertices should be selected in an independent set.
Part 2
Given a direct graph (V, E), a feedback edge set is a set of edges F ⊆ E such that removing these edges leaves an acyclic subgraph. That is, F is a feedback edge set iff (V, E F ) is a directed acyclic graph. Develop an ASP program that outputs a feedback edge set of size given as parameter. Use the binary predicate select/2 to indicate which set of edges should be selected in an independent set.
1
Part 3
The Sokoban puzzle (see the figure on the right) consists in moving a character in a 2D map to push boulders into target cells. Each turn, the player can move to an adjacent cell (no diagonals) if it is empty, or push a boulder one step further. To push a boulder, the player needs to stand next to it, and the space behind the boulder needs to be empty (no other boulders and no walls).1
We would like to use a STRIPS planner to solve the Sokoban problem. Our representation will use 2 operators, move(i,j,k,l) and push(i,j,k,l,m,n), where (i, j), and (k, l) refer to the starting and ending coordinates of the player when the action is taken, and for the last operator, (k,l) and (m,n) refer to the starting and ending coordinates of the boulder. In the figure, we assume that the bottom leftmost cell has coordinates (1, 1), that the bottom rightmost cell has coordinates (9, 1) and that the top rightmost cell has coordinates (9, 9).
Question 3.1
List the fixed and the dynamic relations.
Question 3.2
Define the preconditions and effects of each operateor.
Question 3.3
Define the initial state corresponding to instance in the figure. If some parts of the answer appear to be very repetitive, it is possible to use ellipsis “. . . ” and not list everything. Use your best judgement.
Question 3.4
Define the goal corresponding to the instance in the figure.
Question 3.5
What is the main obstacle to using Answer Set Programming to solve Sokoban instances? (Answer with no more than one or two sentences in English.)
Assignment Submission
You will need to submit answers to Parts 1, 2 as files independent.lp and feedback.lp respectively, and your answers to Part 3 as PDF file named assn2.pdf.
give cs4418 assn2 assn2.pdf independent.lp feedback.lp
The deadline for this submission is 17:59:59 Friday 8 November (Sydney time). Late Submissions
Late submissions will be accepted until 11:59:59 Monday 11 November (Sydney time) with no penalty. However, no submissions will be accepted after 11:59:59 Monday 11 November, regardless of the excuse. Extensions may only be granted in case of illness or misadventure occuring before the Friday deadline. In particular, if UNSW servers crash on Saturday and are only fixed on Tuesday and a student did not submit their assignment before the crash, they will got 0 marks for it. On the other hand, if UNSW servers crash on Friday or earlier, every student will get an appropriate extension. It is much safer to submit before Friday evening.
Read the course outline carefully for the rules regarding plagiarism.
1You can play and familiarize yourself with the rules at https://sokoban.info/.
2
Reviews
There are no reviews yet.