Complex problems encountered in day to day life can be solved using AI algorithms. Defining new algorithms for each of the millions of problems today is a very difficult task. The objective of Search and Constraint Satisfaction in automated problem-solving in AI is to find a common underlying principle for all these problems.
Automated problem solving by Search is a generalized technique where the problem statement is is the input and the solution is the output.
These are called meta-algorithms, i.e. the algorithm to solve the problem is an output (not just the result).
What is the underlying structure of each of these problems?
Can all problems be mapped to a single structure to solve the problem?
These questions help form the objective of automated problem solving by search.
How can one model this problem?
State Space Search is used to model the problem. In the state space graph, nodes represent the configuration and edges represent the possible moves from one configuration to another. The State Space mechanism has the following properties:
- Any configuration can be modeled as a STATE.
- The configuration must be a VALID CONFIGURATION.
- STATE TRANSFORMATION RULES are how we define rules in moving from one state to another state. State transformation rules produce the state space.
- The initial state, goal state, the implicit or configuration space — All these are mapped to finding valid solutions from start to goal in the state space.
This mechanism can be used to find solutions to all problems that can be mapped to the state space configuration.
However, state spaces are very large, and sometimes even infinite. Therefore, intelligently exploring state space from implicit transformations within space and time requirements, to reach the goal configuration as soon as possible, is required.
SEARCH in Automated Problem Solving serves as a single mechanism for this. Therefore, SEARCH is the foundation of Artificial Intelligence.