Shi Haoran 1400012931
Xu Zhirong, Li Shang, Zhang Song, Deng Ziqing

You can find source code here:

Maze Problem

Maze Design

Original maze: Labyrinth


  • Crete structure:Labyrinth: no diverge and bypass
  • graph structure
    • simply connected
    • Multi-connected

Our robot can find pathways in simply connected mazes, which means no loop and connected.
There are many maze solving algorithms are closely related to graph theory.

  • A traveler with no prior knowledge of the maze, which is our research focus
    • random mouse
    • depth-first search
    • wall follower
  • A supervisor can see the whole maze at once
    • easy, various efficient algorithms
    • shortest path algorithms
    • breadth-first search
    • depth-first search

Exploring the Maze as a Traveller

Random Mouse

a trivial method

  • proceed following the current direction until an obstacle is reached
  • make a random choice of accessible directions and proceed

Wall follower

the best known algorithm for traversing maze

  • left direction rule
  • right direction rule

Why wall following works?

  • Mazes containing no loops are known as “simply connected”, or “perfect” mazes, and are equivalent to a tree in graph theory.
  • internal wall: branch streched out from the outside wall
  • If the walls are connected, then they may be deformed into a loop or circle.

if the maze is not simply connected ?

(i.e. if the start or endpoints are in the center of the structure surrounded by passage loops, or the pathways cross over and under each other and such parts of the solution path are surrounded by passage loops), this method will not reach the goal.

We can set up a favored direction

If the current direction is the same as the favored direction, keep forward instead of following the wall.

However, when entering a G-shape maze, it will trap.

We can also set a value named “Sum of turns taken”

  • when turn right , decrement
  • when turning left, decrement
  • keep stepping forward
  • set a favored direction
  • if current direcition is the same as favored direction
    • if “sum of turns taken” equals 0:
      • forward
    • else
      • wall following

2. Robot Design

Robot Prototype

We attach compass sensor to the initial e-puck prototype.
E-puck Prototype with sensors:
– differential_Wheels and encoder
– camera
– leds
– distance sensor: IR sensor


  • random controller
  • wall following controller
  • pledge controller

Controller Modules:

  • wall changed
  • threshold
  • bias back
  • decide which direction to continue proceed
  • turn left
  • turn right

3. Performace Demo

Video Deme : please make sure you can visit youtube fluently.

0 thoughts on “Artificial Intelligence Report

Leave a Reply

Your email address will not be published. Required fields are marked *