Return to Answer

`State space search' is a general and ubiquitous AI activity that includes numerical optimization (e.g. via gradient descent in a real-valued search space) as a special case.

State space search is an abstraction which can be customized for a particular problem via three ingredients:

1. Some representation for candidate solutions to the problem (e.g. permutation of cities to represent a Travelling Salesman Problem (TSP) tour, vector of real values for numeric problems).
2. A solution quality measure: i.e. some means of deciding which of two solutions is the better. This is typically achieved (for single-objective problems) by having via some integer or real-valued function of a solution (e.g. total distance travelled for a TSP tour).
3. Some means of moving around in the space of possible solutions, in a heuristically-informed manner. Derivatives can be used if available, or else (e.g. for black-box problems or discrete solution representations) the kind of mutation or crossover methods favoured by genetic algorithms/evolutionary computation can be employed.

The first couple of chapters of the freely available "Essentials of Metaheuristics" give an excellent overview and Michalewicz and Fogel's "How to Solve It - Modern Heuristics" explains in more detail how numerical optimization can be considered in terms of state-space.

In response to a request in the comments to explain how clarify how "the 'search through possible plans' might occur", the idea is to choose all three of the above for the planning problem and then apply some metaheuristic such as Simulated Annealing, Tabu Search, Genetic Algorithms etc. Clearly, for nontrivial problems, only a small fraction of the space of "all possible plans" is actually explored.

CAVEAT: Actually planning (in contrast to the vast majority of other problems amenable to state-space search such as scheduling, packing, routing etc) is a bit of a special case, in that it is sometime possible to solve planning problems simply by using A* search, rather than searching with a stochastic metaheuristic.

State space search is a general and ubiquitous AI activity that includes numerical optimization (e.g. via gradient descent in a real-valued search space) as a special case.

State space search is an abstraction which can be customized for a particular problem via three ingredients:

1. Some representation for candidate solutions to the problem (e.g. permutation of cities to represent a Travelling Salesman Problem (TSP) tour, vector of real values for numeric problems).

2. A solution quality measure: i.e. some means of deciding which of two solutions is the better. This is typically achieved (for single-objective problems) by having via some integer or real-valued function of a solution (e.g. total distance travelled for a TSP tour).

3. Some means of moving around in the space of possible solutions, in a heuristically-informed manner. Derivatives can be used if available, or else (e.g. for black-box problems or discrete solution representations) the kind of mutation or crossover methods favoured by genetic algorithms/evolutionary computation can be employed.

The first couple of chapters of the freely available "Essentials of Metaheuristics" give an excellent overview and Michalewicz and Fogel's "How to Solve It - Modern Heuristics" explains in more detail how numerical optimization can be considered in terms of state-space.

How shall the "search through possible plans" occur? The idea is to choose all 3 of the above for the planning problem and then apply some metaheuristic (such as Simulated Annealing, Tabu Search, Genetic Algorithms etc). Clearly, for nontrivial problems, only a small fraction of the space of "all possible plans" is actually explored.

CAVEAT: Actually planning (in contrast to the vast majority of other problems amenable to state-space search such as scheduling, packing, routing etc) is a bit of a special case, in that it is sometime possible to solve planning problems simply by using A* search, rather than searching with a stochastic metaheuristic.

`State space search' is a general and ubiquitous AI activity that includes numerical optimization (e.g. via gradient descent in a real-valued search space) as a special case.

State space search is an abstraction which can be customized for a particular problem via three ingredients:

1. Some representation for candidate solutions to the problem (e.g. permutation of cities to represent a Travelling Salesman Problem (TSP) tour, vector of real values for numeric problems).
2. A solution quality measure: i.e. some means of deciding which of two solutions is the better. This is typically achieved (for single-objective problems) by having via some integer or real-valued function of a solution (e.g. total distance travelled for a TSP tour).
3. Some means of moving around in the space of possible solutions, in a heuristically-informed manner. Derivatives can be used if available, or else (e.g. for black-box problems or discrete solution representations) the kind of mutation or crossover methods favoured by genetic algorithms/evolutionary computation can be employed.

The first couple of chapters of the freely available "Essentials of Metaheuristics" give an excellent overview and Michalewicz and Fogel's "How to Solve It - Modern Heuristics" explains in more detail how numerical optimization can be considered in terms of state-space.

In response to a request in the comments to explain how clarify how "the 'search through possible plans' might occur", the idea is to choose all three of the above for the planning problem and then apply some metaheuristic such as Simulated Annealing, Tabu Search, Genetic Algorithms etc. Clearly, for nontrivial problems, only a small fraction of the space of "all possible plans" is actually explored.

