CAP 378: Artificial Intelligence

Intelligent Agent, Types Of Agent Programs

Formulating Problems :

• Water Jug Problem

• 8 Puzzle Problem

• Missionaries And Cannibals Problem

Intelligent Agent
• Entity that acts, generally on behalf of someone else.

• More precisely, an agent is an entity that perceives its environment through sensors and
acts on the environment through actuators.

• An Agent runs in the cycle of perceiving, thinking, and acting.

Agent Perceive Think Act

Types of Agent Sensors Actuators

Human-Agent Eyes, Ears and other Hand, legs. Vocal tract
organs
Robotic Agent Cameras, infrared range Various motors
finder, NLP
Software Agent Keystrokes, file contents Act on sensory input and
display output
Intelligent Agent

Job of AI is to design an Agent Program

Task Environment
• Include all the elements involved in the problems for which agents are thought of as solutions.
• PEAS: A standard set of measures or parameters for specifying a task environment.
• For designing an agent, the first requirement is to specify the task environment to the maximum
extent possible.
• The task environment for an agent to solve one type of problems, may be described by the four
major parameters namely:
• Performance : Which is actually the expected performance
• Environment : World around the agent
• Actuators : Which include entities through which the agent may perform actions
• Sensors: Which describes the different entities through which the agent will gather
information about the environment.
SR Agents
• IF a human being comes in front of the automobile suddenly
THEN apply breaks immediately.

A simple reflex agent executes its

functions by following the
condition-action rule, which
specifies what action to take in a
certain condition.

They do not store or remember

anything

They are capable of operating

correctly only if the environment
is fully observable.
Model - Based Agents

In order to handle properly the partial observability of the environment.

The model-based reflex agent operates in four stages:

Sense: It perceives the current state of the world with its sensors.
Model: It constructs an internal model of the world from what it sees.
Reason: It uses its model of the world to decide how to act based on a set of predefined rules or heuristics.
Act: The agent carries out the action that it has chosen.
Goal - Based Agents
• Use information from their environment to achieve specific goals.
• They employ search algorithms to find the most efficient path towards their objectives within a given
environment.
• These agents are also known as rule-based agents, as they follow predefined rules to accomplish their goals
and take specific actions based on certain conditions.
The working pattern of the goal-based agent can be
divided into five steps:
Perception: The agent perceives its environment using
sensors or other input devices to collect information about
its surroundings.
Reasoning: The agent analyzes the information collected
and decides on the best course of action to achieve its
goal.
Action: The agent takes actions to achieve its goal, such
as moving or manipulating objects in the environment.
Evaluation: After taking action, the agent evaluates its
progress towards the goal and adjusts its actions, if
necessary.
Goal Completion: Once the agent has achieved its goal, it
Utility - Based Agents
• Utility-based agents are often used in
applications where they have to
compare and select among multiple
options, such as resource allocation,
scheduling, and game-playing.

A utility-based agent aims to choose actions that lead to a high utility state.
To achieve this, it needs to model its environment, which can be simple or complex.

Then, it evaluates the expected utility of each possible outcome based on the probability distribution and the utility
function.

Finally, it selects the action with the highest expected utility and repeats this process at each time step.
Learning Agents

• An AI learning agent is a software agent that can learn from past experiences and improve its performance. It
initially acts with basic knowledge and adapts automatically through machine learning.

• The learning agent comprises four main components:

• Learning Element: It is responsible for learning and making improvements based on the experiences it gains
from its environment.
• Citric: It provides feedback to the learning element by the agent’s performance for a predefined standard.
• Performance Element: It selects and executes external actions based on the information from the learning
element and the critic.
• Problem Generator: It suggests actions to create new and informative experiences for the learning element to
improve its performance.
Rule for AI Agents
Problem Solving
• First, the problem which can be solved by using
Deterministic Procedure and the success is guaranteed.
Deterministic
• But most real-world problems can be solved only by
searching a solution. Problem Solving
• AI is concerned with these second types of problems Search
solving.
To build a system to solve a problem, we need to

Define the problem precisely-find initial and final configuration for acceptable solution to the
problem.

Analyse the problem-find few important features that may have impact on the appropriateness of
various possible techniques for solving the problem

Isolate and represent task knowledge necessary to solve the problem

Choose the best problem-solving technique(s) and apply it to the particular problem
Problem Formulation
• To provide a formal description of a problem, we need to do the following:

• Define a state space that contains all the possible configurations of the
relevant objects.

• Specify one or more states that describe possible situations, from which the
problem solving process may start. These states are called initial states.

• Specify one or more than one goal states.

• Defining a set of rules for the actions (operators) that can be taken.

