CMI3504 Assignment Specification

FIND A SOLUTION AT Academic Writers Bay

CMI3504 Assignment Specification
Handed to Students : Start of teaching Block
Deadline : End of Block 2.2 – Sunday 25th April 2021 (Returned in w/c 10th May 2021)
To understand key concepts of search in AI Planning
To develop skills in using planning algorithms, and compare and contrast their performance
To develop skills in modelling using PDDL
To develop skills needed to solve a complex planning problem using available tools
Outcomes to be Assesses
This assignment addresses all learning outcomes for the module.
This assignment is worth 100% of your total grade for this module, and there will be two separate submissions,
both of them at the end of the deliver block.
Submission 1: Search and Heuristics (40%)
This submission is for an investigation into the effectiveness of heuristic search techniques in AI Planning. You’ll
have to compare greedy-best-first search and A* search for AI Planning in terms of strengths and weaknesses
when a delete-relaxation heuristic is used. The submitted report should be of around 1500 words and must
• Description of the two search approaches, and of the delete-relaxation heuristic, with appropriate
references provided.
• A discussion of weaknesses and strengths of the search approaches, in general, and when a deleterelaxation heuristic is used.
o You can also use examples from domain models and problems, such as Blocksworld, to
highlight the issues. A list of models can be found from the repository of the
Submission 2: Planning Models (60%)
This submission will test your understanding of planning models, and of operational use of planning engines.
You must produce a PDDL domain file and the corresponding planning problem files. Your problem files must be
runnable by at least 2 planners taken from either (i) the itSIMPLE collection. In this case I must be able to import
your PDDL into itSIMPLE and run the planning problems with each planner, and obtain solutions; (ii) the planner
used in, and also in this case I must be able to upload your files and obtain solutions; (iii) the
web. In this case you must give me the URL where you obtained the planners, and include the command line
you used to run the planner(s); or (iv) from those mentioned in the module’s slides; also in this case include the
command line you used to run the planner(s).
A zip file containing the following items will be uploaded to Brightspace:
1. A pdf copy of your report .
2. The domain model and the problem models, in PDDL.
3. The output logs of 2 planning engines that run on the PDDL models.
For the report, there is a maximum word count of 1,000 and you are encouraged to use a concise writing style,
allowing the examiner to easily assess your report. The layout of the report is up to you; however, it must provide
the following details in a logical order.
• A list of the names and/or URLs of existing PDDL domain models (if any) that you have used to help you
create your PDDL models;
• A description of how you produced the models, and what tools, if any, you used (e.g. a text editor,
• A short description of the meaning of each operator schema in the model, even if some were imported
from some other domain model;
• A very short comparison of the performance of the planners you have used to generate solutions. To
do this, use and refer to the planning literature, to results of IPCs where they have competed if
appropriate, and with reference to how the planners performed on the planning problems you set.
Practical Planning Problem to Be Solved for Submission 2
In this domain we want to use planning engines for solving a match-three game.
This is a type of game where the player (in this case, the planner) can remove tiles according to a matching
criterion. Here, three tiles of the same type which are adjoined, either vertically or horizontally, can be removed
from the board. Once tiles are removed, the corresponding cells are left empty.
Given an initial board setting, the goal is to obtain an empty board by removing all the tiles. In order to achieve
the goal, the planner can swap two tiles at the time –that must be of a different type– which are adjoined either
vertically or horizontally. There is only one constraint: it is not possible to swap a tile with an empty cell.
It is important to notice that three adjoined tiles of the same type are not automatically removed: the planner
can decide to remove them, but can also decide to keep them on the board for swapping purposes. However,
the final goal is always to have a completely empty board.
Four different type of tiles are considered in this version of the game:
• Gryffindor (G),
• Hufflepuff (H),
• Ravenclaw (R),
• Slytherin (S).
It should be noted that, for some inexplicable reasons, when a Gryffindor tile is swapped with a Slytherin tile,
the swap is correctly performed, but the Slytherin tile is destroyed, resulting in an empty cell.
Quality of plans is measured in terms of number of swaps needed to achieve the goal.
The following three problems have to be encoded:
Problem 1
The goal is to have the board empty. An example solution could be:
• Swap c3, b3 (row c can then be emptied)
• Match-three c1, c2, c3
• Swap a2, a3
• Swap a3, b3 (rows a and b can then be emptied)
• Match-three a1, a2, a3
• Match-three b1, b2, b3
Problem 2
The goal is to have the board empty – i.e., all the cells are empty
Problem 3
Black cell is empty. The goal is to have the board empty – i.e., all the cells are empty
Getting Started
You should start by spending a good amount of time understanding the PDDL language. Study existing domain
models and problems, try to understand how behaviours and dynamics are usually implemented in the language,
and how planning engines cope with different design choices. Identify the main features and the main operators
needed for the domain model to be designed, and think in terms of properties that they need to take into
account. Solve problems by hand, and think about the process you are doing.
For the development of the PDDL models, it is completely up to you where to start, and what tool to use for
encoding. However, I would recommend that you carefully consider the design of existing models before
developing yours. I would recommend an iterative development approach, committing each revision to your
SVN/GIT repository.
Resources Required
Tools and useful websites will be introduced during the module. In a nutshell, what is needed for this
assignment is:
1. A text editor or a GUI/web tool to encode the PDDL models
2. 2 planning engines. Either included in one of the tools, or freely available on the web from IPCs
webpages or their own developers page.
Assessment Criteria
This assignment comprises 100% of the total marks for this module. Submission 1 is worth 40% and Submission
2 is worth 60%.
The first submission will be judged and assessed on:
1. The quality and detail of the description of the selected planning approaches.
2. The quality and detail of the comparison.
3. The justification of the described weaknesses and strengths.
4. The appropriateness of included references.
The second submission will be judged and assessed on:
1. The quality and appropriateness of the PDDL models generate.
2. The quality and detail of the description of the PDDL models.
3. The ability of planning engines to solve encoded problems.
4. The quality and detail of the comparison between planning engines.

READ ALSO...   Plant and Machinery Account
Order from Academic Writers Bay
Best Custom Essay Writing Services