Problem Formulation in AI

What Is Problem-Solving in AI?

Problem-solving in AI is the process of identifying a goal and finding a sequence of actions that leads from an initial situation to the desired outcome.

For example, a navigation system must determine how to travel from one location to another. A puzzle-solving program must determine which moves will transform the initial puzzle into its solved state.

Before choosing a search algorithm, the problem must be represented in a form that the algorithm can process.

Components of an AI Search Problem

A typical search problem includes the following components:

1. Initial State

The starting situation from which the system begins searching.

Example: A robot is located at the entrance of a building.

2. Actions

The possible operations available in each state.

Example: The robot can move forward, turn left, or turn right.

3. Transition Model

A description of how an action changes the current state.

Example: Moving forward takes the robot from one grid cell to an adjacent cell, provided the path is not blocked.

4. Goal Test

A condition that determines whether the desired state has been reached.

Example: The robot has reached the specified destination.

5. Path Cost

A numerical value representing the cost of a sequence of actions.

Example: A route's cost may represent distance, travel time, fuel consumption, or a combination of these factors.

Example: Finding a Route

Suppose a robot must travel from point A to point D.

• Initial state: A
• Available actions: Move along connected paths
• Transition model: Each movement leads to a connected location
• Goal test: Current location is D
• Path cost: Total distance traveled

The search algorithm explores possible paths until it finds a solution according to its strategy.

State Space

The state space is the collection of states that may be reached while solving a problem.

In a maze, each reachable position can represent a state. In a board game, each possible board configuration can represent a state.

The size of the state space affects the difficulty of the problem. When the number of possible states grows rapidly, searching every possibility may become impractical.

Search Tree

A search tree represents the exploration of possible states.

• The root represents the initial state.
• Branches represent possible actions.
• Child nodes represent resulting states.
• A goal node represents a successful solution.

A search tree may contain repeated states, so practical algorithms often maintain a set of visited states to avoid unnecessary exploration.