A* Search, Knowledge Representation, and Automated Planning

Artificial Intelligence and Intelligent Agents
Coursework 1
A* Search, Knowledge Representation, and Automated Planning
You should complete this coursework individually. Coursework 1 has three parts (A* search, knowledge
representation in Prolog, and automated planning using PDDL) and is worth 17.5% of your overall F29AI mark.
Details of what you should do and hand in, and how you will be assessed, are described below and on Canvas.
Part 1: A* Search problem description
The above grids represent two problem environments where an agent is trying to find a path from the start
location (S) to the goal location (G). The agent can move to an adjacent square provided the square is white or
grey. The agent cannot move to a black square which represents a wall. No diagonal movement is allowed. Moving
into a white square has a cost of 1. Moving into a grey square has a cost of 3.
What to do: Undergraduate students, 1-year Edinburgh postgraduate students, and all
Dubai postgraduate students (full time and part time)
Implement a solution to the grid problem using A* search. You have two programming language options for this
question: Java or Python. Starter code is provided for you in both languages.
Programming language option: Java
Starter code can be found in the package uk.ac.hw.macs.search, which is a set of classes that can be used to
represent a search problem. To implement a specific search problem, you will need to do the following:
1. Define a class that implements the State interface. This should include the following:
a. A method for determining whether a state is a goal state (isGoal())
b. A method for computing the heuristic value of a state (getHeuristic())
2. Define a class that implements the SearchOrder interface. This interface has one public method,
addToFringe, that is used to add a set of nodes to the frontier. You can use the costs and/or heuristic
values to determine the order that nodes are added to the frontier
The classes in the uk.ac.hw.macs.search.example package show examples of these two interfaces being used to
implement depth-first search and breadth-first search, as well as a simple integer-based state. The Main class in
this package shows an example of how to use the classes.To solve the problem, you will need to implement the following:
1. An encoding of the state in the grid by implementing the State interface appropriately, including
methods for detecting a goal state and computing a heuristic value. You should use the Manhattan
distance heuristic for generating heuristic values in your search.
2. A class implementing A* search by implementing the SearchOrder interface and implementing
addToFringe appropriately.
Programming language option: Java
A Python implementation of the Java classes has also been provided as an alternative to using Java: the file
hwu_search.py contains Python versions of the classes in uk.ac.hw.macs.search, while the file example.py
contains a Python version of the code from uk.ac.hw.macs.search.example. You should consult the Java source
files for full documentation of these classes.
If you choose to work in Python, you should follow the above two steps, but using the provided Python classes
and following the Python example: that is, you should implement an encoding of the state and heuristic in the grid
via the State interface, and an implementation of A* using the SearchOrder interface.
What to hand in
Test your code on the two grid problems provided by running A* search on them and capture the output. Submit
the code for the implementation as well as the output. Make sure your code includes appropriate comments in
the parts of the code you implemented. Do not change any of the classes in the uk.ac.hw.macs.search package or
the hwu_search.py file: we will test your implementation against the provided versions of these classes.
What to do: 2-year Edinburgh postgraduate students only
Provide a solution to the grid problem by applying A*search by hand. In particular, you should do the following:
1. Draw a graph (with nodes and edges) to represent each of the grid problems as a search problem. Label
each of the nodes in your graph and include appropriate costs on the edges.
2. Use the Manhattan distance heuristic and calculate appropriate heuristic values for each of the nodes in
your graph.
3. Apply A* search to each grid and list the final set of states expanded and the goal path for each grid. You
do not need to provide a full derivation for each search (unless you wish to do so), however, you should
provide at least the first 5 steps of each derivation with calculations for the f values to demonstrate you
understand the application of the A* algorithm in your graph.
What to hand in
Submit your answers in a report in PDF format. You do not need to write or submit any code.Part 2: Knowledge Representation problem description
A popular fictional monster battling game features a type system that is used to determine the effectiveness of a
monster’s ability to attack or defend against another monster. In this coursework you will write a short Prolog
program to represent knowledge about this system and to answer queries using the resulting knowledge base.
The version of the game we will use includes five monsters: annihilape, espathra, flamigo, lechonk, and
mabosstiff. Each monster can be one of five basic types: psychic, fighting, dark, ghost, and normal.
Each monster has four moves that it can use. Each move is also assigned one of the basic types. The details of
each monster, its type, its moves, and the move types are given in the following table:
Monster Monster type Move Move type
annihilape ghost lowKick
shadowPunch
rageFist
bodySlam
fighting
ghost
ghost
normal
espathra psychic psybeam
quickAttack
lowKick
shadowBall
psychic
normal
fighting
ghost
flamigo fighting lowKick
payback
megaKick
closeCombat
fighting
dark
normal
fighting
lechonk normal tackle
takeDown
zenHeadbutt
bodySlam
normal
normal
psychic
normal
mabosstiff dark snarl
lick
bite
bodySlam
dark
ghost
dark
normal
E.g., annihilape is a ghost type monster with 4 moves: lowKick (a fighting type move), shadowPunch (a
ghost type move), rageFist (a ghost type move), and bodySlam (a normal type move).
The effectiveness of a monster’s move when used on another monster depends on the move type (of the
monster using the move) and the monster type (of the monster the move is being used on). Certain moves are
strong against certain types of monsters while other moves are weak or superweak against other monster
types. The effectiveness of a move type against a monster type is represented in the following table:
move \ monster psychic fighting dark ghost normal
psychic weak strong superweak ordinary ordinary
fighting weak ordinary strong superweak strong
dark strong weak weak strong ordinary
ghost strong ordinary weak strong superweak
normal ordinary ordinary ordinary superweak ordinary
E.g., a fighting type move is weak against psychic type monsters but a dark type move is strong against
ghost type monsters. Combinations that aren’t strong, weak, or superweak are ordinary.What to do
Write a Prolog program to represent the knowledge in the monster game according to the following specification:
1. Encode information about the monsters and their moves using Prolog facts of the following form:
− basicType(t): to represent the idea that t is a basic type.
− monster(mo,t): to represent the idea that mo is a monster of type t.
− move(mv,t): to represent the idea that mv is a move of type t.
− monsterMove(mo,mv): to represent the idea that monster mo has a move mv.
2. Encode effectiveness information using Prolog facts of the form typeEffectiveness(e,t1,t2): a
move of type t1 used again monsters of type t2 has effectiveness e.
3. Encode basic effectiveness relationships using Prolog facts of the form moreEffective(e1,e2): e1 is
more effective than e2. You should only encode the strict ordering on effectiveness in this way, i.e.,
strong is more effective than ordinary, ordinary is more effective than weak, and weak is more
effective than superweak.
4. Encode transitive effectiveness information using a Prolog rule of the form
moreEffectiveThan(E1,E2): E1 is more effective than E2. The rule should cover the basic
effectiveness information above but also information not represented by the facts in part 3, e.g., strong
is more effective than weak, ordinary is more effective than superweak, etc. E1 and E2 should be
variables in your rule definition.
5. Define a Prolog rule called monsterMoveMatch(T,MO1,MO2,MV) which represents the idea that
monster MO1 and monster MO2 both have a move MV which has type T. MO1, MO2, MV, and T should be
variables in your rule definition.
6. Define a Prolog rule called moreEffectiveMoveType(MV1,MV2,T) to represent the idea that move
MV1 is more effective than move MV2 against monsters of type T. MV1, MV2, and T should be variables in
your rule definition.
7. Define a Prolog rule called moreEffectiveMove(MO1,MV1,MO2,MV2) to represent the idea that if
monster MO1 performs move MV1 against MO2, and monster MO2 performs move MV2 against MO1, then
MV1 is more effective than MV2. MO1, MV1, MO2, and MV2 should be variables in your rule definition. Note
that the monsters should actually be capable of performing their respective moves.
NOTE: For parts 4-7 of the specification, ensure that you write Prolog rules. You should not implement Prolog facts
as your solution for these parts and you will lose marks if you do this. However, it is okay if need to write multiple
rules for each definition. If you are interested, the game mechanics in this coursework are based on information
from https://pokemondb.net/.
What to hand in
• Prolog program file: Submit a single Prolog program file with all your Prolog facts and rules. Ensure that
the file is a plain text file with the name monster.pl or monster.pro. Make sure there are comments in
your program file to describe the different parts of your program.
• Output file: Test your program by selecting a series of Prolog queries to demonstrate the various facts and
rules you have implemented. Capture the queries and output to a text file. Include at least 10 queries in
your output file. Ensure that the file is a plain text file with the name output.txt.Part 3: Automated Planning problem description
Heriot-Watt Underwater has decided to continue its exploration activities in the sea. Mission operations will be
controlled by plans generated using an automated planner that will direct the activities of personnel and
underwater vehicles. The area of operation is divided into a series of grid-based locations involving land and
water. A command centre, which acts as a base of operations, is in one of the water locations near the land.
Several types of personnel serve at the command centre, including engineers, scientists, and pilots. The main
activities are performed by advanced subs, which can travel underwater and perform various types of exploration
and construction tasks. All personnel and subs initially begin at the command centre. Some of the operations of
the underwater mission are described in the following list (which isn’t exhaustive):
1. Each location in the area of operation can be either land, shallow water, or deep water.
2. A sub can only move in shallow or deep water and must have a pilot on board in order to move. A sub can
only move to an adjacent location from its current location (i.e., it may take multiple moves to reach
distant locations).
3. Subs are big enough to carry two people at a time.
4. Subs can carry at most one construction kit at a time: a structure kit or an energy cable kit. Kits can be
loaded or unloaded to/from subs by engineers at the command centre.
5. A sub can perform two types of underwater scans. A sub can perform a subsea survey of a location, to
make sure the location is safe for construction. A sub can also perform a more intensive research scan of a
location, to gather data for further analysis. A scientist must be on board the sub to perform a scan and
only one type of scan can be performed at a time.
6. A tidal power generator can be constructed by a sub provided the location has been surveyed and an
engineer is on the sub. A tidal power generator can only be built in shallow water in a location adjacent to
land. The sub must be carrying a structure kit which is used up by constructing the power generator.
7. An offshore energy cable can be installed by a sub in a water location (deep or shallow) provided the
location has been surveyed and an engineer is on the sub. An energy cable can only be installed in a
location provided the location is adjacent to a tidal power generator or another energy cable. The sub
must also be carrying an energy cable kit, but the kit can be reused any number of times.
8. An underwater research base can be constructed by two subs operating in the same deep water location.
The location must have been surveyed and both subs must have engineers on board. An offshore energy
cable must also be in the location before the research base can be built. Each sub must also be carrying a
structure kit which is used up by constructing the research base.
9. Some locations of shallow and deep water are marine protected areas. Subs are permitted to travel
through marine protected areas, but no construction or installation of offshore energy cables is permitted
in a marine protected area.
10. Personnel can move between the command centre and a sub, or an underwater research base and a sub,
provided the command centre/research base and sub are in the same location.
11. The results of a research scan can be transferred from a sub into the computer system of an underwater
research base if the sub is at the same location as the base. The results of a research scan can be analysed
by a scientist at an underwater research base if the results have been transferred to the base computers.
12. A sub has a protective energy shield that can be turn on or off by the pilot.
13. Several locations are home to a kraken. If a sub passes through a location with a kraken without having its
energy shield on, then the sub will be destroyed by the kraken.
14. If two underwater research bases are operational then a special sonar array can be turned on by an
engineer at one of the bases. The sonar array confuses any kraken, allowing subs to pass through a
location with a kraken, even if their energy shield is turned off.
15. All personnel, subs, and kits start at the command centre. The command centre must be situated in a
water location adjacent to a land location. There are a finite number of personnel, subs, and kits. No tidal
power generators, offshore energy cables, or underwater research bases are initially built/installed. At
least one location must contain a kraken and at least one location must be a marine protected area.
At the start of operations, the command centre is given a series of missions to complete that involve setting up
structures and analysing particular locations in the area of operation.What to do: all students
1. PDDL implementation: You must model the underwater exploration domain in PDDL by defining the
properties, objects, and actions that are needed to describe the domain. Note that the planning domain is
described at an abstract level and is somewhat incomplete, with certain pieces of information missing.
You must make design decisions as to how you will represent the knowledge and actions necessary to
encode this scenario as a planning problem. Some requirements are more difficult than others. It is
strongly recommended that you try to implement the domain incrementally, ensuring that some parts of
the domain work correctly before moving on to others. Use the example domains from the PDDL lectures
as a starting point for your solutions. You may also find that the planning time increases as you add more
complexity. You may have to consider whether an alternative knowledge representation leads to a better
solution. You may use the planning tools available at http://editor.planning.domains/, the Fast Forward
(FF) planner, or the Fast Downward planner. You should ensure that your solution works with one of these
planners. Note that the performance of certain planners may outperform that of the web-based planner.
Do not use any features of PDDL that we have not covered in the course. Make sure you test your
solution on a series of different problem scenarios. Include comments in your PDDL files to describe
important sections of your code. You do not need PDDL features that we have not covered in the course.
2. PDDL report: Write a short report (maximum 2 pages) briefly discussing how you structured your domain.
Show the different types of locations in your domain and the location of the command centre. Also list in
your report the particular problem instances you have included in your code and what planner you have
used to test your domain/problems. The report will be used by the markers to help understand your code.
What to do: 1-year Edinburgh postgraduate students and all Dubai postgraduate
students (full time and part time)
In addition to the above instructions for all students, 1-year Edinburgh postgraduate students and all Dubai
postgraduate students (full time and part time) should design an additional feature in PDDL to add to the domain
(e.g., new personnel that can perform some task, a new activity, etc.) that isn’t included in the above domain
description. Add this feature to your domain and test it. Your new features should not simplify or remove any of
the existing requirements. Include a description of the additional feature in your report (maximum 1 extra page).
What to hand in: all students
• PDDL source files: Submit your PDDL source files consisting of a single domain file and at least 4 different
problem files. Make sure your source files have comments describing the properties and actions you’ve
defined. Your solution should illustrate the different scenarios that are supported by your domain. You
should aim for comprehensive scenarios that support multiple missions in each problem file. Your source
files will be checked for plagiarism and tested to see if they are operational. For 1-year Edinburgh
postgraduate students and all Dubai postgraduate students (full time and part time): one of the problem
files must test your additional feature.
• PDDL report: Submit your report as a PDF file. Your report will be checked for plagiarism.
Declaration of Authorship: Students are also required to sign and include a standard declaration of
authorship with each submission. This is a mandatory part of the assessment submission. Links to the
standard declaration can be found on the Canvas site for F29AI.Deadlines
The deadline for submitting Coursework 1 (all parts) is Thursday, 26 October 2023. Submissions are due by 15:30
(Edinburgh time) for the Edinburgh Campus, 23:59 (Dubai time) for the Dubai Campus, and 17:00 (Malaysia time)
for the Malaysia Campus. Details on how to submit your coursework will be posted on Canvas.
Feedback
Individual written feedback will be provided to students approximately three working weeks after the submission
of Coursework 1.
Additional notes
This is an individual coursework assignment. All submitted files will be checked for plagiarism. You must confirm
to the naming conventions described in this document. If files are unreadable or code does not run, you will
receive 0 marks on that part of the assessment. You are not permitted to use generative AI tools for any part of
this coursework.Assessment
This coursework will count towards 17.5% of your overall mark for F29AI and will be marked out of 40 marks.
A* Search: Java/Python code (10 marks)
Your Java/Python code will primarily be marked on its correctness with respect to the two grid problems. We will
also check the implementation of the heuristic in your solution.
0
None
1-2
Poor
3-4
Fair
5-6
Good
7-8
Very good
9-10
Excellent
No code
submitted.
Major problems
with code.
Solution is
incorrect and/or
code does not
run.
Code partially
works but there
are major
problems with
code structure,
solution, and/or
heuristic.
Good code and
solution. Code
runs almost
perfectly but
there are
problems with
code structure,
solution, or
heuristic.
Very good code
and solution.
Code runs
perfectly. Small
problems with
code structure,
solution, or
heuristic.
Exceptional code
and solution.
Code runs
perfectly.
Heuristic is well
defined.
A* Search: Non-coding solution (10 marks)
Your solution will primarily be marked on its correctness with respect to the two grid problems. We will also check
your graph and heuristic values you are using in your solution.
0
None
1-2
Poor
3-4
Fair
5-6
Good
7-8
Very good
9-10
Excellent
No solution
submitted.
Major problems
with solution.
Solution is
incorrect and/or
many parts of the
solution are
wrong or missing.
Major problems
with solution.
Some parts of the
solution partially
incorrect or
missing.
Description of the
solution could be
improved in many
places.
Good solution.
Solution is mainly
correct but there
are some minor
problems.
Description of the
solution could be
improved.
Very good
solution. All parts
of the solution are
described and the
solution is correct
but there are
some small
problems with the
description that
could be
improved.
Exceptional
solution. All parts
of the solution are
well described
and solution is
perfect.
Knowledge Representation (10 marks)
You will be assessed on the correctness of your Prolog program and the output it produces.
0
None
1-2
Poor
3-4
Fair
5-6
Good
7-8
Very good
9-10
Excellent
No source code or
minimal source
code submitted.
Weak solution.
Many important
requirements of
the specification
or important parts
of the output
missing.
Comments
missing.
Adequate
solution. Some
requirements of
the specification
implemented but
important parts
missing. Output
cases do not
provide complete
coverage and/or
missing many
comments.
Thorough
solution. Majority
of program meets
specification.
Some small
problems with the
program, missing
cases in the
output file, and/or
missing
comments.
Very thorough
solution. Program
almost works
perfectly. There
might be very
small problems
with the program,
some missing
cases in the
output file, and/or
missing
comments.
Program works
perfectly. Output
illustrates all
important cases.
Comments in code
are descriptive.Automated Planning (20 marks)
The automated planning mark will primarily be based on the PDDL code you have supplied and how correctly it
implements the coursework specification. You should submit a single PDDL domain file and multiple PDDL
problem files. The supplied files should provide coverage of the various scenario requirements and demonstrate
correct behaviour. The marker will test a selection of the specified PDDL files for plan correctness. You should
clearly indicate in your report what planner you have used to test your solution. PDDL files will only be tested on
editor.planning.domains, FF, or Fast Downward. Correctness will be assessed not only against the coursework
requirements but also with respect to the specific implemented solution. (I.e., non-obvious or incorrect/missing
action preconditions or effects may lead to strange plan output and mark deductions.) Usual program quality
criteria (e.g., use of whitespace, comments, naming conventions, etc.) will apply here to assess the readability of
the code. The marker will be looking to see if you understand how to write PDDL domains and problems and have
made good use of the language features that are available. Deductions for poor code quality (up to 5 marks,
depending on severity) may be made even if your domain works perfectly.
1-year Edinburgh postgraduate students and all Dubai postgraduate students (full time and part time): Up to 2
marks will be allocated for the correctness of the additional feature. The additional feature should be similar in
terms of complexity to the requirements in the main specification (and may be more complex if you’d like), and
you are encouraged to be creative in your solutions. Trivial additional features will receive very few marks.
0
None
1-4
Poor
5-8
Fair
9-12
Good
13-16
Very good
17-20
Excellent
No source code
submitted.
Weak solution.
Many important
requirements or
test cases missing
and/or not
working perfectly.
Basic domain
features. PDDL
code is not
understandable
Adequate
solution. Some
requirements
implemented but
important
requirements
missing. Test
cases do not
provide complete
coverage. Some
test cases may not
work perfectly.
Mostly basic
domain features.
PDDL code is very
difficult to
understand.
Thorough
solution. Majority
of requirements
are met. Choice of
test cases is
convincing. Very
few test cases do
not work
perfectly. A good
quality solution
overall with a mix
of basic and
advanced domain
features. PDDL
code is mainly
well written, clear,
and
understandable.
Very thorough
solution. All
requirements met
and choice of test
cases provides
maximum
coverage of
requirements.
Solution plans are
quite convincing.
Everything works
perfectly. A good
mix of domain
features, with
advanced features
enhancing the
overall approach.
PDDL code is very
well written,
completely clear
and
understandable.
Exceptional
solution. All
requirements are
easily met and
well
demonstrated.
Test cases are
comprehensive
and demonstrate
robust behaviour.
Everything works
perfectly.
Excellent design
designs and use of
advanced features
which enhance
the overall
approach. PDDL
code is excellent,
with all aspects of
the code easily
understandable.Learning Objectives