Artificial 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 Artificial 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 effort spent on the assignment for each unit should be approximately equal, being roughly equivalent to 1.5 working weeks each.
Academic Offences: Academic offences (including submission of work that is not your own, falsification of data/evidence or the use of materials without appropriate referencing) are all taken very seriously by the University. Suspected offences will be dealt with in accordance with the University’s policies and procedures. If an academic offence 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 offence. 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 significantly 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, 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 significantly 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 briefly 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 efficiently find shortest paths from an agent’s position to specified 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 find 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 reflections 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 files (where 12345 stands for your student number) along
with the associated grid configurations, a quick-start guide to running the code, and the relevant marking criteria:
Overview
Part 1
Part 2
Part 3
solution predicate
solve_task/2
find_identity/1
solve_maze/0
submission filename
cw_12345.pl
cw_12345_wp.pl
cw_maze_12345.pl
grid size:
20
15-25 (odd or even)
11-31 (odd only)
visibility
initially visible
initially visible
initially hidden
energy
initially 100
but is reduced by 1 unit per move and
10 units per query
initially /4 but is reduced by 1 unit per move and
10 units per query
not applicable!
# agents
1
1
1-10
# oracles
1
1-10
0
# chargers
4
2-4
0
# obstacles
~80
~80-100
~ /2
easy way
to run code
./ailp.pl cw part1
start. .
shell.
setup.
demo.
./ailp.pl cw part2
start. .
join_game(A).
reset_game.
start_game.
find_identity(ID).
./ailp.pl cw part3
start. .
join_game(As,4).
reset_game.
start_game.
solve_maze.
2n
2n ≤ =
n
Example
Drawing
Drawing
Drawing
Task
A* search for tasks find(Obj)/go(Pos)
visit oraces to find secret actor id
lead all agents out of the maze
Marking Criteria (5 marks each)
* minimising moves * minimising time
* indirect paths
* edge cases
* good coding
* maximise oracles * minimising moves * minimising time
* edge cases
* good coding
* one agent
* three agents * multi agents * end game
* time taken
Table 1: Quick-start Guide for Parts 1-3.
⚠
The code in the table above assumes a Linux installation (but alternative commands for Windows and alternative ways of running the code are given later in the document). Please note that you will need to hit “run” in the GridWorld browser window that will appear (or nothing else will happen until you do)!
⚠
Remember to rename the default skeleton submission files 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 benefit from your experiences all the other Parts 1-3.
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 reflecting 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
As there is no dependency between Part 2 and Part 3, you may start work on either or both of these after you have made progress in Part 1.
i
Note that an introductory guide to interactive and declarative logic program debugging was provided in a forum post from the 27th of October, 2020.
i
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.
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 clarification on the coursework questions.
⚠
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.
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 files (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 files until the deadline – at which point standard Faculty late penalties will apply (to the submission as a whole).
3 GridWorld Library
A Zip file containing the GridWorld library files and skeleton submission files should be downloaded from Blackboard and unzipped on your working machine. These files 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 define, the library predicates they’ll need to call, and the files 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 files (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 files if you wish!
⚠
Remember that 12345 should be replaced by your (7-digit) student number.
⚠
Note that, in this documentation, predicates are often annotated with their respective arities (name/arity) and arguments are often annotated with their intended modes (+Input, -Output or ?Partial). As explained in the SWI manual these arity and mode decorations should not be typed in any actual code!
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%)
Drawing
Drawing
Drawing
part3 part1 part2
cw_12345_report.pdf
PART 4 (25%) Short Report
Figure 1: Overview of part/file/predicate dependencies and grid configurations
The above dependencies are set up by a file loader ailp.pl that allows you to run the different parts of the assignment from the command line. After moving to the library root folder (containing ailp.pl file) you should run the following command:
}3,2,1{ ∈ n
on a Linux machine type ./ailp.pl cw part in a bash terminal (if necessary, after first making the file 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:
Command
Meaning
?-start. .
start web-server
?-join_game(-A).
add a new agent to the game (returns integer ID of agent e.g. 1 each time you call it)
?-reset_game.
(re-)initialise the grid (and stop the game if it is running)
?-start_game.
begin the game
n
n
n
n
n
i
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
Meaning
?-leave_game.
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 significantly reduce the amount of typing required and will also print some helpful messages (to the Prolog console and GridWorld window):
Macro
Meaning
?help.
% display a list the macros below
?stop.
% exit from this command shell
?setup.
?-join_game(A),reset_game,start_game.
?reset.
?-reset_game,start_game.
?whoami.
?-my_agent(A)
?position.
?-my_agent(A),get_agent_position(A,P)
?energy.
?-my_agent(A),get_agent_energy(A,Energy).
?topup(+Stat).
?-my_agent(A),agent_topup_energy(A,Stat).
?ask(+Orac,+Qu).
?-my_agent(A),agent_ask_oracle(A,Orac,Qu,Ans).
?call(+G).
?-findall(G,call(G),L).
?search.
?-search_bf % Lab Search
?go(+Pos).
?-solve_task(go(Pos),Cost). % Part 1
?find(+Obj).
?-solve_task(find(Obj),Cost). % Part 1
?demo.
?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
?identity.
?-find_identity(ActorName). % Lab Identity, Part 2
?maze.
?-solve_maze. % Part 3
Table 3: Possible shell macros.
i
Note how the shell prompt “?” omits the dash in the standard Prolog prompt “?-“.
i
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)define 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!
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 figure, 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-first 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!
Drawing
Drawing
Terminal output GridWorld output
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 (with one or more agents) are illustrated below – using either the built-in demo (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:
setup.
start. .
remember to hit “run” in browser window
start web-server and open browser window
start running the grid simulation
SHELL
<.......... :
:
<..:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
: demo. : : :
:..........
TERMINAL
shell.
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
join_game(A).
reset.
reset_game.
start_game.
find( (1) ).
solve_task(find( (1) ) ).
::
:
go(p(10,10) ).
solve_task(go(p(10,10) ) ).
energy.
my_agent(A), agent_current_energy(A,E).
:
:
stop shell a
: : : : : : :
stop.
remove current agent from game
stop web-server
leave_game.
stop.
remember to close your browser window
halt.
Figure 3: Different ways the user can run a GridWorld session
exit from Prolog
⚠
Once a game has started, you will need to run reset_game (which will implicitly stop the game) if you want to join up more agents to the game.
⚠
Don’t forget to use make and reset_game after you make changes to your code (and you may also need to refresh your browser window).
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 find all solutions of the specified goal).
☒
If you want to make your head hurt, try running call(shell) from within the shell!
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 significant 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
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.
i
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)
Parts 1-3 of this coursework all involve you navigating one or more agents around square grids of various sizes and configurations in order to solve different 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 offsets (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 identifier of the corresponding object):
Term
Colour
Object
Meaning
a(N)
random
agent
a user-controllable agent is located at this position (colour and shape chosen at random)
empty
green
empty space
an agent adjacent to this cell can move here at a cost of 1 energy unit
c(N)
orange
charge station
an agent adjacent to this cell can top its energy back up to its original level
o(N)
red
oracle
an agent adjacent to this cell can ask the oracle a question at a cost of 10 energy units
t(N)
black
thing
these represent “walls” or “obstacles” that your agent cannot move through
unknown
grey
hidden
an agent will need to visit an adjacent cell to reveal the contents of this cell (in Part 3)
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 define specific predicates to solve different tasks, as detailed in the following sections. Of course, you are welcome to consider
alternative static and dynamic variations of these task definitions and grid configurations 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 specified 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-off 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-tested predicate definition is in the correct file 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 definitions 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 flow 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
Part 1 of the coursework (worth 25%) requires you to write path finding code for a single agent on a square grid of some integer size between 15-25 containing 2-4 charging stations, 1-10 oracles and about 80-100 obstacles. Each move will cost one unit of energy, but the agent’s energy can be topped up to a pre-set maximum value of /4 by visiting any of the charging stations (any number of times).
To provide you with a stable environment for debugging, the Part 1 library will always set up the exact same demo configuration depicted below for 1 agent (white) on a 20`x`20 grid (green) with 4 charging stations (orange), 1 oracle (red) and 84 obstacles (black). In this scenario, the agent will always start in the top left corner at position p(1,1) with the maximum possible 100 units of energy. In the following figure the agent is at the point in the demo where it has moved to location p(7,7):
The standard grid configuration for Part 1
The point of Part 1 is to write code that enables your agent to (efficiently) find a (short) path from its current location to a specified cell or object. More specifically, you will
i
Run Part 1 using ./ailp.pl cw part1 (Linux) or swipl ailp.pl cw part1 (Windows)
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.
n
2n
need to write a predicate solve_task(+Task,-Cost) that solves Tasks of the form shown below:
Task
Meaning
go(?Pos)
execute a path to a grid position that unifies 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 one containing an object that unifies with Obj (which, if set to c(1) or o(X), would 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 – defined 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). Your solution should make use of the following library predicates (some of which should be familiar from Lab Search) to interact with the grid:
Predicate
Meaning
my_agent(-A)
returns integer ID of the first 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 defined as Dist = x1- x2 + y1-y2
lookup_pos(+Pos,-Obj)
return Object located at given Position
agent_current_energy(+A,-Energy)
return Agent’s current energy
agent_current_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)
run a sequence of moves on the grid (or fail at the first point where a move is found to be invalid)
say(+Message,+A)
print Message next to the current Agent on the grid
Table 4: Library Predicates for Part 1.
|
|||
Your skeleton submission file cw_12345.pl contains an initial version of solve_task/2 which finds (poor) solutions with a (naive) backtracking depth-first search solve_task_dfs/3 that uses the predicate achieved/2 to detect goal states, as defined 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-first 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
If the location of the target is known (as in a ground go task) then the Manhattan distance is an excellent A* heuristic, but if it’s not (as in a find task) then the constant 0 is also a monotonic heuristic which will reduce A* to a breadth-first.
i
You may use the built-ins sort/2 and ord_union/3 for sorting a list and merging two sorted list, 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) – thereby avoiding the situation in the demo where the skeleton code runs out of fuel.
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) and a suite of hand-crafted edge cases (subject to the general conditions stated at the start of Part 1). Your code will be marked according to the following 5 criteria (relative to the baseline skeleton code you were given):
up to 5 marks for minimising the number of moves made when executing direct paths in the standard and random grids (as would be ensured by breadth-first search);
up to 5 marks for minimising the amount of time taken when finding direct paths in the standard and random grids (as would be ensured by A* search);
up to 5 marks for also being able to find 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 very tricky or unusual edge cases that will be set up on specially hand-crafted grids;
up to 5 marks for demonstrating good coding practice.
i
Since there is a significant time cost associated with GridWorld interactions, such querying a cell’s contents or moving an agent (which are all done via http), there is likely to be a strong correlation between the first two criteria and an A* search strategy is likely to perform very well, in practice, on this task.
i
As well as testing your code on the standard Part 1 demo (above), you are advised to run (a copy of) your code on the random grids of Part 2 (below) to get a better idea of your code performs in wider variety of sizes and configurations.
5 Part 2
Part 2 of the coursework (worth 25%) involves you writing route planning code for grids conforming to the same requirements as Part 1. To provide you with a varied
i
Run Part 2 using ./ailp.pl cw part2 (Linux) or swipl ailp.pl cw part2 (Windows)
environment for debugging, the Part 2 library will always set up a different random configuration 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 81obstacles (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 figure below it started at 5,12 and visited 4 oracles.
Figure 5: A representative grid configuration 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 finding 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:
find_identity/1 will need to be defined 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 first 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-finding more complex)
But you will only be able to ask each oracle one question;
Each time you query an oracle, it will cost 10 units of energy;
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.
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):
Predicate
Meaning
init_identity/0
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/0
Test that find_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 cost 10 units of energyif Qu=link then the oracle will return ) cost=10
agent_check_oracle(+A,+Orac)
check if Agent has already visited 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 finding 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 file cw_12345_wp.pl provides the following initial version of find_identity/1 adapted from Lab Identity which (sometimes) finds (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):
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 effort 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-off 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 find 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;
up to 5 marks for demonstrating good coding practice.
6 Part 3
In part 3, the grid configuration and the task you need to solve is very different 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 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 (at 31,31 in the following figure) where it must call the leave_maze(+A) predicate:
Example maze configuration 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 (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 from view (denoted by the term unknown and a grey colour) until some agent is first moved onto an adjacent cell. Thus, the only way to find information about the maze is by moving through it.
i
Run Part 3 using ./ailp.pl cw part3 (Linux) or swipl ailp.pl cw part3 (Windows)
⚠
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.
n
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 agent 1 to p(1,1) and agent 2 to p(2,2). An example of a batched request is given below.
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 that allows you to specify the number of agents you want to add. This and many other library predicates are summarised 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 first 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
☒
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.
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
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.
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 asigned a unique id from the digits 1-10.
i
It is possible to join more agents after the game has started BUT you will need to run reset_game from outside the shell or call(reset_game) from inside the shell in order to allow this.
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 find 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 time of individual runs. The grid size MUST be odd or else it will never successfully generate.
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).
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 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 effective use of them. This means agents will explore different 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 efficiency 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 briefing 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 artificial 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 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 waffle, 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 first 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 flee) 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 different techniques without being able to describe each one to any great extent.
formatted by Markdeep 1.11
✒