CS6659 - AI Notes
- Lecture Videos - Collection 1
- Lecture Videos - Collection 2
- Lecture Videos - Collection 3
Problem Solving Agent
- Goal Formulation -Set of one or more (desirable) world states.(eg.Checkmate in Chess)
- Problem Formulation - What actions and states to consider given a goal and an initial state
- Search for solution - Given the problem, search for a solution-- a sequence of actions to achieve the goal starting from initial state
- Execution of the solution
Really helpful assets there
Problem Solving Agents in Artificial Intelligence
In this post, we will talk about Problem Solving agents in Artificial Intelligence, which are sort of goal-based agents. Because the straight mapping from states to actions of a basic reflex agent is too vast to retain for a complex environment, we utilize goal-based agents that may consider future actions and the desirability of outcomes.
You Will Learn
Problem Solving Agents
Problem Solving Agents decide what to do by finding a sequence of actions that leads to a desirable state or solution.
An agent may need to plan when the best course of action is not immediately visible. They may need to think through a series of moves that will lead them to their goal state. Such an agent is known as a problem solving agent , and the computation it does is known as a search .
The problem solving agent follows this four phase problem solving process:
- Goal Formulation: This is the first and most basic phase in problem solving. It arranges specific steps to establish a target/goal that demands some activity to reach it. AI agents are now used to formulate goals.
- Problem Formulation: It is one of the fundamental steps in problem-solving that determines what action should be taken to reach the goal.
- Search: After the Goal and Problem Formulation, the agent simulates sequences of actions and has to look for a sequence of actions that reaches the goal. This process is called search, and the sequence is called a solution . The agent might have to simulate multiple sequences that do not reach the goal, but eventually, it will find a solution, or it will find that no solution is possible. A search algorithm takes a problem as input and outputs a sequence of actions.
- Execution: After the search phase, the agent can now execute the actions that are recommended by the search algorithm, one at a time. This final stage is known as the execution phase.
Problems and Solution
Before we move into the problem formulation phase, we must first define a problem in terms of problem solving agents.
A formal definition of a problem consists of five components:
It is the agent’s starting state or initial step towards its goal. For example, if a taxi agent needs to travel to a location(B), but the taxi is already at location(A), the problem’s initial state would be the location (A).
It is a description of the possible actions that the agent can take. Given a state s, Actions ( s ) returns the actions that can be executed in s. Each of these actions is said to be appropriate in s.
It describes what each action does. It is specified by a function Result ( s, a ) that returns the state that results from doing action an in state s.
The initial state, actions, and transition model together define the state space of a problem, a set of all states reachable from the initial state by any sequence of actions. The state space forms a graph in which the nodes are states, and the links between the nodes are actions.
It determines if the given state is a goal state. Sometimes there is an explicit list of potential goal states, and the test merely verifies whether the provided state is one of them. The goal is sometimes expressed via an abstract attribute rather than an explicitly enumerated set of conditions.
It assigns a numerical cost to each path that leads to the goal. The problem solving agents choose a cost function that matches its performance measure. Remember that the optimal solution has the lowest path cost of all the solutions .
The problem solving approach has been used in a wide range of work contexts. There are two kinds of problem approaches
- Standardized/ Toy Problem: Its purpose is to demonstrate or practice various problem solving techniques. It can be described concisely and precisely, making it appropriate as a benchmark for academics to compare the performance of algorithms.
- Real-world Problems: It is real-world problems that need solutions. It does not rely on descriptions, unlike a toy problem, yet we can have a basic description of the issue.
Some Standardized/Toy Problems
Vacuum world problem.
Let us take a vacuum cleaner agent and it can move left or right and its jump is to suck up the dirt from the floor.
The vacuum world’s problem can be stated as follows:
States: A world state specifies which objects are housed in which cells. The objects in the vacuum world are the agent and any dirt. The agent can be in either of the two cells in the simple two-cell version, and each call can include dirt or not, therefore there are 2×2×2 = 8 states. A vacuum environment with n cells has n×2 n states in general.
Initial State: Any state can be specified as the starting point.
Actions: We defined three actions in the two-cell world: sucking, moving left, and moving right. More movement activities are required in a two-dimensional multi-cell world.
Transition Model: Suck cleans the agent’s cell of any filth; Forward moves the agent one cell forward in the direction it is facing unless it meets a wall, in which case the action has no effect. Backward moves the agent in the opposite direction, whilst TurnRight and TurnLeft rotate it by 90°.
Goal States: The states in which every cell is clean.
Action Cost: Each action costs 1.
8 Puzzle Problem
In a sliding-tile puzzle , a number of tiles (sometimes called blocks or pieces) are arranged in a grid with one or more blank spaces so that some of the tiles can slide into the blank space. One variant is the Rush Hour puzzle, in which cars and trucks slide around a 6 x 6 grid in an attempt to free a car from the traffic jam. Perhaps the best-known variant is the 8- puzzle (see Figure below ), which consists of a 3 x 3 grid with eight numbered tiles and one blank space, and the 15-puzzle on a 4 x 4 grid. The object is to reach a specified goal state, such as the one shown on the right of the figure. The standard formulation of the 8 puzzles is as follows:
STATES : A state description specifies the location of each of the tiles.
INITIAL STATE : Any state can be designated as the initial state. (Note that a parity property partitions the state space—any given goal can be reached from exactly half of the possible initial states.)
ACTIONS : While in the physical world it is a tile that slides, the simplest way of describing action is to think of the blank space moving Left , Right , Up , or Down . If the blank is at an edge or corner then not all actions will be applicable.
TRANSITION MODEL : Maps a state and action to a resulting state; for example, if we apply Left to the start state in the Figure below, the resulting state has the 5 and the blank switched.
GOAL STATE : It identifies whether we have reached the correct goal state. Although any state could be the goal, we typically specify a state with the numbers in order, as in the Figure above.
ACTION COST : Each action costs 1.
You Might Like:
- Agents in Artificial Intelligence
Types of Environments in Artificial Intelligence
- Understanding PEAS in Artificial Intelligence
- River Crossing Puzzle | Farmer, Wolf, Goat and Cabbage
Digital image processing: all you need to know.
Problem-Solving Agents In Artificial Intelligence
I'm Hridaya Manoj, I love tech and writing. I make tech easy to understand. Let's learn about tech together!
In artificial intelligence, a problem-solving agent refers to a type of intelligent agent designed to address and solve complex problems or tasks in its environment. These agents are a fundamental concept in AI and are used in various applications, from game-playing algorithms to robotics and decision-making systems. Here are some key characteristics and components of a problem-solving agent:
- Perception : Problem-solving agents typically have the ability to perceive or sense their environment. They can gather information about the current state of the world, often through sensors, cameras, or other data sources.
- Knowledge Base : These agents often possess some form of knowledge or representation of the problem domain. This knowledge can be encoded in various ways, such as rules, facts, or models, depending on the specific problem.
- Reasoning : Problem-solving agents employ reasoning mechanisms to make decisions and select actions based on their perception and knowledge. This involves processing information, making inferences, and selecting the best course of action.
- Planning : For many complex problems, problem-solving agents engage in planning. They consider different sequences of actions to achieve their goals and decide on the most suitable action plan.
- Actuation : After determining the best course of action, problem-solving agents take actions to interact with their environment. This can involve physical actions in the case of robotics or making decisions in more abstract problem-solving domains.
- Feedback : Problem-solving agents often receive feedback from their environment, which they use to adjust their actions and refine their problem-solving strategies. This feedback loop helps them adapt to changing conditions and improve their performance.
- Learning : Some problem-solving agents incorporate machine learning techniques to improve their performance over time. They can learn from experience, adapt their strategies, and become more efficient at solving similar problems in the future.
Problem-solving agents can vary greatly in complexity, from simple algorithms that solve straightforward puzzles to highly sophisticated AI systems that tackle complex, real-world problems. The design and implementation of problem-solving agents depend on the specific problem domain and the goals of the AI application.
Hello, I’m Hridhya Manoj. I’m passionate about technology and its ever-evolving landscape. With a deep love for writing and a curious mind, I enjoy translating complex concepts into understandable, engaging content. Let’s explore the world of tech together
Which Of The Following Is A Privilege In SQL Standard
Implicit Return Type Int In C
Leave a Comment Cancel reply
Save my name, email, and website in this browser for the next time I comment.
Reach Out to Us for Any Query
SkillVertex is an edtech organization that aims to provide upskilling and training to students as well as working professionals by delivering a diverse range of programs in accordance with their needs and future aspirations.
© 2023 Skill Vertex
Searching is one of the classic areas of AI.
A problem is a tuple $(S, s, A, \rho, G, P)$ where
Example: A water jug problem
You have a two-gallon jug and a one-gallon jug; neither have any measuring marks on them at all. Initially both are empty. You need to get exactly one gallon into the two-gallon jug. Formally:
A graphical view of the transition function (initial state shaded, goal states outlined bold):
And a tabular view:
To solve this problem, an agent would start at the initial state and explore the state space by following links until it arrived in a goal state. A solution to the water jug problem is a path from the initial state to a goal state .
There are an infinite number of solutions. Sometimes we are interested in the solution with the smallest path cost; more on this later.
Awww Man.... Why are we studying this?
Even if they’re not completely right, there are still zillions of problems that can be formulated in problem spaces, e.g.
State finding vs. action sequence finding.
A fundamental distinction:
Offline vs. Online Problems
In an online problem, the agent doesn’t even know what the state space is, and has to build a model of it as it acts. In an offline problem, percepts don’t matter at all. An agent can figure out the entire action sequence before doing anything at all .
Offline Example : Vacuum World with two rooms, cleaning always works, a square once cleaned stays clean. States are 1 – 8, goal states are 1 and 5.
Sensorless (Conformant) Problems
The agent doesn’t know where it is. We can use belief states (sets of states that the agent might be in). Example from above deterministic, static, single-agent vacuum world:
Note the goal states are 1 and 5. If a state 15 was reachable, it would be a goal too.
Contingency Problem: The agent doesn’t know what effect its actions will have. This could be due to the environment being partially observable, or because of another agent. Ways to handle this:
Example: Partially observable vacuum world (meaning you don’t know the status of the other square) in which sucking in a clean square may make it dirty.
Can also model contingency problems is with "AND-OR graphs".
Example: find a winning strategy for Nim if there are only five stones in one row left. You are player square. You win if it is player circle’s turn with zero stones left.
In general then, a solution is a subtree in which
If the tree has only OR nodes, then the solution is just a path.
Hey, we know what a problem is, what a problem space is, and even what a solution is, but how exactly do we search the space ? Well there are zillions of approaches:
Types of Problem Solving Tasks
Agents may be asked to be
An algorithm is
Example: The water jug problem with 4 and 3 gallon jugs. Cost is 1 point per gallon used when filling, 1 point to make a transfer, 5 points per gallon emptied (since it makes a mess). The search tree might start off like this:
Search trees have
The complexity of most search algorithms can be written as a function of one or more of $b$, $d$ and $m$.
In general though there may be more states than there are fundamental particles in the universe. But we need to find a solution. Usually is helpful to