Software laboratory
Experiment 1
Introduction to Intelligent System
Class: T.E COMP
Experiment 1: Specify problem formulation
Learning Objective:
Basic Experiments
Specify problem formulation for an AI problem and Implement the same.
Tools: Python
Theory:
To design a rational agent we need to specify a task environment • a problem specification for which the agent is a solution PEAS: to specify a task environment· • Performance measure • Environment • Actuators • Sensors
PEAS: Specifying an automated taxi driver
PEAS: Specifying an automated taxi driver Performance measure: • safe, fast, legal, comfortable, maximize profits Environment: • roads, other traffic, pedestrians, customers Actuators: • steering, accelerator, brake, signal, horn Sensors: • cameras, sonar, speedometer, GPS
PEAS: Medical diagnosis system Performance measure: Healthy patient, minimize· costs, lawsuits Environment: Patient, hospital, staff· Actuators: Screen display (form including:· questions, tests, diagnoses, treatments, referrals) Sensors: Keyboard (entry of symptoms, findings,· patient's answers)
Environment types: Definitions I Fully observable (vs. partially observable): An agent's· sensors give it access to the complete state of the environment at each point in time. Deterministic (vs. stochastic): The next state of the· environment is completely determined by the current state and the action executed by the agent. • If the environment is deterministic except for the actions of other agents, then the environment is strategic. Episodic (vs. sequential): The agent's experience is· divided into atomic "episodes" during which the agent perceives and then performs a single action, and the choice of action in each episode depends only on the episode itself.
Environment types: Definitions II Static (vs. dynamic): The environment is unchanged while· an agent is deliberating. • The environment is semi dynamic if the environment itself does not change with the passage of time but the agent's performance score does. Discrete (vs. continuous): A limited number of distinct,· clearly defined percepts and actions. Single agent (vs. multiagent): An agent operating by· itself in an environment.
Environment Restrictions for Now We will assume environment is· • Static • Fully Observable • Deterministic • Discrete
The rational agent designer’s goal Goal of AI practitioner who designs rational agents:· given a PEAS task environment, 1. Construct agent function f that maximizes (the expected value of) the performance measure, 2. Design an agent program that implements f on a particular architecture
Example search problem: 8-puzzle Formulate goal· • Pieces to end up in order as shown… Formulate search problem· • States: configurations of the puzzle (9! configurations) • Actions: Move one of the movable pieces (≤4 possible) • Performance measure: minimize total moves Find solution· • Sequence of pieces moved: 3,1,6,3,1,…
Holiday in Romania II On holiday in Romania; currently in Arad· • Flight leaves tomorrow from Bucharest Formulate goal· • Be in Bucharest Formulate search problem· • States: various cities • Actions: drive between cities • Performance measure: minimize distance Find solution· • Sequence of cities; e.g. Arad, Sibiu, Fagaras, Bucharest,
More formally, a problem is defined by:
1. A set of states S SÎ
2. An initial state si
3. A set of actions A s Actions(s) = the set of actions that can be executed in s,"— that are applicable in s. sr®Actions(s) Result(s, a) Î a" s"
4. Transition Model: —sr is called a successor of s —{si Successors(siÈ} )* = state space
5. Goal test Goal(s) — Can be implicit, e.g. checkmate(x) — s is a goal state if Goal(s) is true
6. Path cost (additive) —e.g. sum of distances, number of actions executed, … —c(x,a,y) is the step cost, assumed ≥ 0 – (where action a goes from state x to state y)
Solution A solution is a sequence of actions from the initial state to a goal state. Optimal Solution: A solution is optimal if no solution has a lower path cost.
8 puzzle Problem using Branch And Bound
We have introduced Branch and Bound and discussed 0/1 Knapsack problem in below posts.
· Branch and Bound | Set 1 (Introduction with 0/1 Knapsack)
· Branch and Bound | Set 2 (Implementation of 0/1 Knapsack)
In this puzzle solution of 8 puzzle problem is discussed.
Given a 3×3 board with 8 tiles (every tile has one number from 1 to 8) and one empty space. The objective is to place the numbers on tiles to match final configuration using the empty space. We can slide four adjacent (left, right, above and below) tiles into the empty space.
Complete Algorithm:
/* Algorithm LCSearch uses c(x) to find an answer node
* LCSearch uses Least() and Add() to maintain the list
of live nodes
* Least() finds a live node with least c(x), deletes
it from the list and returns it
* Add(x) adds x to the list of live nodes
* Implement list of live nodes as a min-heap */
struct list_node
{
list_node *next;
// Helps in tracing path when answer is found
list_node *parent;
float cost;
}
algorithm LCSearch(list_node *t)
{
// Search t for an answer node
// Input: Root node of tree t
// Output: Path from answer node to root
if (*t is an answer node)
{
print(*t);
return;
}
E = t; // E-node
Initialize the list of live nodes to be empty;
while (true)
{
for each child x of E
{
if x is an answer node
{
print the path from x to t;
return;
}
Add (x); // Add x to list of live nodes;
x->parent = E; // Pointer for path to root
}
if there are no more live nodes
{
print ("No answer node");
return;
}
// Find a live node with least estimated cost
E = Least();
// The found node is deleted from the list of
// live nodes
}
}
// Program to print path from root node to destination node
// for N*N -1 puzzle algorithm using Branch and Bound
// The solution assumes that instance of puzzle is solvable
#include <bits/stdc++.h>
using namespace std;
#define N 3
// state space tree nodes
struct Node
{
// stores the parent node of the current node
// helps in tracing path when the answer is found
Node* parent;
// stores matrix
int mat[N][N];
// stores blank tile coordinates
int x, y;
// stores the number of misplaced tiles
int cost;
// stores the number of moves so far
int level;
};
// Function to print N x N matrix
int printMatrix(int mat[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
printf("%d ", mat[i][j]);
printf("\n");
}
}
// Function to allocate a new node
Node* newNode(int mat[N][N], int x, int y, int newX,
int newY, int level, Node* parent)
{
Node* node = new Node;
// set pointer for path to root
node->parent = parent;
// copy data from parent node to current node
memcpy(node->mat, mat, sizeof node->mat);
// move tile by 1 position
swap(node->mat[x][y], node->mat[newX][newY]);
// set number of misplaced tiles
node->cost = INT_MAX;
// set number of moves so far
node->level = level;
// update new blank tile cordinates
node->x = newX;
node->y = newY;
return node;
}
// botton, left, top, right
int row[] = { 1, 0, -1, 0 };
int col[] = { 0, -1, 0, 1 };
// Function to calculate the number of misplaced tiles
// ie. number of non-blank tiles not in their goal position
int calculateCost(int initial[N][N], int final[N][N])
{
int count = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (initial[i][j] && initial[i][j] != final[i][j])
count++;
return count;
}
// Function to check if (x, y) is a valid matrix cordinate
int isSafe(int x, int y)
{
return (x >= 0 && x < N && y >= 0 && y < N);
}
// print path from root node to destination node
void printPath(Node* root)
{
if (root == NULL)
return;
printPath(root->parent);
printMatrix(root->mat);
printf("\n");
}
// Comparison object to be used to order the heap
struct comp
{
bool operator()(const Node* lhs, const Node* rhs) const
{
return (lhs->cost + lhs->level) > (rhs->cost + rhs->level);
}
};
// Function to solve N*N - 1 puzzle algorithm using
// Branch and Bound. x and y are blank tile coordinates
// in initial state
void solve(int initial[N][N], int x, int y,
int final[N][N])
{
// Create a priority queue to store live nodes of
// search tree;
priority_queue<Node*, std::vector<Node*>, comp> pq;
// create a root node and calculate its cost
Node* root = newNode(initial, x, y, x, y, 0, NULL);
root->cost = calculateCost(initial, final);
// Add root to list of live nodes;
pq.push(root);
// Finds a live node with least cost,
// add its childrens to list of live nodes and
// finally deletes it from the list.
while (!pq.empty())
{
// Find a live node with least estimated cost
Node* min = pq.top();
// The found node is deleted from the list of
// live nodes
pq.pop();
// if min is an answer node
if (min->cost == 0)
{
// print the path from root to destination;
printPath(min);
return;
}
// do for each child of min
// max 4 children for a node
for (int i = 0; i < 4; i++)
{
if (isSafe(min->x + row[i], min->y + col[i]))
{
// create a child node and calculate
// its cost
Node* child = newNode(min->mat, min->x,
min->y, min->x + row[i],
min->y + col[i],
min->level + 1, min);
child->cost = calculateCost(child->mat, final);
// Add child to list of live nodes
pq.push(child);
}
}
}
}
// Driver code
int main()
{
// Initial configuration
// Value 0 is used for empty space
int initial[N][N] =
{
{1, 2, 3},
{5, 6, 0},
{7, 8, 4}
};
// Solvable Final configuration
// Value 0 is used for empty space
int final[N][N] =
{
{1, 2, 3},
{5, 8, 6},
{0, 7, 4}
};
// Blank tile coordinates in initial
// configuration
int x = 1, y = 2;
solve(initial, x, y, final);
return 0;
}
Output :
1 2 3
5 6 0
7 8 4
1 2 3
5 0 6
7 8 4
1 2 3
5 8 6
7 0 4
1 2 3
5 8 6
0 7 4
Learning Outcomes: Students should have the ability to
LO1: Understand the problem formulation
Course Outcomes:Upon completion of the course students will be able to understand problem formulation in IIS.
Conclusion:Thus, the aim to study and implement Nmap which include port scanning, OS fingerprinting, tcp scan and udp scan is accomplished.
Viva Questions:
Ques.1 What do you understand by Problem Formulation?
Ques. 2. Explain the basic steps in problem formulation?
Ques. 3. Write types of problem discussed in detail.
For Faculty Use
Correction Parameters
Formative Assessment [40%]
Timely completion of Practical [ 40%]
Attendance / Learning Attitude [20%]
Marks Obtained