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.
• 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!