Problem solving in AI
Problem solving in AI begins with a formal definition of the problem. A search problem consists of four components: an initial state where the agent starts...
Framing Problems Formally
Problem solving in AI begins with a formal definition of the problem. A search problem consists of four components: an initial state where the agent starts, a set of actions available at each state, a transition model describing what each action produces, and a goal test that checks whether the current state satisfies the objective. Optionally, a path cost function assigns a numeric cost to each sequence of actions, allowing the agent to seek not just any solution but the cheapest one.
This formal framing turns the problem into a search through a graph of states. Consider the classic eight-puzzle, a three-by-three grid with eight numbered tiles and one blank. The initial state is a scrambled configuration. The actions are sliding a tile into the blank space. The goal test checks whether tiles are arranged in the correct order. The agent's job is to find the shortest sequence of slides that transforms the scrambled configuration into the solved one.
The size of the state space grows rapidly with problem complexity. A simple puzzle may have tens of thousands of reachable states. A chess game has more states than there are atoms in the observable universe. Efficient AI problem solving therefore depends critically on choosing the right search strategy and using domain knowledge to prune irrelevant parts of the space.
Well-Defined vs Real-World Problems
Textbook problems like the missionaries and cannibals puzzle are well-defined and fully observable. Real-world problems such as route planning on a live map involve partial observability, stochastic outcomes, and changing environments, requiring more sophisticated techniques beyond basic search.
Exam Tip
A common exam question presents a problem scenario and asks you to define its state space, actions, transition model, and goal. Practice writing these four components clearly for examples like route finding, the water jug problem, and the n-queens puzzle. Being precise about what constitutes a state versus an action is often where marks are lost.