Well-Defined Problems and Measuring Problem-Solving Performance in AI
Artificial Intelligence (AI) is primarily concerned with designing systems that can solve problems automatically. To do this effectively, we must define what the problem is and how well the problem-solving approach performs. In this post, we will discuss what constitutes a well-defined problem in AI and explore the key metrics used for measuring the performance of problem-solving algorithms.
What is a Well-Defined Problem?
In AI, a problem must be clearly specified so that it can be tackled by a problem-solving agent. A well-defined problem includes:
- Initial State
The state in which the agent begins its journey. - Actions (Successor Function)
A set of legal actions available to the agent at any given state. - State Space
All possible states reachable from the initial state through sequences of actions. - Goal Test
A function that checks whether the current state satisfies the goal conditions. - Path Cost
A numeric cost associated with a path from the initial state to the goal. Often used to determine the optimal solution.
Example: Vacuum Cleaner World
- Initial State: The vacuum is in Room A, both rooms are dirty.
- Actions: Move Left, Move Right, Suck.
- Goal Test: Both rooms are clean.
- Path Cost: Each move or suck action costs 1 unit.
By clearly defining all these elements, the problem becomes well-posed, and an intelligent agent can begin to search for a solution.
Measuring Problem-Solving Performance
Once we have a problem defined, we use search algorithms to find solutions. But how do we know if a search algorithm is any good? We evaluate its performance using the following four key criteria:
1. Completeness
- Definition: Is the algorithm guaranteed to find a solution if one exists?
- Example: Breadth-First Search is complete for finite spaces, but Depth-First Search is not.
2. Time Complexity
- Definition: How long does it take to find a solution in the worst or average case?
- Measured By: The number of nodes expanded.
- Depends On:
- b: Branching factor (maximum number of successors per node)
- d: Depth of the least-cost solution
- m: Maximum depth of the search space
3. Space Complexity
- Definition: How much memory is required to perform the search?
- Measured By: Maximum number of nodes held in memory at once.
- Note: Algorithms like Breadth-First Search consume more memory compared to Depth-First Search.
4. Optimality (or Admissibility)
- Definition: If a solution is found, is it the best one (i.e., least path cost)?
- Example: A* Search is optimal when using an admissible heuristic, while Greedy Best-First Search is not.
Summary Table
| Criterion | Description | Example |
|---|---|---|
| Completeness | Will it always find a solution? | BFS – Yes, DFS – No |
| Time Complexity | Time required (in terms of node expansions) | O(b<sup>d</sup>) |
| Space Complexity | Memory required during execution | O(b<sup>d</sup>) or more |
| Optimality | Will it find the best (least cost) solution? | A* – Yes, Greedy – No |
Conclusion
Defining a problem properly is the first step toward building intelligent agents that can reason and act. A well-defined problem ensures the agent knows where to start, what actions to take, and when the goal has been reached.
But finding a solution is not enough — the solution must be found efficiently and optimally. This is where performance metrics like completeness, time and space complexity, and optimality come into play. These help us compare algorithms and choose the best one for a specific application.