The Maze Problem

Problem Description

This problem is looked at in Section 8.2.2 of [1]. Section 8.2 discusses using CE more generally in this way.

Program Descriptions

  • maze.m
    This program tries to find the shortest path through a maze, by generating a set of choices at junctions. For example, an output may indicate something along the lines of ``At Junction 1, go East, at the next Junction, go South ...''. The set of choices is updated via the CE method.

    Usage:
    Call the program from MATLAB, with the following syntax:

    pi = maze( N , rho , alpha , M , start , finish )

    Example: pi = maze( 1000 , 0.02 , 0.7 , MAZE , [1,1] , [12,12] )
    Where, in this example, M is a 12x12 maze of 0s and 1s, with 1s representing walls, and 0s representing the paths. The start of the maze is at [1,1] and the end is at [12,12]. Note that this method seems to perform quite well on very small mazes, or on mazes with few junctions, but performs less well on larger problems.

    Inputs:   
     N - Number of samples to generate each iteration
     rho - Fraction of samples to use to update the choices
     alpha - Smoothing parameter
     M - A matrix of 1s and 0s, representing a maze
     start - Starting position
     finish - Ending position
    Outputs:   
     pi - Output choice set
  • gmaze.m
    This program is used internally to generate a set of direction choices.

  • smaze.m
    This program is used internally to evaluate the performance of a given set of direction choices.

Bibliography

  1. D. P. Kroese and R. Y. Rubinstein.
    The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation and Machine Learning.
    Springer, 2004.