Lincoln School of Computer Science
Assessment Component Briefing Document
Title: CMP2020M Artificial Intelligence – Component One
Indicative Weighting: 40%
RESIT
Learning Outcomes:
On successful completion of this component a student will have demonstrated competence in the following areas:
• [LO2] Apply Artificial Intelligence techniques to solve practical problems
• [LO3] Locate and reference relevant information.
Requirements
This is a coursework assignment about implementing different Artificial Intelligence methods in Prolog and PDDL (the Planning Domain Definition Language). The coursework is split into two main parts, each composed of a number of smaller tasks. All your source code has to be suitably documented, i.e. every relevant statement in your code needs to be explained in terms of the function it fulfils in order to get full marks on each task. Also make sure you reference any source (websites, books, papers, etc.) that you used to solve the tasks in your source code, using appropriate comments that a formatted according to the Harvard referencing guide.
The submission should be a single ZIP file, comprising exactly two files:
1. A PDDL domain file that solves the problems detailed in Appendix A below. This domain file should be downloaded from the planning webservice at http://lcas.lincoln.ac.uk/fast-downward/ and named “domain.pddl” (make sure you get the name correct, or you will incur a presentation penalty) and submitted as part of your submission ZIP file (again, make sure it is a ZIP file, not a RAR archive or similar, only ZIP is accepted). Your code will be tested using the Webservice for marking against the exemplary problems given there and additional ones to verify the general applicability of your solution. You can download the file from the webservice by
clicking the button.
2. A Prolog file containing the rules and facts to solve the tasks detailed in Appendix B. This single
Prolog file containing all facts and rules and should be named “swish.pl” in your submission ZIP file. Make sure you name the rules precisely as asked for in the task specification. You can use the webservice at http://lcas.lincoln.ac.uk/swish/ to program and test your solution. Download
your solution via the “Download” menu item:
You will submit your work as a ZIP file via blackboard under the respective submission items (under “Assessment Item 1 – Coursework”). Please make sure you read the instructions for submission carefully, as failing to do so may incur a presentation penalty. In particular pay attention to the naming convention for files to be submitted. Your submission should comprise one ZIP file containing two files only: “domain.pddl” and “swish.pl”
Not complying with above requirements will result in a presentation penalty.
Useful Information
This assessment is an individually assessed component. Your work must be presented according to the Lincoln School of Computer Science guidelines for the presentation of assessed written work. Please make sure you have a clear understanding of the grading principles for this component as
detailed in the accompanying Criterion Reference Grid. If you are unsure about any aspect of this assessment component, please seek the advice from the module coordinator Marc Hanheide (mhanheide@lincoln.ac.uk).
Submission Instructions
The deadline for submission of program code is given in the official documentation for hand-in dates. Every student is required to be able to demonstrate and explain his or her solution to the delivery team on request.
You must make an electronic submission of your work in a ZIP file containing all developed code files by using the assessment link on Blackboard for this component (see above).
DO NOT include this briefing document with your submission.
Appendix A: Assessment Item 1.1 – AI Planning [50 marks]
Your task is to write a PDDL domain that can solve the wolf-goat-cabbage planning problem for any valid goal configuration. The problem is described in http://www.mathcats.com/explore/river/crossing.html as follows:
Make sure you understand the constraints and have play at http://www.mathcats.com/explore/river/crossing.html to really understand the problem.
You should use the planning webservice provided to you at http://lcas.lincoln.ac.uk/fast-downward/. In the “Problem” section of that web service you find exemplary problem definitions, and in the “Domain” section you will find a skeleton PDDL domain for this problem (named wolf-goat- cabbage-domain-template) and also other examples.
Complete the domain skeleton so it solves the given problems (wolf-goat-cabbage- problem-01 and wolf-goat-cabbage-problem-02). These problem definitions already define the valid configurations that are considered safe, i.e. where nothing gets eaten. As hinted in the template, you need to define the preconditions and effects for four actions, namely move_wolf, move_goat, move_cabbage, and move_empty. Make sure, you name the actions precisely as asked for.
Make sure you comment your solution appropriately using comments starting with “;”. Your comments must explain what your actions model and how this helps to solve the problem. You are advised to extend on the given domain template, but you may also develop your own from scratch. But your domain must be able to solve the given problem definition as they are. You are not supposed to provide your own problem definition!
Sailor Cat needs to bring a wolf, a goat, and a cabbage across the river. The boat is tiny and can only carry one passenger at a time.
If he leaves the wolf and the goat alone together, the wolf will eat the goat. If he leaves the goat and the cabbage alone together, the goat will eat the cabbage.
How can he bring all three safely across the river?
Here is the domain template to get you started (available as wolf-goat-cabbage-domain- template from the webservice, with the places where you need to add your own definitions indicated by “…”):
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; domain for wolf, goat, cabbage problem ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (domain boat) (:requirements :strips)
;; THE PREDICATES
(:predicates
;; The key idea is that the overall state
;; of the world is modeled as ONE single predicate ;; with four arguments, namely the position
;; of each entitity, ordered as
;; wolf, goat, cabbage, and boat
;; This predicate represents the state
;; that is manipulated by the actions
;; e.g. the predicate (config w w w w) represents ;; the situation that wolf, goat, cabbage, and boat ;; are all located at the west bank
(config ?wolf ?goat ?cabbage ?boat)
;; This predicate represent all valid configurations ;; The actions need to make sure that only
;; valid configuration are ever created
;; i.e. that nothing gets eaten.
(valid ?wolf ?goat ?cabbage ?boat)
)
;; THE ACTIONS
;; Each action changes the state of the world, ;; in this example they will modify the
;; (config ?wolf ?goat ?cabbage ?boat) predicate
;; You should have (at least) four actions named
;; “move_wolf”, “move_goat”, “move_cabbage”, “move_empty”
;; with suitable parameters, preconditions, and effects
;; that enable the planner to find a solution to the problems ;; Here is a stub action definition to work from
;; (replace … by your definitions)
(:action move_empty :parameters (…)
:precondition (and …
) :effect
(and …
Make sure to fully understand the requirements, also by asking in the workshop. You find all required resources in the assessment section on blackboard, including link to the domain template and the problem files.
) )
)
Appendix B: Assessment Item 1.2 – Implementing a tournament analyser in Prolog
Your task is to write Prolog code that uses the bracket of possible matches at a football world cup tournament after the group stage has finished. Your code should analyse the structure of the tournament plan (the “bracket”). We will use the 2014 World Cup bracket:
You are given the following knowledge base in Prolog, which should be included in your solution: The predicate “team/1” introduces all teams that play in the round of 16. The
structure of the bracket itself is given by a predicate “game/4”. The predicate is used to describe the planned matches, so who plays in which named match. For a full definition of the knowledge base check the assessment item on blackboard, including further explanation. Also, make sure you resolve any questions in the workshop sessions.
% 16 teams:
team(brz).
team(chi).
team(col).
team(uru).
team(fra).
team(nga).
team(ger).
team(alg).
team(ned).
team(mex).
team(crc).
team(gre).
team(arg).
team(sui).
team(bel).
team(usa).
%
%
%
%
%
%
%
% Round of 16:
% For these the previous stage “PrevStage” was “group”,
% as we assume the groups stage has been played already,
% we can put the team names here as “PrevGame”.
describing the planned games: Who plays in which named match:
The predicate “game” has four arguments with the following meaning
game(PrevStage, PrevGame, ThisRound, ThisGame)
PrevStage: Indicates which round they are coming from PrevGame: Represents the game or team from the previous round ThisRound: Indicates the name of this round
ThisGame: The identifier of this game
% The round of 16 has 8 % in round “r16”.
game(group,brz,r16,g1). game(group,chi,r16,g1). game(group,col,r16,g2). game(group,uru,r16,g2). game(group,fra,r16,g3). game(group,nga,r16,g3). game(group,ger,r16,g4). game(group,alg,r16,g4). game(group,ned,r16,g5). game(group,mex,r16,g5). game(group,crc,r16,g6). game(group,gre,r16,g6). game(group,arg,r16,g7). game(group,sui,r16,g7). game(group,bel,r16,g8). game(group,usa,r16,g8).
games, represented as “g1”-“g8”,
Task A. Which games would a team play potentially play in?
Write a rule “playing/3” that determines if a team has the potential to play in a given match, given it would win all their previous matches.
Your rule must have this signature:
playing(Team, Round, Game).
with
“Team” representing the team,
“Round” the round the team play in, and
“Game” the game that team plays in that round
For instance, the queries
playing(ger,r16,g4).
and
playing(ger,r4,g2).
and
playing(ger,final,g1).
should all return “true”.
A query with variables like
playing(fra,R,G).
should return all rounds R and games G France could play in.
Your solution must use recursion to query the information given by the game/4 predicate.
Task B. Who could play whom and when?
Write a rule “plays/4” that determines when two teams could potential play against each other if they’d be winning their previous games.
Your rule must have this signature:
plays(TeamA, TeamB, Round, Game).
with
“TeamA” representing the first team of the query,
“TeamB” representing the second team of the query,
“Round” the round these teams would meet, and
“Game” the game these teams would meet at that round
For instance, the query
plays(ger,fra,R,G).
needs to return the round “R” and game “G” the teams could play against each other IF they would win their previous games.
NOTE: In order to get full marks you code needs to take into account that if two teams met in an earlier round (e.g. in the quarter finals), they won’t meet again in the later rounds (e.g. the semi- final).
Task C. Taking partial results into account to determine potential next opponents.
Extend your solution from B to be able to dynamically add information about match outcomes to your system. Do this by implementing a dynamic predicate “is_out” which is true if a team has been kicked out. Research the “dynamic” keyword in Prolog to implement this dynamic “is_out” predicate and modify you “plays/4” rule from task B so that it would only return matches that are still possible, e.g. a query like
assert(is_out(uru)), plays(ger,T,r2,_).
must NOT return Uruguay anymore.