✦ScienexySCIENCE KNOWLEDGE LIBRARY
Science reference · SCI-CS-003-031

Problem Formulation in AI

Problem formulation is the process of defining an AI problem in terms of its initial state, possible actions, transition model, goal test, and path cost.

Problem = (Initial State, Actions, Transition Model, Goal Test, Path Cost)

Explanation

Problem formulation is a foundational step in classical artificial intelligence problem-solving. It converts a real-world task into a formal representation that a search algorithm can process. A typical problem formulation contains five components. The initial state describes the starting situation. The action set specifies the available operations. The transition model explains the state reached after performing an action. The goal test determines whether a state satisfies the objective. The path-cost function assigns a cost to a sequence of actions. For example, a route-finding problem can be formulated by representing cities as states, roads as actions, travel between cities as transitions, the destination as the goal, and distance or travel time as path cost. A good formulation captures the important aspects of a task while avoiding unnecessary complexity. Different formulations of the same real-world problem can produce different search spaces and computational requirements.

Variables

SymbolMeaning

Initial State

The state from which the problem-solving agent begins.

Actions

The operations available to the agent.

Transition Model

The rule describing how an action changes the current state.

Goal Test

The condition used to determine whether the objective has been achieved.

Path Cost

The total cost associated with a sequence of actions.

Example or application

In a route-finding problem, the initial state may be Dhaka, the available actions are traveling along connected roads, the transition model identifies the next city, the goal test checks whether the destination has been reached, and the path cost measures total distance.

Text

Before an AI agent can search for a solution, the problem must be represented in a structured way. Problem formulation identifies where the agent starts, what actions it can take, how those actions change the environment, what counts as success, and how solution quality is measured.

Key Points

  • Problem formulation converts a real-world task into a formal search problem.

  • A search problem normally includes five major components.

  • The goal test defines what counts as a successful solution.

  • Path cost helps compare alternative solutions.

  • A suitable formulation can reduce unnecessary search complexity.

Applications

  • Route planning and navigation

  • Robot movement and task planning

  • Puzzle solving

  • Automated scheduling

  • Game-playing systems

Learning Outcomes

  • Identify the five components of a classical AI search problem.

  • Convert a simple real-world task into a formal problem representation.

  • Explain why problem formulation affects search performance.

Practice Questions

  • What is problem formulation in artificial intelligence?

  • What are the five components of a search problem?

  • How does a path-cost function help an AI agent?

Related Concepts

  • State Spaces and Search Trees

  • Search Algorithms

  • Goal Testing

  • Path Cost

Common Mistakes

  • Confusing the goal state with the initial state.

  • Ignoring the transition model.

  • Assuming every action has the same cost.

  • Including unnecessary details that make the search space excessively large.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Russell, S. and Norvig, P. Artificial Intelligence: A Modern Approach, section on Problem-Solving Agents.
  • Poole, D. and Mackworth, A. Artificial Intelligence: Foundations of Computational Agents, search and problem-solving chapters.

Suggest a correction or source · More in Artificial Intelligence & Machine Learning