Lecture 03.1: Problem Solving and Search Formulation

When we think about what makes us intelligent, the ability to plan before carrying out actions is a prominent attribute. In AI, agents that plan their actions to achieve specific goals are known as Problem-Solving Agents.

Searching in Planning

Searching is the act of exploring various options to make informed decisions in a plan. It is integral to refining and adjusting plans in response to new information.

Practical Example: A Trip Scenario

• Initial Plan: Journey to the beach with specific stops, dining, and activities planned.
• Encountering Changes: Unexpected closure of a planned restaurant or a closed shortcut road.
• Role of Searching: Finding alternatives (a new restaurant, a different route, alternate lodging) and adjusting the plan to accommodate new constraints, resulting in a modified yet successful outcome.

Plans evolve through searching and responding to real-time changes. AI systems leverage search algorithms to continuously optimize plans dynamically.

---

Problem-Solving Workflow & System Types

Before an agent can act, it structures its decision-making into four distinct stages:

1. Goal Formulation

The agent defines its objectives, clearly identifying the desired outcomes or target states it needs to achieve. This sets the direction for all subsequent actions.

2. Problem Formulation

The agent translates its goals into a structured mathematical problem. This involves formalizing five core elements:

• State Space ($S$): A set of all possible states the environment can be in.
• Initial State ($s_0$): The starting state of the agent (e.g., $In(Arad)$).
• Goal State(s) ($G$): A set of one or more states that satisfy the objective (e.g., $\{In(Bucharest)\}$).
• Actions ($\text{ACTIONS}(s)$): The set of executable actions available in state $s$. For example: $\text{ACTIONS}(Arad) = \{\text{ToSibiu}, \text{ToTimisoara}, \text{ToZerind}\}$
• Transition Model ($\text{RESULT}(s, a)$): A function returning the outcome state of taking action $a$ in state $s$. For example: $\text{RESULT}(Arad, \text{ToZerind}) = Zerind$
• Action Cost Function ($\text{ACTION-COST}(s, a, s')$): A function that assigns a numerical cost to performing action $a$ to transition from state $s$ to $s'$. A problem-solving agent uses a cost function that reflects its performance measure (e.g., distance in miles, time in minutes).

3. Search

Search is the process of examining alternate sequence of actions to reach a goal state given the problem formulation. Search strategies are broadly divided into uninformed (blind) and informed (heuristic) search.

4. Execution

Execution is the final step where the agent carries out the chosen sequence of actions one at a time in the environment.

• Open-Loop System: In a fully observable, deterministic, and known environment, the solution is a fixed sequence of actions. Once the agent finds a solution, it can ignore its percepts during execution—"closing its eyes"—because the outcome is guaranteed.
• Closed-Loop System: If the model might be incorrect or the environment is non-deterministic or partially observable, the agent monitors its percepts during execution. Its solution is a branching strategy recommending different future actions based on incoming percepts.

---

State Space Representation & Terminology

A state space is represented as a directed graph where vertices represent states and directed edges represent actions.

Key Definitions

• Path: A sequence of actions leading from one state to another.
• Solution: A specific path that leads from the initial state to a goal state.
• Optimal Solution: The solution path with the lowest total path cost among all possible solutions. Path costs are assumed to be additive and positive to simplify calculation.

Graph Representation: Romania Map

Below is a simplified subset of the classic textbook road map of Romania showing cities (states) and road distances in miles (action costs):

---

Abstraction and Level of Abstraction

In the Romania map example, the model is an abstract mathematical description rather than a literal 1:1 simulation. Real-world details such as weather, traffic, radio stations, scenery, and exact steering wheel angles are omitted.

Abstraction is the process of simplifying a problem representation by removing extraneous details and keeping only what is relevant.

Finding the Right Level of Abstraction

• Model vs. Reality: An agent's model ignores real-world complexity to focus solely on critical decision points (e.g., location connections).
• Level of Abstraction: If an abstraction includes too much detail (e.g., specifying foot movements on the gas pedal), the state space becomes exponentially huge and unmanageable. If it omits crucial detail, actions cannot be carried out.
• Utility of Good Abstraction:
  • Valid and Manageable: Ensures each abstract action can be expanded into detailed actions and executed without further high-level planning.
  • Simplification without losing essence: Removes overwhelming complexity while preserving the ability to reach an optimal solution.

---

Problem Formulation Example: The 8-Queens Problem

The goal of the 8-Queens problem is to place 8 queens on an $8 \times 8$ chessboard such that no two queens attack each other (no two queens share the same row, column, or diagonal).

Below is a valid non-attacking solution configuration on an $8 \times 8$ board:

Impact of Abstraction on State Space Size

The choice of problem formulation and abstraction dramatically impacts search space size:

By choosing a refined abstraction where actions place queens column-by-column without mutual attacks, the search space drops from 180 trillion sequences to just 2,057 states!