Practice Exercise 4.C
SLS for CSP

Back to practice exercises.

1: Background Reading

2: Learning Goals

  • Implement local search for a CSP
  • Implement different ways to generate neighbours
  • Implement scoring functions to solve a CSP by local search through either greedy descent or hill-climbing
  • Implement SLS with random steps and random restarts
  • Compare SLS algorithms with runtime distributions

3: Directed Questions

  1. In local search, how do we determine neighbours? [solution]

  2. What is the difference between random walk and random restart? [solution]

  3. What is the key weakness of stochastic local search? [solution]

4: Exercise: Traffic Flow

Consider the following scenario. You are on a city planning committee and must decide how to control the flow of traffic in a particular residential neighbourhood. At each intersection, you have to decide whether to install a 4-way stop, a roundabout, or an uncontrolled intersection (in an uncontrolled intersection, the streets intersect without signs, roundabouts or other traffic conrols). There are several restrictions in how the intersections can be controlled. The following figure gives an overview of the neighbourhood.
Traffic Flow
The red stars indicate the 8 intersections under consideration. The intersection nearest the school in the NW corner of the neighbourhood must contain a 4-way stop for safety reasons. Along the east side of the neighbourhood runs a truck route, and no roundabouts can be placed on this street because they pose a problem for large trucks. Also, it is not allowed to have 4-way stops at consecutive intersections or to have two consecutive uncontrolled intersections. Finally, due to the cost of installing roundabouts compared with the other options, each block can have at most one of its four corners with a roundabout.

4.1: CSP Representation

  1. How would you represent the above problem as a CSP? Identify the variables, their domains, and the constraints involved. Once you are done a sketch on paper, open the stochastic local search tool and load the file http://www.aispace.org/exercises/roundabouts.xml by clicking File → Load from URL. This shows one possible representation, but there might be more than one correct representation.

4.2: Comparing Local Search Algorithms

Using the local search tool, we will experiment with several local search algorithms for solving this problem.
  1. Greedy Descent
    From the menu, choose Hill Options -> Algorithm Options and then select Greedy Descent from the dropdown menu. Click Ok. Click Initialize. This will assign a value to each variable. Note: you can choose Hill Options -> Auto Solve Speed -> Very Fast to speed up the solver. Click Auto Solve. What happens? Does it find a solution within 100 steps? Hypothesize why or why not. Now click Batch Run, which will calculate the runtime distribution and plot the percentage of successes against the number of steps. What does the runtime distribution tell you about this solver? [solution]

  2. Greedy Descent
    Go back to Algorithm Options and now select Greedy Descent with Random Restarts. Click Batch Run again and compare the runtime distributions. Do the random restarts improve Greedy Descent? Why or why not? [solution]

  3. Random Walk
    Go back to Algorithm Options and now select Random Walk. Click Batch Run again. How does this compare with plain Greedy Descent? How would the two algorithms compare if you gave them 10000 steps? (a logarithmic scale might help the visualization) [solution]

5: Learning Goals Revisited

  • Implement local search for a CSP
  • Implement different ways to generate neighbours
  • Implement scoring functions to solve a CSP by local search through either greedy descent or hill-climbing
  • Implement SLS with random steps and random restarts
  • Compare SLS algorithms with runtime distributions

Valid HTML 4.0 Transitional