Assignment 2: A Production System for Bagging COM1005 Machines and Intelligence Semester 2: Experiments with AI Techniques Heidi Christensen University of Sheffield Tuesday 31st March, 2020 This assignment carries 18.75% of the marks for COM1005 DUE DATE: Monday 11th May 2020 at 23.59 (UK Time) The task for this assignment is to explore and document improvements of the Bagger Pro- duction System. The problem is introduced in Week 6, Lecture 12 (Rule-Based Systems). The Problem Robbie the Robot has a job in a supermarket. As shopping items are passed through the checkout, Robbie must put them into bags in the most efficient way possible. Robbie wants to minimise the number of bags that have been used once all the items have been packed. Simplifications: • All bags have a space capacity of 100. • All items are stacked one on top of the other. • We don’t care about item fragility or overall weight of the bags or items – we just care about using the space in the bags most effectively. Restrictions: • The ‘trolley’ will contain a number of items in a set order. You cannot pre-sort the items or put them to one side to maximise efficiency – you must bag them in the order they appear. Example with a greedy solution where we have three items: 1) bread of space 30, 2) spuds of space 50, and 3) cornflakes of space 40. We have to bag the items in the order in which they appear on the list. We put in bread and spuds in Bag 1, using 70/100 of the space available. Since there isn’t enough space for cornflakes, we open another bag (Bag 2) and put them in there. We have used two bags in total. 1 Your tasks Here is an overview of the two tasks you need to complete. More detail on each task can be found below. 1. Implement an improved solution: You are given a system, BasicBagger, which implements a simple solution to this problem. Your first task is to implement a better solution by adapting the code base. We define a ‘better’ system as a system that uses fewer bags. 2. Produce a report: Finally, you should produce an experimental report using the template provided. The report should include graphs comparing the performance of the given BasicBagger algorithm and your ImprovedBagger algorithm. Task1: Implement an improved system For this Assignment, you will have been supplied with: • this Assignment brief; • a report template; • a code base named assignmenttwo. The code base assignmenttwo has the following structure: • logger (package for helpful prints); • pmatch (pattern matching package); • production (production rules and system): – BasicGetNextItem.java – BasicPutInCurrentBag.java – BasicStartBagging.java – BasicStartNewBag.java – Production.java – ProductionSystem.java • trolley (trolley generator package); – TrolleyGen.java • RunProductionSystem.java • RunTrolleyGen.java To run the Bagging system, compile and run RunProductionSystem.java (note: it is com- patible with Java 1.8+; it’s also ready to build in IntelliJ). The group of files with names beginning Basic implement a basic algorithm for Bagging. Each of the files is a separate Production rule (note: they all extend Production.java). Your task is to implement an improved algorithm for Bagging – remember, an improved algorithm will use fewer bags. 2 In this assignment we ask you to substitute all Basic* production rules with a set of new production rules of your own design. We will call them Improved* productions, and you can refer to your algorithm as Improved, ImprovedBagger etc. in your report. These changes will require an update of the PRODUCTION LIST in Production.java. Your algorithm will be tested by markers against the program structure you were originally supplied with. Therefore, other than Production.java and the production rules needed to implement your algorithm (i.e. the Improved* files, you are asked not to amend any of the other files in the code base. Your submission should only include the files you have changed, and you should check it will run with the original file system before submitting. You can have as many Improved* files as you like, but bear in mind that a more concisely implemented algorithm will score more marks. A complete solution on your machine may look something like: • logger (unchanged) • pmatch (unchanged) • production – Improved{production name}.java – Improved{production name}.java – Improved{production name}.java – Improved{production name}.java – Improved{production name}.java – Production.java – ProductionSystem.java (unchanged) • trolley (unchanged) – TrolleyGen.java • RunProductionSystem.java (unchanged) • RunTrolleyGen.java (unchanged) where production name is a descriptive name for the particular production rule. From this solution, you should submit the following code files: • Improved{production name}.java • Improved{production name}.java • Improved{production name}.java • Improved{production name}.java • Improved{production name}.java • Production.java Logger To aid in your understanding of the system, the code contains Logs which you can use to print the proceedings according to your needs. By default most of these logs are commented out. 3 Task2: Produce a report Your experimental report should compare the performance of your ImprovedBagger with the BasicBagger. You should include, at the very least: • pseudo-code describing both the given BasicBagger and your ImprovedBagger algo- rithms • graphs, charts or tables to illustrate differences in performance of the two algorithms • carefully specified information about the tests performed to compare the algorithms • your own conclusions A LATEX report template is provided, with compulsory sections specified. You may add more sections if you wish: include in your report what you think is interesting. Note: You must use the LATEX template provided for your report. You will not be marked on your ability to use LATEX to format your report (i.e. there are no extra marks for making it look fancy!). That being said, LATEX is an essential piece of software for communicating research and results in engineering and science, so we want you to get experience using it early on. The online Latex editing website, Overleaf is excellent for your first project. Please, see a tutorial here: https://www.overleaf.com/learn/latex/Tutorials. Summary of assignment tasks 1. Write pseudo-code for BasicBagger (we strongly encourage you to begin here as this will help you understand the Production System you’re dealing with); 2. Copy all Basic* production files, and rename them (changing Basic* to Improved*); 3. Write pseudo-code for your ImprovedBagger algorithm 4. Implement your solution by amending/adding Improved* productions 5. Amend the PRODUCTIONS LIST field in the Production.java interface** to include all your productions 6. Design a set of tests to compare BasicBagger and ImprovedBagger 7. Complete your report with the results from your experiments What to submit Submit your solution, as a zipped file called SURNAME FIRSTNAME.zip, where SURNAME is your surname (family name), and FIRSTNAME is your first name (given name). This zip file should contain: 4 • a .pdf copy of your report named SURNAME FIRSTNAME.pdf • all Improved* production files (for novel productions we expect extra comments ex- plaining the functionality of each production), • Your Production.java file which is the original Production.java file with amended PRODUCTION LIST according to your needs. Marking Scheme Remember: readability is of great importance for coding style. You should therefore take great care with line breaks, document your code appropriately and use indentation consis- tently. Before you hand in your code, ask yourself whether the code is understandable by someone marking it. Marks will be awarded according to these criteria: Percentage points Categories and example score weights 60% Implement and test of improved system 25% Quality of proposed improvements (high scores for ingenuity and quantity of proposed production rules) 10% Quality of implementation of your improved production rules 15%
Implementation of tests (high scores for adequate and succinct tests). 10% Well documented (comments used to ease understanding of more complex parts of the code) and well presented code (in- dentations, brackets and choice of variable names). 20% Documentation – quality of presentation of your ex- perimental results in your report 5% Pseudo-code (high scores for presentation and accuracy) 5% Quality of graphs, charts or tables to communicate your re- sults 5% Motivation and choice of tests to compare algorithms 5% Quality of conclusions (high scores for being comprehensive and backed by evidence from your tests). 20% Experimental results 20% Higher scores for larger improvements. 100% Total Marks and feedback will be returned through MOLE/Blackboard within 3 weeks. 5 Rules Unfair means: This is an individual assignment so you are expected to work on your own. You may discuss the general principles with other students but you must not work together to develop your solution. You must write your own code. All code submitted may be examined using specialized software to identify evidence of code written by another student or downloaded from online resources. Frequently Asked Questions Can I add new classes to the code base? Yes. Since the Improved implementation is more complex than the Basic implementa- tion, you may find it helpful to define new classes. You are welcome to do this if you wish. You will not be marked up or down based on the number of classes you have, so long as your code behaves as it should and is well commented. How do we define ’efficiency’ in the context of this problem? Given two bagging algorithms, Bx and By, we say that Bx is more efficient than By if, on average, Bx uses fewer bags than By for a given trolley. There doesn’t seem to be much programming in this assignment. Have I misunderstood? No, that’s OK. All the coding that needs to be done is specified in the sections Your task and Code base. This assignment tests your ability to adapt someone else’s code base to your own needs in a neat and readable way, not to write an entire code base yourself. The assignment also asks you to test experimental results, and present your results coherently in a report. I get an error when I try to run the code from the command line? Like in Assignment 1, you will be able to run this code from the command line. To com- pile from the command line, navigate to the directory where the assignmenttwo folder is stored, and then run the command ‘javac assignmenttwo/filename.java’, where ‘filename’ is the file with a main function. To run a java programs from the command line, run the com- mand ‘java assignmenttwo/filename’ (no file extension is needed here). Two common errors encountered are: • jdk (Java Developer Kit) is not installed, so you can’t compile from the command line. In this case, you need to install jdk – you can do that here: https://www.oracle.com/ java/technologies/javase-jdk11-downloads.html. 6 • Mismatched versions of Java Run-time and previously compiled classes. You are most likely to have this error if you have written code on one computer, and then try to run it on another. To solve it, delete all files with a .class extension – this includes .class files in the pmatch folder, or any other sub folders. Then recompile your code from the command line! How do I extract the number of bags used for a given trolley? Doing algorithm runs on groups of generated trolleys is obviously part of the assignment – this is how you obtain your experimental results. As for the number of bags used, think of how you can use the final Short Term Memory to arrive at that value! 7
