### Assignment 1 Maze Learning

Very cool project as an introduction to Robotics. I got a chance to play around with "real" robot instead of wathcing it run on the simulator.
Basically I have to program a robot that can "learn" a maze (straight lines only, no loop) using Finite State Machine and find the shortest path from start to goal.

Here is an example (not my robot, but still impressive):

I used a Finite State Machine as an approach to solve mazes.
The basic idea is very straightforward:
1. The Finite State Machine consists of 7 states: Start, Follow, Enter, Turn Left, Turn Right, Uturn, Goal. Each state represents an action which the robot should execute.
There are several transitions that connect between different states (all transitions are line types and intersection types ): Intersections, Straight, Dead End, Turned, etc.

FSM illustrated below:

This graph may seems a little bit overwhelming, but the principle are simple:
When a robot comes across a intersection, it will follow the LEFT HAND RULE -- Always turn left if it can, otherwise straight, then right.
Besides, since the robot may be stuck in Uturn infinite loop, so I build an escape, Dead End Counter, which will terminate Uturn if there are two consecutive Uturns.

Based on this FSM, the robot will traverse the maze until it finds the goal.

The maze learner will provide me a path to the goal, but it may not be the shortest path. In this case, I use Replacement Rules to eliminate unnecessary steps, like Uturn.
There are many versions of this rule, these are the rules I applied:
if 1. Turn Left + Uturn + Turn Left = Straight (No action)
if 2. Turn Left + Turn Left + Uturn = Straight (No action)
if 3. Uturn + Turn Left = Turn Right
if 4. Turn Left + Uturn = Turn Right

Here are some sample mazes and there shortest paths: 1. When a robot runs in a real world scenario, there are so many aspects to consider - lighting, sensor reading, acceleration, time elapsed, etc, but tuning the robot is the most pleasant thing to do.
2. It's really hard to make a right turn. Frankly, this is so unexpected. At first I thought making a turn should be the simplest thing to do, yet it took me a while to figure out how to stop at an intersection and turn with an appropriate twist.
3. Can't wait for the new robot!