Join GitHub today
GitHub is home to over 28 million developers working together to host and review code, manage projects, and build software together.Sign up
This assignment is to be carried out in groups of two or three students (please record the composition of your group via the online form announced on Blackboard before starting the assignment). The assignment consists of three parts and an optional part, described below.
Note: part 1 and 2 of this assignment are independent so if you have troubles solving part 1 you can move on to part 2 and then return to part 1.
Submission and marking guidelines
- The only Prolog files to be submitted are
12345is your candidate number -- all group members need to submit).
- If you aim for a mark of 70% you do not need to submit anything else. We will test your program on a number of random configurations, and you will get 70% if (for each not satisfied requirement we will deduct marks pro-rata):
- your program solves most of them,
- without running out of fuel,
- following more-or-less shortest paths,
- on grid sizes that are slightly larger or smaller than 20,
- without relying on the internals of the provided library, and
- fails whenever the task is not feasible.
- Additional marks can be gained by doing the optional part. If you want to claim additional marks, please submit a short report (up to 400 words) in PDF explaining what you have done to merit them.
- The following predicates should be implemented in each part (you must not change their arity):
- You need to set up the grid world by calling
start_game/0). After this, running your code should not require calling any other predicates except the predicates under 1.
- Your agent should not run out of energy when traveling the grid world with
solve_task/2and discovering its identity with
Part 1: Getting around (40%)
You need to be able to navigate a two-dimensional grid world populated by obstacles. Every move depletes your energy and so you frequently need to visit a charging station for a top-up. A basic depth-first search strategy is given but you need to improve this to get around efficiently.
Download the latest coursework file here to get started, unzip it and go to the root directory. Do not move or rename any files other than changing the candidate number in the answer files.
To run this assignment execute:
./ailp.pl assignment2 part1.
assignment2_12345.plcontains a simple backtracking search predicate
solve_task/2; you need to change this to apply A* search.
Update your candidate number in both filename and the
candidate_number/1predicate at the top of the file.
Assignment 2 library file (
ailp/library/oscar_library.pl) contains a simple command shell
shell/0which might make interaction easier (you can invoke it with
shell.), although you don't have to use it. Typing
help.in the shell gives you a list of shell commands and their Prolog equivalents.
In the lectures I demonstrated the following sequence of commands, which leave you out of energy without a charging station in sight so your only option is to
reset.(which corresponds to Prolog's
reset_game.) the board (you can reproduce this sequence of commands in the shell by typing
? reset. ! ok ? find(o(1)). ! [cost(5),depth(5)] ? ask(o(1),'What is the meaning of life, the universe and everything?'). ! 42 ? go(p(7,7)). ! [cost(9),depth(9)] ? energy. ! current_energy(76) ? position. ! current_position(p(7,7)) ? go(p(19,9)). ! [cost(64),depth(64)] ? energy. ! current_energy(12) ? position. ! current_position(p(19,9)) ? call(map_adjacent(p(19,9),P,O)). ! map_adjacent(p(19,9),p(19,10),empty) ! map_adjacent(p(19,9),p(20,9),c(3)) ! map_adjacent(p(19,9),p(19,8),empty) ! map_adjacent(p(19,9),p(18,9),t(48)) ? topup(c(3)). ? energy. ! current_energy(100) ? go(p(10,10)). ! This failed. ? energy. ! current_energy(0)
Querying the grid world happens through http by means of the predicate
possible_query/2in the file
ailp/library/oscar_library.pldefines the predicates you can use (see the module declaration at the top). Don't change this file!
The given grid world is 20 by 20, has four charging stations, one oracle and about 80 obstacles. Locations and numbers may change when testing your code. In part 3 the grid worlds will be randomly generated.
- The first step is to change backtracking search into agenda-based search. Where
solve_task_bthas an input variable
Currentyou need to change that to an agenda (a list).
- The format of
Currentin the given code is
Posis the current position,
RPathis the reverse path up to and including the current position, and
Costis the cost (i.e., number of steps) of reaching the current position.
- The agenda needs to hold a list of such structures. Children to be added to the agenda can be generated by an appropriate
- For A* search
Costwould be the F-value of a node, where F=G+H, G is the distance travelled, H is estimated by the Manhattan distance to the goal.
- Note that putting
Costat the front of the
[c(Cost,Pos)|RPath]structure ensures that
setof/3generates children in the order of increasing F-value, which is convenient because it simplifies adding the children to the agenda.
- I find it generally easiest to maintain both F- and G-values for each node on the agenda, which would lead to the structure
[c(F,G,Pos)|RPath]. You are free to modify these functors, as long as you do it consistently; as Prolog is an untyped language these functors are "declared" by usage.
- For tasks of the form
find(o(1))you don't know the location of the goal and so can't estimate H; in this case your search strategy should be breadth-first search so that you still find an optimal path. This could be achieved by setting H=0 for all children of the current position.
Part 2: Identity crisis (10%)
You know you are a famous actor or actress at the forthcoming Academy Awards ceremony -- but you have forgotten which one! Oracles can give you clues about your identity. The file
wp_library.pl located in the
ailp/library directory defines a Prolog interface to Wikipedia. For example, the following query lists all links found on a particular Wikipedia page:
?- wp('Peter Flach',WT),wt_link(WT,L),writeln(L),fail. Sneek University of Bristol Sneek Computer science Professor Artificial Intelligence Department of Computer Science, University of Bristol University of Bristol Universiteit Twente PhD Universiteit van Tilburg data mining machine learning Category:1961 births Category:Living people Category:Artificial intelligence researchers Category:Dutch computer scientists Category:British computer scientists Category:Machine learning researchers Category:People from Sneek Category:University of Twente alumni Category:Tilburg University alumni Category:Academics of the University of Bristol false.
(Note: this is a particular Prolog technique called a failure-driven loop.)
To run this assignment execute:
./ailp.pl assignment2 part2. Every time
wp_library.pl is loaded it will assert a random secret identity from among those enumerated by
actor/1. You can find out information about this secret identity by means of
agent_ask_oracle(oscar,o(1),link,L)., which will return a random link
L from the secret identity's Wikipedia page (actually, from a specific subset enumerated by
Your mission, should you choose to accept it, involves the implementation of a predicate
find_identity/1 (located in the file
assignment2_wp_12345.pl) which repeatedly calls
agent_ask_oracle(oscar,o(1),link,L) and deduces the secret identity by a process of elimination. You can test your code by means of the query
test., which iterates through all possible secret identities.
Hint: with the given code to query Wikipedia this is easier than it may sound: my solution has less than 20 lines of Prolog code.
Part 3: Identity crisis, continued (20%)
Now you need to adapt
find_identity/1 to work in the grid world. Running the assignment with
./ailp.pl assignment2 part3 will create random 20 by 20 grid worlds with 10 oracles, 2 charging stations and up to 100 obstacles. You can get a random link from each oracle that will help you to deduce the secret identity as before. The catch is that each oracle can be queried only once. Furthermore, querying the oracle costs 10 units of energy, so you need to keep your energy levels topped up (at the start and after each top-up your energy level is 100).
- Run the assignment with
./ailp.pl assignment2 part3.
find_identity/1to navigate around the grid world, find oracles and ask for random links.
- It is a good idea for your agent to maintain an internal memory of where it has seen oracles and charging stations, so that it can easily navigate to the nearest charging station and (unvisited) oracles.
query_world/2API includes an
agent_check_oraclequery which succeeds if your agent has already queried this oracle.
- The worlds are entirely randomly generated, which means that some worlds are unsolvable (e.g., you may not be able to leave the starting position). Also, the oracles are independent and often give you a link you already knew, so sometimes you don't know your identity even after visiting all oracles.
Part 4: Optional (30%)
You will need to navigate a dynamic world, as some of the obstacles, oracles and charging stations may be moving around, and the world may contain additional agents. It is likely that your previous A* search will fail whenever the agent finds its planned path blocked by a moved object or another agent. So the minimum I'm looking for here is robustness in your search and the ability to re-plan when necessary.
- To run the assignment execute:
./ailp.pl assignment2 part4.
start. % press start in the web browser join_game(G). % if you want more than one agent open another terminal window, % run assignment2 part4 and execute `join_game(G).` reset_game. % after this no further agents can join start_game.
- Objects in the world can move around in a random fashion. The parameters controlling this can be changed in the file