• Problem formulation is the process of deciding what actions and states to consider,
given a goal.
• The process of looking for a sequence of actions that reaches the goal is called
search.
• A search algorithm takes a problem as input and returns a solution in the form of
an action sequence.
• Once a solution is found, the carrying actions it recommends is called the
execution phase.
Formulating Problem
• A problem space is represented by a directed graph,
where nodes represent search state and paths represent
the operators applied to change the state.
• To simplify search algorithms, it is often convenient to
logically and programmatically represent a problem
space as a tree.
• A tree usually decreases the complexity of a search at a
cost. GRAPH TREE
• A tree is a graph in which any two vertices are
connected by exactly one path.
• Alternatively, any connected graph with no cycles is a
tree.
Water Jug Problem
• Problem statement:
• Given two jugs, a 4-gallon and a 3-gallon, both of which do not have measuring
indicators on them. The jugs can be filled with water with the help of a pump that is
available
• The question is “how can you get exactly 2 gallons of water into 4-gallon jug”.
• The state space or production rule of this problem can be defined as a collection of
ordered pairs of integers:
• (x,y) where x=0,1,2,3,4 and y= 0,1,2,or 3.
• In the order pair (x,y),
• x is the amount of water in four-gallon jug
• y is the amount of water in the three-gallon jug.
• State space: all possible combination of (x,y)
• Start state Is: (0,0) and
• Goal state Is: (2, 𝑛)
• 𝑤ℎ𝑒𝑟𝑒 𝑛 = 0,1,2,3
Production Rules
The following table-1 shows the set of production rules (actions) that can be used to change one state to another.
Water Jug Problem: Solution 1
The following 2 solutions are found for the problem “how can you get exactly 2 gallons of water into 4-gallon jug”,
as shown in Table-2 and in Table-3.
Water Jug Problem: Solution 2
The following 2 solutions are found for the problem “how can you get exactly 2 gallons of water into 4-gallon jug”,
as shown in Table-2 and in Table-3.
8 Puzzle Problem
• The eight-tile puzzle consists of a 3-by-3 (3 × 3) square frame board which holds eight (8) movable tiles
numbered as 1 to 8.
• One square is empty, allowing the adjacent tiles to be shifted.
• The objective of the puzzle is to find a sequence of tile movements that leads from a starting configuration to a
goal configuration
• Given a 3 × 3 grid with 8 sliding tiles and one “blank”
• Initial State: some other configuration of the tiles, for example
• Goal State:

• Operators: : Slide tiles (Move Blank) to reach the goal (as shown below).
• There are 4 operators that is, “Moving the blank”:
• Move the blank UP
• Move the blank DOWN
• Move the blank LEFT
• Move the blank RIGHT
8 Puzzle Problem
Path Cost: Sum of of the cost of each path from initial state to goal state.
Here cost of each action (blank move) = 1,
So cost of a Sequence of Actions= the number of Actions.
A optimal solution is one which has a lowest cost path.

Performing State-Space Search: Basic idea:

If the initial state is a goal state, return it.
If not, apply the operators to generate all states that are one step from the initial state (its successors)

All possible successors for a given initial state

8 Puzzle Problem
Consider the successor (and their successors…) until you find a goal state.
Different search strategies consider the state in different orders. They may use different data structures to store the
states that have yet to be considered.

State-Space Search Tree for 8-Puzzle problem: The predecessor reference connects the search nodes, creating a
data structure known as a tree.

Tracing a tree bottom-up form Goal state to initial sate.

When we reach a goal, we trace up the tree to get the solution
i.e., the sequence of actions from the initial state to the goal.
Missionaries And Cannibals Problem

https://www.youtube.com/watch?v=laLS8gHzROg

On one bank of a river are three

missionaries(M) and three cannibals(C).

There is one(B) boat available that can hold up

to two people and that they would like to use to
cross the river.

If the cannibals ever outnumber the

missionaries on either of the river’s banks, the Missionaries
missionaries will get eaten. Cannibals

How can the boat be used to safely carry all

the missionaries and cannibals across the
river?
Missionaries And Cannibals Problem
State: (M,C,B)
Where,

M : Number of missionaries in the left side bank (i.e., left side

of the river)

C : Number of cannibals in the left side bank (i.e., left side of

the river)

B : Boat position of the boat.

Where, 0 indicates the boat is on the left side of the river
1 indicate the boat is on the right side.

Start state:(3,3,0)
Goal State: (0,0,1)

Boat carries: (1,0) or (0,1) or (1,1) or (2,0) or (0,2).

Here in (i,j), i represents number of missionaries and j means number of cannibals.