CMI3504 Assignment Specification | My Assignment Tutor

1CMI3504 Assignment SpecificationHanded to Students : Start of teaching BlockDeadline : End of Block 2.2 – Sunday 25th April 2021 (Returned in w/c 10th May 2021)AimsTo understand key concepts of search in AI PlanningTo develop skills in using planning algorithms, and compare and contrast their performanceTo develop skills in modelling using PDDLTo develop skills needed to solve a complex planning problem using available tools.Outcomes to be AssessesThis assignment addresses all learning outcomes for the module.AssessmentThis 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’llhave to compare greedy-best-first search and A* search for AI Planning in terms of strengths and weaknesseswhen a delete-relaxation heuristic is used. The submitted report should be of around 1500 words and mustinclude:• Description of the two search approaches, and of the delete-relaxation heuristic, with appropriatereferences 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, tohighlight the issues. A list of models can be found from the repository of the planning.domainswebsite.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 berunnable by at least 2 planners taken from either (i) the itSIMPLE collection. In this case I must be able to importyour PDDL into itSIMPLE and run the planning problems with each planner, and obtain solutions; (ii) the plannerused in, and also in this case I must be able to upload your files and obtain solutions; (iii) theweb. In this case you must give me the URL where you obtained the planners, and include the command lineyou used to run the planner(s); or (iv) from those mentioned in the module’s slides; also in this case include thecommand 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.23. 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 providethe 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 youcreate your PDDL models;• A description of how you produced the models, and what tools, if any, you used (e.g. a text editor,itSIMPLE,;• A short description of the meaning of each operator schema in the model, even if some were importedfrom some other domain model;• A very short comparison of the performance of the planners you have used to generate solutions. Todo this, use and refer to the planning literature, to results of IPCs where they have competed ifappropriate, and with reference to how the planners performed on the planning problems you set.Practical Planning Problem to Be Solved for Submission 2In 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 matchingcriterion. Here, three tiles of the same type which are adjoined, either vertically or horizontally, can be removedfrom 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 achievethe goal, the planner can swap two tiles at the time –that must be of a different type– which are adjoined eithervertically 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 plannercan 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:3Problem 1The 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, b3Problem 2The goal is to have the board empty – i.e., all the cells are emptyProblem 3Black cell is empty. The goal is to have the board empty – i.e., all the cells are empty4Getting StartedYou should start by spending a good amount of time understanding the PDDL language. Study existing domainmodels 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 operatorsneeded for the domain model to be designed, and think in terms of properties that they need to take intoaccount. 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 forencoding. However, I would recommend that you carefully consider the design of existing models beforedeveloping yours. I would recommend an iterative development approach, committing each revision to yourSVN/GIT repository.Resources RequiredTools and useful websites will be introduced during the module. In a nutshell, what is needed for thisassignment is:1. A text editor or a GUI/web tool to encode the PDDL models2. 2 planning engines. Either included in one of the tools, or freely available on the web from IPCswebpages or their own developers page.Assessment CriteriaThis assignment comprises 100% of the total marks for this module. Submission 1 is worth 40% and Submission2 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.


Leave a Reply

Your email address will not be published.