05/12/2020 Artificial Intelligence Coursework (COMS30012)
Arti cial Intelligence Coursework (COMS30012) Boiler-plate Text · Coursework Brief · GridWorld Library · Part 1 · Part 2 · Part 3 · Part 4
This document provides an overview of and guidelines for the coursework assessment option (COMS30012) on the 3rd year Arti cial Intelligence (AI) unit (COMS30014) in the 2020 academic year. What follows is the boiler-plate text (Section 1) applying to all 3rd year courseworks, followed by a coursework brief (Section 2), an introduction of the relevant features of the GridWorld library (Section 3) and breakdown of the four individual parts you will need to submit: Part 1 (Section 4) – Part 4 (Section 7).
1 Boiler-plate Text
Deadline: The deadline for submission of all optional unit assignments is 13:00 on Friday 11th of December. Students should submit all required materials to the “Assessment, submission and feedback” section of Blackboard – it is essential that this is done on the Blackboard page related to the “With Coursework” variant of the unit.
Time commitment: The expectation is that students will spend 3 full working weeks on their two assignments. The e ort spent on the assignment for each unit should be approximately equal, being roughly equivalent to 1.5 working weeks each.
Academic O ences: Academic o ences (including submission of work that is not your own, falsi cation of data/evidence or the use of materials without appropriate referencing) are all taken very seriously by the University. Suspected o ences will be dealt with in accordance with the University’s policies and procedures. If an academic o ence is suspected in your work, you will be asked to attend an interview with senior members of the school, where you will be given the opportunity to defend your work. The plagiarism panel are able to apply a range of penalties, depending the severity of the o ence. These include: requirement to resubmit work, capping of grades and the award of no mark for an element of assessment.
Extenuating circumstances: If the completion of your assignment has been signi cantly disrupted by serious health conditions, personal problems, periods of quarantine, or other similar issues, you may be able to apply for consideration of extenuating circumstances (in accordance with the normal university policy and processes). Students should apply for consideration of extenuating circumstances as soon as possible when the problem occurs,
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 1/35
05/12/2020 Artificial Intelligence Coursework (COMS30012)
using the following online form. You should note however that extensions are not possible for optional unit assignments. If your application for extenuating circumstances is successful, it is most likely that you will be required to retake the assessment of the unit at the next available opportunity.
Implications of UK “travel window”: The UK Government will be instigating a “travel window” to allow students return home from University once UK national restrictions have been lifted. This will take place between the 3rd and 9th of December and as such, will occur during the optional unit assignment period. Students whose work is signi cantly impacted by extended periods of travel and quarantine during this period should apply for extenuating circumstances. As discussed previously, extensions are not possible for optional unit assignments. If your application for extenuating circumstances is successful, it is most likely that you will be required to retake the assessment of the unit at the next available opportunity.
2 Coursework Brief
This coursework comprises 4 equally weighted parts that are brie y outlined below (and explained in more detail in subsequent sections of this document):
Part 1 (25%) involves you extending Lab Search with an A* algorithm in order to more e ciently nd shortest paths from an agent’s position to speci ed cells or objects without running out of energy in grids containing walls, oracles and charging stations;
Part 2 (25%) involves you integrating Part 1 with Lab Identity to plan complex routes that enable your agent to consult as many oracles as possible, topping up its energy as required, in order to nd a secret actor identity;
Part 3 (25%) involves you coordinating the movement of multiple agents in order to explore and solve an initially hidden maze by guiding each agent from an “entrance” point near the top left to an “exit” point at the bottom right;
Part 4 (25%) is a more open-ended exercise that involves writing a short report where you consider (at a conceptual level rather than an implementation level) potential extensions of and re ections upon your solutions to the above tasks.
The following table provides a brief overview of the three coding Parts 1-3 showing the submission predicates and les (where 12345 stands for your student number) along with the associated grid con gurations, a quick-start guide to running the code, and the relevant marking criteria:
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 2/35
05/12/2020
Artificial Intelligence Coursework (COMS30012)
Overview Solution
predicate
Submission lename
Grid size: Visibility
# Agents
# Oracles
# Chargers # Obstacles
Position
Energy
How to run
Example
Task Marking
Part 1 solve_task/2
cw_12345.pl
20
initially visible 1
1
4
~80
start in top left
max=100 initial=100%
but is reduced by
1 unit per move and 10 units per query
./ailp.pl cw part1
start. .
shell.
setup.
demo.
Part 2 find_identity/1
cw_12345_wp.pl
15-25 (odd or even) initially visible
1
1-10
2-4 ~80-100
start at random
max= /4 initial=50-100%
but is reduced by
1 unit per move and max/10 per query
./ailp.pl cw part2
start. .
shell.
setup.
identity.
Part 3 solve_maze/0
cw_maze_12345.pl
11-31 (odd only) initially hidden 1-10
0
0
~ /2
start in top left
exit at bottom right
not applicable!
./ailp.pl cw part3
start. .
join_game(As,4).
reset_game.
start_game.
solve_maze.
2n
2n
†
n
Use A* search to solve tasks of form: find(Obj) ; go(Pos)
* minimising moves
visit and query oracles to nd secret actor id
* maximise oracles
lead all agents out of the maze
* one agent
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 3/35
05/12/2020
Artificial Intelligence Coursework (COMS30012)
Criteria (5 marks each)
* minimising time * indirect paths
* edge cases
* good coding
* minimising moves * minimising time
* edge cases
* good coding
* three agents * multi agents * end game
* time taken
Table 1: Quick-start Guide for Parts 1-3.
Please note that you MUST hit “run” in the GridWorld browser window that will open (or nothing will happen until you do)! See later in this document for alternative ways of running the code in Linux and Windows
Remember to rename the default skeleton submission les above by replacing the number 12345 with your actual student number (a 7-digit number that is not the same as your candidate number or your user id)!
You are advised to tackle the parts in the order they are listed above as the level of guidance deliberately decreases as you progress through Parts 1-4. Moreover, Parts 2 and 3 both build upon the insights and code you develop in Part 1; and Part 4 will bene t from your experiences all the other Parts 1-3.
i
This coursework assumes you have a running version of SWI Prolog and a working knowledge of logic programs obtained by working through Chapters 1-6 & 10-11 of the recommended Learn Prolog Now! tutorial. You should have studied the slides and videos for the Prolog I-III lectures (including material in the relevant lab intros and Q&A sessions) and worked through all three Prolog labs (including re ecting on the example solutions). You should be familiar with the web-server and Wikipedia functionality of the GridWorld library and you should be comfortable editing and running programs in SWIPL as well as using the online manual and the built-in debugger.
i i
†
⚠
⚠
As there is no dependency between Parts 2&3, you may start work on either or both of these after you’ve made some progress on (but not necessarily completed) Part 1. Similarly, you may begin working on Part 4 after making some progress on (but not necessaarily completing) Parts 1-3.
Note that an introductory guide to interactive and declarative logic program debugging was provided in a forum post from the 27th of October, 2020.
Note that swipl comes with a built-in editor (written in Prolog) which has very good syntax highlighting and debugger integration (though its interface looks outdated and its copy-paste behaviour in non-standard). It can be invoked with the edit command or by selecting File->Edit if using swipl-win on Windows.
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 4/35
05/12/2020
Artificial Intelligence Coursework (COMS30012)
Note that, in this documentation, predicates are often annotated with their respective arities (name/arity) and arguments are often annotated with their intended modes (+In, -Out or ?Any These arity and mode decorations should not be typed in any actual code – there are included in the documentation to show how the predicates should be used. As explained in the SWI manual:
an input argument (+) must be instantiated to a correctly typed term when the predicate is called,
an output argument (-) will become instantiated (if it wasn’t already) when the predicate succeeds,
and partial arguments (?) may be variable, ground or partially instantiated when the predicate is called and/or succeeds.
Please note that (SWI built-in and GridWorld library) predicates are only guaranteed to work properly (or even at all) when used in the correct way!
You should treat this coursework as a individual take-home open-book time-limited extended-exam. The questions will be released at the end of Week 7 – where we will give a high-level tour of the GridWorld library in the Q&A (6pm on Thursday) and release this brief in Blackboard (1pm on Friday). Your answers should be submitted in Blackboard by the end of Week 10 (1pm on Friday). You should work by yourself and without assistance from each other or TAs. We will continue running weekly Prolog Clinics during the old lab slot on Wednesdays 9-11am, where you come to ask for generic advice on SWI Prolog and the GridWorld Library, as well as for clari cation on the coursework questions.
i
The deadline for this coursework is 13:00 on Friday (the 11th of December) of Week 10. Answers should be submitted in Blackboard by uploading exactly 4 les (corresponding to the four respective parts) named as follows: cw_12345.pl, cw_12345_wp.pl, cw_maze_12345.pl and cw_12345_report.pdf (where 12345 should be replaced by your student number). Note that you may overwrite your les until the deadline – at which point standard Faculty late penalties will apply (to the submission as a whole).
Joint-honours students (e.g. those doing Maths and CS) are also welcome to attend the drop-in clinics as they may have a di erent workload pro le which means they may wish to go over some other aspects of the taught content.
Since we cannot explicitly help you write coursework solutions, any technical queries may have to be re-cast at a more conceptual level; and where the content of any discussion is deemed of interest to the wider cohort, we may post a summary of any such points on the (coursework) unit forum.
⚠
⚠
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 5/35
05/12/2020 Artificial Intelligence Coursework (COMS30012)
3 GridWorld Library
A Zip le containing the GridWorld library les and skeleton submission les should be downloaded from Blackboard and unzipped on your working machine. These les extend and supersede the library code from the earlier Prolog labs (which means that many of the exported predicates should already be familiar to you). The following diagram provides an overview of the key dependencies between Parts 1-4 of the coursework, the user predicates they’ll need to de ne, the library predicates they’ll need to call, and the les where everything is or needs to be located. Note that:
plain rectangles show library modules (with the exported predicates you may use); round rectangles show parts of the assignment (along with their weighting); semi-round rectangles show the les (and predicates) you’ll need to modify.
i
In this coursework, you will not need to look at the library code or understand how it works – although you are welcome to look inside the given les if you wish!
Remember that 12345 should be replaced by your (7-digit) student number.
⚠
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 6/35
05/12/2020 Artificial Intelligence Coursework (COMS30012)
game_predicates.pl command_channel.pl www_browser.pl http.pl
oscar_library.pl
wp_library.pl
ailp_grid_size/1 ailp_grid_size/1 my_agents/1 my_agent/1
get_agent_position/2 get_agent_position/2
test/0
link/1 actor/1 wp/1 wp/2 wt_link/2 init_identity/0
cw_wp_12345.pl find_identity/1
agent_adjacent/3 map_adjacent/3 map_distance/3
agent_do_moves/2 agents_do_moves/2
lookup_pos/2 leave_maze/1
cw_maze_12345.pl solve_maze/0
get_agent_energy/2 map_adjacent/3 map_distance/3
agent_do_moves/2 say/2
lookup_pos/2 agent_ask_oracle/4
agent_check_oracle/2
cw_12345.pl solve_task/2
PART 1 (25%) Simple Path-Search
: :
PART 3 (25%)
Multi-Agent Maze ……….. ailp.pl ……… Complex Route-Planning
PART 2 (25%)
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 7/35
05/12/2020 Artificial Intelligence Coursework (COMS30012)
part3 part1 part2
cw_12345_report.pdf
PART 4 (25%) Short Report
Figure 1: Overview of part/ le/predicate dependencies and grid con gurations
The above dependencies are set up by a le loader ailp.pl that allows you to run the di erent parts of the assignment from the command line. After moving to the library root folder (containing ailp.pl le) you should run the following command:
on a Linux machine type ./ailp.pl cw part in a bash terminal (if necessary, after rst making the le executable with the command chmod +x ailp.pl)
on a Windows machine type swipl ailp.pl cw part or swipl-win ailp.pl cw part in a cmd or powershell terminal; or double click on aipl.pl in an explorer window and type cw part at the Prolog prompt
To enable interaction with the user, the GridWorld provides the additional commands, shown below, to open and close a session. The commands in the top table allow the user to set up a local web-server, display the grid in a browser window, add one or more agents to the game, (re-)initialise the grid, and start the game running. This setup must be completed before the GridWorld library predicates can be called; The commands in the bottom table allow the user to remove agents from the game (one-by-one) and stop the web-server. These commands must be executed, at the Prolog prompt, in the order shown below:
When running the above commands, remember to replace the symbol by the actual digit (1, 2 or 3) representing the required part number:
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 8/35
n
⚠
nn
n
}3,2,1{ ∈ n
n
05/12/2020
Artificial Intelligence Coursework (COMS30012)
Command ?-start. .
?-join_game(-A).
?-reset_game.
?-start_game.
Meaning
start web-server
add a new agent to the game and return its integer ID (e.g. 1) – only 1 agent allowed in Parts 1 and 2
(re-)initialise the grid (and stop the game if it is running) begin the game
i
☒ Don’tforgettousemakeandreset_gameafteryoumakechangestoyourcode(and you may also need to refresh your browser window).
The extra ” .” after the “start.” command can be optionally used to accept the dialog box which asks the user whether to “open in browser window (y/n)”
Remember to hit “run” in the browser window after starting the web-server (or nothing else will happen until you do)!
⚠
Command ?-leave_game.
Meaning
remove (the current) agent from the game
?-stop.
stop web-server
Table 2: commands to start (top) and end (bottom) a GridWorld session.
In order to further facilitate user interaction during a session, the GridWorld also provides an interactive user shell that can be invoked with the following command that allows the user to run the set of macros listed below (which are especially useful for Parts 1 and 2):
Command Meaning
?-shell. open interactive shell that provides the following macros
i
Note that, while you are not required to use the shell in this coursework, the following macros can signi cantly reduce the amount of typing required and will also print some helpful messages (to the Prolog console and GridWorld window):
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 9/35
05/12/2020
Artificial Intelligence Coursework (COMS30012)
Macro
?help.
?stop.
?setup.
?reset.
?whoami.
?position.
?energy.
?topup(+Stat).
?ask(+Orac,+Qu). ?-my_agent(A),agent_ask_oracle(A,Orac,Qu,Ans).
?call(+G).
?search.
?go(+Pos).
?find(+Obj).
?demo.
?identity.
?maze.
?-findall(G,call(G),L).
?-search_bf % Lab Search ?-solve_task(go(Pos),Cost). % Part 1 ?-solve_task(find(Obj),Cost). % Part 1
?reset, find(o(1)), ask(o(1),’What is the meaning of life, the universe and everything?’), go(p(7,7)), energy, position, go(p(19,9)), energy, position, call(map_adjacent(p(19,9),_P,_O)), topup(c(3)), energy, go(p(10,10)), energy. % Part 1
?-find_identity(ActorName). % Lab Identity, Part 2 ?-solve_maze. % Part 3
i i
Table 3: Possible shell macros.
Note how the shell prompt “?” omits the dash in the standard Prolog prompt “?-“.
Notice how some of these macros refer to the user predicates solve_task/2, find_identity/1 and solve_maze/0 that you’ll need to (re)de ne in Parts 1, 2 and 3 – so you can use the shell to help you test the behaviour of your code.
Note that the above commands and macros should not themselves be used in any code you submit as they are only there to help you run and test that code!
Meaning
% display a list the macros below
% exit from this command shell ?-join_game(A),reset_game,start_game. ?-reset_game,start_game.
?-my_agent(A) ?-my_agent(A),get_agent_position(A,P) ?-my_agent(A),get_agent_energy(A,Energy). ?-my_agent(A),agent_topup_energy(A,Stat).
⚠
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html
10/35
05/12/2020 Artificial Intelligence Coursework (COMS30012)
The easiest way to get a feel for how the GridWorld works is to run the Part1 demo (that was illustrated in the week 7 Q&A) and involves the following sequence of main operations:
1. reset the game and execute a path to oracle 1;
2. ask oracle 1 “What is the meaning of life, the universe and everything?”; 3. execute a path to position 7,7;
4. execute a path to position 19,9;
5. verify that the agent is adjacent to charge station 3;
6. top up the agent’s energy;
7. execute a path to position 10,10 (default code fails!).
As you can see from the following gure, because your agent has a limited supply of energy which gets used up as it moves around and queries oracles, and because it only comes with a naive depth- rst search algorithm, by default the agent runs out of energy on this last task – which is an outcome that you’ll need to change as you work through this coursework!
Terminal output GridWorld output
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 11/35
05/12/2020 Artificial Intelligence Coursework (COMS30012)
Figure 2: Result of running Part 1 Demo with Skeleton Code
The simplest way to run the demo is with the following sequence of commands which will allow you to easily step through the complete command sequence by just repeatedly pressing the
?- start. . ?- shell.
? setup.
? demo.
Various other ways of running the demo are illustrated below – using either the built-in demo macro (centre), or running the constituent shell macros individually (left), or calling their corresponding GridWorld library expansions (right):
i
The vertical alignment and extent of each box is intended to show the correspondence between the macros and their constituents or expansions:
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 12/35
05/12/2020 Artificial Intelligence Coursework (COMS30012)
start. .
remember to hit “run” in browser window
start web-server and open browser window
start running the grid simulation
join at least one agent with command join_game/1 or (shell) macro setup/0
<..... join new agent : up to the game
......
setup the grid (and stop game if already started)
start the game
SHELL
<.......... :
:
<..:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
TERMINAL
. ... shell. ...
.
setup.
join_game(A).
:
:
:
:
: :..........
reset.
demo.
reset_game.
start_game.
find( (1) ).
solve_task(find( (1) ) ).
:: :
go(p(10,10) ).
solve_task(go(p(10,10) ) ).
energy.
my_agent(A),
get agent energy(A,E).
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 13/35
05/12/2020 Artificial Intelligence Coursework (COMS30012)
get_agent_energy(A,E).
stop.
leave_game.
<.... . .....
remove current agent from game
stop web-server
stop.
remember to close your browser window
exit from Prolog
Figure 3: Some di erent ways the user can run the GridWorld demo
halt.
i
You can enter and leave the user shell at any time; and you can run non-shell commands from within the shell by wrapping them up as an argument to a call macro - which will implicitly nd all solutions of the speci ed goal. If you want to make your head hurt, try running call(shell) from within the shell!
The dotted lines show some ways you can add more agents to the game (applicable in Part 3 which is not restricted to one agent). To do this after the game has started (by a call to start_game or one of the macros setup, reset or demo), you'll need to run a precise sequence of commands comprising a reset_game, one or more join_game, another reset_game and a start_game. The rst reset_game is needed to stop the game before more agents can be added (or you'll get an error). To do this from the shell you'll need to explicitly run call(reset_game) as the macro reset also calls start_game which sets the game running again.
☒
Make sure the game is not paused in the browser when you call reset_game or the server may hang due to feature (or bug) in the way http responses may be
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 14/35
⚠
05/12/2020
Artificial Intelligence Coursework (COMS30012)
sequenced.
Although you won't need to exploit this fact in the coursework, the library allows multiple clients to interact with the server over http via an internal predicate query_world/2 that enables one or more Prolog threads running on your machine to join agents to a game, move them around and query the grid. The only thing you need to know is that, because this all happens over http, calls that involve looking up the contents of a cell or moving an agent will have a signi cant time overhead as compared to standard Prolog queries.
One of the main ways of speeding up your code (and potentially gain marks) will be to avoid unnecessary interaction with grid - such as by executing short paths and not querying the contents of unnecessary cells.
i i
Parts 1-3 of this coursework all involve you navigating one or more agents around square grids of various sizes and con gurations in order to solve di erent tasks (illustrated in Figure 1). In all of these tasks, agents may move one step at a time to any empty adjacent (on-grid) cell to the immediate South, East, North or West of the current position (with multiple possibilities being returned in that order). The location of each cell in the grid is represented by a Prolog term p(X,Y) where X and Y are natural numbers denoting the horizontal and vertical o sets (rightwards and downwards) from the top left corner. The contents of each cell in the grid is represented by exactly one of the following Prolog terms (where N is an integer identi er of the corresponding object):
⚠
During program development, you are welcome to use SWI built-ins from the statistics library such as statistics(+Key,Value) with the Key cputime` to run some empirical tests on the execution time of various GridWorld queries.
You may also look at http interactions in your browser by looking in the networking tab of the dev menu for your web browser. This can usually be opened using F12. An example of the requests made to the web browser at a given timestep is shown below:
Figure 4: Example http request for agent 1 (blue) to moving to p(1,3)
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 15/35
05/12/2020
Artificial Intelligence Coursework (COMS30012)
Term Colour a(N) random
empty green c(N) orange
o(N) red t(N) black
unknown grey
Object agent
empty space
charge station
oracle
thing hidden
Note that
is to round its argument up to the nearest integer (i.e. towards positive in nity).
Although the GridWorld library supports the random movement of walls, oracles and charge stations, Parts 1-3 will all be restricted to static grids where only agents will be allowed to move. Moreover, in order to help you test your code and get a realistic estimate of its performance, Parts 1-3 will all impose strict restrictions on the number of various objects in grid and will ask you to de ne speci c predicates to solve di erent tasks, as detailed in the following sections. Of course, you are welcome to consider alternative static and dynamic variations of these task de nitions and grid con gurations in Part 4.
The marking of Parts 1-3 will be mainly carried out by an auto-tester that will take into account several marking criteria speci ed in the following sections. For each criterion, you will gain from 1 mark for a basic solution (that provides some slight improvement over any baseline code) up to 5 marks for (near-) optimal solutions. In cases where there might be a potential trade-o between two or more of the objectives, their respective priorities will be stated in order of importance (primary, secondary, etc); and your mark for any higher priority criteria will serve as an upper bound on your mark for any lower priority criteria (as well helping to adjust the expected performance).
To avoid losing marks, you should take care not to over-optimise low priorities at the expense of high priorities. Before submission, you should also double check that any auto-
i
represents the Prolog ceiling function which can be used within an
Meaning
a user-controllable agent is located at this position
(colour and shape chosen at random)
an agent adjacent to this cell can move here at a cost of energy unit
an agent adjacent to this cell can top its energy up to the maximum value (which is 100 units on the standard 20×20 grid)
an agent adjacent to this cell can ask the oracle (at most) one question at a cost of
(which is 10 units on the standard 20×20 grid)
these represent “walls” or “obstacles” that your agent cannot move through
an agent will need to visit an adjacent cell to reveal the contents of this cell (in Part 3)
⌉01/xame⌈ = ksae
⌉4/2n⌈ = xame
1 = vome
⌉.⌈
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 16/35
05/12/2020 Artificial Intelligence Coursework (COMS30012)
tested predicate de nition is in the correct le with the correct name and arity. While you are free to write any helper predicates you like (with names and arities of your choosing) you should ensure all of your code only make calls standard SWI built-ins or explicitly exported library predicates (as any attempt to modify or expose other library de nitions won't work on the auto-marker).
As good coding practice is part of the marking scheme you are strongly advised to: comment your code to explain the meaning of each argument and the behaviour of each predicate; format your code to make the logical ow clear (using informative variable and predicate names); test your code to make sure it compiles without errors and that predicates terminate properly which means that wherever possible they should be (semi-)deterministic in the sense that they should terminate after succeeding once (or failing). You should especially try to avoid non-termination and run-time exceptions or predicates that return duplicate solutions or leave unnecessary choice points.
4 Part 1
i
Part 1 of the coursework (worth 25%) requires you to write path nding code that allows a single agent on a square grid to e ciently navigate to a speci ed cell or object (charging station or oracle) without running out of energy.
To provide you with a stable environment for debugging, the Part 1 library will always set up the same demo con guration depicted below for 1 agent (white) on a 20×20 grid (green) with 4 charging stations (orange), 1 oracle (red) and 84 obstacles (black); where the agent always starts in the top left corner at position p(1,1) with a 'full tank' of 100 unit of energy.
Each move will cost 1 unit of energy, and each oracle the agent visits can be queried, at most once, at a cost of 10 units of energy. But the agent's energy can be topped up back to maximum value of 100 by visiting any of the charging stations (any number of times).
Run Part 1 using ./ailp.pl cw part1 (Linux) or swipl ailp.pl cw part1 (Windows)
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 17/35
05/12/2020 Artificial Intelligence Coursework (COMS30012)
Standard grid con guration for Part 1: after agent has visited o(1) and moved to p(7,7)
The point of Part 1 is to write code that enables your agent to (e ciently) nd a (short) path from its current location to a speci ed cell or object. More speci cally, you will need to write a predicate solve_task(+Task,-Cost) that solves Tasks of the form shown below:
i
If your agent runs out of energy when it is not adjacent to a charging station, then no further moves are possible and your only option will be to reset the game.
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 18/35
05/12/2020 Artificial Intelligence Coursework (COMS30012)
Task
Meaning
go(?Pos)
execute a path to a grid position that uni es with Pos (which, if set to p(4,5) or p(X,6), would leave the agent at position 4,5 or the nearest accessible cell in row 6, respectively)
find(?Obj)
execute a path to a grid position adjacent to an object that uni es with Obj (which, if set to c(1) or o(X), should leave the agent next to charge station 1 or the nearest accessible oracle, respectively)
The predicate solve_task/2 should either succeed after executing a path to the target (and returning the cost of the path - de ned as the number of moves made) or it should simply fail if the task is not feasible (because obstacles prevent it from reaching the goal or because it would run out of energy in the way). Your solution should make use of the following library predicates (some of which should be familiar from Lab Search) to interact with the grid:
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 19/35
05/12/2020 Artificial Intelligence Coursework (COMS30012)
Predicate
Meaning
my_agent(-A)
returns integer ID of the rst Agent which joined to (but was not subsequently removed from) the game
map_adjacent(+Pos,-Adj,-Obj)
given a grid Position, return any Adjacent on-grid cell location along with the Object it contains (or the term empty)
map_distance(+Pos1,+Pos2,-Dist)
given two cell locations Pos1=p(x1 ,y1) and Pos2=p(x2,y2), returns Manhattan (taxi-cab) Distance de ned as Dist = x1-x2 + y1-y2
lookup_pos(+Pos,-Obj)
return Object located at given Position (n.b. cannot be used the other way around to return Position of a given Object!)
get_agent_energy(+A,-Energy)
return Agent's current Energy
get_agent_position(+A,-Pos)
return Agent's current Position
agent_topup_energy(+A,+Station)
top up Agent's energy at charge Station
agent_do_moves(+A,+Path)
execute sequence of moves in given Path to Agent on grid (or fail at the rst point where a move is found to be invalid)
say(+Message,+A)
Table 4: Library Predicates for Part 1.
print Message next to the current Agent on the grid (maybe useful for debugging?)
Note that lookup_pos/2 with modes lookup_pos(+Pos,-Obj) must have an instantiated rst argument when you call it. So, given a Position, it returns an Object, not vice versa.
Although you, the user, will be able to see the layout of the grid in the browser window, please remember your agent can only obtain that information by making calls to the relevant cells using map_adjacent/3 or lookup_pos/2 (which are comparatively expensive as they operate over http). Thus, the tasks of e ciently nding an optimal path to a given location or nding the location of a given object are non-trivial (given the restrictions imposed by the above mode declarations):
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 20/35
|||
|
⚠ ⚠
05/12/2020 Artificial Intelligence Coursework (COMS30012)
Your skeleton submission le cw_12345.pl contains an initial version of solve_task/2 which nds (poor) solutions with a (naive) backtracking depth- rst search solve_task_dfs/3 that uses the predicate achieved/2 to detect goal states, as de ned below:
solve_task(Task,Cost) :-
my_agent(A), get_agent_position(A,P),
solve_task_dfs(Task,[P],[P|Path]), !,
agent_do_moves(A,Path), length(Path,Cost).
solve_task_dfs(Task,[P|Ps],Path) :-
achieved(Task,P), reverse([P|Ps],Path)
;
map_adjacent(P,Q,empty), \+ member(Q,Ps),
solve_task_dfs(Task,[Q,P|Ps],Path).
achieved(Task,Pos) :-
Task=find(Obj), map_adjacent(Pos,_,Obj)
;
Task=go(Pos).
You will need to replace the above solve_task_dfs/3 by a new predicate (with your choice of name and arity) that implements an appropriate A* search strategy. The easiest way to do this is by the following three consecutive steps:
First substitute solve_task_dfs/3 by a breadth- rst search predicate which can be easily adapted from the search_bf/2 of Lab Search by simply: adding an extra argument to store the Task; and calling achieved/2 instead of complete/1.
Then convert your predicate into an A* search that sorts the agenda using a score obtained by summing the distance of a node from the start with its Manhattan distance to the target (if its location is known) or with the constant 0 (if it's not).
Finally you'll need to adapt your code to take into account the agent's available energy and also gives it the ability to refuel at charging stations along the way, if necessary.
i
Recall that the scoring function
agenda is the sum of the actual cost
and an (optimistic) heuristic estimate
location of the target is known in advance (as in a ground go task), then setting to the Manhattan distance will result in A* nding optimal paths (around any intervening walls) while querying relatively few cells on average. But, if the location of the target is unknown (as in a find task), then setting will revert A* back to a plain breadth- rst search, which is about as good as one can do, on average, in random grids (for the reasons in the next box).
used to the order the nodes in an A* from the start position to the current node of the cost from here to a goal. Thus, if the
i
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 21/35
0=h h
h
g h+g=f
05/12/2020
Artificial Intelligence Coursework (COMS30012)
i
You may use the built-ins sort/2 and ord_union/3 for sorting a list and merging two sorted lists, respectively. You may also use the built-ins var/1 and ground/1 to check if a term is a variable or if it is variable-free.
If there is no (in)direct route from the current position to the target using the current energy, then solve_task/2 should fail (without moving at all) - thereby avoiding the situation in the demo where the skeleton code runs out of fuel.
In Part 1, you should not worry about the agent's energy level at the goal. You should simply execute a shortest possible path to the goal - even if it means the agent wouldn't have enough energy to subsequently reach another charging station in order to top itself up again.
Note that any a-priori attempt to nd the location of an object (by grid search or random sampling) in order to use directed (Manhattan) A* for more e cient path nding will most likely result in querying more cells than needed by blind (breadth- rst) A* to return an optimal path in the rst palce! This is because breadth- rst search is guaranteed to only query cells reachable by the agent (as opposed to disconnected islands - such as cells 14 and 15 in the rst row of the standard grid) and it can also be used to non-deterministically return paths to objects in order of closeness) when solving queries like sove_task(find(c(X))).
Your Part 1 code will be tested on the standard demo grid (generated by the Part 1 library code) along with a number of random test grids (generated by the Part 2 library code - in which the grid size and the number or location of objects may di er slightly) and a suite of hand-crafted edge cases (subject to the same restrictions stated in Part 2, below). Your code will be marked according to the following 5 criteria (relative to the baseline skeleton code):
up to 5 marks for minimising the number of moves made when executing direct paths in the standard and random grids;
up to 5 marks for minimising the amount of time taken when nding direct paths in the standard and random grids;
up to 5 marks for also being able to nd and execute indirect paths that allow agents to reach distant targets by refuelling at one or more charge stations en-route;
up to 5 marks for correctly handling some tricky or unusual edge cases that will be set up on specially hand-crafted grids;
up to 5 marks for demonstrating good coding practice.
As the number of moves made will be minimised by both breadth- rst and A*
search, you will gain all of the marks for a correct implementation of either of
i
†† †
†
⚠ ⚠
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html
22/35
05/12/2020
Artificial Intelligence Coursework (COMS30012)
i
As the time-taken will be dominated by calls to agent_do_moves and map_adjacent (which have a signi cant http overhead), You will gain most of the marks for a correct implementation of A* search - which will minimise the time of agent_do_moves by returning optimal paths and, assuming no major coding ine ciencies (like adding duplicate nodes to the agenda), will also reduce the number of map_adjacent calls on average. You should be able to verify this by ensuring each task in the standard demo nishes in a few seconds (as opposed to minutes or hours). While further optimisation is possible (e.g. by remembering the contents of previously seen cells) the gains will be diminishing and small tweaks to save a few hundred milliseconds won't worth the e ort.
As well as testing your code on the standard Part 1 demo (above), you are advised to also run your code on the random grids of Part 2 (see below) to get a better idea of your code performs in wider variety of con gurations. Note that your Part 1 code will automatically be imported when you invoke Part 2 and you are welcome to run the standard demo - even though some of the tasks may now fail (as they become edge cases) in the random grid con gurations.
these (or an equivalent); And you should be able to get a good idea if your paths are optimal by simply running the standard demo.
5 Part 2
i
Part 2 of the coursework (worth 25%) involves you writing route planning code for a single agent on randomly generated square grids of integer size between 15-25 with 2-4 charging stations, 1-10 oracles and about 80-100 obstacles. The cost of a move is still
unit of energy; the agent's energy can still be topped up to its maximum by visiting any charging stations (any number of times); and each oracle the agent visits can still be queried at most one. But, now, the maximum energy is de ned more generally as
(which is still 100 on a 20×20 grid); the cost of querying an oracle is de ned more generally as (which is still 10 on a 20×20 grid); and the agent will start at a random position with a random energy that is between 50-100% of .
You should ensure your code works out the appropriate starting values and costs in both Part 2 and Part 1 (and does not rely on hard-coded integers for these).
Run Part 2 using ./ailp.pl cw part2 (Linux) or swipl ailp.pl cw part2 (Windows)
xame
n
⌉01/xame⌈ = ksae
⌉4/2n⌈ = xame 1 = vome
††
⚠
⚠
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 23/35
05/12/2020 Artificial Intelligence Coursework (COMS30012)
To provide you with a varied environment for debugging, the Part 2 library will always set up a di erent random con guration like the one shown below for 1 agent (pink) on a 20`x`20 grid (green) with 2 charging stations (orange), 10 oracles (red) and 81 obstacles (black). In these scenarios, the agent will start with random energy at a random position on a grid with size between 15 and 25. In the gure below it started at 5,12 and visited 4 oracles.
Figure 5: A representative grid con guration for Part 2
The point of Part 2 is write code that allows your agent to plan complex routes that visit as many oracles as possible via as many charge stations as necessary in order to maximisie your chances of nding a secret actor identity by asking each oracle to return a random link from that actor's Wikipedia page. This task can be seen as an integration of Part 1 with the Lab Identity, except that:
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 24/35
05/12/2020
Artificial Intelligence Coursework (COMS30012)
nd_identity/1 will need to be de ned in cw_wp_12345.pl not in cw_12345.pl or lab_identity_12345.pl
Instead of the special agent “oscar”, you will use a regular agent that you join to the game (whose id is returned when you rst called join_game(A) or when you later call my_agent(A));
You will have to physically move your agent next to an oracle to ask it a question (which may not always be possible due to obstacles or energy constraints); There are now several oracles (which makes path- nding more complex)
But you will only be able to ask each oracle one question;
Each time you query an oracle, it will cost some energy (one tenth of the maximim) to do so;
As oracles are independent, they may repeat a link (answer) that you had already previously been given;
Thus, sometimes, you may fail to determine your identity even after visiting the maximum possible number of oracles.
The randomness of the grid may mean some oracles are not accessible.
You will need to write a predicate find_identity(-ActorName) that executes a path to as many oracles as possible and either returns the secret actor's name, if it can be determined, or returns the term unknown if it cannot. In addition to earlier Part 1 predicates in Table 4, you will need the following additional library predicates for Part 2 (most of which should be familiar to you from Lab Identity):
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 25/35
05/12/2020 Artificial Intelligence Coursework (COMS30012)
Predicate
Meaning
init_identity
Randomly select a new identity, this should only be used for testing purposes
wt_link(+WT,-Link)
Bind Link to a link inside the supplied WikiText
wp(+Q)
Retrieve the text from the Wikipedia page titled Q and print to stdout
wp(+Q,-WT)
As above, but instead of printing it will bind the text to WT
actor(-A)
Bind A to one of the 12 possible actors
link(-L)
Bind L to one of the 15 possible links
test
Test that nd_identity(A) succeeds for each possible actor
agent_ask_oracle(+A,+Orac,+Qu,- Ans)
return Oracle's Answer to Agent's Question (requires Agent to be adjacent to Oracle and costs 1/10 of max energy). If Qu=link then the oracle will return a random link from the secret actor's Wikipedia page
agent_check_oracle(+A,+Orac)
check if Agent has already queried this Oracle
Table 5: Additional Library Predicates for Part 2.
The primary aim of Part 2 is to maximise the number of oracles that you visit (as that gives you the best chance of nding your identity); The secondary aim is to minimise the number of steps in the solution; and the tertiary aim is to minimise the execution time.
Your skeleton submission le cw_12345_wp.pl provides the following initial version of find_identity/1 adapted from Lab Identity which (sometimes) nds (poor) solutions by (naively) using solve_task/2 from Part 1 to execute paths to consecutive oracles in turn (without considering how much fuel is available):
Note that, unlike in Lab Identity, test should only succeed in nding the identity of a few actors, as your agent can query each oracle at most one once now!
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 26/35
†
†
⚠
05/12/2020 Artificial Intelligence Coursework (COMS30012)
actor_has_link(L,A) :-
actor(A), wp(A,WT), wt_link(WT,L).
eliminate(As,A,K) :-
As=[A], !
;
solve_task(find(o(K)),_), !,
my_agent(N),
agent_ask_oracle(N,o(K),link,L),
include(actor_has_link(L),As,ViableAs),
K1 is K+1,
eliminate(ViableAs,A,K1).
find_identity(A) :-
findall(A,actor(A),As), eliminate(As,A,1).
To get a feel for the problem you could initially try to implement either a brute force method that tries to enumerate all possible valid paths (of which there are many as you may need to visit the same charging station more than once) or a greedy approach that aims towards the closest unvisited oracle (or heads to a charging station whenever the energy goes below some threshold).
By thinking carefully about potential edge cases, you should be able to see that a brute force approach is very expensive, while a greedy approach will often lead to sub-optimal solutions (both in terms of path length and the number of oracles visited). Therefore, you need to decide how much e ort you are willing to invest in developing a more intelligent solution (as you will most likely start to experience diminishing returns and a potential trade- o between the marking criteria).
To speed up your code, you may wish to keep an internal memory of previously discovered oracles and chargers so you may quickly direct your agent to a nearby charging station or (unvisited) oracle. You can also consider various ways of keeping track of the energy such as looking for a charger whenever it goes below some threshold (that you could consider empirically testing to nd a good value). More intelligent approaches are obviously possible, but will take longer to develop and test.
Your mark for Part 2 will be determined by testing your code on a series of random grids generated by the library itself (which means you can get a good feel of how well your code is doing) along with a suite of hand-crafted edge cases (all of which satisfy the general conditions stated at the beginning of this section).
up to 5 marks for the primary aim of maximising the number of oracles visited; up to 5 marks for the secondary aim of minimising the number of moves made; up to 5 marks for the tertiary aim of minimising the time taken;
up to 5 marks for correctly handling edge cases on hand-crafted grids;
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html
27/35
05/12/2020 Artificial Intelligence Coursework (COMS30012)
up to 5 marks for demonstrating good coding practice. 6 Part 3
i
In part 3, the grid con guration and the task you need to solve is very di erent from Parts 1 and 2. The game is now played with 1-10 agents on square grids whose size is given by an odd number between 11-31 and which is populated by empty cells and walls (with no oracles or charging stations). Each grid represents a maze in which there is exactly one path between any two (empty) cells and the width of every such path is exactly one cell wide. The goal is to navigate each of your agents from a starting location near the top left corner to an exit position in the bottom right corner (i.e. at 31,31 in the following gure) where it must call the leave_maze(+A) predicate:
Run Part 3 using ./ailp.pl cw part3 (Linux) or swipl ailp.pl cw part3 (Windows)
n
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 28/35
05/12/2020 Artificial Intelligence Coursework (COMS30012)
Example maze con guration for Part 3
Agents can still move to an immediately adjacent cell (South, East, West or North) but there is no longer any cost associated with making a move; and there are no oracles or charging stations to visit - so you don't need to worry energy in this part! However, the situation is complicated by the fact that the contents of each cell is now initially hidden (denoted by the Prolog term unknown and represented by a grey square in the browser) until some agent is initially placed or subsequently moved onto an adjacent cell. Thus, the only way your agents can nd a path through the maze is by physically moving through it to see what is there.
i
Once an agent has unhidden the contents of a cell (by virtue of being located on an adjacent cell), then each and every agent in the game will henceforth be able to query the contents of that cell.
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html
29/35
05/12/2020 Artificial Intelligence Coursework (COMS30012)
i
Note that as soon as one of your agents has found the exit, no further exploration of the maze is necessary due to the tree property, mentioned above, that there is only one path between any two points in the maze.
This means there will be much more emphasis on moving multiple agents a single step at a time than on moving a single agent multiple steps. For this reason, Part 3 provides the predicate agents_do_moves/2 so that many agents can each move up to one step in the same tick on the server. For example, agents_do_moves([1,2],[p(1,1),p(2,2)]). would move a(1) to p(1,1) and a(2) to p(2,2). In general, this predicate behaves as if the moves of the respective agents had been carried out, from head to tail, in the order they are presented in the list. But, instead of executing the moves on successive hypothetical ticks, they are all batched into one actual tick (potentially allowing must faster movement). An example of a such batched server request is shown below. If any move fails, the o ending agent will stay in place and any remaining moves will be still be attempted.
Figure 6: Example batched request moving 4 agents in a single timestep
The Part 3 library code also allows you add an extra argument to agent_join_game so you can easily specify the number of agents you want to add; and it allows you to get a list of their IDs using get_agents. It also makes available a new predicate agent_adjacent/3 that behaves exactly like map_adjacent, but given an agent as input as opposed to a position. Finally, there is the new predicate agent_leave_maze which allows the an agent to leave the
Please note that when agents are located close together, the ordering of the lists in agents_do_moves may be important - e.g. if one agent must be moved before another can take space it just vacated.
Because (most of) the maze is initially hidden, any code you wrote for Part 1 (and Part 2) may not work directly in Part 3 as map_adjacent/3 and lookup_pos/2 may now return `unknown'.
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 30/35
⚠
⚠
05/12/2020 Artificial Intelligence Coursework (COMS30012)
maze (if it is located in the bottom right corner). A summary of the available library predicates is given below:
Queries
Meaning
agents_do_moves(+As,+Moves)
simultaneously make each Agent in Agents perform the corresponding Move in Moves.
agent_do_moves(+A,+Moves)
As before, although due to the world being concealed this may be less useful
map_adjacent(+Pos,-AdjPos,-
Obj)
This predicate is still imported, although it is slightly less useful with the presence of unknown cells
agent_adjacent(+Agent,-
AdjPos,-Obj)
similar to map_adjacent, but takes in an agent rather than a position
lookup_pos(+Pos,-Obj)
Return the object at Pos, if known
my_agent(-A)
This predicate is stil included and is true if A is the rst agent stored internally. It is best to avoid using this predicate for this section
my_agents(-As)
Binds A to a List of all agents in the current terminal
join_game(+As,+N)
Join N Agents to the game and store the ids in As
get_agent_position(+A,-P)
As before
leave_maze(+A)
Succeeds if A is at the bottom right corner, and makes A leave the game
ailp_grid_size(N)
Bind N to the height/width of the grid
i
The maze generator will always place one agent in the top left corner p(1,1) and will then place any subsequent agents next to a previously placed one. Each agent will be randomly assigned a unique id from 1-10.
☒
A query that attempts to add more than 10 agents to the game will NEVER succeed.
1. To run the assignment execute: ./ailp.pl cw part3.
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 31/35
05/12/2020 Artificial Intelligence Coursework (COMS30012)
2. Implement the predicate solve_maze/0, such that it controls all the agents in the game and leads them to the exit of the maze, then calls leave_maze
The skeleton code provided in cw_maze_12345.pl uses a helper function find_moves to identify moves for each agent at a given timestep. It is possible to extend this predicate to complete this task although it is not required. The provided skeleton code does not check that moves are actually possible nor does it leverage any information about the world, so there is a lot of room for improvement.
solve_maze :-
my_agents(Agents),
find_moves(Agents,Moves),
agents_do_moves(Agents,Moves),
solve_maze.
%%%%%%%%%%%%%%%% USEFUL PREDICATES %%%%%%%%%%%%%%%%%%
find_moves([],[]).
find_moves([A|As],[M|Moves]) :-
findall(P,agent_adjacent(A,P,_),PosMoves),
random_member(M,PosMoves),
find_moves(As,Moves).
i
Even though there is no explicit agent to agent communication, it is possible to communicate implicitly through arguments passed into predicates. For instance, it is possible to keep track of visited positions by adding a new argument to nd moves. To see a simple example of this, look back to how movement direction is communicated between steps of spiral in Lab 2.
i
Feel free to modify the grid size for testing by changing line 66 of game_predicates.pl in order to shorten the time of individual runs. The grid size MUST be odd or else it will never successfully generate.
Marks will be awarded as follows:
5 marks will be awarded for a solution which allows a single agent to successfully leave the maze making reasonable moves. This means that the agent will not
start. % Then press run in the web browser
join_game(As,1).
% if you want more than one agent then change 1 to any number up to 10
reset_game.
start_game. % after this no further agents can join, until the game is reset
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 32/35
05/12/2020
Artificial Intelligence Coursework (COMS30012)
repeatedly explore routes which it has determined lead to a dead end and it will successfully leave the maze once it gets to the end.
5 marks will be awarded for a solution that supports 3 agents and makes e ective use of them. This means agents will explore di erent paths and will ideally avoid dead ends discovered by each other. 3 agents forming a conga line and then exploring as though they were one would not be worth any marks for this section.
5 marks will be awarded for everything up to this point working with a variable number of agents, that can range from 1 to 10.
5 marks will be awarded if upon discovery of the end point by one agent, all the other agents navigate to it using near shortest paths.
5 marks will be awarded for e ciency of solutions in terms of runtime.
7 Part 4
In Part 4, you are required to write a short report (maximum 1000 words) considering how additional AI techniques (beyond those employed in the coursework so far) could be used to extend or improve the performance of the agents that you have coded in Parts 1, 2, and 3, in order to tackle real-world analogues of the kind of search problem that you have considered in the coursework so far.
For this part of the coursework, you are not required to code or implement any of these AI techniques or systems and you will not gain marks for including any code, or results from running any code, as part of your report. However, you may, if you think it improves your report, include pseudocode to help explain an AI algorithm, technique or system that you are discussing.
The report could be imagined to be a technical brie ng written for an engineering audience that is naive with respect to AI in general, but has seen how AI algorithms can be employed to solve the arti cial problems dealt with in Parts 1, 2, and 3, and is interested in how AI techniques could be employed to control autonomous agents to complete real-world search tasks.
Marks will be allocated as follows:
5 marks will be allocated for consideration of the strengths and shortcomings of the approaches used so far in Parts 1, 2, and 3. i.e., these marks are awarded based on your report's discussion of the extent to which the kind of algorithms developed during Parts 1, 2, and 3, may or may not generalise successfully to real-world search problems.
10 marks will be allocated for consideration of the relevance and rationale of/for a selection of additional AI approaches that you present i.e., these marks are awarded to
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 33/35
05/12/2020 Artificial Intelligence Coursework (COMS30012)
the extent that your report's arguments for and against the adoption of selected AI techniques for dealing with real-world versions of the types of problems considered in Parts 1, 2, and 3 are clear, compelling and creative.
5 marks will be allocated for consideration of the design and detail of these approaches i.e., these marks are awarded to the extent that the description and discussion of AI techniques is technically sound and demonstrates a good grasp of the way that they work
5 marks will be allocated for good writing and presentation. i.e., these marks are awarded to the extent that the writing is clear, concise, and articulate, the report is well structured and free from padding or wa e, and any diagrams, pseudocode, etc., are informative and well presented.
Note: Given the word limit, the report is not expected to be exhaustive in any sense. Rather it is expected to pick an angle and do a good job of considering that angle in detail and in depth. A deliberately under-described and incomplete list of possible “angles” that could be taken:
An adversarial version of the problem in which agents are competing with each other A version where agents have to both collaborate to learn from each other and compete with each other to maximise their individual rewards in scenario where the agent who solve the maze rst receive the highest reward
A repeated version of the problem
A dynamic version of the problem where obstacles, charging stations and/or oracle can move about randomly (or deliberately ee) from an approaching agent.
etc.
Note: The phrases “real-world versions of the types of problems considered in Parts 1, 2, and 3" or “real-world search problems” should be understood to mean resource-limited spatial search problems, e.g., search and rescue, environmental monitoring, etc. Feel free to consider one important real-world example in your report, or to consider a small number of related problems.
Note: The AI techniques that you select for discussion in the report could be techniques that were presented in any part of this unit, or techniques that were discussed in wider reading that you have undertaken. Show that you understand your selected techniques in terms of their general use and overall utility and also in terms of the detail of how they work. It may be best to focus on a relatively small number of techniques and do each one justice, rather than spread your report over many di erent techniques without being able to describe each one to any great extent.
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 34/35
05/12/2020 Artificial Intelligence Coursework (COMS30012)
formatted by Markdeep 1.11
https://www.ole.bris.ac.uk/bbcswebdav/pid-4563434-dt-content-rid-17773534_2/courses/COMS30012_2020_TB-1/AI-CW.html 35/35
✒