Hill Climbing

OK, so starting with hill climbing [Rich &Knight, 3.2]. In hill climbing the basic idea is to always head towards a state which is better than the current one. So, if you are at town A and you can get to town B and town C (and your target is town D) then you should make a move IF town B or C appear nearer to town D than town A does. In steepest ascent hill climibing you will always make your next state the best successor of your current state, and will only make a move if that successor is better than your current state. This can be described as follows:

1. Start with current-state = initial-state.
2. Until current-state = goal-state OR there is no change in current-state do:
   1. Get the successors of the current state and use the evaluation function to assign a score to each successor.
   2. If one of the successors has a better score than the current-state then set the new current-state to be the successor with the best score.

Note that the algorithm does not attempt to exhaustively try every node and path, so no node list or agenda is maintained - just the current state. If there are loops in the search space then using hill climbing you shouldn't encounter them - you can't keep going up and still get back to where you were before.

Hill climbing terminates when there are no successors of the current state which are better than the current state itself. This is often a problem - for example, consider the following route map:

Suppose we are search for a route from a1 to a4, using the ``as the crow flies distance to target'' as an evaluation function and using the hill climbing algorithm.

Starting with a1 as the current state, the successors of a1 (a2 and a6) would be evaluated and a2 chosen as having the highest score (nearest to target). But now the successors are a1 and a3. Both are further from the target than a2, so will have a lower score, so using ``pure'' hill climbing the algorithm will terminate without finding the goal state. The same would happen if, say, a6 was closer to a4 than a2 - the first state chosen would be a6, which has no successors nearer a4, and so we'd reach an impasse. The rest of the search space would never be explored.

These problems are essentially the result of local maxima in the search space - points which are better than any surrounding state, but which aren't the solution. There are some ways we can get round this (to some extent) by tweaking or extending the algorithm a bit. We could use a limited amount of backtracking, so that we record alternative reasonable looking paths which weren't taken and go back to them. Or we could weaken the restriction that the next state has to be better by looking ahead a bit in the search - maybe the next but one state should be better than the current one. None of these solutions are perfect, and in general hill climbing is only good for a limited class of problems where we have an evaluation function that fairly accurately predicts the actual distance to a solution.