Describe the basic algorithm for performing local search. Give an example of a search problem for which it is an appropriate solution. When would an algorithm such as A* search be preferred?
Before a robot can move on a line, a plan must be generated first. A plan is a sequence of steps to reach a goal. Generating plans is called search&planning. The idea is to traverse the existing search space to fulfill constraints. The term “local search” is used to make clear, that it's impossible to generate all plans but only a limited set which is in the neighborhood. The neighborhood is located in the error map of the objective function. The first question is, why only a local search is possible but not a global one in the complete state space? In case of pathplanning this can be answered by algorithmic needs. If we want to create a graph from the start to the goal, we can only add new nodes, step by step by executing a for loop. That means, the graph starts with zero nodes, then we add one, then another and so forth. That means, we have to wait a long time until the complete graph is generated and we are always searching nearby the start node.
The local search algorithm has an interesting capability, which is called grammatical evolution. The idea is not to search in the lowlevel statespace, which is the 2d map in a pathplanning problem, but to search in the state space of grammars. Like in the example from the introduction it is only possible to traverse nodes nearby the original one, but this time we are not searching for spatial points on the map, but for nodes in a graph of all possible grammars. That means, on step #1 we are investigating grammar #1, at step #2 we are investigating grammar #2 which is nearby, and then we are testing out grammar #3 and so on.
- Mascia, Franco, et al. "Grammar-based generation of stochastic local search heuristics through automatic algorithm configuration tools." Computers & operations research 51 (2014): 190-199.