Problem-solving in Artificial Intelligence

The reflex agents are known as the simplest agents because they directly map states into actions. Unfortunately, these agents fail to operate in an environment where the mapping is too large to store and learn. Goal-based agent, on the other hand, considers future actions and the desired outcomes.

Here, we will discuss one type of goal-based agent known as a problem-solving agent, which uses atomic representation with no internal states visible to the problem-solving algorithms.

Problem-solving agent

The problem-solving agent perfoms precisely by defining problems and its several solutions.

According to psychology, “a problem-solving refers to a state where we wish to reach to a definite goal from a present state or condition.”

According to computer science, a problem-solving is a part of artificial intelligence which encompasses a number of techniques such as algorithms, heuristics to solve a problem.

Therefore, a problem-solving agent is a goal-driven agent and focuses on satisfying the goal.

Steps performed by Problem-solving agent

• Goal Formulation: It is the first and simplest step in problem-solving. It organizes the steps/sequence required to formulate one goal out of multiple goals as well as actions to achieve that goal. Goal formulation is based on the current situation and the agent’s performance measure (discussed below).
• Problem Formulation: It is the most important step of problem-solving which decides what actions should be taken to achieve the formulated goal. There are following five components involved in problem formulation:
• Initial State: It is the starting state or initial step of the agent towards its goal.
• Actions: It is the description of the possible actions available to the agent.
• Transition Model: It describes what each action does.
• Goal Test: It determines if the given state is a goal state.
• Path cost: It assigns a numeric cost to each path that follows the goal. The problem-solving agent selects a cost function, which reflects its performance measure. Remember, an optimal solution has the lowest path cost among all the solutions.
• Search: It identifies all the best possible sequence of actions to reach the goal state from the current state. It takes a problem as an input and returns solution as its output.
• Solution: It finds the best algorithm out of various algorithms, which may be proven as the best optimal solution.
• Execution: It executes the best optimal solution from the searching algorithms to reach the goal state from the current state.

Example Problems

Basically, there are two types of problem approaches:

• Toy Problem: It is a concise and exact description of the problem which is used by the researchers to compare the performance of algorithms.
• Real-world Problem: It is real-world based problems which require solutions. Unlike a toy problem, it does not depend on descriptions, but we can have a general formulation of the problem.

Some Toy Problems

• 8 Puzzle Problem: Here, we have a 3×3 matrix with movable tiles numbered from 1 to 8 with a blank space. The tile adjacent to the blank space can slide into that space. The objective is to reach a specified goal state similar to the goal state, as shown in the below figure.
• In the figure, our task is to convert the current state into goal state by sliding digits into the blank space.