Artificial Intelligence and Intelligent Agents

F29AI – 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.

Explanation & Answer

Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Order Now and we will direct you to our Order Page at Litessays. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.