Local search and optimization - Artificial Intelligence

Another family of search behaviours is based on ‘local’ search where the agents performing the search apply rules according to the local situation they find themselves in by examining the alternative paths only in relation to the immediate neighbourhood. Therefore they do not need to record any information such as which locations they have already visited, the paths they have taken or the path cost.This type of search can be described using the analogy of a myopic person with a very localised field of vision. The search uses a meta-heuristic that can be applied to solving general problems, rather than a specific heuristic tailored for the problem domain. One form of this type of search called hill climbing (also called greedy local search) is to make the choice of where to move to based on maximising (or equivalently minimising) some criteria. The code for this search is shown in NetLogo Code below.

NetLogo Code :How the Hill Climbing Search is defined.

With hill climbing search, only one searcher agent is active at any time. This agent will create new searcher agents for each path it can expand, but then only one of those is chosen to continue the search, and the rest are killed off. The searcher agent chosen will be the one that has the minimum value for the height variable stored with each agent.This is calculated in the expand-paths procedure. For the Searching Mazes module and the Searching for Kevin Bacon model, the height is calculated using the heuristic function defined in NetLogo Code below:

NetLogo Code :How the height is calculated for the Searching mazes and Searching for Kevin Bacon models.

Using Euclidean distance or Manhattan distance from the goal point as the meta-heuristic for both models ensures that the landscape of the environment is smooth throughout, and consists of a single depression, with the lowest point (zero) being the epicentre. The hill-climbing search then tries to move the agent in a direction towards the epicentre.

Figure provides two screenshots of hill-climbing search on the empty maze for the Searching Mazes model. The left image shows what happens when Euclidean distance is used as the metaheuristic, the right image when Manhattan distance is used. The explanation for the pronounced veering away of the columns of searcher-agents at the beginning and end is that, as discussed above, the x co-ordinate of the goal point is set at -5 which is slightly to the left of the x co-ordinate of the first searcher agent when it enters the maze. Therefore, for Euclidean distance, the agent expanded in the forward direction will always be closer to the goal point until right at the end (in contrast to the two other agents expanded in the left and right directions). For Manhattan distance,the veering occurs at the beginning instead because of the way the distance is calculated as a summation of vertical and horizontal lengths rather than diagonally.

Screenshots of the hill climbing search using the Euclidean distance meta-heuristic (left image) and the Manhattan distance meta-heuristic (right image) for the Searching Mazes model on the empty maze.

Manhattan distance meta-heuristic (right image) for the Searching Mazes model on the empty maze

For the Missionaries and Cannibals model, we need another method for calculating the height variable since the search space is three-dimensional. Referring to Figure, one obvious way for representing height in the environment is the position of each state on the parallel y axes. For example, the highest point is the start state at (3, 3, 1), and the lowest (zero) point is the goal state at (0, 0, 0). We therefore can calculate the height proportionately to reflect the number of missionaries and cannibals, and the current row-boat position as shown in NetLogo Code below.

NetLogo Code :How the height is calculated for the Missionaries and Cannibals model.

A problem with hill climbing search is that it can easily get stuck in local maxima. Another problem is when there is an obstacle blocking the way. This is illustrated by the screenshot in Figure of hill climbing search used on the Hampton Court Palace maze. The search heads directly in the direction to the global minimum at the centre of the maze, but then gets prevented from moving forward by the long horizontal wall in the way. What the search needs to do is head in a non-minimising direction to get around the obstacle. One way of doing this is to include a random walking behaviour when the search has not made any progress. However, the Hampton Court Palace Maze environment is still problematical even for such a solution, as the walls present a series of obstacles parallel to each other that are very wide and difficult to find a way around.

Figure Screenshot showing how Hill Climbing Search gets stuck for the Searching Mazes model on the Hampton Court Palace Maze.

Hill Climbing Search gets stuck for the Searching Mazes model on the Hampton Court Palace Maze.

Similarly, hill-climbing search used for the Searching for Kevin Bacon model can also get stuck in nodes where adjacent nodes are all in directions that are further away from the goal node. This occurs in the screenshot show in Figure where the search starts at node b33, but then cannot proceed beyond node b21 because the distances to the goal node (the white star) from adjacent nodes is longer than the distance from node b25.

Figure Screenshot showing how the Hill Climbing Search get stuck in some cases for the Searching for Kevin Bacon model.

showing how the Hill Climbing Search get stuck in some cases for the Searching for Kevin Bacon model.

The same problem occurs for hill-climbing search on the Missionaries and Cannibals problem. The search very quickly gets stuck when the only future paths all head away from the goal state. Hill climbing is an example of a broader class of problem solving called optimisation. Optimisation methods rely on making some form of guess, and then incrementally refining the guess until no further refinements are possible. Some other forms of optimization are simulated annealing, beam search, genetic search and particle swarm optimization. For the latter two, two models are provided with the NetLogo Models Library – Simple Genetic Search and Particle Swarm Optimization. (These models will be further discussed in Volume 2 of this book series.) Particle swarm optimisation search make use of swarm intelligence and stigmergy.

The use of the blackboards by communicating agents to help search computer networks within the Being Kevin Bacon model described in the previous chapter is another example of distributed agents using stigmergic local information to help improve search. The word of mouth method of communication also implemented in the model is another example of local search, but unlike the blackboard method, does not make use of stigmergy.


All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Artificial Intelligence Topics