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 and activities.
• Encountering Changes: Unexpected closure of a restaurant or a closed shortcut road.
• Role of Searching: Finding alternatives (a new restaurant, different route) and adjusting the plan to accommodate new information, resulting in a successful outcome.

AI systems leverage search algorithms to continuously optimize plans, adapting to the dynamic nature of real-time changes.

Formulation and Execution

Before an agent can act, it must structure its thoughts:

1. Goal Formulation

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

2. Problem Formulation

In this stage, the agent translates its goals into a structured problem. This includes defining:

• State Space: A set of possible states the environment can be in.
• Initial State: Where the agent begins.
• Goal States: A set of one or more states that satisfy the objective.
• Actions: A set of actions available to the agent in a given state.
• Transition Model: A description of what each action does.
• Action Cost Function: A function that reflects the performance measure (e.g., distance, time).

3. Search

Search is the method by which an AI agent explores possible actions to achieve its goals. The choice of strategy (uninformed vs. informed) depends on the problem's complexity.

4. Execution

Execution is the final step, implementing the derived sequence of actions (one at a time).

• Open Loop System: In a fully observable, deterministic, and known environment, the solution is a fixed sequence. The agent can essentially "close its eyes" and ignore percepts while executing because success is guaranteed.
• Closed Loop System: If the model might be incorrect or the environment is non-deterministic, the agent monitors percepts. It uses a branching strategy that recommends actions depending on what percepts arrive.

---

State Space Representation

A state space is often mathematically represented as a graph, where vertices are states and directed edges are actions.

Below is a simplified slice of the classic textbook road map of Romania. We want to find the shortest route from Arad to Bucharest. Rather than visualizing the entire country, let's look at the core paths connecting our start and goal states to understand the problem:

By reducing the graph to a smaller subset, we can easily see the decision points (like choosing between Sibiu, Timisoara, or Zerind from Arad) without being visually overwhelmed.

Abstraction

In the Romania example above, the model is an abstract mathematical description, not reflecting every real-world detail (like weather or traffic). Abstraction is the process of simplifying a representation by removing unnecessary details.

• Finding the Balance: Too much detail impedes problem-solving, but removing too much makes the solution useless.
• Utility: Good abstraction ensures that each abstract action can be executed without further planning, simplifying the problem without losing its essence.

Another Example: The 8-Queens Problem

Consider placing 8 queens on a chessboard so none attack each other.

• States: All possible arrangements of $n$ queens (0 to 8) on the board.
• Initial State: No queens on the board.
• Actions: Add a queen to any empty square.
• Transition Model: Returns the board with the queen added.
• Goal Test: 8 queens on the board, none attacked.

A naive formulation evaluates $\approx 1.8 \times 10^{14}$ sequences. But with better formulation (e.g., adding a queen only in the leftmost empty column such that it is not attacked), we reduce the state space to just 2,057!