GUJARAT TECHNOLOGICAL UNIVERSITY

Chandkheda, Ahmedabad
Affiliated

K.J. Institute of Engineering and Technology

Savli

Laboratory Manual
Of
Artificial Intelligence
(3170716)

B.E. Semester 7
(Computer Engineering)

Submitted By:
Parth Rajput
(190640107029)

Ms. Monika Tripathi

(Assistant Professor)

Mr. Arpit Mehta

(Head of the Department)

Academic Year (2022-2023)

 CERTIFICATE

Department of Computer Engineering

This is to certify that Rajput Parth Bearing Hall Ticket No. 190640107029
student of Computer Engineering 7th Semester has Completed Artificial
Intelligence Lab Record work (3170716) during the year 2022-2023.

Ms. Monika Tripathi Mr. Arpit Mehta

Internal Examiner Head of Department External Examiner
ARTIFICIAL INTELLIGENCE (3170716) 190640107029

INDEX

Practical Page
No. AIM Date Sign
No.

01 Write a program to implement Tic-Tac-

Toe game problem. 02 20/07/2022

Write a program to implement BFS (for

8 02 puzzle problem or Water Jug problem
or any AI search problem). 06 29/07/2022

Write a program to implement DFS (for

8 03 puzzle problems or Water Jug problem 10/08/2022
or any AI search problem). 08

04 Write a program to implement Single

Player Game (Using Heuristic 13 17/08/2022
Function).

05 Write a Program to Implement

A* Algorithm. 17 26/08/2022

06 Write a program to solve N-Queens

problem using Prolog. 22 07/09/2022

07 Write a program to solve 8

puzzle problem using 23 16/09/2022
Prolog.

08 Write a program to solve

travelling salesman problem 24 23/09/2022
using Prolog.

09 Convert following Prolog predicates into

Semantic Net 26 30/09/2022

Write the Conceptual Dependency for

following statements.
10 (a) John gives Mary a book. 31 07/10/2022
(b) John gave Mary the book
yesterday.

1|Page
ARTIFICIAL INTELLIGENCE (3170716) 190640107029

PRACTICAL – 1

AIM:- Write a program to implement Tic-Tac-Toe game

problem. Program:-

#include <stdio.h>

#include <ctype.h>

char square[10] = { 'o', '1', '2', '3', '4', '5', '6', '7', '8', '9' };

int checkwin();

void board();

int main()

int player = 1, i,

choice; char mark;

do

board();

player = (player % 2) ? 1 : 2;

printf("Player %d, enter a number: ", player);

scanf("%d", &choice);

mark = (player == 1) ? 'X' : 'O';

if (choice == 1 && square[1] == '1')

square[1] = mark;

else if (choice == 2 && square[2] == '2')

square[2] = mark;
2|Page
ARTIFICIAL INTELLIGENCE (3170716) 190640107029
else if (choice == 3 && square[3] == '3')

square[3] = mark;

else if (choice == 4 && square[4] == '4')

square[4] = mark;