CAVEAT: Actually planning (in contrast to the vast majority of other problems amenable to state-space search such as scheduling, packing, routing etc) is a bit of a special case, in that it is sometime possible to solve planning problems then using A*, rather than using a stochastic metaheuristic.

`State space search' is a general and ubiquitous AI activity that includes numerical optimization (e.g. via gradient descent in a real-valued search space) as a special case.

State space search is an abstraction which can be customized for a particular problem via three ingredients:

1. Some representation for candidate solutions to the problem (e.g. permutation of cities to represent a Travelling Salesman Problem (TSP) tour, vector of real values for numeric problems).
2. A solution quality measure: i.e. some means of deciding which of two solutions is the better. This is typically achieved (for single-objective problems) by having via some integer or real-valued function of a solution (e.g. total distance travelled for a TSP tour).
3. Some means of moving around in the space of possible solutions, in a heuristically-informed manner. Derivatives can be used if available, or else (e.g. for black-box problems or discrete solution representations) the kind of mutation or crossover methods favoured by genetic algorithms/evolutionary computation can be employed.

The first couple of chapters of the freely available "Essentials of Metaheuristics" give an excellent overview and Michalewicz and Fogel's "How to Solve It - Modern Heuristics" explains in more detail how numerical optimization can be considered in terms of state-space.

In response to a request in the comments to explain how clarify how "the 'search through possible plans' might occur", the idea is to choose all three of the above for the planning problem and then apply some metaheuristic such as Simulated Annealing, Tabu Search, Genetic Algorithms etc. Clearly, for nontrivial problems, only a small fraction of the space of "all possible plans" is actually explored.

CAVEAT: Actually planning (in contrast to the vast majority of other problems amenable to state-space search such as scheduling, packing, routing etc) is a bit of a special case, in that it is sometime possible to solve planning problems simply by using A* search, rather than searching with a stochastic metaheuristic.

`State space search' is a general and ubiquitous AI activity that includes numerical optimization (e.g. via gradient descent in a real-valued search space) as a special case.

State space search is an abstraction which can be customized for a particular problem via three ingredients:

1. Some representation for candidate solutions to the problem (e.g. permutation of cities to represent a Travelling Salesman Problem (TSP) tour, vector of real values for numeric problems).
2. A solution quality measure: i.e. some means of deciding which of two solutions is the better. This is typically achieved (for single-objective problems) by having via some integer or real-valued function of a solution (e.g. total distance travelled for a TSP tour).
3. Some means of moving around in the space of possible solutions, in a heuristically-informed manner. Derivatives can be used if available, or else (e.g. for black-box problems or discrete solution representations) the kind of mutation or crossover methods favoured by genetic algorithms/evolutionary computation can be employed.

The first couple of chapters of the freely available "Essentials of Metaheuristics" give an excellent overview and Michalewicz and Fogel's "How to Solve It - Modern Heuristics" explains in more detail how numerical optimization can be considered in terms of state-space.

`State space search' is a general and ubiquitous AI activity that includes numerical optimization (e.g. via gradient descent in a real-valued search space) as a special case.

State space search is an abstraction which can be customized for a particular problem via three ingredients:

1. Some representation for candidate solutions to the problem (e.g. permutation of cities to represent a Travelling Salesman Problem (TSP) tour, vector of real values for numeric problems).
2. A solution quality measure: i.e. some means of deciding which of two solutions is the better. This is typically achieved (for single-objective problems) by having via some integer or real-valued function of a solution (e.g. total distance travelled for a TSP tour).
3. Some means of moving around in the space of possible solutions, in a heuristically-informed manner. Derivatives can be used if available, or else (e.g. for black-box problems or discrete solution representations) the kind of mutation or crossover methods favoured by genetic algorithms/evolutionary computation can be employed.

The first couple of chapters of the freely available "Essentials of Metaheuristics" give an excellent overview and Michalewicz and Fogel's "How to Solve It - Modern Heuristics" explains in more detail how numerical optimization can be considered in terms of state-space.

In response to a request in the comments to explain how clarify how "the 'search through possible plans' might occur", the idea is to choose all three of the above for the planning problem and then apply some metaheuristic such as Simulated Annealing, Tabu Search, Genetic Algorithms etc. Clearly, for nontrivial problems, only a small fraction of the space of "all possible plans" is actually explored.

CAVEAT: Actually planning (in contrast to the vast majority of other problems amenable to state-space search such as scheduling, packing, routing etc) is a bit of a special case, in that it is sometime possible to solve planning problems then using A*, rather than using a stochastic metaheuristic.