else if (choice == 5 && square[5] == '5

square[5] = mark;

else if (choice == 6 && square[6] == '6')

square[6] = mark;

else if (choice == 7 && square[7] == '7')

square[7] = mark;

else if (choice == 8 && square[8] == '8')

square[8] = mark;

else if (choice == 9 && square[9] == '9')

square[9] = mark;

else

printf("Invalid move

"); player--;

i=

checkwin();

player++;

}while (i == - 1);

board();

if (i == 1)

printf("==>\aPlayer %d win ", --player);

3|Page
ARTIFICIAL INTELLIGENCE (3170716) 190640107029

4|Page
ARTIFICIAL INTELLIGENCE (3170716) 190640107029
else

printf("==>\aGame draw");

return 0;

int checkwin()

if (square[1] == square[2] && square[2] == square[3])

return 1;

else if (square[4] == square[5] && square[5] == square[6])

return 1;

else if (square[7] == square[8] && square[8] == square[9])

return 1;

else if (square[1] == square[4] && square[4] == square[7])

return 1;

else if (square[2] == square[5] && square[5] == square[8])

return 1;

else if (square[3] == square[6] && square[6] == square[9])

return 1;

else if (square[1] == square[5] && square[5] == square[9])

return 1;

else if (square[3] == square[5] && square[5] == square[7])

return 1;

else if (square[1] != '1' && square[2] != '2' && square[3] != '3' &&

square[4] != '4' && square[5] != '5' && square[6] != '6' && square[7]

!= '7' && square[8] != '8' && square[9] != '9')

5|Page
ARTIFICIAL INTELLIGENCE (3170716) 190640107029
return 0;

else

return -

1;

void board()

printf("\n\n\tTic Tac Toe\n\n");

printf("Player 1 (X) - Player 2 (O)\n\n\n");

printf(" | | \n");

printf(" %c | %c | %c \n", square[1], square[2], square[3]);

printf(" | | \n");

printf(" | | \n");

printf(" %c | %c | %c \n", square[4], square[5], square[6]);

printf(" | | \n");

printf(" | | \n");

printf(" %c | %c | %c \n", square[7], square[8], square[9]);

printf(" | | \n\n");

6|Page
ARTIFICIAL INTELLIGENCE (3170716) 190640107029

PRACTICAL – 2

AIM:- Write a program to implement BFS (for 8 puzzle problem or Water Jug
problemor any AI search problem).

Program :-

#include<stdio.h>

#include<ctype.h>

int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1;

void bfs(int v) {

for (i=1;i<=n;i++)

if(a[v][i] && !visited[i])

q[++r]=i;

if(f<=r)

{ visited[q[f]]=

1;

bfs(q[f++]);

int main()

{int v;

printf("\n Enter the number of

vertices:");scanf("%d",&n);

for (i=1;i<=n;i++)

{q[i]=0;

visited[i]=0;

7|Page
ARTIFICIAL INTELLIGENCE (3170716) 190640107029
}

printf("\n Enter graph data in matrix form:\

n");for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

scanf("%d",&a[i][j]);

printf("\n Enter the starting vertex:");

scanf("%d",&v);

bfs(v);

printf("\n The node which are reachable are:\

n");for (i=1;i<=n;i++)

if(visited[i]) printf("%d\

t",i); else

printf("\n Bfs is not possible");

return 0;

8|Page
ARTIFICIAL INTELLIGENCE (3170716) 190640107029

PRACTICAL - 3

AIM:- Write a program to implement DFS (for 8 puzzle problem or Water Jug
problem or any AI search problem).

Program:-

#include <cstdio>

#include <stack>

#include <map>

#include <algorithm>

using namespace

std; struct state {

int x, y;

bool operator < (const state& that) const

{if (x != that.x) return x <

that.x; return y < that.y;

};

int capacity_x, capacity_y, target;

void dfs(state start, stack <pair <state, int> >& path)

{stack <state> s;

state goal = (state) {-1, -1};

map <state, pair <state, int> > parentOf;

s.push(start);
9|Page
ARTIFICIAL INTELLIGENCE (3170716) 190640107029
parentOf[start] = make_pair(start, 0);

while (!s.empty()) {

state top = s.top();

s.pop();

if (top.x == target || top.y == target)

{goal =

top; break;

if (top.x < capacity_x) {

state child = (state) {capacity_x, top.y};

// Consider this state for visiting only if it has not been visited before

if (parentOf.find(child) == parentOf.end()) {

s.push(child);

parentOf[child] = make_pair(top, 1);

if (top.y < capacity_y) {

state child = (state) {top.x, capacity_y};

if (parentOf.find(child) == parentOf.end())

{s.push(child);

parentOf[child] = make_pair(top, 2);

if (top.x > 0) {

state child = (state) {0, top.y};

10 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029
if (parentOf.find(child) == parentOf.end())

{s.push(child);

parentOf[child] = make_pair(top, 3);

if (top.y > 0) {

state child = (state) {top.x, 0};

if (parentOf.find(child) == parentOf.end()) {
s.push(child);

parentOf[child] = make_pair(top, 4);

if (top.y > 0) {

state child = (state) {min(top.x + top.y, capacity_x), max(0, top.x + top.y - capacity_x)};if

(parentOf.find(child) == parentOf.end()) {

s.push(child);

parentOf[child] = make_pair(top, 5);

if (top.x > 0) {

state child = (state) {max(0, top.x + top.y - capacity_y), min(top.x + top.y, capacity_y)};if

(parentOf.find(child) == parentOf.end()) {

s.push(child);

parentOf[child] = make_pair(top, 6);

}
11 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029

if (goal.x == -1 || goal.y == -1)

return;

path.push(make_pair(goal, 0));

while (parentOf[path.top().first].second != 0)

path.push(parentOf[path.top().first]);

int main() {

stack <pair <state, int> > path;

printf("Enter the capacities of first jug :
");

scanf("%d", &capacity_x);

printf("Enter the capacities of second jug : ");

scanf("%d", &capacity_y);

printf("Enter the target amount :

");scanf("%d", &target);

dfs((state) {0, 0},

path); if

(path.empty())

printf("\nTarget cannot be reached.\

n");else {

printf("\nNumber of moves to reach the target : %d\nOne path to the target is as follows

:\n", path.size() - 1);

while (!path.empty())

{ state top = path.top().first;

int rule = path.top().second;

12 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029
path.pop();

13 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029
switch (rule) {

case 0: printf("State : (%d, %d)\n#\n", top.x, top.y);

break;

case 1: printf("State : (%d, %d)\nAction : Fill the first jug\n", top.x, top.y);

break;

case 2: printf("State : (%d, %d)\nAction : Fill the second jug\n", top.x, top.y);

break;

case 3: printf("State : (%d, %d)\nAction : Empty the first jug\n", top.x, top.y);

break;

case 4: printf("State : (%d, %d)\nAction : Empty the second jug\n", top.x, top.y);

break;

case 5: printf("State : (%d, %d)\nAction : Pour from second jug into first jug\n", top.x,

top.y);

break;

case 6: printf("State : (%d, %d)\nAction : Pour from first jug into second jug\n", top.x,

top.y);

break;

return 0;

14 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029

PRACTICAL - 4

AIM:- Write a program to implement Single Player Game (Using Heuristic

Function).

Program :-

#include <stdio.h>
char gridChar(int i)
{switch(i) {
case -1:
return 'X';
case 0:
return ' ';
case 1:
return 'O';
}

return 0;

void draw(int b[9]) {

printf(" %c | %c | %c\
n",gridChar(b[0]),gridChar(b[1]),gridChar(b[2])); printf("---+---+---\
n");
printf(" %c | %c | %c\
n",gridChar(b[3]),gridChar(b[4]),gridChar(b[5])); printf("---+---+---\
n");
printf(" %c | %c | %c\n",gridChar(b[6]),gridChar(b[7]),gridChar(b[8]));
}

int win(const int board[9]) {

//determines if a player has won, returns 0 otherwise.

15 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029
unsigned wins[8][3] = {{0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{2,4,6}};

int i;

16 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029
for(i = 0; i < 8; ++i)
{ if(board[wins[i][0]] != 0 &&
board[wins[i][0]] == board[wins[i][1]] &&
board[wins[i][0]] == board[wins[i][2]])
return board[wins[i][2]];
}
return 0;

int minimax(int board[9], int player) {

//How is the position like for player (their turn) on board?
int move;

int score = -2;//Losing moves are preferred to no

moveint i;
int thisScore;
int winner = win(board);
if(winner != 0) return winner*player;
move = -1;
for(i = 0; i < 9; ++i) {//For all moves,
if(board[i] == 0) {//If legal,
board[i] = player;
thisScore = -minimax(board, player*-1);
if(thisScore > score) {
score = thisScore;
move = i;
}//Pick the one that's worst for the
opponentboard[i] = 0;//Reset board after
try
}
}

if(move == -1) return 0;

return score;
}
void computerMove(int board[9])

17 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029
{int move = -1;
int score = -2;
int i;
int tempScore;
for(i = 0; i < 9; ++i)
{if(board[i] == 0)
{ board[i] = 1;
tempScore = -minimax(board, -
1); board[i] = 0;
if(tempScore > score)
{score = tempScore;
move = i;
}
}
}
//returns a score based on minimax tree at a given
node.board[move] = 1;

void playerMove(int board[9])

{int move = 0;
do {
printf("\nInput move ([0..8]): ");
scanf("%d", &move);
printf("\n");

}
while (move >= 9 || move < 0 && board[move] == 0);
board[move] = -1;

int main() {

int board[9] = {0,0,0,0,0,0,0,0,0};

18 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029
int player=0;
unsigned turn;
//computer squares are 1, player squares are -1.
printf("Computer: O, You: X\nPlay (1)st or (2)nd? ");
scanf("%d",&player);
printf("\n");
for(turn = 0; turn < 9 && win(board) == 0; ++turn)
{if((turn+player) % 2 == 0)
computerMove(board);
else {
draw(board);
playerMove(board);
}
}

switch(win(board))
{case 0:
printf("A draw. How droll.\n");
break;
case 1:
draw(board);
printf("You lose.\n");
break;
case -1:
printf("You win.\n");
break;
}

return 0;
}

19 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029

PRACTICAL-5

AIM:- Write a Program to Implement A* Algorithm.

Program :-

import java.util.*;
public class AStar
{
public static final int DIAGONAL_COST = 14;
public static final int V_H_COST = 10;
static class Cell{
int heuristicCost = 0; //Heuristic cost
int finalCost = 0; //G+H
int i, j;
Cell parent;
Cell(int i, int j)
{
this.i = i;
this.j = j;
}

@Override
public String toString(){
return "["+this.i+", "+this.j+"]";
}
}

//Blocked cells are just null Cell values in grid

static Cell [][] grid = new Cell[5][5];

static PriorityQueue<Cell> open;
static boolean closed[][];
static int startI, startJ;
static int endI, endJ;

public static void setBlocked(int i, int j)

{grid[i][j] = null;
}

public static void setStartCell(int i, int j)

{startI = i;
startJ = j;
20 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029
public static void setEndCell(int i, int j)
{endI = i;

21 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029
endJ = j;
}
static void checkAndUpdateCost(Cell current, Cell t, int
cost){if(t == null || closed[t.i][t.j])return;
int t_final_cost =
t.heuristicCost+cost; boolean inOpen
= open.contains(t); if(!inOpen ||
t_final_cost<t.finalCost){
t.finalCost = t_final_cost;
t.parent = current;
if(!inOpen)open.add(t);
}
}

public static void AStar(){

//add the start location to open

list.open.add(grid[startI][startJ]);
Cell current;
while(true){
current = open.poll();
if(current==null)break;
closed[current.i][current.j]=true;
if(current.equals(grid[endI][endJ])){
return;
}

Cell t;
if(current.i-1>=0){
t = grid[current.i-1][current.j];
checkAndUpdateCost(current, t, current.finalCost+V_H_COST);
if(current.j-1>=0){
t = grid[current.i-1][current.j-1];
checkAndUpdateCost(current, t, current.finalCost+DIAGONAL_COST);
}

if(current.j+1<grid[0].length){
t = grid[current.i-1][current.j+1];
checkAndUpdateCost(current, t, current.finalCost+DIAGONAL_COST);
}
}

if(current.j-1>=0){
t = grid[current.i][current.j-1];
checkAndUpdateCost(current, t, current.finalCost+V_H_COST);
}

22 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029

if(current.j+1<grid[0].length){
t = grid[current.i][current.j+1];
checkAndUpdateCost(current, t, current.finalCost+V_H_COST);
}

if(current.i+1<grid.length){
t = grid[current.i+1][current.j];
checkAndUpdateCost(current, t, current.finalCost+V_H_COST);

if(current.j-1>=0){
t = grid[current.i+1][current.j-1];
checkAndUpdateCost(current, t, current.finalCost+DIAGONAL_COST);
}

if(current.j+1<grid[0].length){
t = grid[current.i+1][current.j+1];
checkAndUpdateCost(current, t, current.finalCost+DIAGONAL_COST);
}
}
}
}

/*

Params :
tCase = test case No.
x, y = Board's dimensions
si, sj = start location's x and y
coordinatesei, ej = end location's x and y
coordinates
int[][] blocked = array containing inaccessible cell coordinates

*/

public static void test(int tCase, int x, int y, int si, int sj, int ei, int ej, int[]
[] blocked){System.out.println("\n\nTest Case #"+tCase);
//Reset
grid = new Cell[x][y];
closed = new boolean[x]
[y];
open = new PriorityQueue<>((Object o1, Object o2) ->
{Cell c1 = (Cell)o1;
Cell c2 =
(Cell)o2;
return c1.finalCost<c2.finalCost?-1:

23 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029
c1.finalCost>c2.finalCost?1:0;
});

24 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029

//Set start position

setStartCell(si, sj); //Setting to 0,0 by default. Will be useful for the UI part

//Set End Location

setEndCell(ei, ej);

for(int i=0;i<x;++i)
{for(int j=0;j<y;++j){
grid[i][j] = new Cell(i, j);
grid[i][j].heuristicCost = Math.abs(i-endI)+Math.abs(j-endJ);
// System.out.print(grid[i][j].heuristicCost+" ");
}
// System.out.println();
}
grid[si][sj].finalCost = 0;
/*
Set blocked cells. Simply set the cell values to null
for blocked cells.
*/

for(int
i=0;i<blocked.length;++i){ setBlocked(bl
ocked[i][0], blocked[i][1]);
}

//Display initial map

System.out.println("Grid: ");
for(int i=0;i<x;++i)
{for(int j=0;j<y;++j){
if(i==si&&j==sj)System.out.print("SO "); //Source
else if(i==ei && j==ej)System.out.print("DE "); //Destination

else if(grid[i][j]!=null)System.out.printf("%-3d ", 0);

else System.out.print("BL ");
}
System.out.println();
}
System.out.println();

AStar();

System.out.println("\nScores for cells: ");

for(int i=0;i<x;++i){

25 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029
for(int j=0;j<x;++j){
if(grid[i][j]!=null)System.out.printf("%-3d ", grid[i][j].finalCost);
else System.out.print("BL ");
}
System.out.println();
}
System.out.println();

if(closed[endI][endJ]){
//Trace back the path
System.out.println("Path: ");
Cell current = grid[endI][endJ];
System.out.print(current);
while(current.parent!=null){
System.out.print(" -> "+current.parent);
current = current.parent;
}
System.out.println();
}else System.out.println("No possible path");
}

public static void main(String[] args) throws Exception{

test(1, 5, 5, 0, 0, 3, 2, new int[][]{{0,4},{2,2},{3,1},{3,3}});

test(2, 5, 5, 0, 0, 4, 4, new int[][]{{0,4},{2,2},{3,1},{3,3}});
test(3, 7, 7, 2, 1, 5, 4, new int[][]{{4,1},{4,3},{5,3},{2,3}});
test(1, 5, 5, 0, 0, 4, 4, new int[][]{{3,4},{3,3},{4,3}});
}
}

26 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029

PRACTICAL - 6

AIM:- Write a program to solve N-Queens problem using Prolog.

Program :-

solution(Queens) :-
permutation([1,2,3,4,5,6,7,8], Queens),
safe(Queens).
permutation([],[]).
permutation([Head|Tail],PermList) :-
permutation(Tail,PermTail),
del(Head,PermList,PermTail).
del(Item,[Item|List],List). del(Item,
[First|List],[First|List1]) :-
del(Item,List,List1).
safe([]). safe([Queen|
Others]) :- safe(Others),
noattack(Queen,Others,1).
noattack(_,[],_). noattack(Y,
[Y1|Ylist],Xdist) :- Y1-Y=\
=Xdist,
Y-Y1=\=Xdist, Dist1
is Xdist + 1,
noattack(Y,Ylist,Dist1).

27 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029

PRACTICAL - 7

AIM:- Write a program to solve 8 puzzle problem using Prolog.

Program :-

sum(N1,N2,N):- sum1(N1,N2,N,0,0,
[0,1,2,3,4,5,6,7,8,9],_).
sum1([],[],[],C,C,Digits,Digits).
sum1([D1|N1],[D2|N2],[D|N],C1,C,Digs1,Digs):-
sum1(N1,N2,N,C1,C2,Digs1,Digs2),
digitsum(D1,D2,C2,D,C,Digs2,Digs).
digitsum(D1,D2,C1,D,C,Digs1,Digs):-
del(D1,Digs1,Digs2),
del(D2,Digs2,Digs3), del(D,Digs3,Digs),
S is D1+D2+C1,
D is S mod
10, C is S //
10. del(A,L,L):-
nonvar(A),!.
del(A,[A|L],L).
del(A,[B|L],[B|L1]):-
del(A,L,L1).
% Some puzzles puzzle1([D,O,N,A,L,D],[G,E,R,A,L,D],
[R,O,B,E,R,T]).
puzzle2([0,S,E,N,D], [0,M,O,R,E],[M,O,N,E,Y]).

28 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029

PRACTICAL - 8

AIM:- Write a program to solve travelling salesman problem using Prolog.

Program :-

domains
town = symbol
distance = unsigned
rib = r(town,town,distance)
tlist = town*
rlist = rib*
predicates
nondeterm way(town,town,rlist,distance)
nondeterm route(town,town,rlist,tlist,distance)
nondeterm route1(town,tlist,rlist,tlist,distance)
nondeterm ribsmember(rib,rlist)
nondeterm townsmember(town,tlist)
nondeterm tsp(town,town,tlist,rlist,tlist,distance)
nondeterm ham(town,town,tlist,rlist,tlist,distance)
nondeterm shorterRouteExists(town,town,tlist,rlist,distance)
nondeterm alltown(tlist,tlist)
nondeterm write_list(tlist)
clauses
write_list([]).
write_list([H|T]):-
write(H,‘ ‘), write_list(T).
townsmember(X,[X|_]).
townsmember(X,[_|L]):-
townsmember(X,L).
ribsmember(r(X,Y,D),[r(X,Y,D)|_]).
ribsmember(X,[_|L]):-
ribsmember(X,L).
alltown(_,[]).
alltown(Route,[H|T]):-
townsmember(H,Route),

29 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029
alltown(Route,T).
way(Town1,Town2,Ways,OutWayDistance):-
ribsmember(r(Town1,Town2,D),Ways), OutWayDistance
=
D. route(Town1,Town2,Ways,OutRoute,OutDistance):-
route1(Town1,[Town2],Ways,OutRoute,T1T2Distance),
%SWITCH HERE
way(Town2,Town1,Ways,LasDist),
OutDistance = T1T2Distance + LasDist. route1(Town1,[Town1|
Route1],_,[Town1|Route1],OutDistance):-
OutDistance = 0. route1(Town1,[Town2|
PassedRoute],Ways,OutRoute,OutDistance):-
way(TownX,Town2,Ways,WayDistance),
not(townsmember(TownX,PassedRoute)),
route1(Town1,[TownX,Town2|PassedRoute],Ways,OutRoute,CompletingRoadDistance)
OutDistance = CompletingRoadDistance + WayDistance.
shorterRouteExists(Town1,Town2,Towns,Ways,Distance):-
ham(Town1,Town2,Towns,Ways,_,Other),
Other < Distance.
tsp(Town1,Town1,Towns,Ways,BestRoute,MinDistance):- way(OtherTown,Town1,Ways,_),
tsp(Town1,OtherTown,Towns,Ways,BestRoute,MinDistance).
tsp(Town1,Town2,Towns,Ways,BestRoute,MinDistance):-
ham(Town1,Town2,Towns,Ways,Route,Distance),
not(shorterRouteExists(Town1,Town2,Towns,Ways,Distance)),
BestRoute = Route,
MinDistance = Distance.
ham(Town1,Town2,Towns,Ways,Route,Distance):-route(Town1,Town2,Ways,Route,Distance),
%SWITCH HERE
alltown(Route,Towns), % if you want simple road without including all towns youcould
uncomment this line
write_list(Route),
write(” tD = “,Distance,“n“).
% fail.

30 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029

PRACTICAL - 9

AIM:- Convert following Prolog predicates into

Semantic Netcat(tom).
cat(cat1).
mat(mat1).
sat_on(cat1,mat1)
.bird(bird1).
caught(tom,bird1)
.
like(X,cream) :– cat(X).
mammal(X) :– cat(X).
has(X,fur) :– mammal(X).
animal(X) :– mammal(X).
animal(X) :– bird(X).
owns(john,tom).
is_coloured(tom,ginger).

Solution:

Semantic Nets:
These are an alternative to predicate logic as a form of knowledge representation.
The idea is that we can store our knowledge in form of a graph with nodes representing
object in the world and arcs representing relationships between those objects.

For example:

31 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029

32 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029

It is intended to represent the data:

Tom is a cat.
Tom caught a bird.
Tom is owned by John.
Tom is ginger in color.
Cat likes cream.
The cat sat on the
mat. A cat is a
mammal.
A bird is an animal.
All mammals are
animals. Mammals have
fur.
The is_a link has two different meanings. It can mean that one object is an individual item
from a class and other is one class is a subset of another.

We can clean up the representation by distinguishing between nodes representing

individualor instances and nodes and representing classes.
The name instance and subclass are often used in place of is_a and ako(a kind
of). Prolog representation can be used, with classes represented by predicates.
Cat(tom)
Cat(cat1)
Mat(mat1)
Sat_on(cat1,mat1).
Bird(bird1).
Caught(tom,bird1).
Like(x,cream):-cat(x).
Mammal(x):-cat(x).
Has(x,fur):-mammal(x).
Animal(x):-mammal(x).
Animal(x):-bird(x).
33 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029
Owns(John,tom).

34 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029
Is_colored(tom,ginger).
In general, an is_a link between a class c and an individual m is represented by fact c(m).
An a_kind_of link between a subclass c and a superclass s is represented by s(x):-c(x).

INHERITANCE:
The prolog equivalent captures an important property of semantic nets that they may be
usedfor a form of inference known as inheritance.
The idea of this is that if an object belongs to class, it inherits all the properties of that class.
For example: As we have a “likes” link between cats and cream, meaning in “all the cats like
cream”, we can infer that any object which has an is_a link to cats will like cream. So both
TOM and CAT1 will like cream.
Inheritance also applies across the a_kind_of links. For example, any property of mammals
oranimals will automatic be a property of cats. So, we can infer, for example, that TOM has
fur,since TOM is a cat, a cat is a kind of animal, all animals are mammals and all mammals
havefur.

35 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029

FRAMES:
Frames are a variant of semantic networks. A frame is a data structure for representing
a stereo typical situation.
All the information relevant to a concept is stored in a single complex entity called a frame.
Superficially, frames look like record, data structures or class, frames also support
inheritance. In frame based systems we refer to:
· Objects - mammal
· Slots - properties such as color and size
· Slot values- values stored in slots such as grey and large.
Slots and the corresponding slot values are inherited through the class
hierarchy. FEATURES:
These are more natural support of values then semantic nets.
Frames can be easily implemented using object oriented programming technique.
In Frames based system, Inheritance is easily controlled.
BENEFITS:
· Easily understood by non-developers.
· Expressive power.
· Easy to include default information and detect missing
values. DRAWBACKS:
· No standards.
· No inference mechanism.

36 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029

PRACTICAL - 10

Write the Conceptual Dependency for following statements

a) John gives Mary a book.

b) John gave Mary the book yesterday.

Solution :-

Conceptual Dependency originally developed to represent knowledge acquired from natural

language input.

The goals of this theory are:

 To help in the drawing of inference from sentences.

 To be independent of the words used in the original input.
 That is to say: For any 2 (or more) sentences that are identical in meaning
there should be only one representation of that meaning.

It has been used by many programs that portend to understand English (MARGIE, SAM,
PAM). CD developed by Schank et al. as were the previous examples.

CD provides:

 a structure into which nodes representing information can be placed

 a specific set of primitives
 at a given level of granularity.

Sentences are represented as a series of diagrams depicting actions using both abstract and
real physical situations.

 The agent and the objects are represented

 The actions are built up from a set of primitive acts which can be modified by tense.

Examples of Primitive Acts are:

ATRANS
-- Transfer of an abstract relationship. e.g. give.
PTRANS
-- Transfer of the physical location of an object. e.g. go.
PROPEL
37 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029
-- Application of a physical force to an object. e.g. push.
MTRANS
-- Transfer of mental information. e.g. tell.
MBUILD
-- Construct new information from old. e.g. decide.
SPEAK
-- Utter a sound. e.g. say.
ATTEND
-- Focus a sense on a stimulus. e.g. listen, watch.
MOVE
-- Movement of a body part by owner. e.g. punch, kick.
GRASP
-- Actor grasping an object. e.g. clutch.
INGEST
-- Actor ingesting an object. e.g. eat.
EXPEL
-- Actor getting rid of an object from body. e.g. ????.

Six primitive conceptual categories provide building blocks which are the set of allowable
dependencies in the concepts in a sentence:

PP
-- Real world objects.
ACT
-- Real world actions.
PA
-- Attributes of objects.
AA
-- Attributes of actions.
T
-- Times.
LOC
-- Locations.

38 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029

How do we connect these things together?

Consider the example:

John gives Mary a book

 Arrows indicate the direction of dependency. Letters above indicate

certain relationships:

o
-- object.
R
-- recipient-donor.
I
-- instrument e.g. eat with a spoon.
D

-- destination e.g. going home.

 Double arrows ( ) indicate two-way links between the actor (PP) and action (ACT).
 The actions are built from the set of primitive acts (see above).
o These can be modified by tense etc.
 The use of tense and mood in describing events is extremely important and
schank introduced the following modifiers:
 p
 -- past
 f
 -- future
 t
 -- transition

 -- start transition

 -- finished transition
 k
 -- continuing
 ?
 -- interrogative
 /
 -- negative
 delta
 -- timeless

39 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029

 c
 -- conditional
 the absence of any modifier implies the present tense.
 So the past tense of the above example:
 John gave Mary a book becomes:

The has an object (actor), PP and action, ACT. I.e. PP ACT. The triplearrow ( )
is also a two link but between an object, PP, and its attribute, PA. I.e. PP PA.

It represents isa type dependencies. E.g

Dave lecturerDave is a lecturer.

Primitive states are used to describe many state descriptions such as height, health, mental
state, physical state.

There are many more physical states than primitive actions. They use a numeric scale.

E.g. John height(+10) John is the tallest John height(< average) John is short
Frank Zappahealth(-10) Frank Zappa is dead Davemental_state(-10) Dave is
sad Vase physical_state(-10) The vase is broken

You can also specify things like the time of occurrence in the relation ship.

For Example: John gave Mary the book yesterday

Now let us consider a more complex sentence: Since smoking can kill you, I stopped Lets
look at how we represent the inference that smoking can kill:

 Use the notion of one to apply the knowledge to.

 Use the primitive act of INGESTing smoke from a cigarette to one.
 Killing is a transition from being alive to dead. We use triple arrows to indicate
a transition from one state to another.
 Have a conditional, c causality link. The triple arrow indicates dependency of
one concept on another.

40 | P a g e
ARTIFICIAL INTELLIGENCE (3170716) 190640107029

To add the fact that I stopped smoking

 Use similar rules to imply that I smoke cigarettes.

 The qualification attached to this dependency indicates that the
instance INGESTing smoke has stopped.

Advantages of CD:

 Using these primitives involves fewer inference rules.

 Many inference rules are already represented in CD structure.
 The holes in the initial structure help to focus on the points still to be established.

Disadvantages of CD:

 Knowledge must be decomposed into fairly low level primitives.

 Impossible or difficult to find correct set of primitives.
 A lot of inference may still be required.
 Representations can be complex even for relatively simple actions. Consider:

Dave bet Frank five pounds that Wales would win the Rugby World Cup.

Complex representations require a lot of storage.

41 | P a g e